RSA暗号

提供:ペチラボ書庫
2024年9月23日 (月) 15:52時点におけるPtt (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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]