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


スポンサーリンク

暗号化する

文字列を送る場合はASCIIコードで変換を行う場合が多いと思いますが、今回は簡単にするため、数字列を送ることとします。

暗号化は$$c=m^e{\rm mod}\, n$$で行います。cが暗号文、mが送りたい数字列、nがp*qです。

幸い、Pythonにはこれを簡単に計算してくれる機能がありますので、利用させてもらいます。
ちなみに、手動で実装する場合、このような「冪剰余」は、$$m^e$$を計算してから剰余をとる方法ではなく、$$(m\, {\rm mod}\, n)\cdot (m\, {\rm mod}\, n)\cdot (m\, {\rm mod}\, n) \cdots$$のように、かけていく途中で毎回剰余をとることで、効率的に簡単に計算できます。さもないと、非常に大きな数を扱うことになり、うまく計算できません。

それでは、送りたい数字列mは1234567890とします。

c = pow(m,e,p*q)
print(c)

を実行すると、ここでは12836671279919となりました。これが、ネットを飛び交う暗号文となるわけですね。ちなみに、あまり大きすぎる数字列は暗号化できません。0以上n未満の数字列を暗号化可能です。

復号化する

それでは暗号文を復号化していきます。

復号化は$$m=c^d{\rm mod}\, n$$で行います。mが復号化された数字列、cが暗号文、nがp*qです。

暗号化と同様にPythonで計算していきます。

m2 = pow(c,d,p*q)
print(m2)

これで、1234567890という平文が表示されたはずです。
おめでとうございます!

最後に

RSA暗号などの公開鍵暗号のおもしろさは、暗号化と復号化のためにそれぞれ違う鍵を使うという点が大きいと思います。巨大な数の素因数分解が困難であるという性質を利用して一方通行の暗号を作り出した先人たちの功績は非常に素晴らしいものだったと思います。

ちなみに、RSA署名というものが存在します。これは秘密鍵を持っているのはサーバーだけであるということを利用して、秘密鍵でデータを署名、公開鍵で署名を検証することで、データが正しいサーバーから送られていることを、クライアントが確認することもできます。

暗号化は$$c=m^e{\rm mod}\, n$$復号化は$$m=c^d{\rm mod}\, n$$という計算式ですが、非常に対称性の高い式となっています。これを使用して署名もできるということになっています。

RSA暗号の使用はいくつか注意点などがありますが、この記事では省略させていただきます。詳しくはWikiなどをご覧ください。

何かおかしなところがあれば、ご指摘いただけると嬉しいです。

最後までご覧いただきありがとうございました。

スポンサーリンク

参考

拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 - Qiita

RSA暗号 - Wikipedia

この記事への感想を教えてください
  • 内容が十分
  • 内容が足りなかったが役立った
  • 内容が足りず役立たなかった
  • 求めている記事ではなかった
last

フォローする