Tweet

RSA暗号の仕組み

ビットコインの説明で用いた「暗号ダイヤル」について詳しく解説していきます。この暗号ダイヤルというのは”RSA暗号”というもののモデル化です。

簡単に説明したのは，
・「秘密の回数」だけ回した暗号ダイヤルに表示された数字を入力エリアに入れた暗号ダイヤルを「公開の回数」だけ回すと元の数字が表示される．
という特徴でした．

この不思議なダイヤルがどのような仕組みで成り立っているのかについて解説していきます．

暗号ダイヤルの挙動

まず，文章を数字に変えます．たとえば，テキストが5という数字に変換されたとしてください．（もちろん実際はもっと大きな数字に変換されます）
暗号ダイヤルには型番があり，型番はたとえば”mod 33″のようにそれぞれのダイヤルに書かれています．
この型番は何を意味するのでしょうか？

暗号ダイヤルを実際に回してみましょう．
最初にテキストとして5を暗号ダイヤルに入力します．

入力すると表示エリアは1となります．（5の0乗です）
この暗号ダイヤルを一回回してみます．

5になりました．
1(表示)×5(input)が計算されました．
もう一回回してみましょう．

5(表示)×5(input)=25
もうわかりましたね．
次は
25×5=125より，125だ！
と思いきや，表示されたのは

26
です．
何が起こったのでしょうか？
ここで型番が登場します．
125÷33 = 3 あまり　26
型番で割ったあまりが表示されました．
これが暗号ダイヤルの機能です．

暗号としての動作

では，続いて本題．「秘密の回数」回した暗号ダイヤルで表示された数字を入力に入れ，「公開の回数」だけ回すと元の数字に戻る．ということについて解説します．
もとの数字が5，秘密の回数が7，ダイヤルの型番は33，公開の回数は3とします．
まず，もとの数字を入れ，秘密の回数だけダイヤルを回します．
$$
5(もとの数字)^{７(秘密の回数) }mod 33(型番)\\
= 78125 mod 33\\
= 14
$$

続いてoutputをinputに代入します．

そして公開した回数だけダイヤルを回します．
$$
14^{3(公開の回数)} \;\;mod 33\\
= 5
$$

もとの数字に戻りましたね！

RSA暗号の数学的な説明

これらの回数はデタラメに決めていいわけではありません．
「フェルマーの小定理」というもので成り立っています．
$$gが素数pの倍数でないとき，g^{p-1} mod \; p = 1$$
証明は帰納法を用いて簡単にできます．

これを少し拡張させます．
$$g^{(p-1)(q-1)} mod\; pq = 1$$

（証明）
この拡張は「aは3と5の倍数であるから，aは15の倍数だ」というイメージです．
$$g^{p-1} mod\;p = 1　より$$
$$g^{(p-1)(q-1)} mod\;p = 1$$
$$（8 mod 5 = 3であり，このとき8^2 mod \;5 = 3^2 mod\; 5のように，一度割り切った数は無視できます）$$

$$g^{(p-1)(q-1)} mod\;p = 1 よりg^{(p-1)(q-1)}-1はpの倍数$$
（参考：16÷3 = 5 あまり 1のとき16-1 は5の倍数）
$$g^{(p-1)(q-1)} mod\; q = 1 よりg^{(p-1)(q-1)}-1はqの倍数$$
$$pとqは互いに素であるため，g^{(p-1)(q-1)} -1 はpqの倍数$$
$$g^{(p-1)(q-1)} mod\; pq = 1$$

この式にさらにgをかけると，
$$g×g^{(p-1)(q-1)}mod\; pq = 1 × g = g$$
要するに，
$$g^{(p-1)(q-1)+1} mod\; pq = gとなるのです．$$
あとは 「公開鍵」×「秘密鍵」= (p-1)(q-1)+1となる数字を準備するだけです！

Tweet