はじめに
こんにちは！iimonでフロントエンジニアをしている「みよちゃん」です！8月も終盤に差し掛かってきましたが、まだ暑いですよね…
エンジニア×夏
といえば、やはりあの映画でしょう！！
明言は避けますがあの映画です！！
毎年地上波で放送しているようですが、エンジニアの皆さんなら毎年欠かさず視聴していることと思います。
見た事のない方のためにざっくり内容をまとめると
「数学にめっっちゃ強い主人公が、ようわからん数字の羅列を見て何かを計算して世界を救う話」です！
今回は「ようわからん数字の羅列の計算」について勉強する機会がありましたので、お話ししたいと思います！
RSA暗号
ようわからん数字の羅列の正体
はじめに、ようわからん数字の羅列がなんなのかについてざっくりお話しします。
あの数列は「RSA暗号」と呼ばれるものです。
皆さんも聞き馴染みのある「公開鍵暗号方式」で用いられており、広く使用されています。
(公開鍵暗号方式に関しては、宣伝大好き「はやっしー」が記事を書いてくれているので、よければ読んでやってください。)
なぜRSA暗号？
前のセクションでRSA暗号は「広く用いられている」とお話ししましたが、なぜRSA暗号が使用されるのでしょうか？
理由はシンプル、秘密鍵がない状態で復号しようとすると、計算に莫大な時間を要する(実質不可能と言われています)からです。
これは素因数分解が難解であるという特性のもとに成り立っています！
暗号化と複号化
暗号化の手順
P-暗号化の準備
文字記号の整数化
文字列記号の各要素に整数を対応させる(公開)
鍵の生成数の設定
公開鍵「n」「e」の作成と公開
n=pqにより「n」を定める
「e」は「p」「q」の大きいほうより大きく、「L」より小さいかつ「L」と互いに素である必要があります
複号鍵の算出
複号鍵「d」をed≡1(mod L)を満たす整数として求めておく
E-暗号化
平文の整数化
送りたい平文に対して、P-1に基づいて整数化する。
整数の暗号化
各整数に対して
Pe≡C(modn), 1≤C<n
を満たすような整数Cを求める。
暗号文の作成
E-2で得られた整数をそれぞれP-1の対応表を用いて平文へ変換する
D-復号化
暗号化された整数Cの算出
受け取った暗号文ををP-1で用意した対応表を用いて整数に変換する
暗号化された整数の復号
Cd≡Q(modn), 1≤Q<nを満たす整数Qを求める
復号化2で得られた整数Qは整数Pに等しいので、Q=P=a1Nt-1+a2N^(t-
- P1の対応表に従い整数文字記号を対応させると平文が得られる。
どうでしょうか、理解できましたでしょうか？おそらく手順だけ読んでもピンとこない方もいると思うので、小さい素数を使用した簡単な例を見ていきましょう！
実際の例
今回の例では「iimon」という平文を暗号化→復号化してみたいと思います！
P-暗号化の準備
文字と整数を対応させる
はじめに文字を整数に対応させます。ここではわかりやすくアルファベットa-zを0-25に対応させます！視覚化すると以下の表のような感じです！
このルールに則ると「iimon」は「8 8 12 14 13」となります！
鍵の生成
次に2つの素数「p」「q」を定め、「L」を求めます。 今回は可能な限り簡単にするためp=3, q=11とおきます！
するとLは(3-1)と(11-1)の最小公倍数のため
「L」=10
となります！
公開鍵の作成
n=qpよりn=3*11=33
「e」は1より大きく10より小さいかつ10と互いに素な自然数の中から、一番小さい
3を選びます！よって
「n」は33、「e」は3となります！
復号鍵の作成
復号鍵dはed≡1(mod L)を満たすような整数のため 3 * d ≡ 1 (mod 10)これに当てはまる 「d」は7 となります。
これにて暗号化の準備は完了です！！ 確認しやすいように準備フェーズで計算した値をまとめておきます。 公開鍵 (n, e) ⇒ (33, 3)秘密鍵「d」⇒ 7
暗号化
平文の暗号化
前項で用意した文字と整数の対応を使用して平文「iimon」を整数化します
するとiimonは(8,8,12,14,13)になります！！
整数の暗号化
公開鍵を用いて整数を暗号化します 8 ⇒ 8³ (mod 33) =17
8 ⇒ 8³ (mod 33) =17
12 ⇒ 12³ (mod 33) =12
14 ⇒ 14³ (mod 33) =5
13 ⇒ 13³ (mod 33) =19
よって暗号文は(17, 17, 12, 5, 19)となります!
暗号文の作成
2で用意した整数の暗号をP-1の対応に則って平文に変換します！ すると 「17」⇒q
「17」⇒q
「12」⇒m
「5」⇒f
「19」⇒s
となります！
復号化
受け取った暗号文(vvcn!)を秘密にしていた復号鍵d(11)を使用して平文に戻します！
暗号化された平文を整数へ変換
E-3の逆のことをしていきます！(qqmfs)は
(17 17 12 5 19)になります。
暗号化された整数の復号
暗号文の各整数CをCd(mod n)の式を用いて複号します！
17 ⇒ 17⁷ mod(33) =8
17 ⇒ 17⁷ mod(33) =8
12 ⇒ 12⁷ mod(33) =12
5 ⇒ 5⁷ mod(33) =14
19 ⇒ 19⁷ mod(33) =13
平文への復号
最後に、復号して得られた整数の列を最初のルールに従って文字に戻します！
8 ⇒ i
8 ⇒ i
12 ⇒ m
14 ⇒ o
13 ⇒ n
これで元の平文「iimon」に戻りましたね！
今回はp,qをものすごく小さな素数にしたため理解しやすかったかと思います！
なぜ正しく複号されるのか
RSA暗号が正しく復号されるのはなぜなのでしょうか？一見とても複雑な計算をしているのに、綺麗に元に戻るのは不思議ですよね！
RSA暗号が正しく復号されるのは「eとd」の関係性と「オイラーの定理」によるものです！
eとdの関係
公開鍵eと秘密鍵dは適当に作られているわけではありません。
これらの二つはe*d ≡1 (modφ(n))という関係を持ちます。
これは整数kを用いるとed = k* φ(n)+1と表すことができます。
オイラーの定理
オイラーの定理とは
nを自然数，aをnと互いに素な正の整数としたとき，aϕ(n)≡1(mod n) が成り立つ
と言うもので、簡単にいうとある数aをφ(n)回かけると、nで割ったあまりが必ず1になると表すことができます。
二つの組み合わせ
これらの関係を組み合わせて考えてみましょう
まず、Mを復号する場合の計算は
Med (mod n)
でしたね
ここにeとdの関係を組み合わせます。すると
Med = Mk*φ(n)+1となります！
これを式変換すると
Mk*φ(n) * M
ここにオイラーの定理を適用すると
Mをφ(n)乗し他ものをnで割ったあまりが0となるので
1k * M = M
元に戻りましたね！！
おわりに
今回はRSA暗号についてまとめてみました！
自分は今まで公開鍵暗号方式がどのような仕組みになっているかは知っていても、暗号化・復号化の方式までは知らなかったので、一通り学んでみて腑に落ちた感じがしました！
何より驚いたのは、某主人公は秘密鍵を知らないRSA暗号を手計算、最後に至っては暗算で解いていたことですね。。「富岳」よりも賢いことは間違いなさそうです！！
最後になりますが、弊社ではエンジニアを募集しています！
この記事を読んで少しでも興味を持ってくださった方は、ぜひカジュアル面談でお話ししましょう！
iimon採用サイト / Wantedly / Green
