RSA
- 隨意選擇兩個大的質數p和q，p不等於q，計算N=pq
- 根據歐拉函數，求得r = Ψ(N) = lcm(Ψ(p), Ψ(q)) = (p-1)*(q-1)
- 選擇一個小於r的整數e，使e與r互質。並求得e關於r的模反元素，命名為d（求d令 ed mod r == 1）。（模反元素存在，若且唯若與互質）
- 將p和q的記錄銷毀。
(N, e)是公鑰，(N, d)是私鑰。Alice將她的公鑰(N, e)傳給Bob，而將她的私鑰(N, d)藏起來
加密訊息
假設Bob想給Alice送一個訊息m，他知道Alice產生的N和e。他使用起先與Alice約好的格式將轉換為一個小於的非負整數，比如他可以將每一個字轉換為這個字的Unicode碼，然後將這些數字連在一起組成一個數字。假如他的訊息非常長的話，他可以將這個訊息分為幾段，然後將每一段轉換為n。用下面這個公式他可以將加密為：
c = n^e mod N
計算並不複雜。Bob算出後就可以將它遞移給Alice
解密訊息
Alice得到Bob的訊息後就可以利用她的金鑰d來解碼。她可以用以下這個公式來將c轉換為n： n = c^d mod N
得到後，她可以將原來的訊息m重新復原。
在Python中：
import gmpy2
d = gmpy2.invert(e, r)
e = gmpy2.invert(d, r)
以BUUCTF的RSA为例
题目提供一个公钥文本文件pub.key和一个二进制数据文件flag.enc。 在这里我们主要是在得到私钥以后用python的rsa模块解密二进制数据文件，得到字节流。
从http://tool.chacuo.net/cryptrsakeyparse 可以从公钥文本文件提取出n和e
从http://www.factordb.com/index.php 可以进行数数分解，得到p和q
exp如下：
import gmpy2
import rsa
import math
# <http://tool.chacuo.net/cryptrsakeyparse> to parse pub.key
# <http://www.factordb.com/index.php> to factor big prime
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
e = 65537
n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
r = (p-1)*(q-1)
d = gmpy2.invert(e, r)
key = rsa.PrivateKey(n, e, int(d), p, q)
with open("./flag.enc", "rb+") as f:
f = f.read()
print(rsa.decrypt(f, key))这里的rsa模块封装了加解密二进制文件的细节，目前没有搞明白它是如何处理文件的。