スポンサーリンク
はじめに
公開鍵暗号の１つである「RSA暗号」について理解を深めるため、実装してみました。
RSA暗号では、公開鍵・秘密鍵が存在します。
サーバーに公開鍵を公開しておき、それをクライアントがダウンロードし、公開鍵で送信したいデータを暗号化してサーバーに送信します。
それを受け取ったサーバーは、秘密鍵を使用して、クライアントが送って来た暗号を復号化して、生のデータを取り出します。
RSA暗号はSSLなどに使用されています。SSL通信を開始するときはRSA暗号によってサーバー・クライアント間で共通鍵を受け渡しします。ただ、RSA暗号の処理は少々重いです。そのため、共通鍵を共有した後は、RSA暗号よりも処理が軽い共通鍵暗号で通信を行うようになります。
このように、SSLでは共通鍵が漏洩しないように受け渡しするためにRSA暗号が使われています。
それでは、どのようにRSA暗号を使用すればよいのでしょうか。
スポンサーリンク鍵を作成する
RSA暗号を使用する第一歩は、鍵を生成することです。
まず、非常に大きな素数p,qを２つ持ってきます。
ここでは$$p=9806359, q=3756671$$としましょう。（実用上は数百桁必要です。）
次に、「ちょうどいい大きさ」の、(p-1)(q-1)と互いに素な整数eを持ってきます。普通e=65537 (2^16+1)が使われるため、ここではそれを使用します。
次に、$$d=e^{-1} ({\rm mod} (p-1)(q-1))$$となる整数dを持ってきます。
「eは分数(1/65537)なのに、それと剰余が等しいdって何？」と思ってしまいますが、これはモジュラ逆数というものとなります。$$de=1 ({\rm mod} (p-1)(q-1))$$となるdを求めることになります。
モジュラ逆数の求め方
$$de=1 ({\rm mod} (p-1)(q-1))$$を変形すると、
$$de - 1 = x(p-1)(q-1)$$
ただしxは整数。さらに変形して
$$de - x(p-1)(q-1) = 1$$
この形は一次不定方程式なので、拡張ユークリッド互除法によってd,xが求まります（xは不要ですが）。おそらく、センター試験の数学Ⅰ・Aで似た問題を解いたことがある方は多いかと思います。
ここではコンピュータに解かせるため、アルゴリズムを言語で記述する必要があります。今回はPythonを使用して作成していきます。
わかりやすくするため、$$ax+by=1$$を満たすx,yを求める関数を書いていきます。
aをbで割ったとき、aを$$a=kb+r$$と表して代入・整理すると$$b(kx+y)+rx=1$$となります。
a←b, x←kx+y, b←r, y←x の変換を（同時に）行うと、$$ax+by=1$$という元の問題に戻ります。これにより、再帰的な関数を使用して解を求めることができます。
また、b=0となった時、再帰を終了させます。その時、$$a\cdot x + 0\cdot y = {\rm gcd}$$となっているので、x=1,y=0となります(b>rより、xの方が1となることがわかります)。
ここで、わかりやすくするため、１段階下の再帰部分でのx,yをs,tとおきます。
再帰が最も深くなった後、今度は１段ずつ上ってきます。この時、$$x=t, y=s-(a//b)\cdot x$$（a//bはPythonの表記でa÷bの整数部分 C言語などではa/b）という関係が成り立つため、１段下のx,yの情報から、その上の段のx,yの情報を得られるということになります。これは、x←kx+y, y←xの変換によるものです（実際にアルゴリズムをメモに書きながら手動でやってみると、その関係性が確認できます）。
実際に作成したPythonのコードを載せておきます。
def my_exe(a,b):
if(b==0):
return 1,0
s,t = my(b,a%b)
x = t
y = s-a//b*x
return x,y
x,y = my_exe(37,7)
print(x)
print(y)
-3
16
という出力が得られます。
$$37\cdot (-3)+7\cdot 16=1$$が成り立つので、合っていそうですね。37も7も素数なので、最大公約数は1となります。
参考：拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita
---------------------------------
モジュラ逆数は求まることが分かったので、dを求めます。
d,_=my_exe(e,(p-1)*(q-1))
d %= (p-1)*(q-1) # マイナス対策
とすることでdが求まります。この場合ではd=19604280248753となりました。１行目だけではdがマイナスになることがあるため、関係式が成り立つのを保ったままdを正に変換する対策を入れています。
eとnのセットが公開鍵、dを秘密鍵となります。
いよいよ準備が整いました。次のページでは暗号文を作成していきます。