RSA暗号を実装してみた @Python


スポンサーリンク

はじめに

公開鍵暗号の1つである「RSA暗号」について理解を深めるため、実装してみました。

RSA暗号では、公開鍵・秘密鍵が存在します。
サーバーに公開鍵を公開しておき、それをクライアントがダウンロードし、公開鍵で送信したいデータを暗号化してサーバーに送信します。
それを受け取ったサーバーは、秘密鍵を使用して、クライアントが送って来た暗号を復号化して、生のデータを取り出します。

RSA暗号はSSLなどに使用されています。SSL通信を開始するときはRSA暗号によってサーバー・クライアント間で共通鍵を受け渡しします。ただ、RSA暗号の処理は少々重いです。そのため、共通鍵を共有した後は、RSA暗号よりも処理が軽い共通鍵暗号で通信を行うようになります。

このように、SSLでは共通鍵が漏洩しないように受け渡しするためにRSA暗号が使われています。

それでは、どのようにRSA暗号を使用すればよいのでしょうか。

スポンサーリンク

鍵を作成する

RSA暗号を使用する第一歩は、鍵を生成することです。

まず、非常に大きな素数p,qを2つ持ってきます。
ここでは$$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となることがわかります)。

ここで、わかりやすくするため、1段階下の再帰部分でのx,yをs,tとおきます。

再帰が最も深くなった後、今度は1段ずつ上ってきます。この時、$$x=t, y=s-(a//b)\cdot x$$(a//bはPythonの表記でa÷bの整数部分 C言語などではa/b)という関係が成り立つため、1段下の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となりました。1行目だけではdがマイナスになることがあるため、関係式が成り立つのを保ったままdを正に変換する対策を入れています。

eとnのセットが公開鍵、dを秘密鍵となります。
いよいよ準備が整いました。次のページでは暗号文を作成していきます。

last

フォローする