CTF中的RSA及攻击方法笔记
2020-12-15 10:57:15 Author: www.freebuf.com(查看原文) 阅读量:762 收藏

本文结合许多当下互联网存在的资料整理出了自己对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。

攻击方法

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

  1. 在线数据库查询:http://factordb.com/

  2. 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相差较小,一般来说相差千万都是比较小的,可以有两种解法

  1. 我们对N开根号,然后从$\sqrt N$ 到$N$依此遍历

  2. 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.pemflag.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)

工具

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

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

解题脚本

n = 0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578d
p_fake = 0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000

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

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

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

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

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}

RSA私钥文件修复

私钥文件修复可参考该帖子:https://code.felinae98.cn/CTF/Crypto/RSA-%E7%A7%81%E9%92%A5%E9%87%8D%E6%9E%84/

Jarvis OJ-God Like RSA

题目

题目给出了三个文件,加密后的 flagflag.enc,残缺的私钥private.corrupted,公钥pubkey.pem

解题

解题可参考:https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html

附2:RSA综合性题集

附3:参考资料

RSA知识大纲:https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory-zh/

大质数在线分解数据库:http://factordb.com

一类RSA:https://www.jianshu.com/p/0272069cb936?utm_campaign=maleskine

对模数N的一些小结:https://nonuplebroken.com/2018/11/26/RSA模数相关攻击/#原理

Jarvis-OJ-Crypto: https://skysec.top/2017/12/11/Jarvis-OJ-Crypto/#very-hard-RSA

对RSA的总结1:https://zhuanlan.zhihu.com/p/76228394

对RSA的总结2:https://xz.aliyun.com/t/6459#toc-59


文章来源: https://www.freebuf.com/articles/web/257835.html
如有侵权请联系:admin#unsafe.sh