公開鍵暗号でなりすましと改ざんを防御
ここまでの話だと，暗号化には公開鍵を使うのみで，秘密鍵で暗号化することはありません。秘密鍵は復号化専用，公開鍵は暗号化専用のように思えます。しかし，秘密鍵を暗号化に使うと，大変便利なことがあります。4つのセキュリティ・モデルのうち「なりすまし」と「改ざん」を防止できるというものです（図6）。現在ではこの副産物の方が重要視されています。
 |
図6●4つのセキュリティ・モデル
なりすましと改ざんの防止はどうするか。
[画像のクリックで拡大表示] |
AliceからBobに送る場合を考えます。AliceはBobに送ろうとするメッセージを自分の秘密鍵で暗号化して送ります（図7）。公開鍵を持つBobは受信した暗号を復号化できますが，盗聴者Eveも公開鍵を持っていますので，元のメッセージを解読できます。この使い方では情報の秘匿には何も役に立っていないようです。
 |
図7●公開鍵をなりすましと改ざん防止に使う
[画像のクリックで拡大表示] |
Eveは復号化したメッセージを改ざんしてBobに送り込もうとします。Bobは「Aliceから来るメッセージは，必ずAliceの公開鍵で復号化してから読む」ことにしておけば，Eveは暗号化されていない平文そのものをBobに送り込むことはできません。そこでAliceになりすまして暗号化したいと思うのですが，残念ながらEveはAliceの公開鍵で復号化できる暗号文を作り出せません。
メッセージの受信者Bobは，「Aliceの公開鍵でメッセージが復号化できたということは，そのメッセージを暗号化したのは秘密鍵を持っている唯一の人物Aliceに違いない」と確証が持てるのです。Alice本人が作成した文書であることが証明されることから，自分の秘密鍵で暗号化することを「電子署名」といいます。次号以降で詳しく解説しますが，実際には文書全体に署名するのではなく，平文から算出されたハッシュという数値に署名します。
このように公開鍵暗号を使うことで，情報の秘匿に加え，セキュリティ・モデルの「なりすまし」と「改ざん」の両方を一気に解決できるのです。
RSA暗号
デフィーとヘルマンのアイデアは画期的で素晴らしいものでしたが，実際に「秘密鍵から公開鍵を作るのは容易だが，その逆は困難である」という鍵をどうやって作るのかという問題がありました。
秘密鍵も公開鍵も一種の数値です。「ある数値を別の数値に変換する計算は簡単だけれど，その逆変換を計算するのは非常に時間がかかる」という関数を一方向関数といいます。2人は，この一方向関数を見付け出せなかったのです。
一方向関数に素因数分解が使えることを発見したのは，MITに所属する3人の科学者でした。その3人とはRivest，Shamir，Adlemanです。彼らの頭文字をとって，素因数分解を一方向関数に使った公開鍵暗号をRSA暗号といいます。
中学校で習ったと思いますが，素因数分解とは，以下のようなものです。
問題）72を素因数分解せよ
答）72=2×2×2×3×3
|
掛け算で2や3から72を算出するのは速くできます。逆に，72を素因数分解するのは時間がかかります。72くらいの数字なら難しい問題ではありませんが，もっと大きな数にあると，素因数分解が途端に難しくなるのです。
問題を解く最初のステップは，与えられた数を2つの数に因数分解することです。これ自体はさほど難しくありません。難しいのは，その因数が素数であるかどうかの判定です。
Nが素数であるかどうかを検査する方法として，√Nまでの素数で次々と割り算してみるというのがあります。しかし，「nより小さな素数は，およそ n/log（n）個ほど存在する」（素数の定理）ため，10進数で150けた程度あるNが素数かどうかを判定するには，10進数で70けた以上の個数の素数をラインナップして割り算をしなければなりません。現在のコンピュータでは，この計算が終了するまでに太陽が燃え尽きているということになります。
RSAの暗号アルゴリズムを図8にまとめます。このRSA暗号は幅広い分野に適用されており，メールを暗号化するPGPメールや，HTTPSやSSHで利用されるSSLにも利用されています。
 |
図8●RSAの暗号アルゴリズム
Pは平文，Cは暗号文を表す。 |
D-H鍵交換アルゴリズム
さて，R，S，Aの3人の力によって，デフィーとヘルマンが考えた秘密鍵と公開鍵のペアを実際に作り出すことができるようになりました。しかし，これを実際のネットワークで使うとなるとまだ問題がありました。
公開鍵暗号は数学的には非常に洗練されているのですが，計算に時間がかかるという問題があります。ネットワークを流れる個々のパケットを公開鍵で暗号化するには時間がかかります。
そのため，通信パケットのビットごとのXOR計算を基本とする「共用鍵（セッション鍵）暗号」を使い，その鍵交換に公開鍵暗号が利用されています。
Diffie-Hellman鍵交換アルゴリズム（略してD-H鍵交換アルゴリズム）を図9にまとめています。このアルゴリズムは「数は累乗するより対数（累乗の逆演算）を計算する方が難しい」という原理に基づいています。
 |
図9●Diffie-Hellman鍵交換アルゴリズム
[画像のクリックで拡大表示] |
このアルゴリズムは，企業の業務ネットワークをインターネットで構築するときに使われるIPSec（アイピーセック）ルーターで使われています。実際には図中のYやPの候補は，インターネット標準（RFC2409）であらかじめ定められており，どの候補で計算しましょうか，ということがルーター間で相談されます。そして得られた鍵で3DES暗号のような共有鍵暗号を使って安全な通信を開始するのです。具体的にはYは2といった整数値が使われますが，Pには1024ビット（10進数で155けた程度）の素数が使用されています。
