- PR -

AESについて

投稿者

投稿内容

Kit: 会議室デビュー日: 2005/08/19; 投稿数: 12

投稿日時: 2005-08-19 23:23

AESのアルゴリズムを理解したいと考えて、NISTのホームページより資料を印刷し読んで理解しようとしている最中なのですが、理解できない点があり困っています。周りでは暗号を専門でやられている方がおられないため質問ができません。
よろしければ私の質問に答えていただけないでしょうか？
先輩の皆様、ご教授宜しくお願いします。（ｍ＿ｍ）
質問はNISTのホームページhttp://csrc.nist.gov/CryptoToolkit/aes/
のFIPS-197
にある4.2 Multiplicationの項目の
ｘ13乗＋ｘ11乗＋ｘ9乗＋ｘ8乗＋ｘ6乗＋ｘ5乗＋ｘ4乗＋ｘ3乗＋１
modulo
(ｘ8乗＋ｘ4乗＋ｘ3乗＋ｘ＋１）
＝ｘ7乗＋ｘ6乗＋１
となぜなるかです。（文字化けするかもしれないのでｎ乗という表記をしました）
私の考え方では十進数で考えた場合１１１２９　mod　２８３　＝　９２（ｘ6乗＋ｘ4乗＋ｘ3乗＋ｘ2乗＋１）となり上記の答えと当てはまりません。
またmoduloはmodと同じと考えて仮に自然数ｈとｙ（ h > y ）をh/yより余りを求める計算方法としやっています。
宜しくお願いします。

jk: ベテラン; 会議室デビュー日: 2005/08/19; 投稿数: 94

投稿日時: 2005-08-20 01:03

私も、暗号のことに関しては詳しくはないですが。
CRC32の計算方法を10年ほど前に学習したときのことを思い出しました。

x^nという表現は 2^nという表現とほぼ同一と思います。
暗号化ブロックのうちの nビット目ということで 2^nだと数値として意味してしまうので
こんな書き方になっているのですよね？

で、・はfinite field manupicationと定義されていて乗算の過程の加算はビットごとに xorで行います。

(x^6 + x^4 + x^2 + x ^ 1 + x^0)(x ^ 7 + x^1 + x^0)
= x^13 + x^11 + x^9 + x^8 + x^7 +
x^7 + x^5 + x^3 + x^2 + x^1 +
x^6 + x^4 + x^2 + x^1 + x^0
=0010 1011 1000 0000
+0000 0000 1010 1110
+0000 0000 0101 0111
=0010 1011 0111 1001

∴
x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 * x^3 + x^0

となります、ココまでは理解できますよね？

moduloも同じく割り算の過程で引き算をビットごとに xor で行います。

x^13 + x^11 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1 modulo x^8 + x^4 + x^3 + x + 1
0010 1011 0111 1001 modulo 0000 0001 0001 1011

0010 1011 0111 1001
0010 0011 0110 0000 xor (左シフトして上位ビットをあわせる)
------------------
0000 1000 0001 1001(0819h)

まだ割る数より大きいのでさらに
0000 1000 0001 1001
0000 1000 1101 1000 xor (左シフトして上位ビットをあわせる)
------------------
0000 0000 1100 0001(00c1h)

これで、割る数より小さくなったので、剰余となるというわけです。

掛け算、割り算の途中式がビットごとの繰り上がり、繰り下がりがないと考えればよいです。
十進数では計算できません。
なので x^nと言う表記になっていると思います。

正解ではないかもしれませんが、多分あってます。
論理回路を設計するのに、桁上がり、桁下がりを使うと遅延が発生するためじゃないでしょうか？
推測ですが....

angel: ぬし; 会議室デビュー日: 2005/03/17; 投稿数: 711

投稿日時: 2005-08-20 07:04

おはようございます。
剰余計算については jkさんの流れの通りになります。

情報関係の数学で出て来る多項式 ( 数字×文字の n乗という項を足し合わせたもの ) は、係数が十進数ではなく、GF(2) となることが多いです。今回もそうですし、CRC の理論で使用するのも、GF(2) を係数とする多項式です。
※ GF(2) … GFとは有限体(ガロア・フィールド)、GF(p) は mod p を基準とした計算になる。
　つまり、GF(2) の要素は 0, 1 のみで、
　　足し算 … 0+0=0, 0+1=1+0=1, 1+1=0 ( 引き算は逆のため、0-1=1 ) … xor と同じ
　　掛け算 … 0*0=0*1=1*0=0, 1*1=1 … and と同じ

でもって、多項式の計算では、x の n乗の項同士での繰り上がり・繰り下がりは発生しません。これは中学生・高校生が習う多項式 ( 係数はフツーの実数 ) の計算と同様です。

各暗号のアルゴリズムについては、cryptographyというページで詳しくかつ親切に説明されています。
※ 数学的に言えば、DES や AES なんかよりも、RSA の方がかなり易しい理論だったりします。

以上、ご参考まで。

訂正：
jkさんというお名前をつけられたのですね。失礼ながら気付いておりませんでした。
文中のお名前を訂正いたしました。

[ メッセージ編集済み編集者: angel 編集日時 2005-08-20 14:58 ]

Kit: 会議室デビュー日: 2005/08/19; 投稿数: 12

投稿日時: 2005-08-20 14:34

＜jk様
はい、その理由よりそういう表記をしました。
また大変分かりやすい流れで記載されていましてすぐに理解できました。
このように丁寧記載していただきありがとうございます。ｐ（＾＿＾）ｑ
また分からない点がでましたら書き込みさせていただきますのでご教授宜しくお願いします。
（ｍ＿ｍ）

＜angel様
参考になるサイトを掲載していただきありがとうございます。
GFの定義などを知ることができ大変勉強になりました。

jk: ベテラン; 会議室デビュー日: 2005/08/19; 投稿数: 94

投稿日時: 2005-08-20 15:21

私は最近、日々ときめきがなかったのですが、Kit様の件に回答してるうちに
昔の好奇心がふつふつと沸いてきました。ありがとうございました。

一晩寝て、思ったのですが。
繰り上がり、繰り下がりがない理由はワイアスピードを実現するためではなく
情報の欠落を防ぐためではないかと、思いました。

隣の桁に干渉してしまうと、桁あふれなどを起して情報が欠落する危険があり
ますよね？これも推測なので実験してみないとわかりませんけど。

＞angel様
さすがですね。私は専門的に学習したことがないのでわからないことばかりです。
CRC32の時は当時は高校生でしたので式を見て解からないことは(逆汗した)ソースを
解析して、理解していました^^;今では信じられない情熱です。

今後も、度々この掲示板で書き込みをさせていただきます。的外れなことを
書き込むこともあろうかと思いますが、どうかよろしくお願いいたします。

angel: ぬし; 会議室デビュー日: 2005/03/17; 投稿数: 711

投稿日時: 2005-08-21 04:37

おはようございます。

引用:
繰り上がり、繰り下がりがない理由はワイアスピードを実現するためではなく情報の欠落を防ぐためではないかと、思いました。

繰り下がり・繰り上がりが無いのは、データをGF(2)上の多項式に見立てて「ビット列」として取り扱っているからだと思います。つまり、「2進整数」ではなく、個々の桁が独立した 0,1 のベクトルと見なすということです。

上でも一寸触れましたが、GF(2)の和・積は、排他的論理和・論理積と同じになりますので、コンピュータでの演算と親和性が高いのだと思います。
※ 純粋な理論だけで言えば、GF(2) で無くとも、GF(3) や GF(5) 等、任意の GF(p) で代用できる筈ですので…

ちょっと対応を挙げてみますと…、

　1.GF(2)上の加算 ( 減算 ) と乗算
　　→ 排他的論理和 ( xor ) と論理積 ( and )

　2.GF(2)を係数とする多項式 ( ≒ GF(2)のベクトル )
　　→ 係数(0,1)を並べたビット列

　3.多項式の加算 ( 減算 )
　　→ ビット列同士の xor

　4.多項式に x の n乗をかける ( ＝各項の指数をプラス n )
　　→ ビット列を n桁左シフト

　5.多項式同士の乗算 ( = 1,3,4 の組み合わせ )
　　→ and と xor と、左シフトの組み合わせ

　6.多項式同士の除算/剰余計算 ( 1,3,4 の組み合わせ )
　　→ and と xor と、左シフトの組み合わせ ( 右シフトも便利 )

とまぁピッタリ。GF(2)というのは、正にコンピュータのために産まれたかのような概念なのですよね。
さらに AES のアルゴリズムでは、これを応用して、8桁のビット列を GF(2の8乗) の要素に対応付ける手法を採っていますし。

群・環・体等の概念からなる「群論」は、栄光無き天才数学者ガロアの構築した理論ですが、当時あまりにも斬新過ぎて、数学界で価値を理解できる人がいなかったらしいです。
※今では、符号化・暗号・乱数等も含め、色々な所で無くてはならない重要な理論。

私も、どうすればこんな発想が出てくるのかサッパリでして… 奥の深い話だなと感じている次第です。

以上、ご参考まで。

補足：寧ろ、環や体は「群論」の中の概念ではなく、「ガロア理論」へと連なる一連の理論で出てくるものかな? という感じがします。ちょっと正確なところは分かりません…

[ メッセージ編集済み編集者: angel 編集日時 2005-08-21 12:58 ]

Kit: 会議室デビュー日: 2005/08/19; 投稿数: 12

投稿日時: 2005-10-09 02:06

皆様、お世話になります。

まず最初に以前ご質問させて頂いた際に私の質問にお答え頂いたjk様、angel様、AESのアルゴリズムを理解することができました。
ありがとうございます。

ところで質問なのですがAESには鍵長やブロック長に対する規格化された定められたパディング方式は存在するのでしょうか？ネットで色々と調べてみるとどうやらパディングは自由に決めることができるように解釈し、私自身の考えでは空白に０を埋めればよいと思っておりますが違っていましたらご指摘を御願いします。
またよろしければ参考になるサイトが、御座いましたら教えていただけないでしょうか？

またパディングとは
例えば128bitsを暗号化する際の平文が108bitsだった場合にその空白（20bits）に定められた方式で空白を埋めて
（平文108bits）+（定められた方式のパディングによる20bits）＝128bits
として暗号化をするというように理解しています。

angel: ぬし; 会議室デビュー日: 2005/03/17; 投稿数: 711

投稿日時: 2005-10-11 00:43

こんばんは。
本来、こういうお話は、「ソースを使え、ルーク!!」になるのでしょうが、私は OpenSSL のコードを読めるほど強力ではないので…、一寸した実験を行ったことがあります。

引用:

実験の再現コマンド
$ openssl enc -P -aes-128-ecb -pass pass:hoge \
> | sed -e 's/ //g' > param
$ . param
$ seq -f %02g 0 16 \
> | while read i; do
> head -c $i /dev/zero \
> | openssl enc -e -aes-128-ecb -K $key -iv $iv \
> | tee e$i \
> | od -vt x1 -A n > e$i.h
> done
$ seq -f %02g 0 15 \
> | while read i; do
> cat e$i e00 \
> | openssl enc -d -aes-128-ecb -K $key -iv $iv \
> | od -vt x1 -A n > p$i.h
> done

はい。aes 128bit ( 1ブロック 128bit = 16byte ) で、暗号化・復号を行った例です。
ファイルとしては、e00 ～ e16、e00.h ～ e16.h、p00.h ～ p15.h ができます。
※暗号化パスワードは“hoge”で一定ですが、鍵データは都度変わるため、できる e* ファイルの内容は変わります。

これにより、

　1. e00.h と e16.h ファイルを見比べるとあることが分かります。
　　※本当は、もう少しサンプルを集めた方が良いですが。

　2. 1.を押さえた上で、各 p00.h ～ p15.h のファイルを見比べると、パディングの規則が見える筈です。

全部解説するのも面白くないので、謎解きはお任せします。
※前提知識：暗号の ecbモード、シェルスクリプトの基礎知識 ( 各コマンドの動作含む )

それでは、お休みなさいませ。

[ メッセージ編集済み編集者: angel 編集日時 2005-10-11 00:43 ]

1|2 次のページへ»

＠IT SpecialPR

AESについて

スキルアップ／キャリアアップ（JOB@IT）