ユークリッド互除法をつかいRSA暗号で秘密鍵と公開鍵のペアを求める方法
しょうがくせい向けRSA暗号では秘密鍵と公開鍵のペアを作る為のユークリッド互除法についてはあまり触れませんでした。
ここでは実例をあげて説明します。
RSA暗号で素数p＝7、q＝11で選ぶと合成数n＝77となる。
公開鍵をe＝7とする時、オイラー関数＝(pー1)(qー1)を用いて秘密鍵dをeの逆数を
求めるやり方(＝ユークリッドの互除法)で求めよ。
まずさいごに求める秘密鍵が正しいかどうかは以下の計算で確かめられます。
ある77未満の数をAとすると
(A^7)mod77で暗号数が求められ
(暗号数^秘密鍵)mod77がもとのAになること(^は累乗、modは剰余とします）
ここでの秘密鍵ですが実は複数あるのです。その条件とは
「公開鍵7にその秘密鍵をかけて(p-1)(q-1)で割ると1になること」です。
(p-1)(q-1)はすなわち6x10=60ですね。つまり7にある数をかけると60の倍数＋1、例えば61や121などになるということです。
7x○=60x△+1ということですね。
そんな組み合わせを求める一つの方法がユークリッド互除法です。
この場合だと7x○=60x△+1を変形して7x○-60x△=1の組み合わせを求めることになります。
やり方は、上記の形でいう7と60の部分の数を「大きい方を小さい方で割る余りを出す」「先ほどの小さい方を余りでわる」作業を繰り返すことで行います。やってみましょう。
60を7でわると8あまり4。つまり4とは(60-7x8)
7を4でわると1あまり3。つまり3とは(7-4x1)
4を3でわると1あまり1。つまり1とは(4-3x1)
最後の行は式で表すと4-3x1=1ですね。目的の7x○-60x△=1と右辺だけは同じです。これをタネとして4-3x1の部分を7と60のかけ算の組み合わせにしていきます。具体的には上の過程で得られた「・・とは・・」の情報を使って置換していく作業です。
4-3x1=1の4の部分を置換してみましょう。4とは(60-7x8)なので
(60-7x8)-3x1=1
次は3の部分です。3とは(7-4x1)でなので
(60-7x8)-(7-4x1)x1=1
もう一息です。4が邪魔なので同じく置換します。4とは(60-7x8)なので
(60-7x8)-(7-(60-7x8)x1)x1=1
無事すべての項が7か60のかけ算になりました。7と60を崩さないように注意して整理すると
7x(-17)+60x(2)=1
60x(2)の符号を反転させて
7x(-17)-60x(-2)=1
これで今回ユークリッド互除法を使う目的である7x○-60x△=1の形になりました。
先ほども触れましたが組み合わせは複数あります。組み合せのバリエーションを増やすには上記の式に7と60を組み合わせた7x60-60x7を足し引きします。7x60-60x7は足して0なので左辺にいくら足しても右辺は変わりませんよね。
一回足すと
7x(43)-60x(5)=1
になりました。変形すると7x(43)=60x(5)+1、つまり7に43をかけると60の倍数＋1になるということです。試しに計算すると301で確かに60の倍数+1ですね。
これで最初の問題である「公開鍵7にその数をかけて(p-1)(q-1)すなわち60で割ると1になる数」である43が求まりました。
確かめましょう。たとえば3という数を暗号化するとして(3^7)mod77→31、31を秘密鍵43で復号化するとして(31^43)mod77→3。無事もとの3に戻りました。
ユークリッド互除法以外の部分に関しては以下を参照してみてください。
