暗号化・復号イメージ
BobからAliceへ暗号文を送る。
①Aliceが公開鍵(n,e)と秘密鍵(d)を生成
(n,e)(d) Alis ------------ Bob
②AliceからBobへ公開鍵(n,e)を送信
Alis (n,e) -----------> Bob
③Bobが公開鍵(n,e)で平文(m)を暗号文(c)に変換
Alis ------------ Bob (m) (n,e) -> (c)
④BobからAliceへ暗号文(c)を送信
Alis <------------ (c) Bob
⑤Aliceが暗号文(c)を秘密鍵(d)で復号して平文(m)を得る
(c) (e) -> (m) Alice ------------ Bob
アルゴリズム
流れをさらっと。
①公開鍵(n,e)生成
2つの素数乱数をそれぞれp1、p2とする。
n = p1 × p2
e = φ(n)と共通因数を持たない奇数
②秘密鍵(d)生成
任意の数をkとする。
φ(n)がnの素因数p1、p2から容易に得られる点がポイント。
φ(n) = ( p1 - 1 ) ( p2 - 1 )
d = ( k × φ(n) + 1 ) / e
③暗号化(m→c)
平文をm、暗号文をcとする。
c = m ^ e mod n
④復号(c→m)
m = c ^ d mod n
やってみる
適当な値を入れてやってみる。
①公開鍵(n,e)生成
p1 = 13
p2 = 17
n = 13 * 17 = 238
e = 11
②秘密鍵(d)生成
k = 2
φ(n) = ( 13 - 1 ) ( 17 - 1 ) = 192
d = ( 2 * 192 + 1 ) / 11 = 35
③暗号化(m→c)
m = 7
c = 7 ^ 11 mod 238 = 133
④復号(c→m)
m = 133 ^ 35 mod 238 = 7
暗号文(133)から秘密鍵(35)を利用して、平文(7)を得ることができた。
何が嬉しいのか
中間者が暗号文を解読するにはφ(n)を得る必要があるが、nの素因数分解は困難である。
(上記の例のn=238はあまりにも脆弱だが…)