RSA 介绍¶

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)}$
将 $p$ 和 $q$ 的记录销毁

此时， $(N,e)$ 是公钥， $(N,d)$ 是私钥。

消息加密¶

首先需要将消息以一个双方约定好的格式转化为一个小于 $N$ ，且与 $N$ 互质的整数 $m$ 。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：

$m^{e}\equiv c\pmod N$

消息解密¶

利用密钥 $d$ 进行解密。

$c^{d}\equiv m\pmod N$

正确性证明¶

即我们要证 $m^{ed} \equiv m \bmod N$ ，已知 $ed \equiv 1 \bmod \phi(N)$ ，那么 $ed=k\phi(N)+1$ ，即需要证明

$m^{k\phi(N)+1} \equiv m \bmod N$

这里我们分两种情况证明

第一种情况 $gcd(m,N)=1$ ，那么 $m^{\phi(N)} \equiv 1 \bmod N$ ，因此原式成立。

第二种情况 $gcd(m,N)\neq 1$ ，那么 $m$ 必然是 $p$ 或者 $q$ 的倍数，并且 $n=m$ 小于 $N$ 。我们假设

$m=xp$

那么 $x$ 必然小于 $q$ ，又由于 $q$ 是素数。那么

$m^{\phi(q)} \equiv 1 \bmod q$

进而

$m^{k\phi(N)}=m^{k(p-1)(q-1)}=(m^{\phi(q)})^{k(p-1)} \equiv 1 \bmod q$

那么

$m^{k\phi(N)+1}=m+uqm$

进而

$m^{k\phi(N)+1}=m+uqxp=m+uxN$

所以原式成立。

基本工具¶

RSAtool¶

安装

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¶

根据给定密钥对，生成 pem 文件
根据 $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。

分解整数工具¶

网站分解，factor.db
命令行分解，factordb-pycli，借用 factordb 数据库。
yafu

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 可知

$2^{eg}=2^{ed * (p-const)}=2^{p-const} \pmod n$

$2^{p-const} * 2^{const-1} = 2^{p-1} \pmod n$

所以

$2^{p-1} = 2^{eg} * 2^{const-1}+kn$

而与此同时根据费马小定理，我们知道

$2^{p-1} \equiv 1 \pmod p$

所以

$p|2^{p-1}-1 | 2^{eg+const-1}-1+kn$

进而

$p|2^{eg+const-1}-1$

所以

$p|gcd(2^{eg+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