RSA暗号を作ってみよう

暗号とは

暗号とは、他の人に知られたくない情報を、別の形に残すことです。
元の情報を暗号にすることを暗号化、暗号化したものを元の情報に戻すことを復号化といいます。

シーザー暗号

例えば、あ→い、い→う、う→え、のように1文字ずつずらしたり、
あ→お、い→か、う→き、のように4文字ずらしたりするような
ずらすことで暗号化する方法です。
4文字前にずらすことで復号が可能です。

例：1文字後にずらす暗号の場合
　平文：いろはにほへとちりぬるを
暗号文：うわひぬまほなつるねれん

しかしこれは見破られやすいため、特にコンピュータの世界では以下のRSA暗号がよく使われています。

RSA暗号

RSA暗号は、大きな「素数×素数」の因数分解が難しいことを利用した暗号です。
細田守監督の「サマーウォーズ」に出てくる電脳世界もRSA暗号で守られています。
今回は、このRSA暗号の作り方を紹介します。
宝探しなどに使って遊んでみてください。

RSA暗号の作り方

1. 各文字に数値を割り振る
   $$あ-00 か-05 ・・・ は-25 ・・・ や-35$$
   $$い-01 き-06 ・・・ ひ-26$$
   $$う-02 く-07 ・・・ ふ-27 ・・・ ゆ-37$$
   $$え-03 け-08 ・・・ へ-28$$
   $$お-04 こ-09 ・・・ ほ-29 ・・・ よ-39$$

2. 平文を数値に変換する
   $$おはよう \to 04 25 39 02$$

3. 暗号化、解読に使う数値を3つ決める
   3-1. $$2つの素数p,qを決め、掛けたものを公開鍵とする。$$
   $$例：素数を7、11とし、77を公開鍵とする$$
   3-2. $$(p-1)(q-1)と互いに素かつ0<e<(p-1)(q-1)となるeを公開鍵とする。$$
   $$例：(7-1)(11-1)=60なので、60と互いに素な17を公開鍵とする$$
   3-3.$$e\times A+(p-1)(q-1)\times B=1を満たすA(>0)を求め、これを秘密鍵dとする$$
   $$例：7A+60B=1 A=43,B=-5$$

4. 公開鍵$n,e$を暗号文を作成する人に通知する。秘密鍵$d$は解読する人だけの秘密にする。

5. 2.の平文を暗号化する。
   暗号文の数値 ≡ $平文の数{値}^e\mathrm{mod}pq$
   例
   $${04}^{17}\mathrm{mod}77\equiv 16\to ち$$
   $${25}^{17}\mathrm{mod}77\equiv 09\to こ$$
   $${39}^{17}\mathrm{mod}77\equiv 30\to ま$$
   $${02}^{17}\mathrm{mod}77\equiv 18\to て$$
   平文は「おはよう」、暗号文は「ちこまて」となる。

6. 暗号を解く
   平文の数値 = $暗号文の数{値}^d\mathrm{mod}pq$
   例
   $${16}^{43}\mathrm{mod}77\equiv 04\to お$$
   $${09}^{43}\mathrm{mod}77\equiv 25\to は$$
   $${30}^{43}\mathrm{mod}77\equiv 39\to よ$$
   $${18}^{43}\mathrm{mod}77\equiv 02\to う$$
   暗号文は「ちこまて」、平文は「おはよう」となる。

7. RSA暗号を作ってみよう

RSA暗号が作れるワケ

前提

$$p,q：素数$$
$$\mathrm{\exists }d(>0), 0<\mathrm{\exists }e<(p-1)(q-1) s.t. ed+(p-1)(q-1)\times B=1, gcd(e,(p-1)(q-1))=1,$$

平文→暗号文

$x$を平文とすると、暗号文は$x^e\mathrm{mod}pq$　で表される
中国剰余定理より、この$x^e$は$\mathrm{mod}pq$の下で一意に決まるので
平文に対して、暗号文が一意に決まる。

暗号文→平文

暗号文$x^e\mathrm{mod}pq$に対し、復号文は$x^{ed}\mathrm{mod}pq$　で表される
$$x^{ed}\mathrm{mod}pq$$
$$\equiv x^{1-(p-1)(q-1)B}\mathrm{mod}pq$$
フェルマーの小定理より
$$x^{p-1}\equiv 1\mathrm{mod}p, x^{q-1}\equiv 1\mathrm{mod}q$$
$$x^{p-1}{x}^{q-1}\equiv x^{q-1}\mathrm{mod}p$$
$$x^{p-1}{x}^{q-1}\equiv 1\mathrm{mod}pq$$
$$x^{-B}{x}^{p-1}{x}^{q-1}\equiv 1\mathrm{mod}pq$$
$$x^{-B(p-1)(q-1)}\equiv 1\mathrm{mod}pq$$
よって
$$x^{ed}\mathrm{mod}pq$$
$$\equiv x^{1-(p-1)(q-1)B}\mathrm{mod}pq$$
$$\equiv x{x}^{-B(p-1)(q-1)}\mathrm{mod}pq$$
$$\equiv x\mathrm{mod}pq$$