ウォンツテック

そでやまのーと

■

RSA STL RSA STL

STLの勉強をするのにただつまらないコードを書いてもあれなのでRSAの暗号アルゴリズムによるkey（公開鍵、秘密鍵）の生成とファイルの暗号、復号化のコードを書いてみようと思う。
ざっくり調べてみたところRSA Algorithmとその周辺には以下の要素がある。

1. Key Generation Algorithm
2. Encryption
3. Decryption
(以下はRSAとは直接関係無い）
4. 多倍長整数
5. 素数生成

多倍長整数とかはライブラリを使うかどうしようか悩みどころ、素数生成は結構難しそう。1024bitのkeyを生成するのに512bit程度の素数(10^154くらい)を二つ作る必要があるらしいけど、乱数を作ってそれが素数かのテストをする方法で作るとなると結構な時間がかかりそう。と思ったけどこないだSICPでやったFermatテストを数回やって「素数である確率が極めて高い」って方法を採用しようかな。
全体としては実は結構簡単に出来てしまいそうな気がする。多倍長整数の取り扱いが一番むずかしかったりして？（極度に難しそうだった場合はライブラリを使います。。）

RSA論文

論文から暗号化と複合化の概要を示す。

1. 暗号化しようとするメッセージをある整数n未満の単位に区切る。たとえば1バイト単位にする。
2. ある整数nとは巨大な二つのランダムに選んだ素数から
[ n = p*q
で生成する。
3. 2.で選んだp, qに関して以下の条件を満たす整数dを探す
 gcd(d, (p-1)*(q-1)) = 1
※dと(p-1)*(q-1)の最大公約数が1（互いに素）
4. p, q, dから以下の条件を満たす整数eを探す
 e*d ≡ 1 (mod (p-1)*(q-1))
※e*dを(p-1)*(q-1)で割った余りが1

5. (e, n)をpublic keyとし送りたいメッセージを1.で区切った単位Mから整数Cを以下のように生成する。
 C ≡ M^e (mod n)
Cが暗号文となる。
6. (d, n)をprivate keyとし受け取った暗号メッセージCを以下のように解凍する。
 M ≡ C^d (mod n)
  • 数学的証明
1. オイラーの定理
オイラー関数\phi(n)を以下のように定めたとき
a^{\phi(n)} \equiv 1 (mod n) ... ①
が成り立つ。
\phi(n):nを正の整数であるとするとき、1〜nまでの整数でnと互いに素な整数の個数。素数pに関して\phi(p) = p-1となる事は自明。
2. 補助定理
nとmを互いに素な正の整数とすると以下が成り立つ
\phi(mn) = \phi(m)\phi(n) ... ②

3. RSAの生成規則
e*d \equiv 1 (mod \phi(n)) ... ③

ここで本文M、暗号文Cに対して暗号化の操作をE、復号化をDとした時に
D(E(M)) = M (C = E(M)) ... ④
E(D(M)) = M ... ⑤
を証明する。

まず暗号文の生成規則により
D(E(M)) \equiv (E(M))^d \equiv (M^e)^d (mod n) = M^{ed} (mod n) ... I
E(D(M)) \equiv (D(M))^e \equiv (M^d)^e (mod n) = M^{ed} (mod n) ... II
※a \equiv b (mod n) \Rightarrow a^x \equiv b^x (mod n) xは整数
が成り立ち、kを整数とすると③より
ed = k \phi(n)+1とおけるので
M^{ed} \equiv M^{k\phi(n)+1}  ... ⑥
が得られる。
また、①でn=p（素数）とした時
M^{p-1} \equiv 1 (mod p)
で、②でm=p, n=qとした時
\phi(n) = \phi(p)\phi(q)
なので
[tex:M^{k\phi(n)+1} \equiv M^{k\phi*1}M \equiv M^{k\phi(p-1)\phi(q-1)}M]
 \equiv M^{(p-1)k(q-1)}M \equiv 1^{k(q-1)}M \equiv M (mod p)
が得られる。
同様に
M^{k\phi(n)+1} \equiv M (mod q)
となる。
従って合同式の定義より
M^{k\phi(n)+1} \equiv M (mod n)
となり、これと⑥により
M^{ed} \equiv M (mod n)
となるがこれはI,IIより
D(E(M)) \equiv M (mod n)
E(D(M)) \equiv M (mod n)
であり、ここでMはn未満の整数を選んでありかつD,Eの操作では文自体のサイズは増えないのでD(E(M))もE(D(M))もn未満の整数である。よってD(E(M))、E(D(M))、Mをnで割った余りのその値そのものになる。すなわちD(E(M)) = M、E(D(M)) = Mが得られる。

*1:p-1)(q-1