RSA暗号を作ってみよう
暗号とは
暗号とは、他の人に知られたくない情報を、別の形に残すことです。
元の情報を暗号にすることを暗号化、暗号化したものを元の情報に戻すことを復号化といいます。
シーザー暗号
例えば、あ→い、い→う、う→え、のように1文字ずつずらしたり、
あ→お、い→か、う→き、のように4文字ずらしたりするような
ずらすことで暗号化する方法です。
4文字前にずらすことで復号が可能です。
例：1文字後にずらす暗号の場合
平文：いろはにほへとちりぬるを
暗号文：うわひぬまほなつるねれん
しかしこれは見破られやすいため、特にコンピュータの世界では以下のRSA暗号がよく使われています。
RSA暗号
RSA暗号は、大きな「素数×素数」の因数分解が難しいことを利用した暗号です。
細田守監督の「サマーウォーズ」に出てくる電脳世界もRSA暗号で守られています。
今回は、このRSA暗号の作り方を紹介します。
宝探しなどに使って遊んでみてください。
RSA暗号の作り方
各文字に数値を割り振る
$$あ-00 か-05 ・・・ は-25 ・・・ や-35$$
$$い-01 き-06 ・・・ ひ-26$$
$$う-02 く-07 ・・・ ふ-27 ・・・ ゆ-37$$
$$え-03 け-08 ・・・ へ-28$$
$$お-04 こ-09 ・・・ ほ-29 ・・・ よ-39$$平文を数値に変換する
$$おはよう → 04 25 39 02$$暗号化、解読に使う数値を3つ決める
3-1. $$2つの素数p,qを決め、掛けたものを公開鍵とする。$$
$$例：素数を7、11とし、77を公開鍵とする$$
3-2. $$(p-1)(q-1)と互いに素かつ0 \lt e \lt (p-1)(q-1)となるeを公開鍵とする。$$
$$例：(7-1)(11-1) = 60 なので、60と互いに素な17を公開鍵とする$$
3-3.$$e×A+(p-1)(q-1)×B=1を満たすA(\gt 0)を求め、これを秘密鍵dとする$$
$$例：7A+60B=1 A=43,B=-5$$公開鍵$n,e$を暗号文を作成する人に通知する。秘密鍵$d$は解読する人だけの秘密にする。
2.の平文を暗号化する。
暗号文の数値 ≡ $平文の数値^{e} \mod pq$
例
$$04^{17} \mod 77 ≡ 16 → ち$$
$$25^{17} \mod 77 ≡ 09 → こ$$
$$39^{17} \mod 77 ≡ 30 → ま$$
$$02^{17} \mod 77 ≡ 18 → て$$
平文は「おはよう」、暗号文は「ちこまて」となる。暗号を解く
平文の数値 = $暗号文の数値^{d} \mod pq$
例
$$16^{43} \mod 77 ≡ 04 → お$$
$$09^{43} \mod 77 ≡ 25 → は$$
$$30^{43} \mod 77 ≡ 39 → よ$$
$$18^{43} \mod 77 ≡ 02 → う$$
暗号文は「ちこまて」、平文は「おはよう」となる。RSA暗号を作ってみよう
RSA暗号が作れるワケ
前提
$$p,q：素数$$
$$\exists d(\gt 0), 0 \lt \exists e \lt (p-1)(q-1) s.t. ed+(p-1)(q-1)×B=1, gcd(e,(p-1)(q-1))=1, $$
平文→暗号文
$x$を平文とすると、暗号文は$x^{e} \mod pq$ で表される
中国剰余定理より、この$x^{e}$は$\mod pq$の下で一意に決まるので
平文に対して、暗号文が一意に決まる。
暗号文→平文
暗号文$x^{e} \mod pq$に対し、復号文は$x^{ed} \mod pq$ で表される
$$x^{ed} \mod pq$$
$$≡x^{1-(p-1)(q-1)B} \mod pq$$
フェルマーの小定理より
$$x^{p-1} ≡ 1 \mod p, x^{q-1} ≡ 1 \mod q$$
$$x^{p-1}x^{q-1} ≡ x^{q-1} \mod p$$
$$x^{p-1}x^{q-1} ≡ 1 \mod pq$$
$$x^{-B}x^{p-1}x^{q-1} ≡ 1 \mod pq$$
$$x^{-B(p-1)(q-1)} ≡ 1 \mod pq$$
よって
$$x^{ed} \mod pq$$
$$≡x^{1-(p-1)(q-1)B} \mod pq$$
$$≡xx^{-B(p-1)(q-1)} \mod pq$$
$$≡x \mod pq$$
