Public key cryptography

【Public key cryptography】公開鍵暗号

• 秘密鍵と公開鍵のペアを使う。

• 秘密鍵は復号に用いられ、鍵の所有者が管理する。

• 暗号化には公開鍵を使う。これは誰でも入手可能。よって公開鍵で暗号化された情報は秘密鍵の持ち主にしか復号することができない。

例）RSA

秘密鍵と公開鍵の生成

2つの素数pとqを選択する。ここでは
p = 23
q = 31
とする。

両方を乗算
n = p * q = 713
nは公開鍵の一部であり、秘密鍵の一部でもある。

p-1 と q-1 の最小公倍数sを計算
s = lcm(p-1, q-1) = lcm(22, 30) = 330

s と互いに素で、sよりも小さいeを選択する。eは公開鍵の一つとなる。
ここでは
e = 71とする

e*d ≡ 1 (mod s) となる正の整数dの値を求める。dは秘密鍵の一部。  
（つまり、e * d mod s の値が1になる整数dを求めるということ。）
71 * d ≡ 1 (mod 330)
d = 251 （71 * 251 = 17821. 17821 mod 330 = 1 となるので）

ここまで
公開鍵(e, n) = (71, 713)
秘密鍵(n, d) = (713, 251)
を計算してきた。

ここから暗号化と復号を行う。

送信者側（公開鍵のみをもつ）が、

暗号文C = M^emod n を計算する。

送信者が平文 M = 10を送信する際、
C=10⁷¹mod 713 = 19

受信者（秘密鍵をもつ）は、
元の平文M = C^dmod n を計算する。

M = 19²⁵¹mod 713 = 10