RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。
RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。
基本原理
公钥与私钥的产生
随机选择两个不同大质数 $p$ 和 $q$，计算 $N = p \times q$
根据欧拉函数，求得 $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$
选择一个小于 $\varphi (N)$ 的整数 $e$，使 $e$ 和 $\varphi (N)$ 互质。并求得 $e$ 关于 $\varphi (N)$ 的模反元素，命名为 $d$，有 $ed\equiv 1 \pmod {\varphi (N)}$
此时，$(N,e)$ 是公钥，$(N,d)$ 是私钥。
消息加密
首先需要将消息 以一个双方约定好的格式转化为一个小于 $N$，且与 $N$ 互质的整数 $m$。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：
me≡c(modN) 消息解密
利用密钥 $d$ 进行解密。
cd≡m(modN) 正确性证明
即我们要证$m^{ed} \equiv m \bmod N$，已知$ed \equiv 1 \bmod \phi(N)$，那么 $ed=k\phi(N)+1$，即需要证明
mkϕ(N)+1≡mmodN 这里我们分两种情况证明
第一种情况 $gcd(m,N)=1$，那么 $m^{\phi(N)} \equiv 1 \bmod N$，因此原式成立。
第二种情况 $gcd(m,N)\neq 1$，那么 $m$ 必然是 $p$ 或者 $q$ 的倍数，并且 $n=m$ 小于 $N$。我们假设
那么 $x$ 必然小于 $q$，又由于 $q$ 是素数。那么
mϕ(q)≡1modq 进而
mkϕ(N)=mk(p−1)(q−1)=(mϕ(q))k(p−1)≡1modq 那么
mkϕ(N)+1=m+uqm 进而
mkϕ(N)+1=m+uqxp=m+uxN 所以原式成立。
基本工具
安装
git clone https://github.com/ius/rsatool.git
cd rsatool
python rsatool.py -h
生成私钥
python rsatool.py -f PEM -o private.pem -p 1234567 -q 7654321
RSA Converter
根据 $n$，$e$，$d$ 得出 $p$，$q$
openssl
查看公钥文件
openssl rsa -pubin -in pubkey.pem -text -modulus
解密
rsautl -decrypt -inkey private.pem -in flag.enc -out flag
更加具体的细节请参考 openssl --help。
分解整数工具
python 库
primefac
整数分解库，包含了很多整数分解的算法。
gmpy
gmpy.root(a, b)，返回一个元组 (x, y)，其中 x 为 a 开 b 次方的值，y 是判断 x 是否为整数的布尔型变量
gmpy2
安装时，可能会需要自己另行安装 mpfr 与 mpc 库。
gmpy2.iroot(a, b)，类似于 gmpy.root(a,b)
pycrypto
安装
sudo pip install pycrypto
使用
import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
msg = 'crypto here'
p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
privatekey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_v1_5.new(pubkey)
enc = key.encrypt(msg).encode('base64')
key = PKCS1_v1_5.new(privatekey)
msg = key.decrypt(enc.decode('base64'), e)
Jarvis OJ - Basic - veryeasyRSA
p = 3487583947589437589237958723892346254777 q = 8767867843568934765983476584376578389
e = 65537
求 d =
请提交 PCTF{d}
直接根据 $ed\equiv 1 \pmod{\varphi (N)}$，其中 $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$，可得 $d$。
import gmpy2
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
phin = (p - 1) * (q - 1)
print gmpy2.invert(e, phin)
➜ Jarvis OJ-Basic-veryeasyRSA git:(master) ✗ python exp.py
19178568796155560423675975774142829153827883709027717723363077606260717434369
2018 CodeGate CTF Rsababy
程序就是一个简单的 RSA，不过程序还生成了两个奇怪的数
e = 65537
n = p * q
pi_n = (p-1)*(q-1)
d = mulinv(e, pi_n)
h = (d+p)^(d-p)
g = d*(p-0xdeadbeef)
所以，问题应该出自这里，所以我们就从此下手，不放这里先假设 const = 0xdeadbeef。那么
eg=ed∗(p−const) 进而，根据 RSA 可知
2eg=2ed∗(p−const)=2p−const(modn) 2p−const∗2const−1=2p−1(modn) 所以
2p−1=2eg∗2const−1+kn 而与此同时根据费马小定理，我们知道
2p−1≡1(modp) 所以
p∣2p−1−1∣2eg+const−1−1+kn 进而
p∣2eg+const−1−1 所以
p∣gcd(2eg+const−1−1,n) 因此，代码如下
tmp = gmpy2.powmod(2,e*g+const-1,n)-1
p = gmpy2.gcd(tmp,n)
q = n/p
phin = (p-1)*(q-1)
d =gmpy2.invert(e,phin)
plain = gmpy2.powmod(data,d,n)
print hex(plain)[2:].decode('hex')
2018 国家安全周 pure math
题目的基本描述是这个样子的
1) p ** p % q = 1137973316343089029387365135250835133803975869258714714790597743585251681751361684698632609164883988455302237641489036138661596754239799122081528662395492
2) q ** q % p = 6901383184477756324584651464895743132603115552606852729050186289748558760692261058141015199261946483809004373728135568483701274908717004197776113227815323
3) (p ** q + q ** p) % (p*q) = 16791287391494893024031688699360885996180880807427715700800644759680986120242383930558410147341340225420991368114858791447699399702390358184412301644459406
4) (p+q) ** (p+q) % (p*q) = 63112211860889153729003401381621068190906433969243079543438386686621389392583849748240273643614258173423474299387234175508649197780206757067354426424570586101908571600743792328163163458500138799976944702155779196849585083397395750018148652864158388247163109077215394538930498877175474225571393901460434679279
5) FLAG ** 31337 % (p*q) = 6931243291746179589612148118911670244427928875888377273917973305632621316868302667641610838193899081089153471883271406133321321416064760200919958612671379845738048938060512995550639898688604592620908415248701721672948126507753670027043162669545932921683579001870526727737212722417683610956855529996310258030
Now, what’s the FLAG???
我们的目的基本上就是求得 FLAG，那么怎么做呢?这个题目需要我们具有较好的数论功底。
根据题目中这样的内容，我们可以假设 $p$，$q$ 都是大素数，那么
$p^{q-1} \equiv 1\bmod q$
那么
$p^{q} \equiv p \bmod pq$
那么我们可以根据 3）知道
$p^q+q^p \equiv p+q \bmod pq$
而 $p+q$ 又显然小于 $pq$，所以我们就知道 $p+q$ 的数值。
进一步，我们假设1），2），3），4），5）对应的值分别为 $x_1$, $x_2$, $x_3$, $x_4$, $x_5$ 则
根据4），我们可以知道
$(p+q)^{p+q} \equiv p^{p+q}+q^{p+q} \bmod pq$
又因为1）和 2），则
$p^pp \equiv px_1\bmod pq$
$q^qq \equiv qx_2 \bmod pq$
因此
$px_1+qx_2 \equiv x_4 \bmod pq$
根据 $x_1$ 和 $x_2$ 的求得方式，我们可以知道这里也是等号，因此我们得到了一个二元一次方程组，直接求解即可。
import gmpy2
x1 = 1137973316343089029387365135250835133803975869258714714790597743585251681751361684698632609164883988455302237641489036138661596754239799122081528662395492
x2 = 6901383184477756324584651464895743132603115552606852729050186289748558760692261058141015199261946483809004373728135568483701274908717004197776113227815323
p_q = 16791287391494893024031688699360885996180880807427715700800644759680986120242383930558410147341340225420991368114858791447699399702390358184412301644459406
x4 = 63112211860889153729003401381621068190906433969243079543438386686621389392583849748240273643614258173423474299387234175508649197780206757067354426424570586101908571600743792328163163458500138799976944702155779196849585083397395750018148652864158388247163109077215394538930498877175474225571393901460434679279
if (x4 - x1 * p_q) % (x2 - x1) == 0:
print 'True'
q = (x4 - x1 * p_q) / (x2 - x1)
print q
p = p_q - q
c = 6931243291746179589612148118911670244427928875888377273917973305632621316868302667641610838193899081089153471883271406133321321416064760200919958612671379845738048938060512995550639898688604592620908415248701721672948126507753670027043162669545932921683579001870526727737212722417683610956855529996310258030
phin = (p - 1) * (q - 1)
d = gmpy2.invert(31337, phin)
flag = gmpy2.powmod(c, d, p * q)
flag = hex(flag)[2:]
print flag.decode('hex')
flag 如下
➜ 2018-国家安全周第一场-puremath git:(master) ✗ python exp.py
True
7635093784603905632817000902311635311970645531806863592697496927519352405158721310359124595712780726701027634372170535318453656286180828724079479352052417
flag{6a66b8d5-6047-4299-a48e-4c4d1f874d12}
2018 Pwnhub LHY
首先分析这段代码
assert gmpy.is_prime(y)**2016 + gmpy.is_prime(x + 1)**2017 + (
(x**2 - 1)**2 % (2 * x * y - 1) + 2
)**2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146
由于 gmpy.is_prime 要么返回1，要么返回 0，所以我们可以很容易地试出来 y 是素数，x+1 也是素数，并且
$(x^2-1)^2\equiv 0 \bmod (2xy-1)$
为了式子能够整除，猜测 $x=2y$ 。
于是，对于下面的内容
p = gmpy.next_prime(x**3 + y**3)
q = gmpy.next_prime(x**2 * y + y**2 * x)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy.invert(0x10001, phi)
enc = pow(bytes_to_long(flag), 0x10001, n)
print 'n =', n
print 'enc =', enc
$p$ 和 $q$ 自然为
$p=next_prime(9y^3)$
$q=next_prime(6y^3)$
根据素数的间隔，可以知道 $p$ 和 $q$ 最多比括号里的数字大一点，这里一般不会超过 $1000$。
那么
$n \geq 54y^6$
所以我们知道了 $y$ 的上界，而对于 $y$ 的下界其实也不会离上界太远，我们大概减个几十万。进而，我们利用二分查找的方式来寻找 $p$ 和 $q$，如下
import gmpy2
tmp = 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146
print gmpy2.iroot(tmp, 2018)
print gmpy2.iroot(tmp - 1, 2018)
print gmpy2.iroot(tmp - 2, 2018)
n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741
y = 191904757378974300059526915134037747982760255307942501070454569331878491189601823952845623286161325306079772871025816081849039036850918375408172174102720702781463514549851887084613000000L
y = gmpy2.next_prime(y)
enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612
end = gmpy2.iroot(n / 54, 6)[0]
beg = end - 2000000
mid = 1
while beg < end:
mid = (beg + end) / 2
if gmpy2.is_prime(mid) != 1:
mid = gmpy2.next_prime(mid)
p = gmpy2.next_prime(9 * mid**3)
q = gmpy2.next_prime(6 * mid**3)
n1 = p * q
if n1 == n:
print p, q
phin = (p - 1) * (q - 1)
d = gmpy2.invert(0x10001, phin)
m = gmpy2.powmod(enc, d, n)
print hex(m)[2:].strip('L').decode('hex')
print 'ok'
exit(0)
elif n1 < n:
beg = mid
else:
end = mid
print beg, end