理論
2010年04月07日
インターネット通信における暗号では、主として公開鍵暗号方式が使われている。
この暗号化方式では、大きな数の素因数分解は容易ではないことが暗号強度の数学的根拠になっている。
任意に決めた2つの素数の積をとり、その積の数値が第三者に分かっても、元の素数を算出するには時間がかかる性質を利用している。
コンピュータ上の暗号化に関する設定では、公開鍵と秘密鍵の鍵ペアを作成し、公開鍵は誰に知られてもよく、秘密鍵は知られてはいけないファイルとして保存される。
数学的な素数の原理と、公開鍵および秘密鍵との関係をよく理解していなかったので、改めて数学的な原理を元に、鍵の意味について勉強した。
一般的に使われるRSA暗号を例にとり、手計算で暗号化と復号化をシミュレートすることにする。
実際の計算においては、ユークリッドの互除法をはじめ、なかなか難しい話が多いので、ここでは「どうしてそうなのか」といった理屈には踏み込まない。(踏み込めない)(笑)
気になる方は、以下の参考リンクを読み込んでください。
表面的な流れのみを、できるだけ容易に整理してみる。 厳密な表現から外れることはもとより、誤解や誤りもあるかもしれない。
プログラミングしようにも、巨大な数を多倍長整数で扱うなり、特殊なアルゴリズムが必要だったりと、実装は大変そうである。暗号化には計算コストがかかる、というのもよくわかる。
1.参考リンク
- This is Takuya TSUCHIYA's Home Page.
数学的な説明が、とてもわかりやすく、理解できた気になれる(^^;解説ページ。 - KENJI'S HOMEPAGE
手計算の仕方は、ここをマネした。 - CPU 実験日記
コンパクトにうまくまとめてくれている。
2.鍵の作り方
(1)素数の決定
ふたつの異なる素数p,qを決める。
(2)2つの素数の積(n)を求める
(3)最小公倍数(u)を求める
(p-1)と(q-1)の最小公倍数を求める。
これをuとする。
(面倒なら でもいい)
(4)uと素な数(d)を決める
uとの最大公約数が1となるdを求める。
つまりdは、uと共通の約数を持っていない数値のこと。
dの候補は複数あるが、その中から任意に決める。
(5)eを求める
eにdをかけて、uで割った時、余りが1となるようにする。
eの候補は複数あるが、その中から任意に決める。
(6)鍵の完成
公開鍵は、nとe
秘密鍵は、nとd
2.暗号化
送信者が受信者の公開鍵n,eで平分Mを暗号化し、暗号文Eを作る。
平文メッセージMは公開鍵nより小さくなければならない。
暗号文Eは以下のように求める。
E= [ をnで割った余り]
3.復号化
2で暗号化された暗号文Eを、正規の受信者が自分の秘密鍵dを使って復号化し平文Mを求める。
M= [ をnで割った余り ]
4.結論
公開鍵と秘密鍵は、大きな数の素因数分解においてどんなものなのかと捉えると、誤解を恐れずに大胆に言えば、余りをハッシュという考え方で置き換えて。
秘密鍵:素数同士の積と元になった素数のハッシュ値
公開鍵:素数同士の積と秘密鍵のハッシュ値
専門家からはクレームつきそう・・・。
実際の鍵ファイルは、テキストファイルである。これは、上記の値をbase64エンコードし、扱いやすくしている。
以下が手計算で流れを追ってみた結果。
(1)素数(p,q)を決める
(2)積(n)を求める
(3)最小公倍数(u)を求める
(4)uと素の数(d)を求める
を素因数分解をすると。
もしd= 2なら、uとdの最大公約数2
もしd= 3なら、uとdの最大公約数3
もしd= 4なら、uとdの最大公約数2
もしd= 5なら、uとdの最大公約数2
もしd= 6なら、uとdの最大公約数6
もしd= 7なら、uとdの最大公約数1
もしd= 8なら、uとdの最大公約数2
もしd= 9なら、uとdの最大公約数3
もしd=10なら、uとdの最大公約数2
・
・
・
そこで、 とする。
(5)eを求める
もしe= 1なら、ed= 7それをu=66で割って余り7
もしe= 2なら、ed=14それをu=66で割って余り14
もしe= 3なら、ed=21それをu=66で割って余り21
もしe= 4なら、ed=28それをu=66で割って余り28
・
・
・
もしe=10なら、ed=70それをu=66で割って余り4
もしe=11なら、ed=77それをu=66で割って余り11
もしe=12なら、ed=84それをu=66で割って余り18
・
・
・
もしe=18なら、ed=126それをu=66で割って余り60
もしe=19なら、ed=133それをu=66で割って余り1
もしe=20なら、ed=140それをu=66で割って余り8
・
・
・
そこで、 とする。
(6)鍵の完成
公開鍵 n=161, e=19
秘密鍵 n=161, d=7
(7)暗号化
平分Mを10とし、これを暗号化する。
E= [ を で割った余り ]
-->1000をn=161で割った余りを求めると、34
--> 39304をn=161で割った余りを求めると、20
--> 4000のn=161で割った余りは136
暗号文E=136である
(8)復号
暗号文E=136を、秘密鍵d=7で復号し、平文Mを求める。
M= [ を で割った余り ]
--> 18496をn=161で割った余りを求めると、142
--> 2863288をn=161で割った余りを求めると、64
--> 8704をn=161で割った余りを求めると、10
平分Mは、M=10である。
送信者の平文Mと一致し、めでたく復号できた。