暗号化・復号イメージ

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はあまりにも脆弱だが…)