- 1 名前：デフォルトの名無しさん mailto:sage [2008/07/07(月) 08:55:08 ]
- 前スレ
Cellプログラミングしちゃいなよ2
pc11.2ch.net/test/read.cgi/tech/1183091522/
- 700 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 03:57:56 ]
- 刹那な午後の人が hack the cell 始めてる〜 ＆ここも見てるっぽい。
いやー、さんざん勉強させて貰ったんで、なんか感慨深い感じ。
- 701 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:13:25 ]
- ああ、herumi氏のことか。
ここじゃないと思うよ。
リアルGoogle社員の人の日記（あそこのこと）見て真似を始めたらしい。
交流があるそうな。
去年ぐらいから一連のやり取りヲチしてるけど
東大院出身と京大院出身の頭脳バトルは見てて面白い。
素晴らしいじゃないか。
俺もherumi氏と戦えるなら負けても悔いはない。
＃妨害ついでにXbyakのAtom新命令対応パッチまた送りつけてやるかﾋﾋﾋ
- 702 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:29:35 ]
- まてよ
60倍云々って・・・俺のカキコが初出の情報かもしれない・・・ｗｗｗｗ
まああの人は俺の日記読んでるからな
- 703 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 04:46:51 ]
- んー、わからん。誰だろ？ > real google の人
&日記更新してたんね。15cycle の latency の話だけど、
6cycle なのは命令実行後 LS に反映されるまでの latency
だから、命令解釈やら register file から各演算器の latch
への転送とかの 15cycle とは別物だよー。マジ長いねw
- 704 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 04:51:42 ]
- しょっちゅうherumi氏が日記のネタにしてるじゃないの
ヒント：「yajit」
- 705 名前：202 mailto:sage [2009/01/22(木) 09:29:56 ]
- 俺も初めてアセンブラ触った動機がMMXで画像処理したい！で、
へるみさんのサイトに散々お世話になった。
なんか感慨深いなー。
- 706 名前：202 mailto:sage [2009/01/22(木) 09:31:57 ]
- >>704
チーム参戦型のICFPプロコンで、個人で上位を取っちゃうあの方ですね、わかります。
- 707 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 16:11:09 ]
- 今日もサボリのタミフルが、何故かおとなしいな
- 708 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 16:16:48 ]
- 呼んだら出てきちまうだろ！ｗ
- 709 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 20:26:42 ]
- くそー、13 切れねぇ orz
- 710 名前：202 mailto:sage [2009/01/22(木) 21:07:07 ]
- 13が増えてきてるのが凄く脅威なんだが・・・
693、俺、だんごさんが13切ってて、227と709が13か
- 711 名前：579 mailto:sage [2009/01/22(木) 21:08:07 ]
- >>640
>それよりUNIX crypt(3)のハッシュ値からキーをダイレクトに
>求めるアルゴリズムでも解明して下さいよｗｗｗ
暗号乱数とモンテカルロ乱数は別物だと何度もいっているだろバカ
>>647
>まあとりあえず脳内珍論はブログでやれ。
ブログに書くほどの内容でもないからここに書いているわけだがｗ
>>657
>テーブルのオフセットをアドレスを求めて値をロードするのも「演算」です。
これは痛すぎるだろ。tempering も線形写像なわけだが。
>>683
>それに比べればこちとらまだ青天井みたいなもんだよ。
青天井の意味知ってる？
- 712 名前：579 mailto:sage [2009/01/22(木) 21:10:55 ]
- どうせ団子理解できないだろうから教えてやるよ。
その前に md5sum = 770e20e29056b7e5d420fc46bdc5ee6a
>>637
>んで、頭弱い子は加算命令をXORとANDに分解してソフト的に
>加算すればいいと思ってるだろ？
>レジスタ足りる？むしろメモリ足りる？
お前が挫折したからって俺と一緒にするな。
数値の表記法は n 進表記だけじゃないんだぜ？
欲しいのは 2 進表記の sum なわけだが、最終的に変換可能で
あれば途中経過の表記法は何だって構わない。交番だっていい。
問題なのは、mod 2^32 がガロア体ではないことだ。
- 713 名前：579 mailto:sage [2009/01/22(木) 21:11:18 ]
- ループの内側がガロア体で、外側がガロア体ではなかったら、
そりゃ計数するのは非効率だろう。だったら、2^33 のガロア
拡大体の上で計数してみようという発想にはならんのかい？
33 次 M 系列の生成多項式 (33, 13) を使えば、十分実用的だ。
この系で 1 を計数する方法を考えれば明らか。
外側のループが ^= になっただろ？
>>628
>→「あり得ない仮定を持ち出す」
馬鹿が。
いくらお前でも、ガロア拡大体上での計数を前提としておけば、
tempering をループの外側に出せることも少し考えればわかるだろ？
そして、最後にシンドローム計算すれば 2 進表記に戻せる。
- 714 名前：579 mailto:sage [2009/01/22(木) 21:11:51 ]
- >>631
>ああ、ちなみに最初くらいに1ビット×128並列のビットスライス
>実装思いついたけど全然速くなかったよ。
馬鹿はここで諦める。
ガロア拡大体上での計数は、ビットスライスで行った方が効率が
良いは明らか。が、mt[] の更新をビットスライスで行うのはいささか
非効率。これは、MT が "ビットスライスではない" 計算機での効率を
狙ったものなので当然といえば当然。
ビットスライスではない計算機で扱える効率的な線形写像は、
行列 [[0ii,0ij]T,[Iij,Ojj]T] (つまりビットシフト) の掛け算と
要素どうしの掛け算(AND)と足し算(XOR)、その組み合わせだ。
それに対して、ビットスライスで扱いやすい線形写像の条件は、
行列中に "1" の出現頻度が少ないもの。至極当然。
ならば、最初に mt[] を別の空間に写像しておいて、その空間で
更新行列の "1" が少なくなるように設計すればいくらでも
(それこそ青天井に)効率は改善される。
- 715 名前：579 mailto:sage [2009/01/22(木) 21:12:34 ]
- しかし、これだけだとビットスライスを用いる根拠としてはまだ
少し弱い。それは、mt[] のサイズがレジスタ数と比較して大きい
(load, store をスケジュールするのが大変)のと、"1" の割合を
減らせたとしても行列自体が大きいので、必然的に計算量は多いまま。
そこで、mt[] 自体を小さくすることを考えよう。
が、残念なことに MT は mt[](19968 bit)のうち、19937 bit が
直交していることが理論的に証明されている。
さて、どうしよう？
>>640
>なんにせよ10000≦num_rand＜UINT_MAXだからなぁ
答え書いてあるじゃないかーい。INT_MAX だけどな。
つまり、32bit の seed から始まる 31bit の空間は、19937bit の
空間の中で、非常に小さな部分空間でしかない。
その小さな部分空間では、19937bit の大部分が直交していない。
直交していないビットは、それこそ計算する必要はない。
課題アナル(仮称)の正体は、直交していないビットを探索するものに
他ならない。
- 716 名前：デフォルトの名無しさん [2009/01/22(木) 21:23:46 ]
- だンゴサんの括約で棺桶スレが成立したな
- 717 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:33:32 ]
- >>579
なんでこんな大事なことばらしちゃうの？ｗ
- 718 名前：202 mailto:sage [2009/01/22(木) 21:36:40 ]
- 一応、みんな判ってると思うが、Hack the Cell の課題が何か確認しておく。
ttp://cell.fixstars.com/challenge/challenge.html
課題は、メルセンヌ・ツイスタの最適化です。
注意事項
※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ乱数列を生成してください。
- 719 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:39:22 ]
- 芽のない方法を芽がないと割り切る能力が欠落した人間の遠吠えはむなしいのう
- 720 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:42:03 ]
- >>717
机上の空論だよ
突っ込みどころのデパート。詭弁の集大成。
まったくもって今回の課題の解法として役に立たない。
- 721 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:45:16 ]
- >>710
あれ？202 も 13 切ってたの？ >>598-599 のやり取り見て、
まだ切ってないと思ってたよｗ
>>720
自分も >>599 が当てはまるとやばいんじゃないの？ｗ
- 722 名前：579 mailto:sage [2009/01/22(木) 21:47:43 ]
- 連続投稿引っかかったｗｗ
最後に、端数をどうするかだ。
その前に、報告しておく。俺のアナルはもう検算フェーズに入ったぜ？
ざっくりと pmt[] の最悪値を見積もり始めた頃から勝算はあった
わけだが、解析結果を見ると想像以上に小さい。
これが何を意味するかわかるな？
第一に、mt[](pmt[]) の更新はほぼ O(rn^2) のコストであること。
r は線形写像行列に含まれる "1" の割合。n は行列のサイズ。
第二に、pmt[] から計数ベクトルへの写像行列を N-1 種類まるまる
用意してもメモリサイズ的に余裕ができたこと。
いまからマネしようとしても、解析の方法なんて想像もつかないだろ？
お前はご自慢の 59ms アナルでおとなしく全数探索でもしていろｗ
さーて、そろそろ実装でも始めますかｗｗｗ
- 723 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:50:46 ]
- >>721
単純にMTの式をMTを32ビット×4並列化したものではないということだよ。
配列状態とサマリの値が等価になる範囲で高速化出来る方法は全て駆使してる。
もうやることは終わってさじ加減次第かな。
部分的にスカスカな部分があったりするのでループ全体を見て命令数が減るようにバランス調整が必要だ。
- 724 名前：579 mailto:sage [2009/01/22(木) 21:51:09 ]
- >>719
自分に自信がないやつほど声がでかいってのは本当だったんだな。
- 725 名前：579 mailto:sage [2009/01/22(木) 21:52:11 ]
- >もうやることは終わってさじ加減次第かな。
青天井じゃなかったのかよ
- 726 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:52:40 ]
- >>722
机上の空論は結果を出してから言うことだ
- 727 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 21:53:13 ]
- >>724←これとかな
- 728 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 21:53:27 ]
- >>579
アンタ、糞団子と接するのは初めてかい?
まあ力抜いてアナル(r
- 729 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:00:14 ]
- だんごも>>579もすごいぜ
少なくとも議論の台に乗れるんだから
俺も工学系だから少なくとも理系ではあるんだが何を言ってるのか全くわからんｗ
とりあえずサイクルの話はあんまりしない方がいいとおもた
サイクルの話見ただけでどこの最適化やっててどこの最適化やってないか想像できるし
- 730 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:00:24 ]
- 負け犬579をアボーンリストに追加しとけばいい
彼は全然役に立たないことしか言ってない。
まあ見えない敵と戦ってる馬鹿だから相手にするな
- 731 名前：579 mailto:sage [2009/01/22(木) 22:05:16 ]
- >>717
どうせ団子理解できないだろ？
>>718
>※似乱数列は、メルセンヌ・ツイスタの実装 mt19937ar.c と同じ
>乱数列を生成してください。
何をもって「同じ」とするか、だ。
tempering 前の数値も tempering 後の数値も、表記法が
異なるだけで、同じ数値なわけだ。tempering した方が
モンテカルロに用いる上では好都合な事が多いので
しているだけ。
>3. それともチェックサムだけ合ってればなんでもアリなのか、
>1. プログラム中でmt[]の内容を計算していたら良いのか、
>2. 全乱数wordについてtempering後の値も計算していないといけないのか、
これが 2 だったら、出題者が問題の意図理解していないよ orz
1 の判断は微妙だが、仮に 1 だとするとできる事は限られてくる、
つまりそんなコンテ誰が出ても結果は一緒。ツマンネ。
- 732 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:06:35 ]
- ハイ おさらい。
pc11.2ch.net/test/read.cgi/tech/1158559031/l50
SSE実行できないCellでSSEの実測をしたという捏造の瞬間ｗｗｗｗｗ
864 名前： ・∀・）っ-○◎● [sage] 投稿日： 2007/06/17(日) 16:22:27
movd xmm0, eax
movd eax, xmm0
movd xmm0, eax
movd eax, xmm0
movd xmm0, eax
movd eax, xmm0
movd xmm0, eax
movd eax, xmm0
こんな感じで繰り返せば一応往復のレイテンシは計測できるよね
で、何クロックかかるのかな？
答えてね。俺より頭いい子ならすぐわかるはず。
もっとも俺は実測結果あるけど
866 名前： デフォルトの名無しさん [sage] 投稿日： 2007/06/17(日) 16:26:12
CellでSSEって
- 733 名前：202 mailto:sage [2009/01/22(木) 22:08:13 ]
- >>721
>>689は超えたよ。
結構苦労してアセンブラ書いたしね。
>>721(=>>693?)もだんごさんも、tempering後の値をまじめに計算して
add を繰り返してる訳じゃないのか・・・
とりあえず、チェックサムだけ合ってればOKなのか訊いてみて、
OKならまただんごさん超えに挑戦してみるよ。
- 734 名前：579 mailto:sage [2009/01/22(木) 22:09:04 ]
- >>728
アナルの力抜いておくよ。
>>730
ｶﾞｸﾌﾞﾙしている姿が見えて楽しいよｗ
- 735 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:09:26 ]
- 693だけどtemperingは毎回やってる
というか処理の7割がtempering
泣きそう
- 736 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:15:59 ]
- 話の腰をもんで悪いんだが
temperingってなんだ？
- 737 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:17:17 ]
- 揉むな!ｗ
- 738 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:20:06 ]
- 勘で出てきた乱数を32bit空間で偏りが無い様に再マッピングしてるんだと勝手に思ってた
- 739 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:21:20 ]
- マージャン用語です
テンパイ ＝【聴牌】
麻雀で、あと一枚必要な牌がくればあがることのできる状態。
これが、転じて何か事を成し遂げようとしたときの最終段階、、待ちの状態になったときに使うケースがあります。
てんぱる、てんぱってる。
スタンばる（スタンバイする）、、などと同じ和製語ですね。
- 740 名前：579 mailto:sage [2009/01/22(木) 22:22:14 ]
- さてさて。
一日静かだと思っていた矢先、団子登場。団子はよっほど俺の
アナルが好きなんだなｗ 頼むから寝込み襲ってくるなよ。
この手の作戦だと実装を後回しにした方が効率いいわけだが、
結果出せ出せウルセーやつがいるから、俺はそろそろ実装始める
ことにするよ。
その前にクソして寝る。
- 741 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:23:20 ]
- >>739
そうだったのか…
勘とはいえすごい的外れな嘘を教えてしまった
ごめんよ>>736
- 742 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:27:12 ]
- おおざっぱに、MTで乱数生成の為に行うアルゴリズムでビットシフトを行う操作のことだな
tempering
- 743 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:30:00 ]
- >>729
暗号論の世界にも差分解読法なんてのがあって、ビットの並びの特徴から演算をショートカットする
方法に関しては俺自身もいろいろ試したことがあってね。
んで、今回はそういうショートカットは全くもって役に立たない。
MTのTemperingはフェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。
RISCオペレーションで10命令程度のビット論理演算で構成できるとはいえ、
けっこううまい具合にビットがばらけるように考えてある。
加算ってさ、簡易的にはXORとANDの組み合わせで作れるわけだけど、
キャリーアップ先は、1ビット隣じゃん。
Tempering前と後じゃその1ビット隣すら全然別物になっちゃうんだよね。
だからTempering前の値をいくら「加算」しても無意味なんだ。
Temperingは少ない命令数ながら、うまく考えてあると思うよ。
暗号の実装の話になるけど、AltiVecのVPERMやSPUのSHUFBはAESのS-Boxを16並列で処理する
ことができるけど、SSEだと同様のシャッフル命令であるpshufb命令なんかを使うより別の方法のほうが速い。
今回の課題はそう言う観点で何が最適なアルゴリズムかを考えられる人でないと難しいと思う。
- 744 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:31:58 ]
- > フェイステイル型暗号でいうところの一種のS-boxみたいなもんだ。
ち・が・う
- 745 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:34:09 ]
- >>739
(y << 15)んとこが16だったらアレしてこうして・・・とか思ったけど
なかなかうまくいかないもんだね
- 746 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:36:08 ]
- >>744
あらゆるフェイステイル型暗号のS-boxはビット論理演算の組み合わせだけで実装できるの知ってる？
- 747 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:37:44 ]
- お得意の bitslice か？ それと s-box の意義は全然別物だぞ？
- 748 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:39:16 ]
- フェイステイル型暗号におけるS-boxの役割は、簡単に言うと前後のビットの並びの相関性を破壊するための仕組み。
MTのTemperingも、Temperingを省いて合計値を計算しようとしても出来ないようにする程度には相関性を破壊できてる。
- 749 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 22:45:37 ]
- そりゃ、暗号も擬似乱数も拡散って意味ではなんだって拡散だし、
ほとんどが論理演算の組み合わせで実装できるだろうよ。
その程度の意味で、feistel の s-box と同じって言ったのか？
- 750 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 22:53:59 ]
- Tempering＝「調律」
スイーツ（笑）用語でいうとチョコレートコーティングの表面を滑らかにするための行程。
もちろん、そのまんまの意味で解釈しても意味はない。
ビットの並びの相関性をある程度破壊することに意味がある。
MTにおいては、相関を破壊することが、ビットの出現確率の均一化（Tempering）になる。
S-BoxのSはsubstitution
ようするにテーブルルックアップなわけだが。
たしかにTemperingとS-boxは別の単語だが、言葉をそのまま捉えても意味はない。
本質を理解しないといけない。
テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では
ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。
だから本質的に同じだって言ったんだよ。
- 751 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:07:52 ]
- >テーブルルックアップを使わない暗号・ハッシュアルゴリズムの実装では
>ほとんどMTのTemperingみたいな簡単なシフト＋ビット論理演算をやってる。
へー、すごいなｗ。いや、LUT を使わない実装が標準とか思わないほうがいいぞ？
暗号作ってる方は簡単なシフト＋ビット論理演算で求められないように sbox を
導入してるのに、なんか可哀想になってきちゃうよ。
まぁ確かに本質的には両方拡散だから同じだしなｗ
- 752 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:30:18 ]
- >>751
RSAのRivest Cipher(RC)シリーズとかMD5なんてS-boxを使わずにスワップを繰り返す
暗号・ハッシュアルゴリズムの代表格なわけだが？
RC6はAESの最終候補まで残ったぞ。
- 753 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:36:19 ]
- なんで軒並み落ちてって、今 feistel ばっかなのか考えようぜｗ
- 754 名前：デフォルトの名無しさん [2009/01/22(木) 23:37:45 ]
- >>743
よわかりませんが、M系列で「加算」する場合もキャリーは１ット隣なのでしょうか？
- 755 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:42:56 ]
- >>754
最低限言えることは、SPUには任意の位置のビットにキャリーアップしてくれるような特殊な算術加算命令はないということだ。
まあそういうことだ。
ハードウェアに不向きなことをやらせて性能を出そうという方が間違い。
- 756 名前：デフォルトの名無しさん [2009/01/22(木) 23:49:49 ]
- なんだかよくわかりませんが、よくわかりました。
ありがとうございました。
- 757 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/22(木) 23:55:21 ]
- 関係ないけどJNBのトークンって暗号形式なんだったっけ？
- 758 名前：デフォルトの名無しさん mailto:sage [2009/01/22(木) 23:59:44 ]
- そろそろ詭弁の○○ヶ条で〆てくれ
- 759 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:06:08 ]
- >>753
そこはAESばっか、に訂正しろよ。
AESが世界的に選ばれてるのはAESがAESだからだ。
AESに選ばれなかったfeistel暗号の信頼性を保証する根拠にするのは間違いだな。
とっくに死んだはずのDESが何故かワンタイムパスワードとして現役で使われてたりするくらいだし。
そのレベルで言うならMD5やRC4だって未だに使われてるんだぜ。
iがつかないニンテンドーDSだとWi-FiはWEP（RC4）強制だしｗｗｗｗｗ
それに比べれば国産暗号のMISTYとかCamelliaなんてまだまだマイナー杉。
松井さんには悪いが。
- 760 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:11:09 ]
- ん？ DES も Feistel だろ？ MISTY1 も Camellia も NESSIE とってるが。
＆ MD5 と RC4 をこれから新規に採用する規格があったら驚きだが？
- 761 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:17:04 ]
- ちなみに、SHA-3 コンペでも feistel 使われてるぞｗ
- 762 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:18:28 ]
- 当たり前のこと言ってどうすんだ。鍵長考えてものを言え。
引き合いに出すならRC6あたりだろ。
RijndaelがAESに選ばれたのはその一つとしてDESみたいな複雑なビットシャッフル演算がなくて
専用ハードウェアでなくても実装コストが軽いからだ。
別にRC6の暗号強度が否定されたわけではない。
- 763 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:30:55 ]
- すまん、ちょっと読み違えてた。が、時間がない。また今度w
あ、俺も RC6 の暗号強度を否定するつもりは毛頭ないよ。
- 764 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:33:43 ]
- そもそも別にLUTよりビット演算のほうがコストパフォーマンスが優れてるなんて言う気はない。
不毛すぎ
今回のTemperingを通す前にサマリ計算が出来るかどうかだが
実用的な計算時間をはじき出すのは「無理」と言えるレベルの相関性の破壊は達成できてるというのが
俺の見解。
俺個人は国産暗号マンセーの立場なので君に付き合ってRSAの腐れの擁護する気もない。
ちなみにSHA-3候補として俺が注目してるのはこれ
ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf
＃あとAESは厳密にはSPNSであってFeistelには分類されない。
- 765 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 00:37:12 ]
- 日本語でおｋ
- 766 名前：デフォルトの名無しさん [2009/01/23(金) 00:39:15 ]
- 当たり前のこと言ってどうすんだ。
- 767 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 00:43:44 ]
- 個人的にCamelliaのSSE4向け実装とか開発中
おれ松井さん好きだし
＞Fixstarsさん
来年の課題はCamelliaでお願いします。
- 768 名前：復活 mailto:sage [2009/01/23(金) 01:17:25 ]
- >>764
俺の見解は、拡散って意味では tempering も sbox も同じってのには同意。
だが、シフト＋ビット論理演算ではできない substitution を実現するために
sbox を導入してんだから、それを安易に同列に扱うのは理解できん。
あ、国産マンセーは俺も一緒。来年 Camellia いいねぇw
- 769 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:09:19 ]
- ま、とりあえず俺の情報源のひとつ晒しておくわ。
暗号アルゴリズム及び関連技術の評価報告
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 名前：227 ◆eZQcaIaFJs mailto:sage [2009/01/23(金) 02:17:31 ]
- >>710
とりあえず13clock切れた。けど謎のストールに阻まれ停滞中orz
- 771 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:34:03 ]
- 本命：団子
対抗：>>202,>>227
大穴：>>579
- 772 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:44:12 ]
- 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 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 02:47:12 ]
- まあ、どうやってコンパイラの副作用を抑え込んだのかっていうのはソースにびっしり書いてたりするから
俺が上位に残ってたら参考にしてくれ、的な。
- 774 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:55:35 ]
- >>769
俺の言いたい事は >>768 で言ったが、「今 feistel ばっか」とかが
気に食わないんかな？ sbox ＝ 堅牢と言ってるんではなくて、堅牢さと
速度を両立するのに sbox が向いてると言いたいだけなんだが。
シフト＋ビット論理演算だけで同等の堅牢さを実現するよりも、
sbox の方が早くし易いし、小さくもし易いって理解なんだけど。
だから NIST にしろ NESSIE にしろ、feistel 系ばっかなんでしょ。
それだけ別物だから俺には tempering と sbox を同列には扱えん。
以上。
- 775 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 02:55:47 ]
- >>772
俺はアセンブリじゃないと絶対に出来ないことをやってるから他の点の実装が一緒なら有利かもしれん
正直な話このスレで結構な数のヒント貰ったからこれがないと負けてた
- 776 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 03:46:15 ]
- この程度ならあんまり影響っていうレベルで、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 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 04:24:16 ]
- うーん、論点がどこなんだかイマイチ解らん。
feistel の sbox と spn の sbox は別物なのか？
俺も不可能とは思ってないし否定もしないよ＞RC6
負担が小さいとも思ってない。堅牢性と共に、早く
出来ることも小さくする事も可能なのが重要なだけ。
AES の sbox も 256 だったと思うのだが違うのか？
俺には tempering と sbox を同列に扱うのは理解
できないし、「みたいなもん」なんて説明には到底
同意できんから異は唱えるが、別に団子がそれで
間違ってないって思うのはどーでもいーよ。
ってか、こんな話誰もついてこねーよなw
でもさー、団子も sbox 系とシフト・論理演算系を
綺麗に別けてねーかw やっぱ別なんじゃね？w
- 778 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 05:11:28 ]
- >>770
みんなすげぇなぁ。
おいら even -1 したら、odd +3 = total +1 で意味なかったよ orz
- 779 名前：202 mailto:sage [2009/01/23(金) 09:21:02 ]
- >>778
wwwwwwwwwwwww
すっげーヒントあげたいけど、その壁は自分で超えろ。
- 780 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 09:41:39 ]
- >>778
大丈夫、私もその辺で挫折した。つーか、飽きたw
- 781 名前：202 mailto:sage [2009/01/23(金) 09:42:23 ]
- >>693が、58156364 / 4 * 12.5 / 40 = 4543466 か。
この数値が出せてたら俺より速い。
>>775 の意味も判る。
現時点でこのスレだと、
優勝、準優勝候補 : >>693 , 俺
優勝候補を抜く可能性のあるヒト: >>568, >>579
だんごさんと >>579 の話にはついていけなかったんだが、
とりあえず >>579 の Prolog が導き出した解法のサイクル数が
出るまではインラインアセンブラで限界まで行った者勝ちっぽいな。
- 782 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 11:13:19 ]
- まー普通に考えても、ここに書き込んでないやつで優れた奴もいるだろ〜から
優勝候補をこのスレ内で絞るってのも無理があると思うんだけどな
- 783 名前：202 mailto:sage [2009/01/23(金) 11:46:04 ]
- >>782
もちろんその可能性は否定しない。このスレを読まないと、「命令数どこまで減らせる」という
指標がない状態でチキンレースに参加しないといけないからキツイけど、このスレをROMってるなら
命令数がどこまで減らせるか判るね。
- 784 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 11:59:48 ]
- >>781
おい、俺様を優勝・準優勝の可能性からはずすな！
いや外してもいいや。こっから先の手の内は明かすわけにはいかない
とりあえずカードは残してる。
- 785 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 12:06:20 ]
- >784
だって亀田兄弟的ポジションじゃんｗ
- 786 名前：202 mailto:sage [2009/01/23(金) 12:08:22 ]
- >>784
まじかよ・・・
>>693の12.5がもう限界だと思ってた。
- 787 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:16:58 ]
- >>786
全然関係ないけどさ
Oddへの置き換えなしだとEven側は18くらいかかるわけだけど、これを17に減らす方法って気づいた？
- 788 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:27:55 ]
- 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日くらいで考えたネタだけど、最終的に高速化の候補としては外れた方法だから敢えて紹介しておく。
あとブロック単位じゃなくてスカラ単位で取り出す場合はこっちのほうが速いかもしれない。レイテンシ的な意味で。
- 789 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 12:44:24 ]
-
^ x ^
↑このへんがむかつく
- 790 名前：202 mailto:sage [2009/01/23(金) 13:24:28 ]
- >>787
evenの命令数削減は無意識だから、どうやったら even18 になるか悩んだ。
andc ともう一つ命令を使うヤツか？
もう一つの命令で予約違反してるけど、将来のSPUで動かなくなっても
構わないと判断したよ。
- 791 名前：202 mailto:sage [2009/01/23(金) 13:26:21 ]
- andcじゃなくてselでも良いのか。
- 792 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 13:48:27 ]
- >>202 なに言ってんだ？w
- 793 名前：202 mailto:sage [2009/01/23(金) 13:54:00 ]
- いっか、トップランカーには無意味な情報だからバラしちゃえ。
spu_and( matrix_a, spu_cmpeq( spu_and( x , 1 ) , 1 ) )
↓
spu_andc( matrix_a, spu_subx( z, z, x ) )
- 794 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 13:58:00 ]
- コンテスト参加してんのお前らだけじゃねーぞ
少しは考えろ
- 795 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 14:00:30 ]
- ってか、202 には >>788 の答えは見えてないのか？
- 796 名前：202 mailto:sage [2009/01/23(金) 14:00:57 ]
- >>794
悪い。調子乗りすぎた。
締め切りまで黙ってる。
- 797 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 14:03:11 ]
- >>793
そ ん な 方 法 も あ っ た の か
第一オペランド破壊する命令はうまく考えて使わないと困るんだよね。
>>788見つけたときは俺SUGEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEって思った
- 798 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 14:06:19 ]
- >>797 こんなので思うな!w
- 799 名前：,,・´∀｀・,,）っ-○◎● mailto:sage [2009/01/23(金) 21:14:51 ]
- 8bit×4の水平加算とかあるけど何に使うんだコレ
SSEのPSADBW/MPSADBWと同じく、動画の動き検出とかに使うんだろ？
それしか思いつかない。
悲しいことに今回の課題でも役に立たない。
如何あがいても垂直加算のほうが性能出る。
これがもしもOddで処理されるならまた使い方も違ったんだけど。
- 800 名前：デフォルトの名無しさん mailto:sage [2009/01/23(金) 21:23:56 ]
- absdb/avgb/sumb あたりは動画のためだぁな。
|
 |
