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{ c = m^e ~\%~ N }[/math]

復号

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