たまにCTFをやるのですが、RSAの問題が全く解けないしRSAの原理も理解できないので、とりあえずネットで調べてRSAの暗号化と復号プログラムを作って（集めて？）みました。ちゃんと動いているので合っているとは思いますが、使用する時は自己責任でお願いします。

#公開鍵、秘密鍵を作る

まず公開鍵と秘密鍵を作っていきたいと思います。一応下のプログラムで公開鍵と秘密鍵を作れます。pythonのライブラリであるsympyとgmpyを利用しています。

import sympy
import gmpy
p = sympy.randprime(10000000,100000000)
q = sympy.randprime(10000000,100000000)
n = p*q
e = 65537
l = (p-1)*(q-1)
d = gmpy.invert(e,l)

pとqは素数で、これが盗聴者に知られると暗号解読されますので、絶対バレないように隠します。なお（pとqが近いと解読され易い等）作り方が悪いと脆弱性が発生するそうです。よって真面目にRSAを勉強する時はちゃんとしたサイトで勉強し、正しいパラメータを設定し、脆弱性がないことをチェックしてください。今回は動作を理解するだけなので、適当なパラメータ設定をしています。

nはpとqを掛け合わせた数値です。暗号化する平文の最大長に関与します。これより長い平文を使用するときは、平文をこのnに収まるように分割して、複数回暗号化します。

eはpとqと互いに素である素数であり、自分が好きに決める数値となります。理由はわかりませんが65537が多いです。eが小さ過ぎる・大き過ぎるとこれまた脆弱性になるそうです。
この(n,e)の組が公開鍵になります。

lは(p-1)*(q-1)の値で、dを求めるだけの変数です。

dはlとeから逆行列を計算した結果です。
このdが秘密鍵になります。なおdとnで暗号文を復号するので(n,d)が秘密鍵と書いてあるサイトもあります。

#平文の暗号化

下のプログラムで平文を暗号化できます。

暗号化処理

message = 'Hello'
m = eval('0x' + message.encode().hex())
c = pow(m,e,n)

文字列のままだと暗号化できないので数値に変換します。やり方は（上の例では）平文である文字列Helloを16進数のバイナリデータ68656c6c6fに変換し、文字列0x68656c6c6fに更に変換してから10進数にして変数mに入れています。

この変数mの値をe乗して、その結果に対しnの剰余（あまり）を求めたものが暗号文cになります。

#暗号文を復号

下のプログラムで暗号文を復号できます。codecsライブラリを使います。

復号処理

import codecs
m2 = pow(c,d,n)
print(codecs.decode(hex(m2)[2:],'hex'))

暗号文cの値をd乗し、その結果に対しnの剰余（あまり）を変数m2に入れています。

変数m2の値を16進数にしてASCIIコードに変換したものが復号された平文になります。

#おまけ

gmpyのインストールに手間取ったので、私がうまくインストールできたときのコマンドを記載します。当然環境によってはライブラリが足りずインストールできない場合があるのでご了承ください。

gmpyのインストール

sudo apt-get install python-dev libgmp3-dev
sudo pip install gmpy