家庭ではあんまり使わない暗号化の話～遊んでみる。

Post date: Sep 27, 2016 6:38:44 PM

前回の話の中で、ちょっと数字を入れて遊んでみるソフトをぶっつけで作ってみました。（前記事の下部からZipをダウンロードできます。）

どう遊んでみるか、少し解説しておきます。

Zipをダウンロードして展開すると２つの実行ファイルが出来ます。

● RSA認証の基礎体験.exe ～何乗かすると元に戻る数の不思議を体験する。

p,qを適当に選びます。p,qは異なる素数じゃないといけないので簡単に選べるようリストにしました。ぶっつけで作ったものなので、ちっちゃい値しか選べませんが、実際にはものすごくでかい値を使います。選択すると、p*qが計算されますね。
暗号化する整数：mをこれまた適当に入力します。ただし、p*qの値より小さいものにしましょう。
任意の自然数n にも適当な値を入れます。入力が終わると n*lcm(p-1,q-1)+1の値が計算され、下にどんな式を計算するのか表示されます。
計算開始ボタンを押すと、右側の式を実際に計算します。

計算結果は、必ずｍ（この場合だと1234）になります。どんな数字の組み合わせで試してもルールさえ守っていればちゃんとｍとなって計算されますね。

色々試して遊んでみましょう。

さて、上の例でn=3として計算したところ、n*lcm(p-1,q-1)+1＝8281となりました。この部分を2つの数字の掛け算に分けることが出来れば、それが秘密鍵と公開鍵として利用できます。幸い、今回のn=3の計算では 8281＝7ｘ1183、49ｘ169、147ｘ13 等と分けることが出来ます。

どの数字のペアーでも構いませんが、例として公開鍵を13、秘密鍵を147として実験してみましょう。

鍵～巾数に13を入力し、暗号化・復号化ボタンをクリックします。暗号化された数字が出来ましたね。OKをクリックすると暗号化・復号化数のボックスに転記されました。
次に同様に鍵～巾数に147をいれて、ボタンをクリックしてみましょう。きちんと復号化され最初と同じ値になったはずです。

147以外の数字を鍵にすると色んな値に復号され、どれが本物かわかんないですよね。公開鍵による暗号化と秘密鍵による復号化が成功しているみたいです。

色んな数字、いろんな巾乗でも試してみてください。 p*q と巾乗数を秘密鍵、公開鍵というようにペアーにして暗号化・復号化が出来ますね。

お詫び：今気づいたんですけどソフトで「復号化数」が「複合化数」と誤字になってました。済みません読み替えてください。

重要なところは、

暗号化する整数を何乗かしてある数で余りを求めると、元の数に戻る。
何乗かする数字を、もし２つの掛け算に分けることが出来たなら、片方の数で巾乗し暗号化、暗号化された数字をもう一方の数で巾乗し復号化できる。

というアイデアです。２つに分けられない場合は失敗となります。

色々なｎの値で試してみると、n*lcm(p-1,q-1)+1がうまく掛け算に分けられる場合と難しい場合があることがわかります。これが、大きな数字p,qで計算したなら尚更困難が予想されます。色々なnをあてずっぽうで試してみるわけにもいきません。しかし、二つの数の掛け算に分けられるようなｎを計算する方法があるのです。拡張ユークリッドの互除法と言う技法を使います。

その様子を以下のソフトで体験できます。

● ユークリッドの互除法.exe ～最大公約数を求める方法を利用して鍵を生成する。

上のRSA認証の基礎体験.exeをつかって、求めた数字から、鍵を生成しよう。

RSA認証の基礎体験.exeで、p,qを選び、(p-1)と(q-1)の最小公倍数をチェックします。それを、自然数aの欄に入力します。
自然数bに公開鍵に使いたい数を入れます。実際の暗号化には11とかがよく使われるようです。素数が使いやすいですが、自然数aとの最大公約数が１になるものなら自由に何でも使えます。（これは、aとb共通に割り切れる数が１以外ないという意味で「互いに素」である数と言います。）
数字を入れたら、ユークリッドの互除法（除算）をクリックして、最大公約数は１となる事を確認しましょう。ダメなら別の数字を試します。
自然数a,bが決まったら、拡張ユークリッドの互除法をクリックしましょう。

なんじゃこりゃ？と言う感じですが、やったことを箇条書きにまとめてみます。

RSA認証の基礎体験.exeで、p,qを決めました。それを使って、p*q を計算します。p*qは鍵の一部として利用します。

同じく、(p-1) と (q-1) の最小公倍数を求めておきます。

その最小公倍数を自然数a とし互いに素な自然数b を利用して「ある」計算をします。その計算から、自然数bを公開鍵とした場合の秘密鍵が導き出されます。

今回の例では

p 139 q 121 p*q 16819 (p-1) 138 と(q-1) 120 の最小公倍数は 2760 ここまでがRSA認証の基礎体験.exeで計算したこと。
その後、上で計算できた2760を自然数a に、自然数b には希望する公開鍵の値19をいれて計算
秘密鍵 2179を得る。

という流れ。

さて、それでは実際にこれが使えるのかどうか、実験します。RSA認証の基礎体験.exeにもどって

暗号化復号化数に適当な値。鍵～p*qに16819 鍵～巾数に19を入れて暗号化

出来た暗号で、鍵～巾数に2178を入れて復号化。

ちゃんと元に戻りましたか？

色んな数で遊んでみてください。

制作後記：

今回作った体験ソフトは２つに分ける必要はありませんでした。

ただ、以下のような理由であえて二つに分けました。

ユークリッドの互除法自体は古くから使われていた最大公約数を求める一般的な技法であること。

公開鍵と秘密鍵を使って暗号化・復号化が出来るんじゃないかという理論予測はあったが、それがどう実現されるのかは誰にもわからなかったところ、RSA認証という素数を使った計算で秘密鍵・公開鍵方式が実現できることに気づき、既にあった技法が非常にうまく利用されたこと。

この、非常にうまく利用された部分を遊びながら感じてほしいと考えたわけです。

ちなみにRSAはRivest、Shamir、Adleman 開発者各氏の頭文字で、1978年に開発されました。