情報系の書籍では、公開鍵暗号ってよくみるが、いつも分かったような分からないような感覚があった。（結局わかってないんですよね）
笑わない数学でその辺の説明があったので、私なりに解釈してまとめてみる。
共通鍵暗号
暗号文書をやりとりするAさんとBさんが、暗号を解く鍵を共有している場合、その暗号を共通鍵暗号という。文字通り共通の鍵（暗号を解く物や方法）を持っているということである。
この共通鍵暗号には、次の欠点があり、公開鍵暗号が出現するに至った。
欠点１：暗号を解く物や方法が他者に漏れた場合、暗号の意味がなくなる
欠点２：基本的に１対１の暗号であるため、大人数になると暗号鍵の管理が大変になる。
また、１つの鍵を多数と共有すると他者に漏れるリスクが高くなる。
公開鍵暗号の概要
公開鍵暗号は、暗号鍵を守り抜くことはやめて、暗号鍵を公開してしまおうというものである。
「公開していいの？」と不思議におもうのだが・・・。それは、
暗号を元の情報に戻す方法を簡単にはわからない方法にしてしまえば、暗号鍵を公開しても問題がないらしい。
簡単にはわからない方法とは、以下の２つを使うそうである。
１．合同式
２．素因数分解の困難性
合同式
合同式とは、割る数を１つの数に固定して、割り算の余りが同じものを等しいとする式だそうだ。
例） 10 ÷ 209 = 0 … 10
219 ÷ 209 = 1 … 10
428 ÷ 209 = 2 … 10
これらを、
10 ≡ 219 ≡ 428 (mod 209)
と書く。
ディフィー・ヘルマン鍵共有（DH鍵共有）
公開鍵の１つであるDH鍵共有の説明をこころみる。
１．アリスとボブが通信を行う
２．アリスとボブは公開された情報pとgを得る
３．情報p, ｇと各々独自の秘密鍵（アリス：a, ボブ：b）を使って、各々の公開鍵（アリス：Ａ, ボブ：B）を作る
４．各々の公開鍵を送り合う
５．自分の秘密鍵と相手の公開鍵（アリス持ち：aとＢ, ボブ持ち：bとＡ）から、共通の鍵Ｋを作成し共有することができる
概要はこういうことだが、何のことかさっぱりわからない。
詳細を確認する。
①十分大きな素数ｐを生成し、「有限体 Fp」の原始元ｇ（生成元。1<g<pである）を１つ選択し、p, gは公開された情報とする。
※有限体とは、自然数の集合のようなもの？体とは四則演算が不自由なくできる集合体とおもう。元は集合体の要素。
簡単にするために素数は小さいものp=31としよう。原始元・・・ようわからんが、「有限体 Fp」要素数が有限個（p個）の体ということなので、普通に自然数31と考えて、ｇは素数がいいのかな？とりあえず素数として、g=17としてみよう。
②アリスは整数a(秘密鍵)をランダムに選び、gaをpで割ったあまりＡを計算し、公開鍵としてボブに送付する。つまり、Ａ ≡ ga (mod p)である。
とりあえず、a = 3としてみる。すると、ga = 173 = 4913になる。
なので、Ａ ≡ ga (mod p) = 4913(mod 31) = 15 [4913 ÷ 31 = 158 … 15]
③ボブは整数b(秘密鍵)をランダムに選び、gbをpで割ったあまりBを計算し、公開鍵としてアリスに送付する。つまり、B ≡ gb (mod p)である。
とりあえず、b = 5としてみる。すると、gb = 175 = 1419857になる。
なので、B ≡ gb (mod p) = 1419857(mod 31) = 26 [1419857 ÷ 31 = 45801 … 26]
④アリスは、ボブから受け取った公開鍵Ｂと自分の秘密鍵aを使い、Baをpで割ったあまりを計算する。
B = 26、a = 3なので、Ba = 263 = 17576。17576 ÷ 31 = 566 … 30である。
⑤ボブは、アリスから受け取った公開鍵Ａと自分の秘密鍵bを使い、Abをpで割ったあまりを計算する。
A = 15、b = 5なので、Ab = 155 = 759375。759375 ÷ 31 = 24495 … 30である。
ここで、Ba ≡ (gb)a ≡ gba ≡ gab ≡ (ga)b ≡ Ab (mod p)が成立するので、アリスとボブは④と⑤の計算結果が同じになり共通の鍵として、
K (≡ Ab ≡ Ba ≡ gab (mod p))
を共有できる。
Ba (mod p) = [Ba = 263 = 17576。17576 ÷ 31 = 566 … 30]
Ab (mod p) = [Ab = 155 = 759375。759375 ÷ 31 = 24495 … 30]
K = 30
十分大きな素数pを上手に選べば公開鍵Aから逆にga ≡ A(mod p)となる整数aを求めるには膨大な計算量を必要とする。
第三者は、秘密鍵（アリス：a, ボブ：b）を知らなければ、公開鍵（アリス：A, ボブ：B）だけを知ったとしても共通鍵 K (≡ Ab ≡ Ba ≡ gab (mod p))を求めることは困難である。
まとめ
割り算の余りを使う合同式を使うことによって、このような公開鍵暗号でもセキュリティ的に問題のない暗号が作れるということである。でも、結局は共通鍵なんですね。そして、この共通鍵を使ってメッセージを暗号化するということなんでしょう。
公開暗号鍵はこういう背景があったのですね。私が見てきた情報系書籍はここまで踏み込んだ説明がなかったので、分かったような分からないような感じがしていました。
さらに強固なRSA暗号というものもあるようですが、疲れたので今回はこれで終わりにします。
コメント