元スレcellプログラミングしちゃいなよ3
cell覧 / PC版 / みんなの評価 : ☆
前へ
751 = :
>テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では
>ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。
へー、すごいなｗ。いや、LUT を使わない実装が標準とか思わないほうがいいぞ？
暗号作ってる方は簡単なシフト＋ビット論理演算で求められないように sbox を
導入してるのに、なんか可哀想になってきちゃうよ。
まぁ確かに本質的には両方拡散だから同じだしなｗ
752 = :
>>751
RSAのRivest Cipher(RC)シリーズとかMD5なんてS-boxを使わずにスワップを繰り返す
暗号・ハッシュアルゴリズムの代表格なわけだが？
RC6はAESの最終候補まで残ったぞ。
753 = :
なんで軒並み落ちてって、今 feistel ばっかなのか考えようぜｗ
754 = :
>>743
よわかりませんが、M系列で「加算」する場合もキャリーは１ット隣なのでしょうか？
755 = :
>>754
最低限言えることは、SPUには任意の位置のビットにキャリーアップしてくれるような特殊な算術加算命令はないということだ。
まあそういうことだ。
ハードウェアに不向きなことをやらせて性能を出そうという方が間違い。
756 = :
なんだかよくわかりませんが、よくわかりました。
ありがとうございました。
757 = :
関係ないけどJNBのトークンって暗号形式なんだったっけ？
758 = :
そろそろ詭弁の○○ヶ条で〆てくれ
759 = :
>>753
そこはAESばっか、に訂正しろよ。
AESが世界的に選ばれてるのはAESがAESだからだ。
AESに選ばれなかったfeistel暗号の信頼性を保証する根拠にするのは間違いだな。
とっくに死んだはずのDESが何故かワンタイムパスワードとして現役で使われてたりするくらいだし。
そのレベルで言うならMD5やRC4だって未だに使われてるんだぜ。
iがつかないニンテンドーDSだとWi-FiはWEP（RC4）強制だしｗｗｗｗｗ
それに比べれば国産暗号のMISTYとかCamelliaなんてまだまだマイナー杉。
松井さんには悪いが。
762 = :
当たり前のこと言ってどうすんだ。鍵長考えてものを言え。
引き合いに出すならRC6あたりだろ。
RijndaelがAESに選ばれたのはその一つとしてDESみたいな複雑なビットシャッフル演算がなくて
専用ハードウェアでなくても実装コストが軽いからだ。
別にRC6の暗号強度が否定されたわけではない。
763 = :
すまん、ちょっと読み違えてた。が、時間がない。また今度w
あ、俺も RC6 の暗号強度を否定するつもりは毛頭ないよ。
764 = :
そもそも別にLUTよりビット演算のほうがコストパフォーマンスが優れてるなんて言う気はない。
不毛すぎ
今回のTemperingを通す前にサマリ計算が出来るかどうかだが
実用的な計算時間をはじき出すのは「無理」と言えるレベルの相関性の破壊は達成できてるというのが
俺の見解。
俺個人は国産暗号マンセーの立場なので君に付き合ってRSAの腐れの擁護する気もない。
ちなみにSHA-3候補として俺が注目してるのはこれ
http://ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf
＃あとAESは厳密にはSPNSであってFeistelには分類されない。
765 = :
日本語でおｋ
766 = :
当たり前のこと言ってどうすんだ。
768 = :
>>764
俺の見解は、拡散って意味では tempering も sbox も同じってのには同意。
だが、シフト＋ビット論理演算ではできない substitution を実現するために
sbox を導入してんだから、それを安易に同列に扱うのは理解できん。
あ、国産マンセーは俺も一緒。来年 Camellia いいねぇw
769 = :
ま、とりあえず俺の情報源のひとつ晒しておくわ。
暗号アルゴリズム及び関連技術の評価報告
http://cryptrec.nict.go.jp/cryptrec_03_0424_outrep.htm
S-boxを使わないRC6はかなり高い評価を得てるよ。
一般的なバイトマシン・ワードマシンでビット演算でやったらめちゃくちゃコストかかる演算を
LUTなら簡単に実装出来たりする。S-boxの多くは、RISCプロセッサのビット演算にそのまんま展開すると
とんでもない演算数がかかったりするんだが、それは暗号理論的な堅牢性の根拠としては弱いと思うよ。
バイトマシン・ワードマシンじゃなくて、ビットマシンとかASIC・FPGAだったら？
たとえばDESのS-boxはAND/OR/NOT/XORの基本的な1ビット論理演算で
たったの平均56ゲートで構成出来る。
これは具体的にいうと32ビットワードの全加算回路に必要なトランジスタ数よりもかなり少ない。
AESのS-boxは・・・実装についての論文あったけど、いくらだったか忘れた。
（総当たりで最短を検索するプログラムが手元にあるけど8ビット×8ビットのS-boxは計算時間的に流石にきつい）
見方を変えようか
AESやCamelliaはS-boxを除けば、DESのIP・E・P・FPでやってるような複雑なビット単位の
攪拌処理をやらずに、世界最高水準の安全性を実現してるわけだ。
更にいうと、CamelliaはS-boxは実質的に8ビット入力×8ビット出力のものがたった1つだけしかない。
その点でみてソフトウェアでの実装の複雑さと暗号的な強度は別モノと考えてる。
770 = :
>>710
とりあえず13clock切れた。けど謎のストールに阻まれ停滞中orz
771 = :
772 = :
Camelliaの教科書的実装より引用。
俺はなんでこれでAESなみの強度が得られるのか疑問だったよ。
#define SBOX1(n) SBOX[(n)]
#define SBOX2(n) (Byte)((SBOX[(n)]>>7^SBOX[(n)]<<1)&0xff)
#define SBOX3(n) (Byte)((SBOX[(n)]>>1^SBOX[(n)]<<7)&0xff)
#define SBOX4(n) SBOX[((n)<<1^(n)>>7)&0xff]
2と3は1の出力値をローテートしてるだけ。4は入力値をローテートしてるだけ。
なんでこれで「AESなみの暗号強度を実現できる」（中の人談）のか
>>771
というか、どうやら俺が見つけた最適化方法は既にこのスレで13clk切った連中は見つけてると思うよ。
あとは実装勝負なわけだが、アセンブラ相手にCで勝てる気はしない。
具体的にいうと現時点では>>693よりは遅い。ガチ。
（てかこの人が最速っぽい）
ただ俺にとっては今回の挑戦はどこまでもHack the spu-gcc43なのだ。
アセンブラ使わないと優勝できないのはわかってるが、アセンブラを使うのは俺的に負けなのである。
Cのみで挑戦する人向けに特別賞でも用意してくれるなら俺は喜んで表彰台にあがってやるぜ。
（herumi氏も参戦してきたことで、それですら負ける気がしてきた）
773 = :
まあ、どうやってコンパイラの副作用を抑え込んだのかっていうのはソースにびっしり書いてたりするから
俺が上位に残ってたら参考にしてくれ、的な。
774 = :
>>769
俺の言いたい事は >>768 で言ったが、「今 feistel ばっか」とかが
気に食わないんかな？ sbox ＝ 堅牢と言ってるんではなくて、堅牢さと
速度を両立するのに sbox が向いてると言いたいだけなんだが。
シフト＋ビット論理演算だけで同等の堅牢さを実現するよりも、
sbox の方が早くし易いし、小さくもし易いって理解なんだけど。
だから NIST にしろ NESSIE にしろ、feistel 系ばっかなんでしょ。
それだけ別物だから俺には tempering と sbox を同列には扱えん。
以上。
775 = :
>>772
俺はアセンブリじゃないと絶対に出来ないことをやってるから他の点の実装が一緒なら有利かもしれん
正直な話このスレで結構な数のヒント貰ったからこれがないと負けてた
776 = :
この程度ならあんまり影響っていうレベルで、Cで組む人にアドバイス。
（というかC＋組み込み関数で俺に挑もうと考えてる奴は流石にいないだろう）
特にイライラしたのは、even側の命令減らしたいのに値のロードにimmidiate load（evenロード)に勝手に展開しやがること。
qword型でしてるのにimmidiate load。
どうやらQWORDの全要素が同一の値だと勝手にimm loadに展開しやがるらしい。
んで、volatileにしたらアドレスからロード（Odd）に展開してくれるようになった。
とか、いろいろ。
あと、AND/OR/XORなどで使う値はhalfwordに即値指定すれば命令数を減らせる。
俺としてはまた方針を変えてパイプラインを詰め直そうと思っている。
現時点で片方のパイプが全部埋まるところまでCで詰めることができてるわけで
>>774
残念だが同意できない。
標準規格においてダントツのトップに君臨するAESはFeistel系アルゴリズムとちょっと似てるが分類上別物。
あと示したとおり、Camelliaは普通のFeistel型暗号で従来4つ以上のLUT（S-Box）が必要な処理を
1つのLUTとローテートで水増ししてるけど、その点で強度に問題があるといわれたことは無い。
単一のS-boxにビット演算を少し組み合わせるだけで、強度を得るのに必要なS-boxの数を
実質的に減らすことができるのだから、シフト・論理演算・定数の組み合わせでS-boxを使わずに
性能と強度を得るのが不可能とは思わん。
実際問題、S-boxを使わないRC6は多くのFeistel暗号より高速で、なおかつ十分な堅牢性がある。
S-boxがハードウェアの負担が小さいってこと自体同意できない。
モバイル向けのプロセッサにはAESのS-boxすらデータキャッシュに収まりきらないくらい小さいものもある。
CamelliaがSBOXを最小の実装でたったの256バイトのLUTだけで構成出来るように配慮されてるのは
ミリワットクラスの組み込みCPUでの実装を視野に入れてるからだ。
CamelliaのS-boxが小さいことは、キャッシュメモリが小さいアーキテクチャにやさしいということでもある
で、それでいて十分な強度という評価を得ている。
777 = :
うーん、論点がどこなんだかイマイチ解らん。
feistel の sbox と spn の sbox は別物なのか？
俺も不可能とは思ってないし否定もしないよ＞RC6
負担が小さいとも思ってない。堅牢性と共に、早く
出来ることも小さくする事も可能なのが重要なだけ。
AES の sbox も 256 だったと思うのだが違うのか？
俺には tempering と sbox を同列に扱うのは理解
できないし、「みたいなもん」なんて説明には到底
同意できんから異は唱えるが、別に団子がそれで
間違ってないって思うのはどーでもいーよ。
ってか、こんな話誰もついてこねーよなw
でもさー、団子も sbox 系とシフト・論理演算系を
綺麗に別けてねーかw やっぱ別なんじゃね？w
778 = :
>>770
みんなすげぇなぁ。
おいら even -1 したら、odd +3 = total +1 で意味なかったよ orz
779 = :
>>778
wwwwwwwwwwwww
すっげーヒントあげたいけど、その壁は自分で超えろ。
780 = :
>>778
大丈夫、私もその辺で挫折した。つーか、飽きたw
781 = :
>>693が、58156364 / 4 * 12.5 / 40 = 4543466 か。
この数値が出せてたら俺より速い。
>>775 の意味も判る。
現時点でこのスレだと、
優勝、準優勝候補 : >>693 , 俺
優勝候補を抜く可能性のあるヒト: >>568, >>579
だんごさんと >>579 の話にはついていけなかったんだが、
とりあえず >>579 の Prolog が導き出した解法のサイクル数が
出るまではインラインアセンブラで限界まで行った者勝ちっぽいな。
782 = :
まー普通に考えても、ここに書き込んでないやつで優れた奴もいるだろ～から
優勝候補をこのスレ内で絞るってのも無理があると思うんだけどな
783 = :
>>782
もちろんその可能性は否定しない。このスレを読まないと、「命令数どこまで減らせる」という
指標がない状態でチキンレースに参加しないといけないからキツイけど、このスレをROMってるなら
命令数がどこまで減らせるか判るね。
784 = :
>>781
おい、俺様を優勝・準優勝の可能性からはずすな！
いや外してもいいや。こっから先の手の内は明かすわけにはいかない
とりあえずカードは残してる。
785 = :
>784
だって亀田兄弟的ポジションじゃんｗ
786 = :
>>784
まじかよ・・・
>>693の12.5がもう限界だと思ってた。
787 = :
>>786
全然関係ないけどさ
Oddへの置き換えなしだとEven側は18くらいかかるわけだけど、これを17に減らす方法って気づいた？
788 = :
mt[n] = mt[m] ^ (x >> 1) ^ (((x & 1) == 1)? 0x9908b0dfUL : 0);
↓
x = rotr(x, 1);
mt[n] = mt[m] ^ x ^ ((x > 0x7FFFFFFF)? (0x1908b0dfUL) : 0);
※これを使ってもチキンレースには参加できません。課題が別モノなら有用だったかも
これ問題公開されてから3日くらいで考えたネタだけど、最終的に高速化の候補としては外れた方法だから敢えて紹介しておく。
あとブロック単位じゃなくてスカラ単位で取り出す場合はこっちのほうが速いかもしれない。レイテンシ的な意味で。
790 = :
>>787
evenの命令数削減は無意識だから、どうやったら even18 になるか悩んだ。
andc ともう一つ命令を使うヤツか？
もう一つの命令で予約違反してるけど、将来のSPUで動かなくなっても
構わないと判断したよ。
792 = :
>>202 なに言ってんだ？w
793 = :
いっか、トップランカーには無意味な情報だからバラしちゃえ。
spu_and( matrix_a, spu_cmpeq( spu_and( x , 1 ) , 1 ) )
↓
spu_andc( matrix_a, spu_subx( z, z, x ) )
794 = :
コンテスト参加してんのお前らだけじゃねーぞ
少しは考えろ
795 = :
ってか、202 には >>788 の答えは見えてないのか？
796 = :
>>794
悪い。調子乗りすぎた。
締め切りまで黙ってる。
797 = :
>>793
そ ん な 方 法 も あ っ た の か
第一オペランド破壊する命令はうまく考えて使わないと困るんだよね。
>>788見つけたときは俺SUGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEって思った
798 = :
>>797 こんなので思うな!w
799 = :
8bit×4の水平加算とかあるけど何に使うんだコレ
SSEのPSADBW/MPSADBWと同じく、動画の動き検出とかに使うんだろ？
それしか思いつかない。
悲しいことに今回の課題でも役に立たない。
如何あがいても垂直加算のほうが性能出る。
これがもしもOddで処理されるならまた使い方も違ったんだけど。
みんなの評価 : ☆
cell一覧へ類似してるかもしれないスレッド
- cellプログラミングしちゃいなよ4 (607) - [97%] - 2009/3/24 11:04 ○
- CELL鬯ｯ?ｩ隰ｳ?ｾ??ｽ??ｵ????ｺ?????ｯCore2 QX6700鬯ｯ?ｩ隰ｳ?ｾ??ｽ??ｵ????ｺ???? (92) - [18446744073709551581%] - 2012/1/21 0:39
トップメニューへ / →のくす牧場書庫について