RSA暗号の仕組みと安全性・具体例
RSA暗号とは,公開鍵暗号方式の具体的なアルゴリズムです。RSA暗号の仕組みと安全性について解説します。
前提知識(公開鍵・共通鍵暗号,整数の性質)
前提知識(公開鍵・共通鍵暗号,整数の性質)
以下の2つの知識があると読みやすいです。
-
公開鍵暗号方式についてなんとなくでも知っていると読みやすいです。→共通鍵暗号と公開鍵暗号の仕組み
-
「 と を で割った余りが等しい」とき, と書きます。→合同式の基礎
RSA暗号の仕組み・アルゴリズム
RSA暗号の仕組み・アルゴリズム
1.メッセージを受け取る側の準備
- 大きな素数 を生成し, とする
- と互いに素な整数 を取ってくる
- なる を取ってくる(→補足1)
- と を公開する(公開鍵), は公開しない(秘密鍵)
2.メッセージを送る側の暗号化方法
- 送りたいメッセージを とする。ただし, は 未満の正の整数とする
- 公開鍵を用いて を で割った余りを計算し,これを暗号文( とおく)とする
3.メッセージを受け取る側の復号方法
- 暗号文 と秘密鍵 を用いて を で割った余りを計算すると,実はこれがもとのメッセージに一致する(→補足2)!
4.安全性
- 暗号文 と公開鍵 が分かっても(現実的な時間では) を復元することはできない(と信じられている)
補足1:公開鍵・秘密鍵の準備について
補足1:公開鍵・秘密鍵の準備について
以下の「有名な定理」により のもとで は一意に定まります。
と が互いに素なとき なる が の間ではただ一つ存在する。
証明は,例えば背理法の意味といろいろな例とよくある間違いの例題2から分かります。
また, の計算は高速にできることが知られています。
補足2:復号化がうまくいく理由
補足2:復号化がうまくいく理由
- 暗号化:
- 復号化:
でうまく復号できていることを証明します。証明にはフェルマーの小定理を使います。数学がまあまあ得意な高校生なら理解できるレベルの内容です。
を証明すればよい。
なので, を証明すれば十分(対称性より も同様)。
が の倍数のときは両辺ともに の倍数よりOK。
が の倍数でないとき, が の倍数となるように設定したので,整数 を用いて とおける。よって,
ただし,途中の は であり,フェルマーの小定理を用いた。
RSA暗号の安全性と素因数分解
RSA暗号の安全性と素因数分解
素因数分解が簡単に(短時間で)計算できればRSA暗号は破られます。
暗号文 ,公開鍵 は誰でも見ることができる。
ここで を素因数分解することで が求まる。すると「メッセージを受け取る側の準備」と同じ方法で秘密鍵 が求まり,もとのメッセージ を復号できる。
幸い,大きな数の素因数分解の計算は難しいです。→素因数分解の難しさと素数判定
RSA暗号の計算例
RSA暗号の計算例
実際にRSA暗号の計算例を見ることで,理解を深めましょう。
公開鍵・秘密鍵の準備
- 素数として とします。 です。これくらいの数であれば素因数分解は簡単ですが,あくまで計算例ということで。
- と互いに素な数として, を選ぶことにしましょう。
- 有名な定理により, の解 は と一意に定まります。
- 公開鍵として を公開し,秘密鍵として を秘密にしておきます。
暗号化の処理
メッセージを送る側は, という数を送りたくなったとします。 を法として, です。 として,これを送ります。
復号化の処理
を法として, です。これで,無事に解読できました!
厳密には( などに)もっといろいろ条件があります。興味を持った方は暗号の本を読んでみてください!