RSA暗号の仕組みと安全性・具体例

RSA暗号とは,公開鍵暗号方式の具体的なアルゴリズムです。RSA暗号の仕組みと安全性について解説します。

RSA暗号の仕組み

前提知識(公開鍵・共通鍵暗号,整数の性質)

以下の2つの知識があると読みやすいです。

RSA暗号の仕組み・アルゴリズム

RSA暗号の仕組み

1.メッセージを受け取る側の準備

  • 大きな素数 p,qp,q を生成し,n=pqn=pq とする
  • (p1)(q1)(p-1)(q-1) と互いに素な整数 k1k_1 を取ってくる
  • k1k21(mod(p1)(q1))k_1k_2\equiv 1\pmod{(p-1)(q-1)} なる k2k_2 を取ってくる(→補足1)
  • nnk1k_1 を公開する(公開鍵),k2k_2 は公開しない(秘密鍵)

2.メッセージを送る側の暗号化方法

  • 送りたいメッセージを mm とする。ただし,mmnn 未満の正の整数とする
  • 公開鍵を用いてmk1m^{k_1}nn で割った余りを計算し,これを暗号文(CC とおく)とする

3.メッセージを受け取る側の復号方法

  • 暗号文 CC と秘密鍵 k2k_2 を用いてCk2C^{k_2}nn で割った余りを計算すると,実はこれがもとのメッセージに一致する(→補足2)!

4.安全性

  • 暗号文 CC と公開鍵 n,k1n,k_1 が分かっても(現実的な時間では)mm を復元することはできない(と信じられている)

補足1:公開鍵・秘密鍵の準備について

以下の「有名な定理」により 0k2(p1)(q1)0\leq k_2\leq (p-1)(q-1) のもとで k2k_2 は一意に定まります。

有名な定理

aabb が互いに素なとき ax1(modb)ax\equiv 1\pmod{b} なる xx1xb11\leq x\leq b-1 の間ではただ一つ存在する。

証明は,例えば背理法の意味といろいろな例とよくある間違いの例題2から分かります。

また,k1,k2k_1,k_2 の計算は高速にできることが知られています。

補足2:復号化がうまくいく理由

  • 暗号化: mk1modnm^{k_1}\bmod{n}
  • 復号化: Ck2modnC^{k_2}\bmod{n}

でうまく復号できていることを証明します。証明にはフェルマーの小定理を使います。数学がまあまあ得意な高校生なら理解できるレベルの内容です。

証明

mk1k2m(modn)m^{k_1k_2}\equiv m\pmod{n} を証明すればよい。

n=pqn=pq なので,mk1k2m(modp)m^{k_1k_2}\equiv m\pmod{p} を証明すれば十分(対称性より modq\mathrm{mod}\:q も同様)。

mmpp の倍数のときは両辺ともに pp の倍数よりOK。

mmpp の倍数でないとき,k1k21k_1k_2-1(p1)(p-1) の倍数となるように設定したので,整数 NN を用いて k1k2=1+(p1)Nk_1k_2=1+(p-1)N とおける。よって,

mk1k2=m(mp1)Nm1N=mm^{k_1k_2}=m\cdot (m^{p-1})^N\equiv m\cdot 1^N=m

ただし,途中の \equivmodp\mathrm{mod}\:p であり,フェルマーの小定理を用いた。

RSA暗号の安全性と素因数分解

素因数分解が簡単に(短時間で)計算できればRSA暗号は破られます。

説明

暗号文 CC,公開鍵 k1,nk_1,n は誰でも見ることができる。

ここで nn を素因数分解することで p,qp,q が求まる。すると「メッセージを受け取る側の準備」と同じ方法で秘密鍵 k2k_2 が求まり,もとのメッセージ MM を復号できる。

幸い,大きな数の素因数分解の計算は難しいです。→素因数分解の難しさと素数判定

RSA暗号の計算例

実際にRSA暗号の計算例を見ることで,理解を深めましょう。

公開鍵・秘密鍵の準備

  • 素数として p=23,q=31p = 23, q = 31 とします。n=pq=713n = pq = 713 です。これくらいの数であれば素因数分解は簡単ですが,あくまで計算例ということで。
  • (231)(311)=22×30=660(23-1)(31-1) = 22 \times 30 = 660 と互いに素な数として,k1=7k_1 = 7 を選ぶことにしましょう。
  • 有名な定理により,7×k21mod6607 \times k_2 \equiv 1 \mod 660 の解 k2k_2k2=283k_2 = 283 と一意に定まります。
  • 公開鍵として n=713,k1=7n = 713, k_1 = 7 を公開し,秘密鍵として k2=283k_2 = 283 を秘密にしておきます。

暗号化の処理

メッセージを送る側は,478478 という数を送りたくなったとします。n=713n = 713 を法として, 4787673478^{7} \equiv 673 です。C=673C = 673 として,これを送ります。

復号化の処理

n=713n = 713 を法として, 673283478673^{283} \equiv 478 です。これで,無事に解読できました!

厳密には(pp などに)もっといろいろ条件があります。興味を持った方は暗号の本を読んでみてください!