配布プリント

計算機数学演習 A 2015.7.14. RSA 暗号の原理
この講義の資料は, http://www.sm.u-tokai.ac.jp/~nakayama/ より入手することができる.
1
RSA 暗号
公開鍵暗号で A から B へメッセージを送る手順
1. A はメッセージを B の公開鍵を使って暗号化する.
2. A は暗号文を B へ送信する.
3. B は A からの暗号文を B の秘密鍵を使って復号化して, A のメッセージを受け取る.
公開鍵暗号で B から A へメッセージを送る手順
1. B はメッセージを A の公開鍵を使って暗号化する.
2. B は暗号文を A へ送信する.
3. A は B からの暗号文を A の秘密鍵を使って復号化して, B のメッセージを受け取る.
RSA 暗号では, 公開鍵はある正の整数の組 (e, m) であり, 秘密鍵もある正の整数の組 (d, m) である. 具体的な数の決
め方は次の通り.
• m = pq. ここで p, q は巨大な素数をとる.
• e は φ(m) と互いに素な整数.
• d は d ≡ e−1 mod φ(m) が成り立つ整数. (すなわち ed ≡ 1 mod φ(m) なる整数.) 与えられた m, e から d を計
算するには拡張ユークリッドの互除法を用いる.
平文の文字に対応する数 x について,
y ≡ xe
mod m
で暗号化する. y が暗号文の文字に対応する数である. 逆に復号する場合, 暗号文の文字に対応する数 y について,
x ≡ yd
mod m
で復号化する.
例 1. p = 11, q = 13, e = 17 とする. (各数は素数である.)
• m = pq = 11 × 13 = 143
• φ(m) = φ(pq) = φ(11)φ(13) = 10 × 12 = 120
• d は計算してやると d ≡ 17−1 ≡ 113 mod 120 となる.
平文 ‘C’ の文字を ASCII コードに変換すると数 x = 67 が得られる. これを暗号化するには, xe mod m すなわち 6717
mod 143 を計算してやればよい. この結果は 45 となり, これが暗号文 y = 45 である. 逆に暗号文 y = 45 を復号するに
は, y d mod m すなわち 45113 mod 143 を計算すればよい. この結果は 67 であり, これを文字に直すと ‘C’ と元の平
文が得られる.
定理 2 (RSA 暗号の原理). p, q を互いに異なる素数とし, m = pq とおく. e は φ(m) と互いに素なある整数とする. こ
の時, 0 ≤ x < m なる整数 x について,
(xe )d ≡ x
が成り立つ.
1
mod m
定理 2 の証明には次の定理を用いる.
定理 3 (オイラーの定理). 整数 a と n が互いに素であるとする. この時, aφ(n) ≡ 1 mod n が成り立つ.
系 4 (フェルマーの小定理). p を素数とする. この時, ap−1 ≡ 1 mod p が成り立つ.
1. RSA 暗号の暗号化, 復号化の計算
[1916]
11
[1917]
13
[1918]
143
[1919]
120
[1922]
17
[1923]
113
[1924]
[67]
[1925]
67
[1926]
45
[1927]
67
[1928]
C
P=11;
Q=13;
M=P*Q;
Phi=pari(phi, M);
オイラー関数の計算
E=17;
D=inv(E, Phi);
modulo Phi での E の逆元の計算
strtoascii("C");
文字 C を ASCII コードで数字に直す
X=67;
Y=X^E % M;
暗号化
Y^D % M;
復号化
asciitostr([67]);
数字を ASCII コードで文字に直す
問題 5. 鍵の設定を p = 17, q = 19, e = 11 だとして, m, d, ϕ(m) を計算し, 平文 ’Z’ を暗号文に変換せよ. 暗号文 317 を
平文に戻せ.
例 6. p = 3581, q = 7927, e = 547 とする. (各数は素数である.)
• m = pq = 3581 × 7927 = 28386587
• φ(m) = φ(pq) = φ(p)φ(q) = 3580 × 7926 = 28375080
• d は計算してやると d = 14161603 となる.
平文 “ABC” の各文字を ASCII コードに変換して数をつなげてやると数 x = 656667 が得られる. これを暗号化するに
は, xe mod m すなわち 656667547 mod 28386587 を計算してやればよい. この結果は 18146854 となり, これが暗号文
y = 18146854 である. 逆に暗号文 y = 18146854 を復号するには, y d mod m すなわち 1814685414161603 mod 28386587
を計算すればよい. この結果は 656667 であり, これを文字に直すと “ABC” と元の平文が得られる.
暗号文 y と公開鍵 (e, m) がわかっているとする. (ただし, e, m は巨大な整数であるとする.) これらから平文 x を得
るのは原理的には計算ができるが, 計算が大変であり実際に得るのは困難である. 暗号文 y を復号するには秘密鍵 (d, m)
が必要で, d ≡ e−1 mod φ(m) の計算が必要である. このためには, オイラー関数 φ(m) を計算する必要があるが, m の
素因数分解がどうなるかわかっていない今の状態ではこれを計算するのは大変である. 逆に言うと, m の素因数分解がわ
かると d すなわち秘密鍵は容易に計算できるので, 暗号文が解読されてしまう. このように RSA 暗号は, 巨大な整数の
素因数分解が計算困難なことを使って, 安全性を保っている.
問題 7.
1. Asir では pari(factor, 整数); という命令を用いて整数の素因数分解ができる. 何桁くらいまでの整数
を素因数分解できるか, 実験してみよ.
2. Asir での素因数分解
[1953] pari(factor, 29189280180313841023940914318924);
[ 2 2 ]
[ 227 1 ]
[ 263 1 ]
[ 6877343785177 1 ]
[ 17773012805503 1 ]
2
参考文献
[1] 木田祐司, 初等整数論, 朝倉書店
[2] D. ハーディー, C. ウォーカー, 応用代数学入門, ピアソンエデュケーション
3

Download Report