Post date: Sep 27, 2016 6:38:44 PM
前回の話の中で、ちょっと数字を入れて遊んでみるソフトをぶっつけで作ってみました。(前記事の下部からZipをダウンロードできます。)
どう遊んでみるか、少し解説しておきます。
Zipをダウンロードして展開すると2つの実行ファイルが出来ます。
● RSA認証の基礎体験.exe ~何乗かすると元に戻る数の不思議を体験する。
計算結果は、必ずm(この場合だと1234)になります。どんな数字の組み合わせで試してもルールさえ守っていればちゃんとmとなって計算されますね。
色々試して遊んでみましょう。
さて、上の例でn=3として計算したところ、n*lcm(p-1,q-1)+1=8281となりました。この部分を2つの数字の掛け算に分けることが出来れば、それが秘密鍵と公開鍵として利用できます。幸い、今回のn=3の計算では 8281=7x1183、49x169、147x13 等と分けることが出来ます。
どの数字のペアーでも構いませんが、例として公開鍵を13、秘密鍵を147として実験してみましょう。
147以外の数字を鍵にすると色んな値に復号され、どれが本物かわかんないですよね。公開鍵による暗号化と秘密鍵による復号化が成功しているみたいです。
色んな数字、いろんな巾乗でも試してみてください。 p*q と巾乗数を 秘密鍵、公開鍵というようにペアーにして暗号化・復号化が出来ますね。
お詫び:今気づいたんですけどソフトで「復号化数」が「複合化数」と誤字になってました。済みません読み替えてください。
重要なところは、
というアイデアです。2つに分けられない場合は失敗となります。
色々なnの値で試してみると、n*lcm(p-1,q-1)+1がうまく掛け算に分けられる場合と難しい場合があることがわかります。これが、大きな数字p,qで計算したなら尚更困難が予想されます。色々なnをあてずっぽうで試してみるわけにもいきません。しかし、二つの数の掛け算に分けられるようなnを計算する方法があるのです。拡張ユークリッドの互除法と言う技法を使います。
その様子を以下のソフトで体験できます。
● ユークリッドの互除法.exe ~最大公約数を求める方法を利用して鍵を生成する。
上のRSA認証の基礎体験.exeをつかって、求めた数字から、鍵を生成しよう。
なんじゃこりゃ?と言う感じですが、やったことを箇条書きにまとめてみます。
RSA認証の基礎体験.exeで、p,qを決めました。それを使って、p*q を計算します。p*qは鍵の一部として利用します。
同じく、(p-1) と (q-1) の最小公倍数を求めておきます。
その最小公倍数を自然数a とし 互いに素な自然数b を利用して「ある」計算をします。その計算から、自然数bを公開鍵とした場合の秘密鍵が導き出されます。
今回の例では
という流れ。
さて、それでは実際にこれが使えるのかどうか、実験します。RSA認証の基礎体験.exeにもどって
暗号化復号化数に適当な値。鍵~p*qに16819 鍵~巾数に19を入れて暗号化
出来た暗号で、鍵~巾数に2178を入れて復号化。
ちゃんと元に戻りましたか?
色んな数で遊んでみてください。
制作後記:
今回作った体験ソフトは2つに分ける必要はありませんでした。
ただ、以下のような理由であえて二つに分けました。
ユークリッドの互除法自体は古くから使われていた最大公約数を求める一般的な技法であること。
公開鍵と秘密鍵を使って暗号化・復号化が出来るんじゃないかという理論予測はあったが、それがどう実現されるのかは誰にもわからなかったところ、RSA認証という素数を使った計算で秘密鍵・公開鍵方式が実現できることに気づき、既にあった技法が非常にうまく利用されたこと。
この、非常にうまく利用された部分を遊びながら感じてほしいと考えたわけです。
ちなみにRSAはRivest、Shamir、Adleman 開発者各氏の頭文字で、1978年に開発されました。