暗号を使おう！

付録４――PGP 5.0の高速鍵生成機能について
ジェフリー・シラー

この文書は、<33A98A97.3FCDE446@mit.edu> 1997年６月19日、 alt.security.pgp に投稿されたもの。

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

> 「高速鍵生成」オプションは、これについての情報を求めてヘルプ・ファイ
> ルを探し回らなかった人にとっては、PGP 5.0の無料版と商用版でのデフォ
> ルトの鍵生成法だ。それは、ペンティアム166で64MBメモリ上で4096ビット
> 鍵に１時間近くかかっていた鍵生成に必要な時間を、１、２分に短縮する。
> どうやるのかって？　それは、「前もって計算されていた素数」を使う。そ
> う、缶詰素数だ。もしPGPを弱める陰謀があるなら、これがそうだ。ユーザ
> ーが鍵生成のときにランダムに割り当てられてきた二つの素数を、PGPに固
> 定の数として入れておくわけだ。使用者は高速鍵生成に大喜びで、NSAは暗
> 号解読術の新発見能力に大喜びというわけだ。

これは、その作動法ではない。DSS鍵は４つの構成要素を持っている。

g -- 生成器（ジェネレーター）と呼ばれる。他の作業が行われる土台。
p -- 計算で使われる「例の」素数領域。512〜1024ビットである。
（1024ビットだからといって、本当は安全性を高めるわけではない）
q -- 計算を減らすために使われる160ビットの数。
（qはSHA-1ハッシュと同じ長さ）
x -- 秘密鍵。"x" は単に秘密の値。
y -- 公開鍵。これは g^x mod p。

したがって、あなたの公開鍵は g,p,q,yの合成である。秘密鍵は、g,p,q,xの合成である。

PGP 5.0は、Diffie-HellmanのElgamal変数を使う。それは、"q"値を除いて、DSSと同じパラメーター・セットを持っている。PGP 5.0鍵は実際には二つの完全に別々の鍵である。署名に使われるDSS鍵と、暗号に使われるElgamal鍵である。

PGPは最高4096ビットのElgamal素数をサポートしている。

鍵生成に時間がかかる部分は、（DSSとElgamalのために）巨大な素数 "p" を選ぶことである。しかし、これらが「おおっぴらな」値であって、多くの人々が同じ p,g（とDSSのためのq）を使ったとしても本当は重要ではない。

とはいえ、Diffie-Hellman アルゴリズムは「もろい」。Diffie-Hellman鍵（かDSS鍵）を攻撃するときには、素数を攻撃することになる。ログ表を計算して"y"値を手に入れ、そして"x"値を調べることははっきりしている（xは秘密鍵である）。また、弱い"p"値を特別に計算することも可能だ。だから、使っている"p"値が安全であると信用することが重要である。

1024以上の素数値のためのログ表を計算することは、現在、コンピューター的には手に負えない。

そこで、PGP 5.0が安全な素数フィールドを提供するためにやっていること。

初心者のための、PGP 5.0用作りつけの素数のすべては、少なくとも1536ビットの長さがある。つまり、もしDSS鍵のための1024ビットの値（おすすめ）を選んだとき、それはあなたのためにランダムに生成されているのと同じことだ。だから、もしだれかがコンピューター時間を大量にかけて、1024ビット素数のログ表を解くことができたとしても、それは一つの鍵の値しか得られないのである（これはRSAへの素因数分解攻撃に似ている）。

ランダムな2048ビット素数を生成するのにしばらくかかったとして（上記ほどは長くない）、PGPは組み込まれた値を持っている。組み込まれた値に「トラップ」が仕掛けられていないことを保証するため、それが作られる方法を文書化しよう。

ここに詳細をすべて検討するつもりはないが、ガンジーからの引用文が素数検索のためのランダムな開始点を作るハッシュ機能を通して実行されるというのが要点である。使われたガンジーの引用は、「あなたのすることはすべて取るに足りないが、それをすることは非常に重要だ！」

これが意味することは、1024ビットDSS素数と共有された（組み込まれた）2048ビットDH素数で、DSS/DH鍵をひじょうに妥当な時間で作ることができるということだ。

軽量化は、「もし仮に」だれかが、組み込まれた2048ビットDH素数の一覧表を計算できたならば、その素数を使っているすべての暗号化鍵を破ることができるだろう。しかし、2048ビット素数は、一覧表を計算するには「すごく」「すごく」「すごく」難しい素数なのだ。それは私の生きているあいだにはありそうにもない（あるいは、私の孫の世代でも、少なくとも数学的打開がない限りは）。

ただし、もしあなたが心配なら、あなた自信のDH素数を作ることをおすすめする。そのためには、fastkeygen オプションをチェックしなければそれでいい。

へっ、PGPにバックドアを作りたいなら、悪い素数を使うよりもずっといい方法があるだろうよ（素数がトラップされているかどうか、そんなバックドアが見つかるかどうか、調べてみたらいい）。

-Jeff

-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.0
Charset: noconv

iQA/AwUBM6mKcPAgc1f0FJUrEQLoCACgqObiYpKf486H6dQWDdNWSsIjPuEAoLKk
wlsGQZf0DT6Vk/ud21vTfY+8
=fPo/
-----END PGP SIGNATURE-----

（訳注：この署名は機能しません）

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

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