CTF中的RSA及攻击方法笔记
数论
模运算规则:
模运算与基本四则运算有些相似，但是除法例外。其规则如下: (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 (bc)%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 基于大整数因数分解难题。
RSA
RSA简介
倘若在加解密信息的过程中，能让加密密钥（公钥）与解密密钥（私钥）不同，即
1. 甲要传密信给乙，乙先根据某种算法得出本次与甲通信的公钥与私钥；
2. 乙将公钥传给甲（公钥可以让任何人知道，即使泄露也没有任何关系）；
3. 甲使用乙传给的公钥加密要发送的信息原文m，发送给乙密文c；
4. 乙使用自己的私钥解密密文c，得到信息原文m .
数学概念
需要了解的几个数学概念 1.质数与互质数 2.欧拉函数 3.欧拉定理 4.模反元素 5.同余
质数与互质数
一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为质数（素数）；否则称为合数。 公约数只有1的两个数，叫做互质数。 1.任意两个质数一定构成互质数（如3与11、53与61）； 2.大数是质数的两个数一定是互质数（如97与88）； 在RSA算法中，我们通常使用以上第1条与第2条，即选取两个本身都是质数的数作为互质数
欧拉函数
任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？ 计算这个值的方法就叫做欧拉函数，以φ(n)表示. 例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以φ(n)=4 在RSA算法中，我们需要明白欧拉函数对以下定理成立 1.如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ(p)φ(q); 2.根据“大数是质数的两个数一定是互质数”可以知道： 一个数如果是质数，则小于它的所有正整数与它都是互质数； 所以如果一个数p是质数，则有：φ(p)=p-1 由上易得，若我们知道一个数n可以分解为两个质数p和q的乘积，则有 φ(n)=(p-1)(q-1)
欧拉定理
如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立： aφ(n)≡1(modn)
模运算与模反元素
模运算：让m去被n整除，只取所得的余数作为结果，就叫做模运算。 例如，10 mod 3 = 1 、26 mod 6 = 2 、28 mod 2 = 0 模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1 ab≡1( mod n) 这时候，b就是a的模反元素
同余
“≡”是数论中表示同余的符号，定义如下： 给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b) mod m=0， 那么就称整数a与b对模m同余，记作a≡b(modm)，同时可成立a mod m=b
需要记住的参数
p,q:大整数N的两个因子（factor） N:大整数N，我们称之为模数（modulus） e,d:互为模反数的两个指数（exponent） c,m:密文和明文，这里一般指的是一个十进制的数 e：公钥 d：私钥
RSA加密流程
- 首先选择两个互为质数p和q (q与p互素，公因数只有1)
- 求出n = p * q
- φ(n) = (p−1)*(q−1) 欧拉公式
- 公钥 e : 随机取，要求：e 和 φ(n) 互素（公因数只有 1）; 1< e < φ(n)；
- 私钥 d ：ed ≡ 1 （mod φ(n) ） （ed 除以 φ(n) 的 余数 为 1 ）
- e与d互为模反元素。
- 明文加密后的密文c = pow(m, e, n)
- 密文解密后的明文m = pow(c, d, n)
pow(x, y[, z])
函数是计算x的y次方，如果z在存在，则再对结果进行取模，其结果等效于pow(x,y) %z
依赖库的安装
apt-get install libgmp-dev
apt-get install libmpfr-dev
apt-get install libmpc-dev
apt-get install python3-pip
pip install gmpy2
RSA题目
简单
在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17 求解出d作为flag提交
import gmpy2
p=473398607161
q=4511491
e=17
d=gmpy2.invert(e,(q-1)*(p-1)) # 求逆元，de ≡ 1 mod n
print(d)
进阶
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
# 已知 p q e c 求 m
import gmpy2
p =9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
n = p*q
c =83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
d = gmpy2.invert(e,(p-1)*(q-1)) # d是私钥
m = gmpy2.powmod(c,d,n) # 幂取模，结果是 C = (M^e) mod n
# m = pow(c,d,n)
print(m)
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/ 查询得出：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
def 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) dpe = 1 mod(p-1) dqe = 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()
解题思路 首先我们看一下公钥的一些参数：
python 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爆破出了结果
python 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
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/
#!/usr/bin/python3
import re
from itertools import product
from Crypto.Util.number import GCD, inverse
def solve_linear(a, b, mod):
if a & 1 == 0 or b & 1 == 0:
return None
return (b * inverse(a, mod)) & (mod - 1) # 计算b*a^(-1)%mod
def to_n(s):
s = re.sub(r"[^0-9a-f]", "", s)
return int(s, 16)
def msk(s):
cleaned = "".join(map(lambda x: x[-2:], s.split(":"))) #去掉冒号和多余字符和空格
return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)
def msk_ranges(s): # 求每一个半字节的取值范围
return [range(16) if c == " " else [int(c, 16)] for c in s]
def msk_mask(s):
return int("".join("0" if c == " " else "f" for c in s), 16)
def msk_val(s):
return int("".join("0" if c == " " else c for c in s), 16)
N = to_n("""\
00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
e8:6c:1d""")
p_ranges, pmask_msk, pmask_val = msk("""\
0: e: : : :c :c : : : :b : : : : :
:ab: e: 2: 8:c : : : 1:6 :6 : 6: f:d9: 0:
8 :5c:7 :06: : : :0 : 3:5 :4b: :6 : : :
2 : :6 : : : :2 :bc: c: :85:1 : 1:d : 3:
1:b4: : b: 1: 3: d:a : : :6e: 0:b :2 : :
:b : :9 :e : :82:8d: : :13: : : a: a:
: :4 : :c : f: : :7 :e :0a: : : b: 5:
: e:91:3 : :3c: 9: : 6: : :b5:7d: 1: :
: : :b :a1:99:6 :4 :3 :c :1a:02:4 : : 9:
9 :f : d:bd: :0 : : : :b3: : 4: :e9: 9:
: d: : :7 : :93: : e:dc: : 0: :e7: :
e : :2 : b: 2:5 : : : : : c:5f: : :e2:
: : 9: :2a: : e: : :2 : :9f: 7:3 : :
b : f:b : : 8: 7: : :f :6 :e :c : :3 : :
f7: 5: 8: 5: : : : : : 8: e: :03: c: :
33:76:e : 1:7 : c: : 0: :0b: : a: : 2: 9:
:c8:bf: : :06: 7:d5: :02: c:b :e2: 7:2 :
: """)
q_ranges, qmask_msk, qmask_val = msk("""\
0: f: :d0: 1:55: 4:31: : b:c4:8 : : e: d:
34: 3:f : : : : : 8:99:1 : : a:0 : :4 :
0 : :f : :a4:41:2 : :a : : 1: : a: c: :
: : 9: : : 2:f4: f: : : : :1 : 4:9 :
a : : :79:0 : : : : : 2: 8:b : :4 : 8:
:9b: 1: :d : :f :e4: :4 :c :e : :3 : :
7:2 : :d :8 :2 :7 : :d :67:fc:e : 0:f9: 7:
8 : : : :1 :2f: :51: : :2e:0a: e:3d: 6:
b : :dd: : 0:fb: :f4: : : :b4: 9:c : :
a: : : :d : : :6b: 2: :9b: a:60: :d6:
0:4f:16:d1: : :5 :fc: :f : :8 : : : :
1: 6:e1:9 : e:4 : 6: c: d:d :73: 3: : :7 :
:8 : 9: :3b:f : 2: : :f1: e: : :1e: :
8 : : : 6:0 : 4:99:e : : 5: : : 4: : :
: a:81:64: :7 :f : 9: d: :9 : : 7:93:f :
ac:8c: : 8: : 0: d: 8: :7 : :1d: :f : :
1 :a :6 :8 : :60: :b3: : : :89: : :14:
:5 """)
_, dmask_msk, dmask_val = msk("""\
: : : f:8 :a5:d : 2: 0:b :7 : : 1: : 4:
1:0d: :3 : :6 : : : b: : : :e : : :
0e: 0:db: :1a:1c:c0: : e: : :99:bc:8 :a5:
7 :7 :7 : b: : : 8: 8: :7 :55: 2: : :f :
b2: : :b :f :4 : : 8: :b : : : : 0: :
0 : :6 :9 : : : : b: 4: : 0: a: 5:07:b :
9: c:9a: 9: : 7:9e: : b:60:f : : : :0 :
: 3:0 : : : : 1:b : : : b: 6:0 :f : :
: 2:18: 6: b:1 : : : : :d3:f3: :a : :
3: : : : : 3: d: 1: 2:7 : : d: : 2: d:
: : d:4 : :d : :6d: c:a :b6: : : : 1:
69: : 7: :89: :c :8 :61: d:25: 3:7 :1b: 4:
b : :8 :55: :49: 1:2 :3 : :1 :e9:a8: 3: :
9 : : 1:f8:d3: :e : :d : :9 :b6: : :71:
1 : :c1: : b: 1: : 6:e : :64: : :1a:c :
: b: :bf:c : : 0: : 8:a :4 : :26:a :5 :
6 : : : :eb: :e5: a: :3e:f9:10:0 : : :
6:0 : : 8: : 1:72: c:0 : f:5 : f:9c: 0: e:
7:b : : : : :d9: 4: : e:c :68: : : :
c: :3a: : :a0:ea: 3: 4: :72:a :d : 8: :
:0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
: :17:6 : : c: b: : f: :3 : 5:6 :3 :0e:
: 7:c :3e: 2: 9: 7: 6: f: e: f: 9: :f3: 9:
a :c1:6 : : 1:9 : :43: : f: 5: :0 :27: 4:
4 :a : :e9: : 8: 4:3 :8a: 6:16:d5:c : e: e:
:d : c:b :a8: : 7: : 9: :7 :7d: : : :
: : :4 :2 : : 3: 3: 6: : : :7b:0 : :
e: :0 : :a : : 5: : : : 5:1 :82:c :0d:
4 :2 :fd:36: 5:50:0 : : :d : f: 6: : :e :
0 : : :ce: :9e:8 : :0 :d :07:b3: : : :
0 :e4: : :68:b :c : : c:5 : : :3 : 7: 2:
c:e0: :5 : : :b4: :ef: 7: :1 :e : 0:f :
:6 : : : :e0:c :3 : : : 3: : d: : :
3: 3: c: a: :b : a:71: 3: 0:a : :4 :5d: :
0 :4 """)
_, dpmask_msk, dpmask_val = msk("""\
: 3:2a: : d: : : : :0 :1 : f: : : 6:
1 :2 :1b:07: a:e :b :c5:58:7 : :e8: 7: 1: c:
: 1:b :a0: 4:0f:5 :67: :3 :7 :6 :f9: : c:
:79: 0:1 :65: :8 : :99: d:d : :2 :9 :0 :
e: :0 : : : : d: :d :7 :6 :a9: a:8b: b:
: : 7: a:37: : :7 :1 :6 : :c2: 7:6 :b :
e: : : : : : :b :3a:5 : : : : : :
: : :cd:8 : : d: :7 : 3: : f:e : c: :
: a: :c : f:c : 7:b :5 : : :2 :8 :8 :6 :
0a: a: : :3 :db: : 4:00: : d: :b : 5: :
20: 2: 5: :82: : 0: 6: :8a: :7 : : 8: :
4: 1: : : : 8:46: : : : : : 0:f :c8:
2 : : c:7 : : 1: : :2 : 0: 5: : : 1:9b:
6:9 : 0:74: :c : :e : : :cb:b :3 :3 : :
2: : :47: :2 : 0:5 : : : d: 6:83: : :
:c7: : :0b: : : c: :3 :8 : :9 :4 : 7:
5 :c0:fe: :f9: 1: :0 : e: 8:02: : f: :c :
55:61""")
_, dqmask_msk, dqmask_val = msk("""\
:0b:7 :4 :0 : 0:6 : 7:7e: : 5: : 7: : a:
a :d : 0: 6: 4:86: : :8 : : : : :e :8f:
9: : : : 1: :2 : : 7: b:1 :5 : f: :8 :
:d :21: :e : d: :c9:e : b: : :1 : : :
:d :a2:b7: : : :f3: :42: :e : c: :f :
: 0:f :7 : 4: 5:34: :4 : c: : :8 :d : 8:
5 :af: 3:1d: 5:4 : :2 : :6 :c : 6:a :1 :5 :
a:9 : :d : : :0a:a1: :f :7 :9 :b : : :
f:2 :27: f: :0 :f6:4d: : : : : :5 : :
4:08: : 5: : 8: 5: : : :18: 4: 8:57: 2:
f: a: : :a8: f: c:f : e: 1:9 :c : 4:9 : :
: : : : : 1: :2 : :d1: : 6:e : d: :
: f:04:2 :8d: : 3: : :b : 8: :d6: : 2:
: : :6 : : f: : : 0:6 : :51: :48:19:
: : :69:4 : c: :c : : f: :f4:d : : f:
d:0 :0d:b :3 : 3:2 : : :6 : b:5 :2 : : c:
1:5a: f:f : : :7e:3e: :d :f :0 : d: c: 6:
1""")
E = 0x10001
def search(K, Kp, Kq, check_level, break_step):
max_step = 0
cands = [0] # 广搜队列
for step in range(1, break_step + 1):
# step代表复原倒数第step步
max_step = max(step, max_step)
mod = 1 << (4 * step)
mask = mod - 1
cands_next = []
for p, new_digit in product(cands, p_ranges[-step]):
pval = (new_digit << ((step - 1) * 4)) | p
# 四个剪枝
if check_level >= 1:
qval = solve_linear(pval, N & mask, mod)
if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
continue
if check_level >= 2:
val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
if val is None or not check_val(val, mask, dmask_msk, dmask_val):
continue
if check_level >= 3:
val = solve_linear(E, 1 + Kp * (pval - 1), mod)
if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
continue
if check_level >= 4:
val = solve_linear(E, 1 + Kq * (qval - 1), mod)
if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
continue
if pval * qval == N: #得到答案
print("Kq =", Kq)
print("pwned")
print("p =", pval)
print("q =", qval)
p = pval
q = qval
d = inverse(E, (p - 1) * (q - 1))
print("d =", d)
coef = inverse(p, q)
from Crypto.PublicKey import RSA
print(RSA.construct((N, E, d, p, q, coef)).exportKey().decode())
quit()
cands_next.append(pval)
if not cands_next:
return False
cands = cands_next
return True
def check_val(val, mask, mask_msk, mask_val):
test_mask = mask_msk & mask
test_val = mask_val & mask
return val & test_mask == test_val
for K in range(1, E):
if K % 100 == 0:
print("checking", K)
if search(K, 0, 0, check_level=2, break_step=20):
print("K =", K)
break
for Kp in range(1, E):
if Kp % 1000 == 0:
print("checking", Kp)
if search(K, Kp, 0, check_level=3, break_step=30):
print("Kp =", Kp)
break
for Kq in range(1, E):
if Kq % 100 == 0:
print("checking", Kq)
if search(K, Kp, Kq, check_level=4, break_step=9999):
print("Kq =", Kq)
break
openssl rsautl -decrypt -inkey private.pem -keyform PEM -in flag.enc -oaep
题目
RSA 私钥恢复和最优非对称加密填充(Jarvis OJ-God Like RSA)
题目给出了三个文件，加密后的 flagflag.enc，残缺的私钥private.corrupted，公钥pubkey.pem
godlikeRSA
解题可参考：https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html
import re
import pickle
from itertools import product
from libnum import invmod, gcd
from Crypto.PublicKey import RSA
def solve_linear(a, b, mod):
if a & 1 == 0 or b & 1 == 0:
return None
return (b * invmod(a, mod)) & (mod - 1) # hack for mod = power of 2
def to_n(s):
s = re.sub(r"[^0-9a-f]", "", s)
return int(s, 16)
def msk(s):
cleaned = "".join(map(lambda x: x[-2:], s.split(":")))
return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)
def msk_ranges(s):
return [range(16) if c == " " else [int(c, 16)] for c in s]
def msk_mask(s):
return int("".join("0" if c == " " else "f" for c in s), 16)
def msk_val(s):
return int("".join("0" if c == " " else c for c in s), 16)
E = 65537
N = to_n("""00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
e8:6c:1d""")
p_ranges, pmask_msk, pmask_val = msk(""" 0: e: : : :c :c : : : :b : : : : :
:ab: e: 2: 8:c : : : 1:6 :6 : 6: f:d9: 0:
8 :5c:7 :06: : : :0 : 3:5 :4b: :6 : : :
2 : :6 : : : :2 :bc: c: :85:1 : 1:d : 3:
1:b4: : b: 1: 3: d:a : : :6e: 0:b :2 : :
:b : :9 :e : :82:8d: : :13: : : a: a:
: :4 : :c : f: : :7 :e :0a: : : b: 5:
: e:91:3 : :3c: 9: : 6: : :b5:7d: 1: :
: : :b :a1:99:6 :4 :3 :c :1a:02:4 : : 9:
9 :f : d:bd: :0 : : : :b3: : 4: :e9: 9:
: d: : :7 : :93: : e:dc: : 0: :e7: :
e : :2 : b: 2:5 : : : : : c:5f: : :e2:
: : 9: :2a: : e: : :2 : :9f: 7:3 : :
b : f:b : : 8: 7: : :f :6 :e :c : :3 : :
f7: 5: 8: 5: : : : : : 8: e: :03: c: :
33:76:e : 1:7 : c: : 0: :0b: : a: : 2: 9:
:c8:bf: : :06: 7:d5: :02: c:b :e2: 7:2 :
: """)
q_ranges, qmask_msk, qmask_val = msk(""" 0: f: :d0: 1:55: 4:31: : b:c4:8 : : e: d:
34: 3:f : : : : : 8:99:1 : : a:0 : :4 :
0 : :f : :a4:41:2 : :a : : 1: : a: c: :
: : 9: : : 2:f4: f: : : : :1 : 4:9 :
a : : :79:0 : : : : : 2: 8:b : :4 : 8:
:9b: 1: :d : :f :e4: :4 :c :e : :3 : :
7:2 : :d :8 :2 :7 : :d :67:fc:e : 0:f9: 7:
8 : : : :1 :2f: :51: : :2e:0a: e:3d: 6:
b : :dd: : 0:fb: :f4: : : :b4: 9:c : :
a: : : :d : : :6b: 2: :9b: a:60: :d6:
0:4f:16:d1: : :5 :fc: :f : :8 : : : :
1: 6:e1:9 : e:4 : 6: c: d:d :73: 3: : :7 :
:8 : 9: :3b:f : 2: : :f1: e: : :1e: :
8 : : : 6:0 : 4:99:e : : 5: : : 4: : :
: a:81:64: :7 :f : 9: d: :9 : : 7:93:f :
ac:8c: : 8: : 0: d: 8: :7 : :1d: :f : :
1 :a :6 :8 : :60: :b3: : : :89: : :14:
:5 """)
_, dmask_msk, dmask_val = msk(""" : : : f:8 :a5:d : 2: 0:b :7 : : 1: : 4:
1:0d: :3 : :6 : : : b: : : :e : : :
0e: 0:db: :1a:1c:c0: : e: : :99:bc:8 :a5:
7 :7 :7 : b: : : 8: 8: :7 :55: 2: : :f :
b2: : :b :f :4 : : 8: :b : : : : 0: :
0 : :6 :9 : : : : b: 4: : 0: a: 5:07:b :
9: c:9a: 9: : 7:9e: : b:60:f : : : :0 :
: 3:0 : : : : 1:b : : : b: 6:0 :f : :
: 2:18: 6: b:1 : : : : :d3:f3: :a : :
3: : : : : 3: d: 1: 2:7 : : d: : 2: d:
: : d:4 : :d : :6d: c:a :b6: : : : 1:
69: : 7: :89: :c :8 :61: d:25: 3:7 :1b: 4:
b : :8 :55: :49: 1:2 :3 : :1 :e9:a8: 3: :
9 : : 1:f8:d3: :e : :d : :9 :b6: : :71:
1 : :c1: : b: 1: : 6:e : :64: : :1a:c :
: b: :bf:c : : 0: : 8:a :4 : :26:a :5 :
6 : : : :eb: :e5: a: :3e:f9:10:0 : : :
6:0 : : 8: : 1:72: c:0 : f:5 : f:9c: 0: e:
7:b : : : : :d9: 4: : e:c :68: : : :
c: :3a: : :a0:ea: 3: 4: :72:a :d : 8: :
:0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
: :17:6 : : c: b: : f: :3 : 5:6 :3 :0e:
: 7:c :3e: 2: 9: 7: 6: f: e: f: 9: :f3: 9:
a :c1:6 : : 1:9 : :43: : f: 5: :0 :27: 4:
4 :a : :e9: : 8: 4:3 :8a: 6:16:d5:c : e: e:
:d : c:b :a8: : 7: : 9: :7 :7d: : : :
: : :4 :2 : : 3: 3: 6: : : :7b:0 : :
e: :0 : :a : : 5: : : : 5:1 :82:c :0d:
4 :2 :fd:36: 5:50:0 : : :d : f: 6: : :e :
0 : : :ce: :9e:8 : :0 :d :07:b3: : : :
0 :e4: : :68:b :c : : c:5 : : :3 : 7: 2:
c:e0: :5 : : :b4: :ef: 7: :1 :e : 0:f :
:6 : : : :e0:c :3 : : : 3: : d: : :
3: 3: c: a: :b : a:71: 3: 0:a : :4 :5d: :
0 :4 """)
_, dpmask_msk, dpmask_val = msk(""" : 3:2a: : d: : : : :0 :1 : f: : : 6:
1 :2 :1b:07: a:e :b :c5:58:7 : :e8: 7: 1: c:
: 1:b :a0: 4:0f:5 :67: :3 :7 :6 :f9: : c:
:79: 0:1 :65: :8 : :99: d:d : :2 :9 :0 :
e: :0 : : : : d: :d :7 :6 :a9: a:8b: b:
: : 7: a:37: : :7 :1 :6 : :c2: 7:6 :b :
e: : : : : : :b :3a:5 : : : : : :
: : :cd:8 : : d: :7 : 3: : f:e : c: :
: a: :c : f:c : 7:b :5 : : :2 :8 :8 :6 :
0a: a: : :3 :db: : 4:00: : d: :b : 5: :
20: 2: 5: :82: : 0: 6: :8a: :7 : : 8: :
4: 1: : : : 8:46: : : : : : 0:f :c8:
2 : : c:7 : : 1: : :2 : 0: 5: : : 1:9b:
6:9 : 0:74: :c : :e : : :cb:b :3 :3 : :
2: : :47: :2 : 0:5 : : : d: 6:83: : :
:c7: : :0b: : : c: :3 :8 : :9 :4 : 7:
5 :c0:fe: :f9: 1: :0 : e: 8:02: : f: :c :
55:61""")
_, dqmask_msk, dqmask_val = msk(""" :0b:7 :4 :0 : 0:6 : 7:7e: : 5: : 7: : a:
a :d : 0: 6: 4:86: : :8 : : : : :e :8f:
9: : : : 1: :2 : : 7: b:1 :5 : f: :8 :
:d :21: :e : d: :c9:e : b: : :1 : : :
:d :a2:b7: : : :f3: :42: :e : c: :f :
: 0:f :7 : 4: 5:34: :4 : c: : :8 :d : 8:
5 :af: 3:1d: 5:4 : :2 : :6 :c : 6:a :1 :5 :
a:9 : :d : : :0a:a1: :f :7 :9 :b : : :
f:2 :27: f: :0 :f6:4d: : : : : :5 : :
4:08: : 5: : 8: 5: : : :18: 4: 8:57: 2:
f: a: : :a8: f: c:f : e: 1:9 :c : 4:9 : :
: : : : : 1: :2 : :d1: : 6:e : d: :
: f:04:2 :8d: : 3: : :b : 8: :d6: : 2:
: : :6 : : f: : : 0:6 : :51: :48:19:
: : :69:4 : c: :c : : f: :f4:d : : f:
d:0 :0d:b :3 : 3:2 : : :6 : b:5 :2 : : c:
1:5a: f:f : : :7e:3e: :d :f :0 : d: c: 6:
1""")
def search(K, Kp, Kq, check_level, break_step):
max_step = 0
cands = [0]
for step in range(1, break_step + 1):
#print " ", step, "( max =", max_step, ")"
max_step = max(step, max_step)
mod = 1 << (4 * step)
mask = mod - 1
cands_next = []
for p, new_digit in product(cands, p_ranges[-step]):
pval = (new_digit << ((step - 1) * 4)) | p
if check_level >= 1:
qval = solve_linear(pval, N & mask, mod)
if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
continue
if check_level >= 2:
val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
if val is None or not check_val(val, mask, dmask_msk, dmask_val):
continue
if check_level >= 3:
val = solve_linear(E, 1 + Kp * (pval - 1), mod)
if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
continue
if check_level >= 4:
val = solve_linear(E, 1 + Kq * (qval - 1), mod)
if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
continue
if pval * qval == N:
print("Kq =", Kq)
print("pwned")
print("p =", pval)
print("q =", qval)
p = pval
q = qval
d = invmod(E, (p - 1) * (q - 1))
coef = invmod(p, q)
print (RSA.construct(map(int, (N, E, d, p, q, coef))).exportKey())
quit()
cands_next.append(pval)
if not cands_next:
return False
cands = cands_next
return True
def check_val(val, mask, mask_msk, mask_val):
test_mask = mask_msk & mask
test_val = mask_val & mask
return val & test_mask == test_val
# K = 4695
# Kp = 15700
# Kq = 5155
for K in range(1, E):
if K % 100 == 0:
print ("checking", K)
if search(K, 0, 0, check_level=2, break_step=20):
print ("K =", K)
break
for Kp in range(1, E):
if Kp % 1000 == 0:
print ("checking", Kp)
if search(K, Kp, 0, check_level=3, break_step=30):
print ("Kp =", Kp)
break
for Kq in range(1, E):
if Kq % 100 == 0:
print ("checking", Kq)
if search(K, Kp, Kq, check_level=4, break_step=9999):
print ("Kq =", Kq)
break
最优非对称加密填充
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
with open('pubkey.pem', 'r') as f:
key = RSA.importKey(f)
N = key.n
e = key.e
print(N)
print(e)
with open('private.pem', 'r') as f:
private = RSA.importKey(f)
oaep = PKCS1_OAEP.new(private)
with open('flag.enc', 'r') as f:
print(oaep.decrypt(f.read()))
已知p q e 求 n
# 已知p q e 求 n
# 在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
import gmpy2
p = 473398607161
q = 4511491
e = 17
n = (p-1)*(q-1)
d = gmpy2.invert(e,n)
print(d)
附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