配布プリント

計算機数学演習 A 2014.7.11. RSA 暗号の原理, プログラム
この講義の資料は, http://www.sm.u-tokai.ac.jp/~nakayama/ より入手することができる.
RSA 暗号
1
公開鍵暗号で A から B へメッセージを送る手順
1. A はメッセージを B の公開鍵を使って暗号化する.
2. A は暗号文を B へ送信する.
3. B は A からの暗号文を B の秘密鍵を使って復号化して, A のメッセージを受け取る.
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’ と元の平文が得られる.
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 コードで文字に直す
1
問題 2. 鍵の設定を p = 17, q = 19, e = 11 だとして, m, d, ϕ(m) を計算し, 平文 ’Z’ を暗号文に変換せよ. 暗号文 317 を
平文に戻せ.
例 3. 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” と元の平文が得られる.
上の例を Asir で実行するには次のようにする. web よりプログラム rsa_test.txt をダウンロードし, Asir で読み込
み, 以下の命令を実行する.
RSA 暗号の暗号化, 復号化の計算
[1934] P=3581;
3581
[1935] Q=7927;
7927
[1936] M=P*Q;
28386587
[1937] Phi=pari(phi, M);
オイラー関数の計算
28375080
[1938] E=547;
547
[1939] D=inv(E, Phi);
modulo Phi での E の逆元の計算
14161603
[1940] strtoascii("ABC");
文字列 "ABC" を ASCII コードで数字の列に変換
[65,66,67]
[1941] X=656667;
平文に相当する数
656667
[1942] Y=X^E % M;
暗号化
18146854
/* Y^D % M; このように単純に計算するのは効率が悪く, 計算困難. */
[1943] pow_mod(Y, D, M);
復号化 Y^D % M の計算 (単純な方法とは別の方法で)
656667
[1944] asciitostr([65,66,67]); 数字の列を文字列に変換
ABC
プログラム rsa_test.txt には, 上の計算を自動的に実行する関数として, rsa_encrypt と rsa_decrypt が用意されて
いる.
RSA 暗号の暗号化, 復号化の計算
[1934] P=3581;
3581
[1935] Q=7927;
7927
[1936] M=P*Q;
28386587
[1937] Phi=pari(phi, M);
オイラー関数の計算
28375080
[1938] E=547;
547
[1939] D=inv(E, Phi);
modulo Phi での E の逆元の計算
14161603
[1947] Y=rsa_encrypt("ABC", E, M); 公開鍵 (E, M) を用いて平文 "ABC" を暗号化
18146854
[1948] rsa_decrypt(Y, D, M);
秘密鍵 (D, M) を用いて暗号文 18146854 を復号化
ABC
問題 4. 上の例の鍵の設定 p = 3581, q = 7927, e = 547 の下で, 平文 “CAT” を暗号化するとどうなるか. 暗号文
y = 12873535 を復号すると元の平文は何か.
定理 5. p, q を互いに異なる素数とし, m = pq とおく. e は φ(m) と互いに素なある整数とする. この時, 0 ≤ x < m な
る整数 x について,
(xe )d ≡ x
2
mod m
が成り立つ.
暗号文 y と公開鍵 (e, m) がわかっているとする. (ただし, e, m は巨大な整数であるとする.) これらから平文 x を得
るのは理論的には計算ができるが, 計算が大変であり実際に得るのは困難である. 暗号文 y を復号するには秘密鍵 (d, m)
が必要で, d ≡ e−1 mod φ(m) の計算が必要である. このためには, オイラー関数 φ(m) を計算する必要があるが, m の
素因数分解がどうなるかわかっていない今の状態ではこれを計算するのは大変である. 逆に言うと, m の素因数分解がわ
かると d すなわち秘密鍵は容易に計算できるので, 暗号文が解読されてしまう. このように RSA 暗号は, 巨大な整数の
素因数分解が計算困難なことを使って, 安全性を保っている.
問題 6.
1. Asir では pari(factor, 整数); という命令を用いて整数の素因数分解ができる. 何桁くらいまでの整数
を素因数分解できるか, 実験してみよ.
Asir での素因数分解
[1953] pari(factor, 29189280180313841023940914318924);
[ 2 2 ]
[ 227 1 ]
[ 263 1 ]
[ 6877343785177 1 ]
[ 17773012805503 1 ]
2. 現時点でどれくらい大きな整数が計算機で素因数分解できるか. web で世界記録を調べてみよ.
3. 実際に使われている RSA 暗号ではどれぐらいの桁の整数が用いられているかを調べてみよ. 4. 公開鍵暗号が実際に使われている利用例を挙げよ.
参考文献
[1] D. ハーディー, C. ウォーカー, 応用代数学入門, ピアソンエデュケーション
3

Download Report