Make your own free website on Tripod.com
叛乱オンライン
HOME > Theory > Crypt

暗号を使おう!

 
The comp.security.pgp FAQ
Version 1.4
 

付録2――PGP内部の魔法

FAQのこの部分は、© by Boudewijn W.Ch. Visser.

Version 0.99.1 - コメント、修正などがあればメールをください。

  1. IDEA対称的ブロック暗号
    1. はじめに
    2. IDEAの機能法
    3. 鍵一覧
    4. IDEAのセキュリティ
    5. 鍵の長さ
    6. 弱い鍵
    7. 参考文献
  2. RSA公開鍵暗号法
    1. はじめに
    2. RSAは正確にはどう機能するか
    3. 十分な素数があるだろうか? だれかそれをすべてリストアップできるのではないか?
    4. デジタル署名
    5. セキュリティ
      1. 素因数分解
      2. タイミング攻撃
    6. 参考文献
  3. MD5メッセージ圧縮機能
    1. はじめに
    2. MD5内部の働き
    3. 参考文献
 

IDEA対称的ブロック暗号

はじめに

IDEAは、1991年、Xuejia LaiとJames Masseyによって発明されたブロック暗号である。ブロック暗号は、データをブロックで暗号化する暗号化アルゴリズムである。IDEAは64ビットのブロックサイズを有し、鍵の長さは128ビットである。IDEAは対称的アルゴリズムである。これは、同じ鍵が暗号化と復号化に使われるということである。最初のバージョンはPES(提案された暗号化アルゴリズム, Proposed Encryption Algorithm)であり、1990年に公表された。この版は、ある一定の攻撃、差別的暗号解読法に弱点を有していることが発見されたために、修正された。この修正版は最初、IPES(改善された提案された暗号基準, Improved Proposed Encryption Standard)と呼ばれ、それは現在IDEAと呼ばれる。これは「国際データ暗号化アルゴリズム(International Data Encryption Algorithm)」の頭文字である。

IDEAの機能法

IDEAは8ラウンドから成る。
64ビットのデータブロックは、4つの16ビットパーツに分けられ、X1,X2,X3,X4とラベルを付けられる。これらはIDEAに供給される。Add は追加モジュロ2~16、Mulは乗算モジュロ2^16+1のことである(そしてすべてゼロのサブブロックは、2^16を表わしているものとして扱われる)。そして、Xorはビット単位の排他的論理和(Exclusive Or)である。128ビット鍵から52の16ビットサブ鍵が生成され、それがラウンドで使用される。サブ鍵は Zx_y とラベルをつけられる。ここで y は鍵が使われるラウンドであり、x はラウンド内のサブ鍵の番号である。サブ鍵が引き出される方法についての詳しい説明は、概要図の下にある。

IDEAの1ラウンドは次のように見える。

そして、このラウンドがさらに7回続き、それからこのあとの出力変形。

鍵一覧

Z1_1,..Z6_1, Z1_2..Z6_2, ... Z1_9 Z4_9 はラウンドのためのサブ鍵である。これらは以下の方法で128ビットのマスターキーから生成される。

128ビット鍵は8つのサブブロックに仕切られて、それらは直接最初の8つのサブ鍵として使われる(Z1_1...Z1_6 Z2_1 Z2_2の鍵)。マスターキーはそれから循環的に左へ25の場所分回転して、再び8ブロックに分割され、それが次の8つのサブ鍵として使われる。この手続きは、52の鍵がすべて作られるまで繰り返される。

IDEAでの復号化もまったく同じように働くが、サブ鍵だけが違っている。復号化のためのサブ鍵は、暗号化されたサブ鍵から以下のように引き出される。

ラウンド 1  Z1_9^-1   -Z2_9   -Z3_9   Z4_9^-1   Z5_8   Z6_8
ラウンド 2  Z1_8^-1   -Z3_8   -Z2_8   Z4_8^-1   Z5_7   Z6_7
ラウンド 3  Z1_7^-1   -Z3_7   -Z2_7   Z4_7^-1   Z5_6   Z6_6 
... 
ラウンド 8  Z1_2^-1   -Z3_2   -Z2_2   Z4_2^-1   Z5_1   Z6_1
出  力    Z1_1^-1   -Z2_1   -Z3_1   Z4_1^-1

Zn_mは、暗号化に使われたのと同じ鍵を示す。^-1は、逆乗算(モジュロ2^16+1)であり、-は単にサブ鍵のマイナスを示す。

IDEAのセキュリティ

一般に、暗号化アルゴリズムのセキュリティについて、はっきりした宣言をするのはひじょうに難しい。一回きりのパッドを別として、どんなアルゴリズムもそのセキュリティを数学的に証明する公式を持たない。必要(だが十分ではない)条件はいくつか知られており、IDEAはこれらの条件をすべて満たしている。それに加えて、破られることなく攻撃に耐えるアルゴリズムが長くなるに連れて、それは信頼度が高くなる。IDEAは現在(1996年)、暗号化のための挑戦対象となって6年目である。

鍵の長さ

データを暗号化するために使われた鍵の長さは、アルゴリズムのセキュリティの上限を設定する。原則として、可能な鍵をすべて試して、データを正確に復号化するものを発見することも可能である。これは「総当たり攻撃」と呼ばれる。可能な鍵の数は、これが不可能なくらい十分に大きい。IDEAにとって、2~128鍵が存在し、これは約3x10^38である。1秒間に10億回(10^9/s)試みることのできるコンピューターがあったとして(これは実在するスーパーコンピューターの能力を超える)、一つのIDEA鍵を発見するのにどのくらいかかるだろうか?

1年間には、60x60x24x365 = 3.15x10^7秒ある。

この仮想コンピューターで10^38鍵から一つの鍵を発見するには、3x10^38/(10^9 x 3x10^7) = 10^22年かかる。

地球上の人全員がこのコンピューターを持っていたら、それは 10^22 / 5x10^9 = 2x10^12年「しか」かからない。これは地球の寿命(4.5x10^9年)の数百倍である。このため、IDEAは総当たり攻撃からはまったく安全だと結論づけることができる。

弱い鍵

ある鍵はIDEAで使われるときに弱い。それは選択式平文攻撃によって、わずかな努力で検出できる。これらの弱い鍵の数は大きいが、それらの鍵の一つを偶然選ぶ確率は非常にちいさく、2^96分の1である。それは、IDEAの鍵一覧に小さな変化を起こすことで防止できる。これらの鍵を選ぶ確率は非常に小さいし、そのような鍵を検出するのに選択式平文復号化をとる可能性も小さいので、この弱い鍵のリスクは無視してもよい。私は、IDEAの強さと弱さについて知られていることを、完全を期して述べた。

参考文献:

  • Bruce Schneier, Applied Cryptography 2nd edition John Wiley & Sons
  • Chapter three of Xuejia Lai's Ph.D. thesis, describing IDEA. インターネット上では、ポストスクリプト・ファイルがある。
  • IDEAの弱い鍵(Weak keys for IDEA), paper by Joan Daemen, René Govaerts and Joos Vandewalle. インターネット上ではポストスクリプト・ファイルがある。
 

RSA公開鍵暗号

はじめに

RSAは非常によく知られた公開鍵暗号法アルゴリズムのひとつである。公開鍵暗号法の概念は、なじみ深い対称的暗号法とは少し違う。対称的暗号法では、メッセージの暗号化と復号化に同じ鍵が使われる。これは、暗号化通信のためには鍵を安全な方法で渡しておかなければならないということになる。これは、事前に何かのパーティーで自分で渡すか、だれかに運んでもらうか、何かそういう方法でやらなければならない。鍵を伝えるのには大きな問題があるような状況は多くあることが明らかだ。

公開鍵暗号法だと、状況全体が違ってくる。ここでは二つの鍵があり、一つは公開鍵で、もう一つは私的または秘密鍵である。公開鍵はメッセージを暗号化するのに使われるが、メッセージが一度公開鍵で暗号化されると、それは秘密鍵でのみ復号化できる。

こうして、秘密である必要がないので、公開鍵はどんな方法でも送ることができる。秘密が守られなければならないのは秘密鍵だけだが、それは簡単だ。誰にも送られる必要がないためである。

公開鍵暗号法は1976年、Whitfield Diffie とMartin Hellmanによって、そして独自にRalph Merkleによって発明された。どの公開鍵アルゴリズムの基礎も、簡単に計算できる数学的機能であるが、特別な知識なしにはその逆転は極めて難しい。RSA公開鍵アルゴリズムは1978年、Rivest, Shamir, Adlemanによって発明され、そのイニシャルをとって名称としている。RSAは、巨大な数字を素数に素因数分解するのが難しいということに依拠している。素数とは、1とそれ自身でしか割れない数字であることを思い出そう。ある数が素数でなく、合成数なら、それは簡単に素因数分解できるかもしれない。たとえば、55=5x11。しかし、素因数分解される数が55ではなく、数百桁の長さであれば、これは非常に難しい問題なのである。

RSAは正確にはどう機能するか

最初に、二つの素数 p と q を取る。それを掛け合わせてできた数字を n とする。n = p x q。次に、3以上の数から、(p-1)(q-1)と互いに素である数字 e を見つける。つまり、e と(p-1)(q-1)は共通の素因数を持たないということである。たとえば、15と32は互いに素である。それから、私たちは d x e = 1 mod (p-1)(q-1) [(p-1)(q-1)で割ってあまりが1]となるような数 d を見つける。メッセージMを数として、以下のようにする。

C = M^e mod n.

Cは暗号化メッセージである。

メッセージをデコードするには、以下の計算をする。

M = C^d mod n.

例:

p=5, q =11, n=55, (p-1)(q-1) = 40. e は 3 と 40 の間の数で、40との共通因数を持たない。そこで、 e = 7 .を選ぶ。 de = 1 mod (p-1)(q-1). d = 23, なぜならば 23*7 = 161 = 1 mod 40

暗号化: M = 2 => C = 2^7 mod 55 = 18

復号化: M = C^d = 18 ^ 23 mod 55 = 18 ^1 * 18^2 * 18^4* 18^16 mod 55

それぞれの数にモジュロ操作をすれば

= 18 * 49 * 36 * 26 mod 55 = 2

公開鍵は数 (e, n)から成り、秘密鍵は (d, n)から成る。

p と qが与えられれば d は簡単に計算できるが、 pとqを知らなければdは見つけられないというところに計略がある。

(モジュール式のべき乗、モジュール式の逆など)扱われるべきさまざまな操作は、ひじょうに効率的になされる。

十分な素数があるだろうか? だれかそれをすべてリストアップできるのではないか?

大きな素数を見つけるのは、大きな問題ではないし、PGPを使いたい人だれもが十分に使える素数が存在している。ユークリッドはすでに(紀元前300年ごろ)、素数の数は無限であることを証明しているが、数が大きくなるにつれて素数は不足して手に入らないのではないかと心配する人もいる。まあ、数が大きくなれば素数はだんだんまばらになっていくが、その減り方はひじょうにゆっくりしたものだ。誰かが 2^256 以下、あるいは2^512以下の全素数をリストし、512ビット(2-256ビットの素数)モジュール、あるいは1024モジュールでもいいが、PGP鍵をたやすく素因数分解できるかどうか、ということも時々聞かれる。256ビットの素数がどれほどあるかを知れば、こんな仮定はばかげている。

素数原理は、数 N 以下の素数がN/InNのオーダーで存在すると述べる。N が 2^256であれば、2^256 (1.1*10^77)以下の素数は6.5*10^74あることになる。2^256と2^255の間の素数の数を知るには、2^255以下の素数の数を引けばいい。2^255以下の素数は約3.2*10^74個ある。それゆえ、正確に256ビットの素数は、3.3*10^74個あるわけだ。宇宙の粒子の数はおよそ10^80個というから、素数を調べ上げるとか、素数すべてをリストするとかいうのは、512ビット鍵のためであっても完全に問題外だというのは明らかだ。

そういう素数を探すことはそんなに難しいことではない。そうでなければ、PGPを使うのは不可能だろう! そのような素数を見つけるには、私たちは適切なサイズの乱数を生成し、それが素数かどうか調べる。それが素数でなければ、うまく見つけるまで続ける。ある数字が素数かどうかを調べることのできる超高速アルゴリズムなら、ほんとうに早い。最も早いものは確率論だ。つまり、絶対に素数を合成数であると宣言することはないが、合成数を素数であると述べる確率はある。しかし、もし同じ数字を何度も何度も違った基本数に対して調べるなら、合成数がテストで発見されないという確率は極めて小さくなる。正確な素数テスト(ある数が素数かどうか証明する)も存在するが、それは大変な作業だ。PGPは最初に最高8191までのすべての素数で試験を行い、それから2, 3, 5, 7 をもとにフェルマーテストを使う。

デジタル署名

RSAアルゴリズムのすばらしいことの一つとして、メッセージに署名するために使えるということがある。デジタル署名によって、送り手はそれが本人によって紛れもなく送られたものだと証明する。RSAでこれを行なうには、送り手は単に秘密鍵の指数 d で暗号化すればいい。受け手はメッセージを公開鍵の指数 e で解読する。受け手(とメッセージを受けた他のすべての人)は、秘密鍵の唯一の持ち主がこの署名を作ったと知る。あなたに示された何にでもRSA署名をするのは少々危険だ。攻撃者はあなたに、それに署名されたときには別のメッセージを解読することになるメッセージを示したり、あるいは別の文書に署名させたりするかもしれない。kじょれは、文書そのものに署名しないか、さもなくば一方通行のハッシュか、メッセージ圧縮によって防ぐことができる。これがPGPのやっていることである。PGPによるメッセージ署名には何の危険もない。署名の特別なセキュリティのための追加として、一方方向のハッシュか文書のメッセージ圧縮と、文書それ自体に署名しないことで、ずいぶん早くもなっている。

セキュリティ

まだ知られていないこと:RSA(その他の多くの公開鍵暗号法)についてまだ明瞭でないことがいくつかある。

RSAを破ることは n を因数分解するくらい難しい、ということは証明されていない。それゆえ、巨大な数を素因数分解する必要のないRSAの解読法があるかもしれないのだ。第二に、因数分解そのものも、本当に難しい問題であることが証明されてはいない。私がここで「難しい問題」というのは、数学的な意味である。問題を解くために必要な時間が入力の線形関数、あるいは多項式関数として成長するのであれば、問題は扱いやすいと考えられる。例えば、n のオブジェクトを数えることは、基本的に、n回の作業ということになる。しかし、指数関数は急速に増大するので、問題が手に扱えないと考えるより、入力の数の指数関数(2^nのように、あるいは10^nだともっとひどい)として仕事量が上昇がするということである。

素因数分解
現在、130桁の長さ、つまり約430ビットの整数を素因数分解することは可能である。特別な形態の数字は素因数分解しやすい。ここでは約155桁、2^512+1というような数字が素因数分解できる。
PGPの場合、私たちは整数を扱う。大きな努力があれば、512ビット鍵は現在素因数分解できるかもしれないと信じられている。「大きな努力」とは、数千のワークステーションで何ヶ月もというオーダーで考えてほしい。
よく聞かれる質問の一つとして、「私の鍵はどれくらいの長さであるべきか」とか、「<n>ビット鍵を破るにはどれくらいかかるのか」というものがある。あいにく、現在まで、現在までに素因数分解されたよりもはるかに大きい数を素因数分解するのに必要な時間について正確な予測をすることはひじょうに困難だ。そして、遠い将来における予言として、私たちはコンピューター能力の進歩も考慮する必要がある。

数で示すことを望む人のために、整数フィールドのふるいのための(正確であると証明されてはいないが)発見するためのランタイム公式を示そう。 exp[(1.932+o(1))*(log n)^1/3* loglog(n)^(2/3)]

log は自然対数であり、exp(x) = e^x = 2.718..^x である。

Andrew Odlyzko の「整数因数分解および離散的対数での発展」という(1995年2月現在)未発行の論文から参照されている、「適用された暗号法(Applied Crypotograpy)」からの表を示す。

Mips年は、GNFSで数を素因数分解するのに必要な年数である。

ビット Mips年
512 30,000
768 2*10^8
1024 3*10^11
1280 1*10^14
1536 3*10^16
2048 3*10^20

別の表では、コンピューター能力の増大について寛大な仮定をし、素因数分解アルゴリズムが高速な特別数フィールドふるい(現在は特別な数だけに使われている)と同じくらい早いと仮定したもので、Bruce Schneierはさまざまな相手に対して以下の鍵の長さを示している。

対個人 対企業 対政府
1995 768 1280 1536
2000 1024 1280 1536
2005 1280 1536 2048
2010 1280 1536 2048
2015 1536 2048 2048

これらの数字に対しては数多くの仮定があることに注意。素因数分解の専門家のほとんどは、あえて数年間予言していないのである。

また、特に政府については、あなたの鍵を素因数分解するために数十億ドルを費やして何年もかけるのとは別の、あなたの鍵を手に入れる方法があることを心にとめておくこと。夜盗や電子的捜索(テンペスト)のほうがずっと効果的だし、はるかに安いのだ。

タイミング攻撃
最近、Paul Kocher は、ほとんどのRSA実行ソフトに対する攻撃法を発見した。この攻撃では、復号化のプロセスに必要な時間が非常に正確に測定できるならば、秘密の指数を推論することができる。ペンティアム・コンピューターについては、マイクロ秒レベルで話している。

この攻撃は、PGPにとってたいしたことはない。あなたのCPUがメッセージを処理する時間をこれほどの制度で測定することができる人ならだれでも、メモリーから鍵をコピーできてしまうだろうからだ。この攻撃も、あなたのパスフレーズと秘密鍵をのぞき見するように設計されたウィルスやトロイの木馬ほど危険ではない。

参考文献

以下は、ほとんどがポストスクリプトのオンライン論文の参照である。いくつかはひじょうに技術的なものだ。使われているアルゴリズムについてもっとよく知りたい人は、紙の本と論文紀要を参照する必要がある。

素因数分解と二つの主要なアルゴリズムについてのさらなる情報は非常に多くある。

 

MD5メッセージ圧縮機能

はじめに

MD5は、PGPに採用された一方方向のハッシュ機能である。これは Ronald Rivest によって設計された。一方方向ハッシュ機能は、任意の長さのメッセージに作用して、固定された長さの値を返す機能である。したがって、h = H(M)、H が一方方向ハッシュ機能であり、M がメッセージ、h がメッセージ M のためのハッシュされた値である。

ファイルのなかのすべてのバイトを加算し、それから n 桁で終わるように切りつめた簡単なチェックサム、すなわちCRC(周期的冗長チェック Cyclical Redundancy Check)はハッシュの例だが、それは一方向ではない。一方向であるためには、その機能は以下の特性も持っていなければならない。

  1. 与えられた M は、h を計算しやすくなければならない。
  2. 与えられた h は、h=H(M)となる M を計算するのが困難でなければならない。
  3. 与えられた M は、H(M) = H(M')となる M' を計算するのが困難でなければならない。
ハッシュ機能は、文書の指紋を作るために使われる。最初のものと同じハッシュ値を持つ別の文書を発見することが可能なら、これは詐欺に使える。

いくつかのアプリケーションでは、上記で定義されたような一方向性が十分ではない。ハッシュ機能は衝突にも抵抗力がなければならない。つまり、二つのランダムな M と M' が同じハッシュ値を持つことがほとんどないようにしなければならない。

すべての要求を満たすために、ハッシュ値は一定の長さを持たなければならない。ハッシュ機能の出力より長い文書を手にした瞬間、衝突が起こったに違いないと明らかになる。これは、ハト穴(pigeon-hole)原則と呼ばれる。ハッシュ機能が違う値を4つ出力できるときに、5つの文書をハッシュするなら、少なくとも二つの文書が同じハッシュ値を持つということになる。

関連した問題が「誕生日攻撃」で提示される。この方法は、23人の人が部屋にいるとき、そのうち2人が同じ誕生日を持つ確率が50パーセントあるという、あまり知られていない事実にもとづいてそう呼ばれる。

これは、以下の計算による。

二人の人が同じ誕生日ではない確率は、364/365。3人の人が同じ誕生日ではない確率は、364/365 * 363/365。

こうやっていくと、366人の人のなかで少なくとも二人が同じ誕生日であるというところまでいける。しかし、364/365 * 363/365 * ... * 343/365 ~= 0.5 であるから、ここですでに50対50の確率で同じ誕生日の人がいないという数値が出てくる。これはまた、50対50の確率で、同じ誕生日の人がいるということである。

これと同じことがハッシュでもいえる。もしハッシュ機能が n ビットの長さを持っていれば、2^0.5*n のハッシュされたランダムな文書を試すことで、同じハッシュ値を持つ二つのメッセージを見つける確率があるということだ。

MD5内部の働き

MD5の動きを見よう。メッセージは512ビットのブロックで処理される。メッセージは最初に、512ビットの倍数に64ビットだけ足りないようにするため、詰め物をされる。詰め物は、1というビットが1つ、メッセージの最後に付け加えられ、必要なだけの0のビットが付け加えられる。それから、元々のメッセージの長さ(詰め物以前)が、64ビットの数字として付け加えられる。こうして、メッセージは正確に512ビットの倍数となる。ブロックは、16個の32ビット量として処理される。

最初に、4つの変数が初期設定される。

A=0x01234567
B=0x89abcdef 
C=0xfedcab98 
D=0x76543210

これらの4つの変数は、変数a, b, c, d にコピーされて、メイン・ループが始まる。このループは、メッセージ・ブロックがある限り実行される。

最終のMD5ハッシュは、 最後のメッセージ・ブロックが処理されたあとでは、A, B, C, D となる。

ラウンドでは、4つの非線形関数がある。

F(X, Y, Z) = (X And Y) Or ( (Not X) And Z)
G(X, Y, Z) = (X And Z) Or ( Y And (Not Z))
H(X, Y, Z) = X Xor Y Xor Z
I(X, Y, Z) = Y Xor (X Or (Not Z))

1つのラウンドはこのように見える。

これを以下のように書くならば、

FF(a,b,c,d,M_j,s,t_i) denotes a = b+((a+F(b,c,d) + M_j + t_i <<<s)
GG(a,b,c,d,M_j,s,t_i) denotes a = b+((a+G(b,c,d) + M_j + t_i <<<s)
HH(a,b,c,d,M_j,s,t_i) denotes a = b+((a+H(b,c,d) + M_j + t_i <<<s)
II(a,b,c,d,M_j,s,t_i) denotes a = b+((a+I(b,c,d) + M_j + t_i <<<s)

(<<<s は、ビットを s だけ左にずらすこと)

  /* Round 1 */
  FF (a, b, c, d, M_0,  7, 0xd76aa478); /* 1 */
  FF (d, a, b, c, M_1, 12, 0xe8c7b756); /* 2 */
  FF (c, d, a, b, M_2, 17, 0x242070db); /* 3 */
  FF (b, c, d, a, M_3, 22, 0xc1bdceee); /* 4 */
  FF (a, b, c, d, M_4,  7, 0xf57c0faf); /* 5 */
  FF (d, a, b, c, M_5, 12, 0x4787c62a); /* 6 */
  FF (c, d, a, b, M_6, 17, 0xa8304613); /* 7 */
  FF (b, c, d, a, M_7, 22, 0xfd469501); /* 8 */
  FF (a, b, c, d, M_8,  7, 0x698098d8); /* 9 */
  FF (d, a, b, c, M_9, 12, 0x8b44f7af); /* 10 */
  FF (c, d, a, b, M_10,17, 0xffff5bb1); /* 11 */
  FF (b, c, d, a, M_11,22, 0x895cd7be); /* 12 */
  FF (a, b, c, d, M_12, 7, 0x6b901122); /* 13 */
  FF (d, a, b, c, M_13,12, 0xfd987193); /* 14 */
  FF (c, d, a, b, M_14,17, 0xa679438e); /* 15 */
  FF (b, c, d, a, M_15,22, 0x49b40821); /* 16 */

 /* Round 2 */
  GG (a, b, c, d, M_1,  5, 0xf61e2562); /* 17 */
  GG (d, a, b, c, M_6,  9, 0xc040b340); /* 18 */
  GG (c, d, a, b, M_11,14, 0x265e5a51); /* 19 */
  GG (b, c, d, a, M_0, 20, 0xe9b6c7aa); /* 20 */
  GG (a, b, c, d, M_5,  5, 0xd62f105d); /* 21 */
  GG (d, a, b, c, M_10, 9,  0x2441453); /* 22 */
  GG (c, d, a, b, M_15,14, 0xd8a1e681); /* 23 */
  GG (b, c, d, a, M_4, 20, 0xe7d3fbc8); /* 24 */
  GG (a, b, c, d, M_9,  5, 0x21e1cde6); /* 25 */
  GG (d, a, b, c, M_14, 9, 0xc33707d6); /* 26 */
  GG (c, d, a, b, M_3, 14, 0xf4d50d87); /* 27 */
  GG (b, c, d, a, M_8, 20, 0x455a14ed); /* 28 */
  GG (a, b, c, d, M_13, 5, 0xa9e3e905); /* 29 */
  GG (d, a, b, c, M_2,  9, 0xfcefa3f8); /* 30 */
  GG (c, d, a, b, M_7, 14, 0x676f02d9); /* 31 */
  GG (b, c, d, a, M_12,20, 0x8d2a4c8a); /* 32 */

  /* Round 3 */
  HH (a, b, c, d, M_5,  4, 0xfffa3942); /* 33 */
  HH (d, a, b, c, M_8, 11, 0x8771f681); /* 34 */
  HH (c, d, a, b, M_11,16, 0x6d9d6122); /* 35 */
  HH (b, c, d, a, M_14,23, 0xfde5380c); /* 36 */
  HH (a, b, c, d, M_1,  4, 0xa4beea44); /* 37 */
  HH (d, a, b, c, M_4, 11, 0x4bdecfa9); /* 38 */
  HH (c, d, a, b, M_7, 16, 0xf6bb4b60); /* 39 */
  HH (b, c, d, a, M_10,23, 0xbebfbc70); /* 40 */
  HH (a, b, c, d, M_13, 4, 0x289b7ec6); /* 41 */
  HH (d, a, b, c, M_0, 11, 0xeaa127fa); /* 42 */
  HH (c, d, a, b, M_3, 16, 0xd4ef3085); /* 43 */
  HH (b, c, d, a, M_6, 23,  0x4881d05); /* 44 */
  HH (a, b, c, d, M_9,  4, 0xd9d4d039); /* 45 */
  HH (d, a, b, c, M_12,11, 0xe6db99e5); /* 46 */
  HH (c, d, a, b, M_15,16, 0x1fa27cf8); /* 47 */
  HH (b, c, d, a, M_2, 23, 0xc4ac5665); /* 48 */

  /* Round 4 */
  II (a, b, c, d, M_0,  6, 0xf4292244); /* 49 */
  II (d, a, b, c, M_7, 10, 0x432aff97); /* 50 */
  II (c, d, a, b, M_14,15, 0xab9423a7); /* 51 */
  II (b, c, d, a, M_5, 21, 0xfc93a039); /* 52 */
  II (a, b, c, d, M_12, 6, 0x655b59c3); /* 53 */
  II (d, a, b, c, M_3, 10, 0x8f0ccc92); /* 54 */
  II (c, d, a, b, M_10,15, 0xffeff47d); /* 55 */
  II (b, c, d, a, M_1, 21, 0x85845dd1); /* 56 */
  II (a, b, c, d, M_8,  6, 0x6fa87e4f); /* 57 */
  II (d, a, b, c, M_15,10, 0xfe2ce6e0); /* 58 */
  II (c, d, a, b, M_6, 15, 0xa3014314); /* 59 */
  II (b, c, d, a, M_13,21, 0x4e0811a1); /* 60 */
  II (a, b, c, d, M_4,  6, 0xf7537e82); /* 61 */
  II (d, a, b, c, M_11,10, 0xbd3af235); /* 62 */
  II (c, d, a, b, M_2, 15, 0x2ad7d2bb); /* 63 */
  II (b, c, d, a, M_9, 21, 0xeb86d391); /* 64 */

定数 t_i は、2^32* abs(sin(i))の整数部分であり、iはラジアンである。

最後に、メッセージの最後のブロックが処理されると、数 a, b, c, d は、処理されたファイルのためのMD5ハッシュを形成する。

混乱しましたか? ま、少なくともメッセージのビットがあって、それがすべてだということだ。

参考文献

  • MD5実行の参照は、ここにあるかもしれない。RFC 1321.
  • Applied Cryptography 2nd edition, by Bruce Schneier
 
[ PGP-FAQ目次]
[ 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11]
[ 追補 ]
[ このFAQについて | 用語集 | 著作権]
 

HOME > Theory > Crypt

2000年盗聴法対抗
ダウンロードPGP6.5.1iPGP disk
日本語化PGP鍵作成
PGPdiskマウント秘密鍵を隠す
落とし穴
完全抹消法

PGP ユーザーズ・マニュアル 第1巻
The comp.security.pgp FAQ 日本語版
パスフレーズFAQ 日本語版
バックドア NSAPhrack Magazineソースコード
暗号関係リンク集

叛乱オンライン