RSA暗号

RSA暗号は公開鍵暗号の一つで、大きい数の素因数分解が困難であることを安全性の根拠としている。

手法

メッセージ [math]\displaystyle{ m }[/math] を暗号化する。

鍵の生成

受信者が鍵を生成する。

1. 素数 [math]\displaystyle{ p,q }[/math] を用意する
2. 合成数 [math]\displaystyle{ N=pq }[/math] をつくる
3. [math]\displaystyle{ (p-1)(q-1) }[/math] と互いに素な整数 [math]\displaystyle{ e }[/math] をとる
4. [math]\displaystyle{ ed }[/math] を [math]\displaystyle{ (p-1)(q-1) }[/math]で割った余りが1になるように 整数 [math]\displaystyle{ d }[/math] をとる

このうち [math]\displaystyle{ e, N }[/math] を送信者に伝える。

暗号化

[math]\displaystyle{ c = m^e ~\%~ N }[/math]

復号

[math]\displaystyle{ m = c^d ~\%~ N }[/math]