2

RSA暗号を作ってみよう

20377
0
$$$$

暗号とは

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

シーザー暗号

例えば、あ→い、い→う、う→え、のように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. 平文を数値に変換する
    $$おはよう → 04 25 39 02$$

  3. 暗号化、解読に使う数値を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$$

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

  5. 2.の平文を暗号化する。
    暗号文の数値 ≡ $平文の数値^{e} \mod pq$

    $$04^{17} \mod 77 ≡ 16 → ち$$
    $$25^{17} \mod 77 ≡ 09 → こ$$
    $$39^{17} \mod 77 ≡ 30 → ま$$
    $$02^{17} \mod 77 ≡ 18 → て$$
    平文は「おはよう」、暗号文は「ちこまて」となる。

  6. 暗号を解く
    平文の数値 = $暗号文の数値^{d} \mod pq$

    $$16^{43} \mod 77 ≡ 04 → お$$
    $$09^{43} \mod 77 ≡ 25 → は$$
    $$30^{43} \mod 77 ≡ 39 → よ$$
    $$18^{43} \mod 77 ≡ 02 → う$$
    暗号文は「ちこまて」、平文は「おはよう」となる。

  7. 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$$

投稿日:202142

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

あーく
あーく
104
135848
使える数学、面白い数学の分かりやすい解説を心がけています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中