CTF中的RSA及攻击方法笔记 – 作者:ATL安全团队-安全小百科

本文结合许多当下互联网存在的资料整理出了自己对RSA的一份笔记，本版只是初版，对许多东西还有待补充。

本文所有的解题脚本都经过本人亲自尝试，环境都是Python3，用到的Python库是pycrypto和gmpy2两个。

备注：因平台检测C和4连接词，因此改为C四

数论

模运算规则:

模运算与基本四则运算有些相似，但是除法例外。其规则如下:

(a + b) % p = (a % p + b % p) % p
(a – b) % p = (a % p – b % p) % p
(a * b) % p = (a % p * b % p) % p
(a ^ b) % p = ((a % p)^b) % p

结合律：

((a+b) % p + c) % p = (a + (b+c) % p) % p
((a*b) % p * c)% p = (a *(b*c)%p) % p

交换律：

(a + b) % p = (b + a) % p
(a * b) % p = (b * a) % p

分配律：

((a +b)% p * c) % p = ((a * c) %p + (b * c) % p) % p

重要定理：

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
若a≡b (% p)，则对于任意的正整数c，都有(a * c) ≡ (b * c) (%p)
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a – c) ≡ (b – d) (%p)，
(a * c) ≡ (b * d) (%p)

最大公因子

两个数互素是指：除了它们除了1外没有共同的因子。如果a和n的最大公因子等于1，那么可写作

$gcd(a,n)=1$

欧几里得算法

又称碾转相除法，我们通常使用该方法计算最大公因子。

欧几里得扩展算法

如果gcd(a, b) = c，则存在x, y，使得c = ax + by。

同余

两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。记作：a≡b (mod m)，读作：a同余于b模m，或读作a与b对模m同余，例如26≡2(mod 12)。

模的逆元

简单来说，求a的逆，就是找一个 $x$，使得$1 = (a*x){\pmod n}$

也可记作 $a^{-1} \equiv x{\pmod {n}}$

费马小定理和欧拉定理

费马小定理是数论中的一个定理：假如 ${a}$ 是一个整数，${p}$ 是一个质数，那么${a^{p}-a}$是 $p$ 的倍数，可以表示为 $$a^{p}\equiv a{\pmod {p}}$$ 如果a不是p的倍数，这个定理也可以写成 $$a^{{p-1}}\equiv 1{\pmod {p}}$$ 欧拉定理若$n,a$为正整数，且$n,a$互素（即$gcd(a,n)=1$），那么 $$a^{{\varphi (n)}}\equiv 1{\pmod n}$$

因为欧拉定理是费马小定理的推广，所以欧拉定理的条件对任意互素的a和n与费马小定理的条件若p是素数，a是正整数且不能被p整除相比不可能是缩小范围。

可参考：https://www.cnblogs.com/nysanier/archive/2011/04/12/2014000.html

中国剩余定理

可参考：https://blog.csdn.net/u010468553/article/details/38346195/

RSA原理+基础题目

参考1：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory-zh/ 参考2：https://bbs.pediy.com/thread-263069.htm 基于大整数因数分解难题。

BUUCTF-RSA

题目描述：

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17，求解出d作为flag提交

解题：

import gmpy2
p,q,e = 473398607161, 4511491, 17
phi = (p-1) * (q-1)
d = gmpy2.invert(e, phi)
print(d)

BUUCTF-rsarsa

题目描述：

Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

Use RSA to find the secret message

RSA+数论

2018 CodeGate CTF Rsababy

题目描述：

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)

解析参看：

https://github.com/ashutosh1206/Crypto-CTF-Writeups/tree/master/2018/Codegate-CTF-Preliminary/RSAbaby

解题：

from Crypto.Util.number import *
# g,N,Encrypted_Data已知
e = 65537

# Using Euler’s Theorem and Fermat’s Little Theorem we have
t1 = pow(2, e*g, N)
t2 = pow(2, 0xdeadbeef, N)
p = GCD((t1*t2)-2,N)

assert N % p == 0
q = N / p
phin = (p-1)*(q-1)
d = inverse(e, phin)
m = pow(Encrypted_Data, d, N)
print long_to_bytes(m)

模相关攻击

暴力分解N

可攻击特征

在 N 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 p 和 q。

攻击方法

大整数分解一般有以下两种方法：

在线数据库查询：http://factordb.com/
yafu工具

JarvisOJ – Easy RSA

题目描述：

还记得 veryeasy RSA 吗？是不是不难？那继续来看看这题吧，这题也不难。
已知一段 RSA 加密的信息为：0xdc2eeeb2782c 且已知加密所用的公钥：
N=322831561921859 e = 23
请解密出明文，提交时请将数字转化为 ascii 码提交
比如你解出的明文是 0x6162，那么请提交字符串 ab
提交格式：PCTF{明文字符串}

解题：

# 经过 http://factordb.com/ 查询得出：322831561921859<15> = 13574881 · 23781539
from Crypto.Util.number import long_to_bytes
import gmpy2

p,q = 13574881,23781539
n = q*p
e = 23
c = 0xdc2eeeb2782c
phi = (q-1) * (p-1)
d = gmpy2.invert(e,phi)
m = gmpy2.powmod(c,d,n)
m = long_to_bytes(m)
print(m)

多因子

可攻击特征

N可被分解为多个素数

原理

如果选取两个以上的素数，记为 $p1,p2,p3…$，它们相乘得到 nn，那么：

$φ(n)=(p1−1)(p2−1)(p3−1)$

公钥、私钥、加解密都与一般 RSA 相同。

选取多因子，虽然会减少生成密钥的时间，但同样也更容易被破解。

2018 picoctf：Super Safe RSA 3

题目

每次nc连接可以获得不同的 cc、nn、ee。

例如一次连接中：

c: 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
n: 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
e: 65537

解题

首先用yafu经过多次分解直到所有因子都为素数，可以得到 32 个素数因子，然后直接求解即可：

from Crypto.Util.number import *
import gmpy2

c = 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
n = 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
e = 65537
factors = [2209835647, 3279221983, 2203115203, 3083863231, 2624125561, 4051923611, 3870883097, 3919135769, 3746033843, 2349626557, 2911452569, 2280078727, 3772965367, 2486744167, 3816147749, 2613884417, 2657517431, 2808514571, 3516405091, 3393739981, 2965911017, 2282964227, 2794765357, 2162896789, 4177000211, 2804308609, 2549752151, 2206071653, 2336473199, 2647948099, 3656705023, 2574736709]
phi = 1
for x in factors:
phi *= (x-1)
d = gmpy2.invert(e, phi)
print long_to_bytes(pow(c, d, n))

p或q选取不当分解N

当 RSA 中 p 和 q 选取不当时，我们也可以进行攻击。比如一般有以下四种情况

$|p-q|$ 很大

当$|p-q|$ 很大时，那么其中p或q有一个值一定很小，我们可以用试除法穷举p或q。

$|p-q|$ 较小

参考：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_module_attack-zh/#p-q_1

例题：[GWCTF 2019]BabyRSA

[GWCTF 2019]BabyRSA

题目描述：

import hashlib
import sympy
from Crypto.Util.number import *

flag = ‘GWHT{******}’
secret = ‘******’

assert(len(flag) == 38)

half = len(flag) / 2

flag1 = flag[:half]
flag2 = flag[half:]

secret_num = getPrime(1024) * bytes_to_long(secret)

p = sympy.nextprime(secret_num)
q = sympy.nextprime(p)
N = p * q
e = 0x10001

F1 = bytes_to_long(flag1)
F2 = bytes_to_long(flag2)

c1 = F1 + F2
c2 = pow(F1, 3) + pow(F2, 3)
assert(c2 < N)

m1 = pow(c1, e, N)
m2 = pow(c2, e, N)

output = open(‘secret’, ‘w’)
output.write(‘N=’ + str(N) + ‘\n’)
output.write(‘m1=’ + str(m1) + ‘\n’)
output.write(‘m2=’ + str(m2) + ‘\n’)
output.close()

题目解析：

因为p和q相差较小，一般来说相差千万都是比较小的，可以有两种解法

我们对N开根号，然后从$\sqrt N$ 到$N$依此遍历
yafu分解

解题：

import gmpy2
from Crypto.Util.number import isPrime, long_to_bytes
from z3 import *

N = 636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
e = 65537

m1 = 90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
m2 = 487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546

sqrt_N = gmpy2.iroot(N, 2)[0]

for i in range(sqrt_N, N):
if isPrime(i):
if N % i == 0:
p = i
q = N // i
break

phi = (p – 1) * (q – 1)
d = gmpy2.invert(e, phi)
c1 = gmpy2.powmod(m1, d, N)
c2 = gmpy2.powmod(m2, d, N)

# 当前半部分计算出a和b后，使用z3分解
s = Solver()
F1, F2 = Ints(‘F1 F2’)
s.add(F1 + F2 == 2732509502629189160482346120094198557857912754)
s.add(F1 ** 3 + F2 ** 3 == 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554)
if s.check() == sat:
F1 = (s.model()[F1]).as_long()
F2 = (s.model()[F2]).as_long()

flag1 = long_to_bytes(F1)
flag2 = long_to_bytes(F2)
flag = flag1 + flag2
print(flag)

$p-1$光滑或$p+1$光滑

光滑数（Smooth Number）指可以分解为小素数乘积的正整数。

当 p 是 N 的因数，并且 $p−1$ 是光滑数，可能可以使用 Pollard’s p − 1 算法来分解 N。

原理

根据费马小定理：

如果p是一个素数，而整数a不是p的倍数，则有 $a^{p-1} \equiv 1 \bmod p$

则：$a^{t(p-1)} \equiv 1^t \equiv 1 \bmod p$

可改为等式：$a^{t(p-1)} – 1 = k * p$

即$a^{t(p-1)} – 1$是p的倍数。

然后根据 Pollard’s p – 1 算法：

如果 p−1 是一些很小质数的乘积，那么 n! 就能被 p−1 整除。即 n!=t(p−1)。

对于每一个 n=2,3,4,…，任意选择一个底数 a（事实上，可以简单地选择为 2），并计算：

$gcd(a^{n!} – 1, N)$

如果结果不为 1 或 NNN，那么就已成功分解 NNN。

但n较大时，直接计算n!将会很消耗资源。在便利n时，可以简化运算。

因为：$a^{n!} \bmod N = (a \bmod N) ^ {n!} \bmod N$

所以：$a^{n!} \bmod N = \begin{cases} (a \bmod N) ^ 2 \bmod N & \text{n = 2} \ (a^{(n-1)!} \bmod N) ^ n \bmod N & \text{n >= 3} \end{cases} $

解题脚本

import gmpy2

def Pollards_p_1(N):
a = 2
n = 2
while True:
a = pow(a, n, N)
res = gmpy2.gcd(a-1, N)
if res != 1 and res != N:
print ‘n =’, n
print ‘p =’, res
return res
n += 1

[NCTF2019] childRSA

题目

from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag

def getPrime(bits):
while True:
n = 2
while n.bit_length() < bits:
n *= choice(primes)
if isPrime(n + 1):
return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), ‘big’)
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)
# n = 3284971819733758182300224371705765921850251900438699666088510059287220194883415554312592439561492896275057966734…388249513
# c = 2630801835673985389538224010996889417516673128370292700216526899877370833521633899705831415771714713108329655131…605279108

解题

可以发现 p 和 q 是由前10000个随机的许多小质数乘积加1得到，即p−1为许多小质数的乘积。那么可以利用Pollard’s p − 1 算法来分解 N。

e = 0x10001
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

p = pollards_p_1(n)
q = n // p
assert p*q == n
d = gmpy2.invert(e, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))

模不互素

可攻击特征

当存在两个公钥的 N 不互素时

原理

当存在两个公钥的 N 不互素时，我们显然可以直接对这两个数求最大公因数，然后直接获得 p，q，进而获得相应的私钥。具体来说：

当$n1 = p1 * q1$，$n2 = p1 * q2$ 时，我们先求出p1，然后再求出对应的q1和q2即可。

SCTF-RSA2

题目链接：https://github.com/ohroot/rsatools/blob/master/demos/sctf/rsa2/syc_security_system_traffic2.pcap

题目描述：题目是一个流量包，我们从中提取出两个

解题

import gmpy2
from Crypto.Util.number import long_to_bytes

n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943

p1 = gmpy2.gcd(n1, n2)
q1 = n1 // p1
e = 65537
phi = (p1 – 1) * (q1 – 1)
d = gmpy2.invert(e, phi)
cipher = 0x68d5702b70d18238f9d4a3ac355b2a8934328250efd4efda39a4d750d80818e6fe228ba3af471b27cc529a4b0bef70a2598b80dd251b15952e6a6849d366633ed7bb716ed63c6febd4cd0621b0c四ebfe5235de03d4ee016448de1afbbe61144845b580eed8be8127a8d92b37f9ef670b3cdd5af613c76f58ca1a9f6f03f1bc11addba30b61bb191efe0015e971b8f78375faa257a60b355050f6435d94b49eab07075f40cb20bb8723d02f5998d5538e8dafc80cc58643c91f6c0868a7a7bf3bf6a9b4b6e79e0a80e89d430f0c049e1db4883c50db066a709b89d74038c34764aac286c36907b392bc299ab8288f9d7e372868954a92cdbf634678f7294096c7
plain = gmpy2.powmod(cipher, d, n1)
print(long_to_bytes(plain))

共模攻击

可攻击特征

当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。

具体说就是：明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1也就是e1和e2互质时候，可能导致共模攻击。

原理

设两个用户的公钥分别为 $e_1$ 和 $e_2$，且两者互质。明文消息为 $m$，密文分别为：

$$ c_1 = m^{e_1}\bmod N $$

$$ c_2 = m^{e_2}\bmod N $$

当攻击者截获 $c_1$ 和 $c_2$ 后，就可以恢复出明文。用扩展欧几里得算法求出 $re_1+se_2=1\bmod n$ 的两个整数 $r$ 和 $s$，由此可得：

$$ c{1}^{r}c{2}^{s} \equiv m^{re_1}m^{se_2}\bmod n\ $$

$$ c{1}^{r}c{2}^{s}\equiv m^{(re_1+se_2)} \bmod n\ $$

$$c{1}^{r}c{2}^{s}\equiv m\bmod n $$

jarvisoj-very hard RSA

题目描述

前几题因为N太小，都被你攻破了，出题人这次来了个RSA4096，是否接受挑战就看你了。

#!/usr/bin/env python

import random

N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c四78bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L

def pad_even(x):
return (”, ‘0’)[len(x)%2] + x

e1 = 17
e2 = 65537

fi = open(‘flag.txt’,’rb’)
fo1 = open(‘flag.enc1′,’wb’)
fo2 = open(‘flag.enc2′,’wb’)

data = fi.read()
fi.close()

while (len(data)<512-11):
data = chr(random.randint(0,255))+data

data_num = int(data.encode(‘hex’),16)

encrypt1 = pow(data_num,e1,N)
encrypt2 = pow(data_num,e2,N)

fo1.write(pad_even(format(encrypt1,’x’)).decode(‘hex’))
fo2.write(pad_even(format(encrypt2,’x’)).decode(‘hex’))

fo1.close()
fo2.close()

题目分析

题目中4096位的RSA加密，硬解肯定是解不开的。我们观察题目特点，题目给出了2个flag.enc文件和一个easyRSA.py的脚本。分析该脚本

解题

import gmpy2
from Crypto.Util.number import long_to_bytes,bytes_to_long

e1 = 17
e2 = 65537
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c四78bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929

with open(‘./flag.enc1′,’rb’) as enc1:
c1 = bytes_to_long(enc1.read())
with open(‘./flag.enc2′,’rb’) as enc2:
c2 = bytes_to_long(enc2.read())

_, r, s = gmpy2.gcdext(e1, e2)
m = gmpy2.powmod(c1, r, n) * gmpy2.powmod(c2, s, n) % n
print(long_to_bytes(m))

公钥指数e的相关攻击

小公钥指数攻击

可攻击特征

e 特别小，比如 e 为 3。

原理

假设用户使用的密钥 $e=3$，考虑到加密关系满足：

$c\equiv m^3 \bmod N$

则：

$$\begin{align} m^3 &= c+k\times N\ m &= \sqrt[3]{c+k\times n} \end{align}$$

jarvisoj-Extremely hard RSA

题目描述

没想到RSA4096都被你给破了，一定是我的问题，给了你太多信息，这次我只给你一个flag的加密值和公钥，仍然是RSA4096，我就不信你还能解出来。

题目附件是两个文件：pubkey.pem、flag.enc

解题

首先我们使用openssl工具查看公钥文件的一些参数（为了节省篇幅，省略一些解题无关的内容）

➜ [Jarvis OJ]extremelyhardRSA openssl rsa -pubin -in pubkey.pem -text -modulus
Public-Key: (4096 bit)
Modulus:
00:b0:be:e5:e3:e9:e5:a7:e8:d0:0b:49:33:55:c6:
…
Exponent: 3 (0x3)
Modulus=B0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C四78BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
writing RSA key
—–BEGIN PUBLIC KEY—–
MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4+nlp+jQC0kzVcYY
…

写出脚本

import gmpy2
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long,long_to_bytes
from multiprocessing import Pool
pool = Pool(4)

with open(‘./pubkey.pem’, ‘r’) as f:
key = RSA.importKey(f.read())
N = key.n
e = key.e
with open(‘flag.enc’, ‘rb’) as f:
cipher = bytes_to_long(f.read())

def calc(j):
a, b = gmpy2.iroot(cipher + j * N, 3)
if b == 1:
m = long_to_bytes(a)
print(m)
pool.terminate()
exit()

def main():
inputs = range(0, 150000000)
pool.map(calc, inputs)
pool.close()
pool.join()

if __name__ == ‘__main__’:
print(‘start’)
main()

小公钥指数攻击之Rabin 算法

可攻击特征

Rabin 算法的特征在于 $e=2$。

原理

暂略，数学推导。

jarvisoj-Extremely hard RSA

import gmpy2
import string
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long,long_to_bytes

# 读取公钥参数
with open(‘pubkey.pem’, ‘r’) as f:
key = RSA.importKey(f.read())
N = key.n
e = key.e
with open(‘flag.enc’, ‘rb’) as f:
cipher = bytes_to_long(f.read())

p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
e = 2

# 计算yp和yq
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)

# 计算mp和mq
mp = pow(cipher, (p + 1) // 4, p)
mq = pow(cipher, (q + 1) // 4, q)

# 计算a,b,c,d
a = (inv_p * p * mq + inv_q * q * mp) % N
b = N – int(a)
c = (inv_p * p * mq – inv_q * q * mp) % N
d = N – int(c)

for i in (a, b, c, d):
print(long_to_bytes(i))

私钥指数d的相关攻击

可攻击特征

首先当 d 泄露之后，我们自然可以解密所有加密的消息。我们甚至还可以对模数 N 进行分解。

原理

我们知道 $ed \equiv 1 \bmod \varphi(n)$，那么存在一个 $k$ 使得

$ed-1=k\varphi(n)$

又 $\forall a\in {Z}_n^*$，满足 $a^{ed-1}\equiv1(\bmod n)$ 。令

$ed-1=2^st$

其中，$t$ 是一个奇数。然后可以证明对于至少一半的 $a\in {Z}_n^*$，存在一个 $i\in[1,s]$，使得

$a^{2^{i-1}t}\not\equiv\pm1(\bmod n),a^{2^{i}t}\equiv1(\bmod n)$

成立。如果 $a,i$ 满足上述条件，$gcd(a^{2^{i-1}t}-1,n)$ 是 $n$ 的一个非平凡因子，所以可以对 $n$ 进行暴力分解。

可参考：https://www.di-mgt.com.au/rsa_factorize_n.html

攻击脚本

#!/usr/bin/env python3
import random
import gmpy2
def divide_pq(ed, n):
# ed = e*d
k = ed – 1
while True:
g = random.randint(3, n-2)
t = k
while True:
if t % 2 != 0:
break
t = t//2
x = pow(g, t, n)
if x > 1 and gmpy2.gcd(x-1, n) > 1:
p = gmpy2.gcd(x-1, n)
return (p, n//p)

工具

也可以使用如下工具可以直接进行计算

RsaConverter.exe (https://sourceforge.net/projects/rsaconverter/, for windows )
rsatool.py(分解原理如上)

Wiener’s Attack

可攻击特征

在 d 比较小 $d<\frac{1}{3}N^{\frac{1}{4}}$ 时，攻击者可以使用 Wiener’s Attack来获得私钥。

flatcc备注：e特别大时候也能解？

攻击原理

https://sagi.io/2016/04/crypto-classics-wieners-rsa-attack/

2016 HCTF RSA1

这道题目也是从CTF-WiKi上边摘录的，题目是2016 年 HCTF 中 RSA 1 – Crypto So Interesting，源码链接在这里：https://github.com/Hcamael/ctf-library/tree/master/RSA1

题目描述

我们直接入手题目核心部分，先来看下题目给出的已知条件，题目内容如下：

# 节选部分内容，下边是题目给出的n和e
p=getPrime(2048)
q=getPrime(2048)
n = p * q
e, d = get_ed(p, q)
print “n: “, hex(n)
print “e: “, hex(e)

# 下边是e,d的由来
def get_ed(p, q):
k = cal_bit(q*p)
phi_n = (p-1)*(q-1)
r = random.randint(10, 99)
while True:
u = getPrime(k/4 – r)
if gcd(u, phi_n) != 1:
continue
t = invmod(u, phi_n)
e = pi_b(t)
if gcd(e, phi_n) == 1:
break
d = invmod(e, phi_n)
return (e, d)

解题思路

所以从get_ed()这个函数，我们得知u的位数小于四分之一的n，那么我们就想到了Wiener’s Attack攻击，使用t和n求出u；但要得先求出t来，我们从题目中得知e = pi_b(t)，那么e是又是已知的，这个问题就解决了。

解题脚本

在自己的rsa_toolset/RSA-Wiener-Attack/exp.py

ef wiener_hack(e, n):
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)
for (k, d) in convergents:
if k != 0 and (e * d – 1) % k == 0:
phi = (e * d – 1) // k
s = n – phi + 1
discr = s * s – 4 * n
if (discr >= 0):
t = Arithmetic.is_perfect_square(discr)
if t != -1 and (s + t) % 2 == 0:
print(“Hacked!”)
return d
return False

Coppersmith 相关攻击

相关数学理论基础可参考：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/

Coppersmith method可参考：https://github.com/mimoo/RSA-and-LLL-attacks

Basic Broadcast Attack

中文有人翻译作广播攻击

可攻击特征

如果一个用户使用同一个加密指数 e 加密了同一个密文，并发送给了其他 e 个用户。那么就会产生广播攻击。这一攻击由 Håstad 提出。

原理

这里我们假设 e 为 3，并且加密者使用了三个不同的模数 $n_1,n_2,n_3$ 给三个不同的用户发送了加密后的消息 m，如下

$$ \begin{align} c_1 &=m^3\bmod n_1\ c_2&=m^3\bmod n_2\ c_3&=m^3\bmod n_3 \end{align} $$

这里我们假设 $n_1,n_2,n_3$ 互素，不然，我们就可以直接进行分解，然后得到 d，进而然后直接解密。

同时，我们假设 $m<n_i, 1\leq i \leq 3$。如果这个条件不满足的话，就会使得情况变得比较复杂，这里我们暂不讨论。

既然他们互素，那么我们可以根据中国剩余定理，可得$m^3 \equiv C \bmod n_1n_2n_3$。

此外，既然 $m<n_i, 1\leq i \leq 3$，那么我们知道 $m^3 < n_1n_2n_3$ 并且 $C<m^3 < n_1n_2n_3$，那么 $m^3 = C$，我们对 C 开三次根即可得到 m 的值。

对于较大的 e 来说，我们只是需要更多的明密文对。

BUUCTF-RSA4

题目

题目就给出了几个数字对

N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

解题

解题我们用脚本跑一下即可，但要注意此题所给的数都是5进制的。

Broadcast Attack with Linear Padding

待补充

Related Message Attack

可攻击特征

当 Alice 使用同一公钥对两个具有某种线性关系的消息 M1 与 M2 进行加密，并将加密后的消息 C1，C2 发送给了 Bob 时，我们就可能可以获得对应的消息 M1 与 M2。这里我们假设模数为 N，两者之间的线性关系如下

$$ M_1 \equiv f(M_2) \bmod N $$

其中 f 为一个线性函数，比如说 $f=ax+b$。

原理

首先，我们知道 $C_1 \equiv M_1 ^e \bmod N$，并且 $M_1 \equiv f(M_2) \bmod N$，那么我们可以知道 $M_2$ 是 $f(x)^e \equiv C_1 \bmod N$ 的一个解，即它是方程 $f(x)^e-C_1$ 在模 N 意义下的一个根。同样的，$M_2$ 是 $x^e – C_2$ 在模 N 意义下的一个根。所以说 $x-M_2$ 同时整除以上两个多项式。因此，我们可以求得两个多项式的最大公因子，如果最大公因子恰好是线性的话，那么我们就求得了 $M_2$。需要注意的是，在 $e=3$ 的情况下，最大公因子一定是线性的。

这里我们关注一下 $e=3$，且 $f(x)=ax+b$ 的情况。首先我们有

$$ C_1 \equiv M_1 ^3 \bmod N,M_1 \equiv aM_2+b \bmod N $$

那么我们有

$$ C_1 \equiv (aM_2+b)^3 \bmod N,C_2 \equiv M_2^3 \bmod N $$

我们需要明确一下我们想要得到的是消息 m，所以需要将其单独构造出来。

首先，我们有式 1

$$ (aM_2+b)^3=a^3M_2^3+3a^2M^2b+3aM_2b^2+b^3 $$

再者我们构造如下式 2

$$ (aM_2)^3-b^3 \equiv (aM_2-b)(a^2M_2^2+aM_2b+b^2) \bmod N $$

根据式 1 我们有

$$ a^3M_2^3-2b^3+3b(a^2M_2^2+aM_2b+b^2) \equiv C_1 \bmod N $$

继而我们有式 3

$$ 3b(a^2M_2^2+aM_2b+b^2) \equiv C_1-a^3C_2+2b^3 \bmod N $$

那么我们根据式 2 与式 3 可得

$$ (a^3C_2-b^3)*3b \equiv (aM_2-b)( C_1-a^3C_2+2b^3 ) \bmod N $$

进而我们有

$$ aM_2-b=\frac{3a^3bC_2-3b^4}{C_1-a^3C_2+2b^3} $$

进而

$$ aM_2\equiv \frac{2a^3bC_2-b^4+C_1b}{C_1-a^3C_2+2b^3} $$

进而

$$ M_2 \equiv\frac{2a^3bC_2-b^4+C_1b}{aC_1-a^4C_2+2ab^3}=\frac{b}{a}\frac{C_1+2a^3C_2-b^3}{C_1-a^3C_2+2b^3} $$

上面的式子中右边所有的内容都是已知的内容，所以我们可以直接获取对应的消息。

有兴趣的可以进一步阅读 A New Related Message Attack on RSA 以及 paper 这里暂不做过多的讲解。

SCTF-RSA3

题目链接https://github.com/ohroot/rsatools/tree/master/demos/sctf/rsa3

题目题目给出的是一个TCP的流量包，跟随数据流我们可以看到其中的N，user_id，密文C

解题我们取其中模N相同的0组和9组数据，按照上边的公式，写出解密脚本如下

#!/usr/bin/env python3
import gmpy2
from Crypto.Util.number import long_to_bytes

id1 = 1002
id2 = 2614

c1 = 0x547995f4e2f4c007e6bb2a6913a3d685974a72b05bec02e8c03ba64278c9347d8aaaff672ad8460a8cf5bffa5d787c5bb724d1cee07e221e028d9b8bc24360208840fbdfd4794733adcac四5c38ad0225fde19a6a4c38e4207368f5902c871efdf1bdf4760b1a98ec1417893c8fce8389b6434c0fee73b13c284e8c9fb5c77e420a2b5b1a1c10b2a7a3545e95c1d47835c2718
c2 = 0x547995f4e2f4c007e6bb2a6913a3d685974a72b05bec02e8c03ba64278c9347d8aaaff672ad8460a8cf5bffa5d787c72722fe4fe5a901e2531b3dbcb87e5aa19bbceecbf9f32eacefe81777d9bdca781b1ec8f8b68799b4aa4c6ad120506222c7f0c3e11b37dd0ce08381fabf9c14bc74929bf524645989ae2df77c8608d0512c1cc四150765ab8350843b57a2464f848d8e08
n = 25357901189172733149625332391537064578265003249917817682864120663898336510922113258397441378239342349767317285221295832462413300376704507936359046120943334215078540903962128719706077067557948218308700143138420408053500628616299338204718213283481833513373696170774425619886049408103217179262264003765695390547355624867951379789924247597370496546249898924648274419164899831191925127182066301237673243423539604219274397539786859420866329885285232179983055763704201023213087119895321260046617760702320473069743688778438854899409292527695993045482549594428191729963645157765855337481923730481041849389812984896044723939553
a = 1
b = id1 – id2

# 套公式
def getmessage(a, b, c1, c2, n):
b3 = gmpy2.powmod(b, 3, n)
part1 = b * (c1 + 2 * c2 – b3) % n
part2 = a * (c1 – c2 + 2 * b3) % n
part2 = gmpy2.invert(part2, n)
return part1 * part2 % n

message = getmessage(a, b, c1, c2, n) – id2
print(long_to_bytes(message))

Coppersmith’s short-pad attack

可攻击特征

过短的padding长度导致的容易攻击

Known High Bits Message Attack(Stereotyped messages)

可攻击特征

如果e较小，并且已知m的高位，则可通过此方法求出完整的m。
比如题目给出m=0x65c四6754a7776c8b88867e000000000000000000 前面的部分就是高位，后面的0就是低位，0只是占位的作用并不是真正m的值。

原理

知道了消息m的很大一部分$m_0$

现在，$c=(m_0+x)^e\mod n$，也就是 $f(x)=(m + x)^e – c$ 有一个解满足 $f(x)=k\cdot N(k=0,1,2\cdots)$ ,求解x。

依据coppersmith定理是可以求出剩下的所有明文部分。

解题方法

在线sagemath：https://sagecell.sagemath.org/

自己安装的离线sage

2019强网杯copperstudy—level1

题目

n=0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953L
e=3
m=random.getrandbits(512)
c=pow(m,e,n)=0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c四51562c816e2303990834c94e580bf0cbd1L
((m>>72)<<72)=0x9e67d3a220a3dcf6fc四742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000L

解题思路

要求求出完整的m，很明显e较小，并且已知了m的高位，我们通过CopperSmith算法的Stereotyped messages Attack获得完整的m。

解题脚本

# exp.sage
load(“coppersmith_py3.sage”)
N = 0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953
e = 3
m = 0x9e67d3a220a3dcf6fc四742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000

c = 0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c四51562c816e2303990834c94e580bf0cbd1
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = (m + x)^e – c
dd = f.degree()
beta = 1
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) – 1))
XX = ceil(N**((beta**2/dd) – epsilon))
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
print(“结果是:”, hex(roots[0])) # 注意输出结果是16进制数

运行方式：sage exp.sage

Factoring with High Bits Known Attack

可攻击特征

已知公钥中模数 N 的一个因子的较高位时，我们就有一定几率来分解 N，例如已知p的高位。

攻击方法

sage脚本

2019强网杯copperstudy—level2

题目

n=0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578dL
e=65537
m=random.getrandbits(512)
c=pow(m,e,n)=0x1922e7151c779d6bb554cba6a05858415e74739c36df0bcf169e49ef0e566a4353c51a306036970005f2321d1d104f91a673f40944e830619ed683d8f84eaf26e7a93c四abe1dbd7ca3babf3f4959def0e3d87f7818d54633a790fc74e9fed3c5b5456c21e3f425240f6217b0b14516cb59aa0ce74b83ca17d8cc四a0fbc829fb8L
((p>>128)<<128)=0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000L

解题脚本

pbits = 1024
kbits = 130
pbar = p_fake & (2^pbits-2^kbits)
print(“upper %d bits (of %d bits) is given” % (pbits-kbits, pbits))

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar

x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.3
print(hex(int(x0 + pbar)))

计算结果：

➜ RSA-and-LLL-attacks sage factoring_with_high_bits_know.sage
upper 894 bits (of 1024 bits) is given
0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a87321efe89ec89bdf3e4d9da9a45df22a787

Boneh and Durfee attack

可攻击特征

当 d 较小时，满足$d < N^{0.292}$ 时，我们可以利用该攻击，比 Wiener’s Attack 要强一些。

Partial Key Exposure Attack

可攻击特征

题目给出一组公钥n,e以及加密后的密文
若e较小，已知d的低位，则可通过此方法求出完整的d。

2019强网杯copperstudy—level3

题目

n=0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c四27bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3bL

e=3
m=random.getrandbits(512)
c=pow(m,e,n)=0x3d7e16fd8b0b1afdb4e12594c3d8590f1175800ef07bb275d7a8ad983d0d5d5fd5c6f81efa40f5d10c四8bb200f805e679d633ee584748e5feef003e0921dea736ba91eef72f3d591d3a54cd59fd36f61140fdd3fb2e2c028b684e50cbeae4a1f386f6ab35359d46a29996c0f7d9a4a189f1096150496746f064c3cc四1cf111b0L
d=invmod(e,(p-1)*(q-1))
d&((1<<512)-1)=0x17c四b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749bL

解题脚本

def partial_p(p0, kbits, n):
PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()
f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) # find root < 2^(nbits//2-kbits) with factor >= n^0.3
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)

def find_p(d0, kbits, e, n):
X = var(‘X’)
for k in range(1, e+1):
results = solve_mod([e*d0*X – k*X*(n-X+1) + k*n == X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, kbits, n)
if p:
return p

if __name__ == ‘__main__’:
# n(必须为整形才可计算) = 0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c四27bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3b
# d0=给出的部分d(必须为整形才可计算) = 0x17c四b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749b
e = 3
n = 57569201048993475052349187244752169754165154575782760003851777813767048953051839288528137121670999884309849815765999616346303792471518639080697166767644957046582385785721102370288806038187956032505761532789716009522131450217010629338000241936036185205038814391205848232364006349213836317806903032515194407739
nbits = n.nbits()
kbits = floor(nbits*0.5)
print(“kbits : “, kbits)
d0 = 1244848677959253796774387650148978357579294769878147704641867595620534030329181934099194560059806799908134954814673426128260540575360296026444649631806619
print(“lower %d bits (of %d bits) is given” % (kbits, nbits))

p = find_p(d0, kbits, e, n)
print(“found p: %d” % p)
q = n//p
# print(d)
print(“完整的d是:”+str(inverse_mod(e, (p-1))))

计算结果

➜ RSA-and-LLL-attacks sage partial_key_exposure_attack.sage
kbits : 511
lower 511 bits (of 1023 bits) is given
found p: 7086179599191994333603836952445140343587486096628720220842297473373568276314821730585498733360983965734902690794828276489674036310720194369289757363461559
完整的d是:4724119732794662889069224634963426895724990731085813480561531648915712184209881153723665822240655977156601793863218850993116024207146796246193171575641039

dp或dq泄漏攻击

dp&dq泄露

可攻击特征

已知 p, q, dp, dq, c求m。

原理

dp本来是为了加速rsa加解密效率的,不过由于dp和p的关系相当密切,所以当dp泄漏也有相当大的危害

dp=d%(p-1)
dq=d%(q-1)
dp*e = 1 mod(p-1)
dq*e = 1 mod(q-1)

BUUCTF-RSA1

题目

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

解题

#!/usr/bin/python2

import gmpy2
from Crypto.Util.number import long_to_bytes

InvQ=gmpy2.invert(q,p)
mp=pow(c,dp,p)
mq=pow(c,dq,q)
m=(((mp-mq)*InvQ)%p)*q+mq

print(long_to_bytes(m))

dp泄露

可攻击特征

题目给出公钥n,e以及dp，给出密文要求解明文，我们可以通过n，e，dp求解私钥d。

原理

推导过程参考：https://blog.csdn.net/weixin_45369385/article/details/109208109

WUSTCTF2020-dp_leaking

题目

e = 65537
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

解题脚本

from gmpy2 import invert,powmod
from Crypto.Util.number import long_to_bytes

for x in range(1, e):
if (e * dp % x == 1):
p = (e * dp – 1) // x + 1
if (n % p != 0):
continue
q = n // p
phin = (p – 1) * (q – 1)
d = invert(e, phin)
m = powmod(c, d, n)
if (len(hex(m)[2:]) % 2 == 1):
continue

print(“m:”, m)
print(“flag:”, long_to_bytes(m))

RSA 选择明/密文攻击

选择明文攻击

任意密文解密

RSA parity oracle

RSA Byte Oracle

RSA parity oracle variant

Padding Attack

可攻击特征

加密的Padding可控。

例题

题目

(‘n=’, ‘0xb33aebb1834845f959e05da639776d08a344abf098080dc5de04f4cbf4a1001dL’)
(‘e=’, ‘0x3’)
(‘c1=pow(hex_flag,e,n)’, ‘0x3aa5058306947ff46b0107b062d75cf9e497cdb1f120d02eaeca30f76492c550L’)
(‘c2=pow(hex_flag+1,e,n)’, ‘0x6a645739f25380a5e5b263ff5e5b4b9324381f6408a11fdaab0488209145fb3eL’)

解题分析

原理参考
https://www.anquanke.com/post/id/158944

意思很简单
1.pow(mm, e) != pow(mm, e, n)
2.利用rsa加密m+padding
值得注意的是，e=3，padding可控
那么我们拥有的条件只有
n,e,c,padding
所以这里的攻击肯定是要从可控的padding入手了

解题脚本

import gmpy2
from Crypto.Util.number import long_to_bytes

def getM2(a,b,c1,c2,n,e):
a3 = pow(a,e,n)
b3 = pow(b,e,n)
first = c1-a3*c2+2*b3
first = first % n
second = e*b*(a3*c2-b3)
second = second % n
third = second*gmpy2.invert(first,n)
third = third % n
fourth = (third+b)*gmpy2.invert(a,n)
return fourth % n
e=0x3
a=1
b=-1
c1=0x3aa5058306947ff46b0107b062d75cf9e497cdb1f120d02eaeca30f76492c550
c2=0x6a645739f25380a5e5b263ff5e5b4b9324381f6408a11fdaab0488209145fb3e
padding2=1
n=0xb33aebb1834845f959e05da639776d08a344abf098080dc5de04f4cbf4a1001d
m = getM2(a,b,c1,c2,n,e)-padding2
print(long_to_bytes(m))

RSA LSB Oracle Attack

可攻击特征

可以选择密文并泄露最低位。

参考博客https://www.sohu.com/a/243246344_472906

原理

在一次RSA加密中，明文为m，模数为n，加密指数为e，密文为c。我们可以构造出c’=((2^e)c)%n=((2^e)(m^e))%n=((2m)^e)%n，因为m的两倍可能大于n，所以经过解密得到的明文是 m’=(2m)%n 。我们还能够知道 m’ 的最低位lsb 是1还是0。因为n是奇数，而2m是偶数，所以如果lsb 是0，说明(2m)%n 是偶数，没有超过n，即m<n/2.0，反之则m>n/2.0 。举个例子就能明白2%3=2 是偶数，而4%3=1 是奇数。以此类推，构造密文c”=(4^e)c)%n 使其解密后为m”=(4m)%n ，判断m” 的奇偶性可以知道m 和 n/4 的大小关系。所以我们就有了一个二分算法，可以在对数时间内将m的范围逼近到一个足够狭窄的空间。

攻击脚本

def brute_flag(encrypted_flag, n, e):

flag_count = n_count = 1
flag_lower_bound = 0
flag_upper_bound = n
ciphertext = encrypted_flag
mult = 1
while flag_upper_bound > flag_lower_bound + 1:
sh.recvuntil(“input your option:”)
sh.sendline(“D”)
ciphertext = (ciphertext * pow(2, e, n)) % n
flag_count *= 2
n_count = n_count * 2 – 1

print(“bit = %d” % mult)
mult += 1

sh.recvuntil(“Your encrypted message:”)
sh.sendline(str(ciphertext))

data=sh.recvline()[:-1]
if(data==’The plain of your decrypted message is even!’):
flag_upper_bound = n * n_count / flag_count
else:
flag_lower_bound = n * n_count / flag_count
n_count += 1
return flag_upper_bound

RSA 侧信道攻击

Bleichenbacher’s attack

PKCS 1.5 标准中可以伪造 RSA 签名

http://ddaa.tw/gctf_crypto_201_rsa_ctf_challenge.html

附1:公钥私钥获取信息

OpenSSL

OpenSSL是开源的的软件库包，其支持许多不同的加密算法。当然了其中有许多实用的工具，我们这里就使用其中有关RSA的部分。

openssl genrsa

该命令生成一个RSA私钥。

➜ ~ openssl genrsa -h
usage: genrsa [args] [numbits] //密钥位数，建议在 2048bit 以上
-des encrypt the generated key with DES in cbc mode
-des3 encrypt the generated key with DES in ede cbc mode (168 bit key)
-aes128, -aes192, -aes256 encrypt PEM output with cbc aes
-camellia128, -camellia192, -camellia256 encrypt PEM output with cbc camellia
-out file 输出key到file //公钥可以从该私钥file中提取
-passout arg output file pass phrase source
-f4 use F4 (0x10001) for the E value
-3 use 3 for the E value

openssl rsa

处理RSA密钥的格式转换等问题。

➜ ~ openssl rsa -h
Invalid cipher ‘h’
usage: rsa [-ciphername] [-check] [-in file] [-inform fmt]
[-modulus] [-noout] [-out file] [-outform fmt] [-passin src]
[-passout src] [-pubin] [-pubout] [-sgckey] [-text]

-check Check consistency of RSA private key # 检查输入密钥的正确性和一致性
-in file Input file (default stdin)
-inform format Input format (DER, NET or PEM (default)) # 输入文件格式，默认pem
-modulus Print the RSA key modulus # 输出模数
-noout Do not print encoded version of the key
-out file Output file (default stdout)
-outform format Output format (DER, NET or PEM (default PEM)) # 输出文件格式，默认pem
-passin src Input file passphrase source # 指定输入文件的加密口令，可来自文件、终端、环境变量等
-passout src Output file passphrase source
-pubin Expect a public key (default private key) # 指定输入文件是公钥
-pubout Output a public key (default private key)
-sgckey Use modified NET algorithm for IIS and SGC keys
-text Print in plain text in addition to encoded

openssl rsautl

使用RSA密钥进行加密、解密、签名和验证等运算。

数据补齐方式	输入数据长度	输出数据长度	参数字符串
PKCS#1 v1.5	少于(密钥长度-11)字节	同密钥长度	-pkcs
PKCS#1 OAEP	少于(密钥长度-11)字节	同密钥长度	-oaep
PKCS#1 for SSLv23	少于(密钥长度-11)字节	同密钥长度	-ssl
不使用补齐	同密钥长度	同密钥长度	-raw

➜ ~ openssl rsautl -h
Usage: rsautl [options]
-in file input file
-out file output file
-inkey file input key
-keyform arg private key format – default PEM # 指定密钥格式
-pubin input is an RSA public
-certin input is a certificate carrying an RSA public key # 指定输入的是证书文件
-ssl use SSL v2 padding # 使用SSLv23的填充方式
-raw use no padding # 不进行填充
-pkcs use PKCS#1 v1.5 padding (default)
-oaep use PKCS#1 OAEP
-sign sign with private key # 使用私钥做签名
-verify verify with public key # 使用公钥认证签名
-encrypt encrypt with public key # 使用公钥加密
-decrypt decrypt with private key # 使用私钥解密

openssl 加解密实例

生成私钥:openssl genrsa -out prikey.pem

查看私钥:openssl rsa -in prikey.pem -text -modulus

从私钥总提取公钥:openssl rsa -in prikey.pem -pubout -out pubkey.pem

查看公钥:openssl rsa -in pubkey.pem -text -modulus -pubin

加密:openssl rsautl -encrypt -in file.plain -inkey pubkey.pem -pubin -out file.enc

解密:(如有对应的补齐方式需要指定):rsautl -decrypt -inkey prikey -in filename

其他工具

rsatools

使用使用p,q,e生成pem文件：python rsatools.py -p p参数 -q q参数 -e e的值 -o prikey.pem

RsaCtfTool

查看公钥的一些信息:./RsaCtfTool.py --dumpkey --key ./key.pub

已知公钥求私钥:./RsaCtfTool.py --publickey ./key.pub --private

已知公钥，自动解密:./RsaCtfTool.py --publickey ./key.pub --uncipherfile filename

已知 $n,e$ 生成公钥:./RsaCtfTool.py --createpub -n 7828374823761928712873129873981723...12837182 -e 65537

更多参看：https://github.com/Ganapati/RsaCtfTool

2020西湖论剑-RSA-BrokenSystems

题目

给了两个文件，message 和 public.key，还有一个脚本如下：

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag
import os
rsa = RSA.generate(2048)
public_key = rsa.publickey().exportKey()
f=open(“public.key”,”w”)
f.write(public_key.decode())
f.close()

rsakey=RSA.importKey(open(“public.key”,”r”).read())
rsa = PKCS1_OAEP.new(rsakey)
msg=rsa.encrypt(flag.encode())
f=open(“message”,”wb”)
f.write(msg)
f.close()

解题思路

首先我们看一下公钥的一些参数：

➜ RsaCtfTool git:(master) ./RsaCtfTool.py –dumpkey –key ./2020ctf-BrokenSystems/public.key
private argument is not set, the private key will not be displayed, even if recovered.
n: 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
e: 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583

可以看到这里边的e特别大，大家都说是用Wiener攻击可以解出，我还没尝试，想用RsaCtfTool试试看，所以小结下，本题有两种解法：

常规思路解d –> 生成密钥key –> 解密
使用RsaCtfTool工具suoha

解题

使用RsaCtfTool爆破，我们可以看出该脚本最终用boneh_durfee爆破出了结果

➜ RsaCtfTool git:(master) ✗ ./RsaCtfTool.py –publickey ./2020ctf-BrokenSystems/public.key –private

[*] Testing key ./2020ctf-BrokenSystems/public.key.
…省略暴力尝试的一部分内容…
[*] Performing roca attack on ./2020ctf-BrokenSystems/public.key.
[*] Performing pollard_p_1 attack on ./2020ctf-BrokenSystems/public.key.
[*] Performing boneh_durfee attack on ./2020ctf-BrokenSystems/public.key.

Results for ./2020ctf-BrokenSystems/public.key:

Private key :
—–BEGIN RSA PRIVATE KEY—–
MIIEXgIBAAKCAQEAwgdFIj/1uUss2EEhZvcoiiHyGH4aQhRTkYyrA8gCU0USM+sb
3CNjdEIoqoaUqMLLyDP4Dd9AgxpokBsjC四Pz8P7Uty0LlCteld7ayNzABHoq+5DI
…篇幅过长省略…
UWAvuuxI7lGac2B+/A/EcwBJfOT/qLCPpvFhA0Qje1HqlNSXc9e/FGt1UwxZkJBJ
JNGhlKRKaB0RJgJW5dA1jfyYU8xpPsDxfdDzLf2y167IbfqNNmL7ZF8IHj5+hPsB
0oVAN0gvoLxcOM2qMOXIt6aM
—–END RSA PRIVATE KEY—–

获得Private Key后，我们将该密钥保存为pri.key，使用openssl解出结果，需要注意的是解密时要指定填充模式为PKCS1_OAEP

➜ RsaCtfTool git:(master) ✗ cd 2020ctf-BrokenSystems && openssl rsautl -decrypt -oaep -in message -inkey pri.key
DASCTF{ce02347b86167f2d3519251b9a8a5ba8}