NSSCTF:
[SWPUCTF 2022 新生赛]小明文
附件中给出了e=3和c的值,但没有n
可以判断为小明文爆破,根据c+kn = m^e
通过对m开e次方根,如果得到整数,则我们得到对应的flag
1 | import gmpy2 |
[SWPUCTF 2022 新生赛]yafu分解
我们直接用yafu分解出q,p,解密后得到AFFPGS{snzv1l_ov9_gur_g0_Jr1p0zr}
然后通过凯撒或者Rot13解密得到NSSCTF{fami1y_bi9_the_t0_We1c0me}
1 | import gmpy2 |
[SWPUCTF 2022 新生赛]AES
pad部分
是用来用空格补全到16位的,相应的解密时就需要用rstrip()
来删除末尾空格
AES_en部分
则是加密部分,先用CBC模式新建了一个AES_obj
的实例,
AES_obj.encrypt(data.encode("utf-8"))
这一行代码使用了之前创建的AES对象 (AES_obj
) 来加密输入的数据 (data
)。让我们详细解释这个操作:
data.encode("utf-8")
: 将输入的数据data
转换为UTF-8编码的字节序列。AES加密要求输入数据为字节序列,而不是字符串。AES_obj.encrypt(...)
: 这是AES对象的方法,用于对数据进行加密。它接受一个字节序列作为输入,并返回加密后的字节序列。在这里,输入是通过UTF-8编码的数据。
AES_en_str = base64.b64encode(AES_en_str)
则是解码base64的
1 | import base64 |
[HUBUCTF 2022 新生赛]baby_encrypt
题目提示的是加法,推测为前缀和781612443113954655886887407898899451044114412011257135914071455155316031651170318041861191719652013207021272183228423832485254125932643269827992924
进行分割,为了方便解码,在一开始加一个0
构造序列为0 78 161 244 311 395 465 588 688 740 789 889 945 1044 1144 1201 1257 1359 1407 1455 1553 1603 1651 1703 1804 1861 1917 1965 2013 2070 2127 2183 2284 2383 2485 2541 2593 2643 2698 2799 2924 -1
然后前后做差后转字符
1 |
|
[SWPUCTF 2022 新生赛]爆破MD5
附件中可见是MD5爆破
data='Boom_MD5****' flag=MD5(data) print(flag) #0618ac93d4631df725bceea74d0*****
1 | import base64 |
[UUCTF 2022 新生赛]Easy_base64
base64加密后有个前后异或的加密,但除了开头第一个
1 | import base64 |
[UUCTF 2022 新生赛]unsafe_prime
从附件中可知n=p**3
,其中p为质数
那么φ(n)= p^k^-p^k-1^
证明:显然对于从1到p^k^的所有数中,除了p^k-1^个p的倍数以外其他数都与p^k^互素,所以根据欧拉函数
的定义:φ(p^k^)=p^k^-p^k-1^
1 | import gmpy2 |
[SWPUCTF 2023 秋季新生赛]EasyRSA
题目已经给出了p,q,e,c直接RSA解密即可
n=p*q
欧拉函数 Phi=φ(n)=(p-1)(q-1)
C^d^ mod N =M
1 | import gmpy2 |
[鹤城杯 2021]Crazy_Rsa_Tech
加密指数e很小,且只有一个
;
拿到了多组n和c,且模数n不同,但使用相同的加密指数e进行多次加密
==》低加密指数广播攻击
我们要用到的知识点是:中国剩余定理(CRT)
系统来说解法就是:
M1 = m2 * m3;M2 = m1 * m3 ;M3 = m1 * m2;……
设t1为M1的模m1逆元(t1*M1 ≡ 1 mod m1),t2,t3……
则 x=a * M1 * t1 + b * M2 * t2+ ……-k * m1 * m2 * m3*……(适当选择k使得x为最小值)
即 x= (a * M1 * t1 + b * M2 * t2 +……) mod ( m1 * m2 * m3 *……)
d,r,t=gmpy2.gcdext(n,m):
d为n和m的最大公约数,r和t是满足n*r + m*t = d
的一对贝祖系数,如果 n
和 m
互质,那么 t
就是 m
相对于 n
的乘法逆元,而 r
则是 n
相对于 m
的乘法逆元
1 | import gmpy2 |
[SWPUCTF 2023 秋季新生赛]小明文?
Franklin-Reiter相关信息攻击
如果两个信息之间存在已知的固定差异,并且在相同的模数n下进行RSA加密,那么就有可能恢复出这两个消息
简单点说就是m和m+a两个明文在相同的e和n下进行加密,那么m就可以破解
sagemath运行:
1 | n = 13026126941826887019162872735099540876106694302074884925200107036130428843197729140372377590706535217469477301361486550282890330093772372813532795303163348233096919179478061917423707929667355386062657434467799360617526194768968700908096844475960205671302377364202483195391706116078632202015938962280529309403244885363904094804118278167720593581764017089021116316636464533785051436622916960956665030100255641288863474938703 |
得到长整型结果然后转字符
1 | from Crypto.Util.number import * |
[SWPUCTF 2022 新生赛]Welcome to Modern Cryptography
提供了公钥和私钥,直接利用在线RSA解密即可
[SWPUCTF 2023 秋季新生赛]dpdp
dp泄露,给了n,e,c,dp
公式推理:
1 | from Crypto.Util.number import * |
[UUCTF 2022 新生赛]Impossible_RSA
- 从已知条件可得到两个方程:
n=p*q
leak3=p+q
根据这个即可解出p
(或者q
)
-
由于缺少了密文
c
,我们可以通过中国剩余定理
得到,此处采用sage内置的crt() -
由于缺少了e,但给定了e的范围,且范围不是很大,可以爆破得到
以下部分中:
1.注释部分利用sympy库的solve解出p(或q)
2.c=[int(crt([leak1,leak2],[p,q])),int(crt([leak1,leak2],[q,p]))]
由于无法确定第一步得到的是p还是q,所以将两个结果都要算出来
1 | from Crypto.Util.number import * |
[UUCTF 2022 新生赛]简单的数学
1.c=(m*p+kn)^e mod n
2.根据二项式展开可知最后不含n的项仅有m*p
3.c=(m*p)^e mod n
4.m*p=c^d mod n
1 | from Crypto.Util.number import * |
[SWPUCTF 2023 秋季新生赛]dpdpdpdp
将已知信息放入轩禹CTF_RSA工具中,dp先放入Private(D)中,在模式中选取仅dp泄露
得到Prime(P,Q),在常规中计算Euler(φN),然后右键选取计算私钥D,然后计算明文,转为字符
![](https://a1ic3-blog.oss-cn-hangzhou.aliyuncs.com/img/屏幕截图 2024-08-09 134958.png)
[NUSTCTF 2022 新生赛]ezRSA
简单分析可知,p和q差距太大了,所以N~1~/N~2~接近q~1~/q~2~,考虑用连分数逼近N~1~/N~2~,得到q~1~和q~2~
尝试对N~1~/N~2~ 进行连分数展开并求其各项渐进分数,记为 t~i~/s~i~ 并验证 N~1~%t~k~==0 是否成立,如果成立,那么 q~1~=t~k~,q~2~=s~k~。
1 | from Crypto.Util.number import * |
[SWPUCTF 2023 秋季新生赛]polynomial
主要是利用sympy库解多项式方程
1 | from Crypto.Util.number import * |
[SWPUCTF 2022 新生赛]DisceteDiscrete!
-
附件中可见的并非RSA加密,因为
c=x^m mod n
,明文m在指数位置,且同时还存在模运算, -
为了求得m,则会进行基于同余运算和原根的一种对数运算,也就是**
离散对数
**
本题很简单,只需直接利用sage中的内置函数discrete_log()
即可
1 | n = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 |
[HGAME 2022 week2]RSA Attack2:
task1 : 公像素数,task2:直接开根,task3:共模攻击
1 | from Crypto.Util.number import * |
[HGAME 2022 week3]RSA attack 3:
连分数攻击
n和e的位数差不多
1 | #Sage |
[黑盾杯 2020]Factor:
1 | #yafu分解得到三个质因数 |
[FSCTF 2023]兔帽的奇妙冒险:
base64解密的结果加一个U2FsdGVkX18
(rabbit 头)后rabbit解密
[LitCTF 2023]Euler:
c = pow(m,n-p-q+3,n) 其中, n=p * q, n-p-q+3=(p-1)*(q-1)+2
故有: **c = m^( (p-1)*(q-1)+2 )%n **
根据欧拉定理,m^( (p-1)*(q-1) ) = m^phi = 1%n 故有: c = m^2%n 因此,可以直接对c进行开方,爆破求解得到m。
1 | from Crypto.Util.number import * |
[LitCTF 2023]e的学问:
e和phi不互素数,所以要先约去公约数t
1 | from Crypto.Util.number import * |
[LitCTF 2023]Virginia:
两段不同密钥的维吉尼亚,但密钥未知,利用Vigenere Solver
爆破
但发现最后还有一段是乱码,再次爆破
My password is not a regular Caesar password,and the enc flag=[86, 116, 128, 80, 98, 85, 139, 122, 134, 114, 125, 136, 117, 123, 129, 127, 128, 128, 142, 130, 140, 147, 127, 132, 131, 136, 151, 134, 152, 164] -Caesar
参考ASCII码表:
根据比赛的flag头为LitCTF
,
发现第一个字符偏移为10,第二个为11,第三个为12……属于变异凯撒
1 | enc=[86, 116, 128, 80, 98, 85, 139, 122, 134, 114, 125, 136, 117, 123, 129, 127, 128, 128, 142, 130, 140, 147, 127, 132, 131, 136, 151, 134, 152, 164] |
[LitCTF 2023]The same common divisor (高级):
n3 = n1 ^ n2 ,则 n2= n3 ^ n1
1 | from Crypto.Util.number import* |
[LitCTF 2023]Where is P?:
CopperSmith攻击:p高位泄露
pbits=1024 , kbits=340,
P^3^的大小跟n很接近,可以通过爆破得出P,
然后就是常规的CopperSmith攻击
1 | #Sage |
[LitCTF 2023]babyLCG:
LCG板子题:
1 | from Crypto.Util.number import * |
[AFCTF 2018]Single:
quipquip一把梭
[柏鹭杯 2021]试试大数据分解?:
1 | from xenny.ctf.crypto.modern.asymmetric.rsa.factor import attack |
[红明谷CTF 2022]easy_ya:
coppersmith:
1 | #Sage |
[HITCTF 2021]Baby ECC:
1 | #Sage |
[鹤城杯 2021]BabyRSA:
coppersmith攻击:
题目给出了**p的高300位
和q的低265位
**:
n = p~l~ * q~l~ (mod 2^265^)
pl = n*q~l~^-1^ (mod 2^265^)
==> q~l~ = q % (2^265^) = hint2
==> q~l~^-1^ = invert(hint2 , 2^265^)
则p的高300位和低265位之和为:
**pbar = p~h~ +p~l~ = (hint1<<724) + n * invert(hint2 , 2^265^) **
中间459位接下来通过coppersmith求解:
低265位为p~l~,由于直接构造 **f = pbar + x * 2^265^ **会导致无解
所以尝试相对于2^265^抬高2^6^ 以进行爆破(未知:459==>453)
因此,在coppersmith
中,构造f的表达式中间项为x * 64 + 2^265^,
对应small_roots系数为 X = 2^453^
1 | #Sage |
[广东强网杯 2021 团队组]RSA and BASE?:
e很大,跟n接近,先用wiener攻击
得到base32加密后的结果
注意到此处的BASE都是不重复的,猜测是换表base32
加密,但有四位未知,爆破
注意:加密字符表单的作用只是根据下标来映射而已,所以我们一一对应用题目新的表单来对应原生的base32加密下标。
1 | from Crypto.Util.number import * |
[安洵杯 2020]easyaes:
首先根据len(key) == 16
可以知道key是128位的,而len(hint) == 32
,所以在异或过程中会有一半的hint没有被异或,
而且根据hint = os.urandom(4)*8
则hint是4字节重复的,
==》通过hint ^ key
可以泄露出key
aes = AES.new(key,AES.MODE_CBC,iv)
解释一下:
AES.new()
创建一个新的AES实例key
是加解密过程中的密钥,应是一个字节数组,长度取决于所选的AES密钥长度AES.MODE_CBC
表示使用CBC模式,为一种加密迭代过程iv
为初始化向量,在CBC模式下用于加密第一个数据块
测试得到len(msg) == 64
,根据key我们要每16个字节分一组,然后反转让低字节的放在前面
CBC模式
下,每次的明文会先和前一个密文异或然后在根据密钥加密,所以解密过程也是一样,
每次密文要先和前一个得到的明文异或然后在根据密钥解密,而跟第一个密文异或的就是初始化向量,也就是我们的flag
在解密时我们采用最简单的一对一的ECB模式
1 | from Crypto.Util.number import long_to_bytes |
[HDCTF 2023]Math_Rsa:
解法一:
利用a = pow(p,2,r)
,Sagemath已知a,r ==> p
1 | #Sage |
其中,PR.<p> = PolynomialRing(Zmod(r))
Zmod(r)
:指定模,定义界限为r的环;Z表示整数;Zmod代表这是一个整数域中的r模环ZZ
:整数环;QQ
:有理数环;RR
:实数环;CC
:复数环PR
:只是一个指针,指向PolynomialRing指定的那个环(可以使用任意字符)PolynomialRing
:这个是说建立多项式环<p>
: 指定一个变量,可以是任意字符f = (p^2) - a
则是定义一个函数fans = f.roots()
是求解f中所有满足函数的自变量
解法二:
根据a = pow(p,2,r)
可知a是模r的二次剩余,且提示了r%4==3
1 | import gmpy2 |
羊城杯 2021:
[羊城杯 2021]Bigrsa:
发现n1和n2共享素数
1 | from Crypto.Util.number import * |
[羊城杯 2021]Easy_Rsa:
Common Prime RSA ,攻击方式是一种修改的phllard_rho
参考论文:
1 | from Crypto.Util.number import * |
LitCTF 2024:
[LitCTF 2024]small_e:
小明文爆破
1 | from Crypto.Util.number import * |
[LitCTF 2024]common_primes_plus:
已知条件:
-
hint1 = a * n1+b * n2
,hint2 = c * n1 + d * n2
-
已知 hint1,hint2,c,n1,且abcd均为素数
-
==> 可知
p = gcd(hint1,hint2) = gcd(n,hint1) = gcd(n,hint2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17from Crypto.Util.number import *
from gmpy2 import *
n1 = 72619153900682160072296441595808393095979917106156741746523649725579328293061366133340736822282117284050717527134297532031234706715551253283030119063143935874516054785948327252045453986903379262257406260016876625891582923191913450785482873961282498295762698500898694660964018533698142756095427829906473038053
hint1 = 115150932086321440397498980975794957800400136337062771258224890596200580556053305338941267789684878816176014493153795643655219028833232337281425177163963414534998897852644398384446019097451620742463880027107068960452304016955877225140421899265978792650445328111566277376529454404089066088845864500514742797060500618255170627
hint2 = 166820160267525807953634213157298160399912450930658918773153592459310847514047652216110562360456335336533080444219104489314586122760398361430693763814336759476811490524054588094610387417965626546375189720748660483054863693527537614055954695966458622029711055735399842018236940424665041143785192280089418185085532002136215976
c = 28378912671104261862184597375842174085651209464660064937481961814538145807266472966765374317717522401362019901110151858589886717440587644003368826809403188935808872400614919296641885383025657934630410406898092262104442977722339379234085663757182028529198392480656965957860644395092769333414671609962801212632
e = 65537
p = gcd(hint1, hint2)
q = n1//p
phi = (p-1)*(q-1)
d = invert(e, phi)
m = pow(c, d, n1)
print(long_to_bytes(m))
[LitCTF 2024]common_primes:
p = gcd(n1,n2)
1 | from Crypto.Util.number import * |
[LitCTF 2024]真·EasyRSA:
史
1 | from Crypto.Util.number import * |
[LitCTF 2024]small_e_plus:
先爆破出e,然后爆破flag
- 此时如果采取小明文爆破的话,效率很低
1 | from Crypto.Util.number import * |
[LitCTF 2024]真·签到!!!
先爆破出e,然后爆破出flag
1 | from Crypto.Util.number import * |
[LitCTF 2024]little_fermat:
1 | from Crypto.Util.number import * |
[LitCTF 2024]little_fermat_plus:
这里其实用到了费马小定理的扩展,由费马小定理得
666666^p−1^≡1 (mod p)
如果我们给两边同时乘上y次方,就有
666666^y(p−1)^≡1^y^(mod p)
1 | from Crypto.Util.number import * |
[LitCTF 2024]Polynomial_plus:
多项式利用roots()
,找到多项式的根,进而求解出k
1 | #Sage |
[LitCTF 2024]Polynomial:
solve解方程
1 | from Crypto.Util.number import * |
[LitCTF 2024]CRT:
1 | from Crypto.Util.number import * |
[LitCTF 2024]CRT_plus:
低加密指数广播
1 | #Sage |
[LitCTF 2024]midRSA:
已知p的高位和低位,找到中位即可
1 | # Sage |
[RoarCTF2019]babyRSA:
1 | from Crypto.Util.number import * |
[湖湘杯 2021]signin:
解法一:
**n~1~= p~1~^4^*q~1~ 和n~2~= p~2~^4^*q~2~ **
看到这种多因子+大数都可以考虑连分数分解
由题可知 p2 > p1
,
则 n1/n2 = (p1/p2)^4^ * (q1/q2) < q1/q2
q1/q2 ∈ (n1/n2,1)
对 n1/n2
进行连分数展开并求其各项渐进分数,进而求解 q1、q2
1 | from Crypto.Util.number import * |
解法二:
wiener能解的题目一般格
都能解
n = p^4^q,pbits = 360,qbits = 128
根据连分数渐进得到的公式**|n1/n2 -q1/q2| **,
我们令s = n2 * q1 - n1 * q2
再补充一个恒等式q2 = q2
但考虑到(s,q2)
的配平,
引入一个平衡矩阵的项D = (n2//q2).bit_length()-q2.bit.length()
~(再减去2留出安全余量)~
这样我们就能构造一个格[[n2,0],[-n1,D]]
最终的式子就是:(q1,q2)[[n2,0],[-n1,D]] = (s,q2)
1 | #Sage |
[强网杯 2022]ASR:
n = p^2^ × q^2^ × r^2^ × t^2^ = (p × q × r × t)^2^ 开方后分解更容易,借助yafu或者factordb得到了p,q,r,t
e与phi不互质
,而且e很小,结合中国剩余定理(CRT)求解:
-
将同余方程 m^e^ ≡ c mod n 化为
- m^e^ ≡ c mod p
- m^e^ ≡ c mod q
- m^e^ ≡ c mod r
- m^e^ ≡ c mod t
-
分别求解以上剩余类环(Zmod())得到了
- m ≡ m~1~ mod p
- m ≡ m~2~ mod q
- m ≡ m~3~ mod r
- m ≡ m~4~ mod t
-
利用中国剩余定理结合以上m~1~ ~ m~4~得到若干m值,
- 根据条件筛选
- 或者全部转字符观察可见明文
1 | from Crypto.Util.number import * |
moectf-2024:
week1
1.现代密码学入门指北:
RSA解密(有n,p,q,c,e)
1 | from Crypto.Util.number import * |
2.Signin:
用已知信息表示Phi即可
1 | from Crypto.Util.number import * |
3.ez_hash:
题目介绍中说是联系方式,则应是纯数字
,利用hashcat爆破
1 | hashcat -m 1400 -a 3 3a5137149f705e4da1bf6742e62c018e3f7a1784ceebcb0030656a2b42f50b6a 2100?d?d?d?d?d?d |
1400表示sha256的编码,?d为数字
4.Big and small:
小明文爆破
1 | from Crypto.Util.number import * |
5.baby_equation:
k已知,(a^2^ + 1)(b^2^ + 1) - 2(a - b)(ab - 1) = 4*(k + a*b)
化简得到 (a+1)^2^(b-1)^2^=4k
1 | from Crypto.Util.number import * |
接下来要爆破对应a,b的因子组合
1 | from itertools import combinations |
1 | factors = [ |
week2:
1.大白兔:
1 | from Crypto.Util.number import * |
2.More_secure_RSA:
C = m^e^ mod (n*r) ,又n,r互素
==> C = m^e mod r
1 | from Crypto.Util.number import * |
3.new_system:
由条件可得到 c1+c2-c3 = (a1+a2-a3) mod q
令 C = c1+c2+c3
, A = a1+a2+a3
即 C = Ax mod q
则 **CA^-1^ mod q = x **
1 | from Crypto.Util.number import * |
4.ezlengrede:
通过判断二次剩余
1 | from Crypto.Util.number import * |
5.rsa_revenge:
RSA剪枝问题:
- 已知条件: n = p*q ,p和q的二进制序列相反
- 搜索方式:
- 从低位向高位搜索
- p的低位bits位已知,与xor的高bits位同
- 剪枝条件:
- 将p和q剩下位全部填充为1,需要满足p*q>n
- 将p和q剩下位全部填充为0,需要满足p*q<n
- 这里注意要把p的已知的高bits位加上
- 确保p*q的已知高位与n相同
- 结束条件:
- bits = 256
- n = p*q
1 | from Crypto.Util.number import * |
BaseCTF-2024:
week1:
1.你会算md5吗:
md5碰撞
1 | from hashlib import md5 |
2.helloCrypto:
AES解密
1 | from Crypto.Cipher import AES |
3.ez_rsa:
1 | from Crypto.Util.number import * |
4.十七倍:
计算了 17 在模 256 下的逆元(即乘法逆元
)。然后,对于 cipher
数组中的每一个元素,我们使用逆元来恢复原始的字符值,并将这些值组合成一个字节串。
1 | from Crypto.Util.number import * |
5.babyrsa:
用sage计算Phi
1 | from Crypto.Util.number import * |
6.babypack:
简单的**背包解密
**
根据加密:
1 | for i in range(length): |
exp:
1 | from Crypto.Util.number import * |
7.ez_math:
矩阵运算,det_B=1
,最后flag=det_MAT/(point1-point2)
这里用gmpy2的mpz来存储大整数
1 | from Crypto.Util.number import * |
8.mid_math:
与上一题解法相同
1 | from Crypto.Util.number import * |
week2:
1.two_squares:
直接利用sage的内置函数two_squres()
分解平方数
1 | #Sage |
2.铜匠:
给了p的高位和q的低位,
简单变形:
n = p~low~ * q~low~ (mod 2^266^)
p~low~ = n * q~low~ (mod 2^266^)
1 | #Sage |
3.random_primes:
题目提示len(flag)==45
,
则n的大小大概为2^360^ , 而其中的组成n的素因子的大小为2^128^,也就是说三个素因子的乘积就已经比n大,
所以我们只要知道其中组成n的三个因子即可求解
1 | from Crypto.Util.number import * |
4.basic:
1 | from pwn import * |
5.try_to_factor:
1 | from Crypto.Util.number import * |
6.mid_math2:
1 | #Sage |
week3:
1.没有n啊:
yafu分解c,得到质因数,然后得到phi_c,然后解出n,注意此处由于先是计算c = pow(m,e,n), 然后是 x = pow(n,e,c),所以c是比n小的,此处 n = n+c
1 | from Crypto.Util.number import * |
2.exgcd:
共模攻击,e1e2不互素
1 | from Crypto.Util.number import * |
3.wiener? :
leak = decimal.Decimal((3 * P * Q-1)/(3 * Q * Q))
直接对leak进行连分数展开即可得到P/Q
,则分子为P,分母为Q
1 | #Sage |
4.没有n啊 _pro:
5.ez_log:
用sage里内置的log可以解 z = y^x^ mod n 中的x,然后AES解密
1 | #Sage |
week4:
3.rabin:
e=4,如果是一般的rabin算法的话e要求为2,此处只要在最后求解出的m处开个平方根即可
1 | from Crypto.Util.number import * |
buuctf-2023:
week1:
1.Caesar’s Secert:
凯撒加密,偏移为5
flag{ca3s4r’s_c1pher_i5_v4ry_3azy}
2.Fence:
栅栏加密,栏数为2
flag{reordering_the_plaintext#686f8c03}
3.brainfuck:
brainfuck加密
flag{Oiiaioooooiai#b7c0b1866fe58e12}
4.Vigenère:
维吉尼亚加密,密钥为kfc
flag{la_c1fr4_del_5ign0r_giovan_batt1st4_b3ll5s0}
5.babyencoding:
第一段为base64加密,结果为flag{dazzling_encoding#4e0ad4
第二段为base32加密,结果为f0ca08d1e1d0f10c0c7afe422fea7
第三段为UUencode加密,结果为c55192c992036ef623372601ff3a}
6.babyxor:
单步异或
1 | from pwn import xor |
7.babyrsa:
提供了n,c,e,且n的位数不大,可以直接利用sage的factor()分解,用euler_phi()计算得到Phi
1 | from Crypto.Util.number import * |
8.Affine:
仿射加密Affine cipher:
加密函数:e(x) = ax+b (mod m)
解密函数:d(x) = a^-1 *(x-b) (mod m)
求乘法逆元的公式子:a*a^(-1) (mod m) = 1
字母含义及加密条件:
1 | from Crypto.Util.number import * |
9.Small d:
e过大,d很小,可以通过算法快速得到d的值
1 | from Crypto.Util.number import * |
10.babyaes:
解密 flag 我们需要获取到 key 和 iv 的值,由条件:
key=os.urandom(16)*2
iv=os.urandom(16)
可知:key是32bytes,256bits ;iv是16bytes ,128bits
key^iv ,那么只有 iv 与 key 的低128位相异或,所以 key 的⾼128位是固定不变的。
所以 xor 的⾼128bits,就是 key 的⾼128bits,进⽽可以得到 key 的所有值256bits。
之后 key 的低128bits,与 xor 的低128bits 相异或,所得结果就是 iv
的值了
得到 key , iv 后就可以直接⽤aes.decrypt()来解密了
1 | from Crypto.Cipher import AES |
week2:
1.不止一个pi:
根据简化剩余系与欧拉函数的性质:
设a=p~1~^a1^p~2~^a2^……p~k~^ak^,则
φ(a) = a(1-1/p~1~)(1-1/p~2~)……(1-1/p~k~)
1 | from Crypto.Cipher import AES |
2.Rotate Xor:
round_rotate_left
:实现了将 num
的最高 step
位移动到最低 step
位的位置,同时保持其他位不变。
根据加密手搓解密脚本即可
1 | from Crypto.Util.number import * |
3.滴啤:
给了 p*q=n
,d mod (p-1)=dp
,pow(m,e,p*q)=c
1 | from Crypto.Util.number import * |
4.halfcandecode:
p,q很接近,可以用yafu分解,也可以q=next_prime(gmpy2.iroot(n)[0]);p=n//q
得到,进而得到前半部分的flag
后半则进行md5爆破
1 | from Crypto.Util.number import * |
5.partial decrypt:
m = c^d mod n
中国剩余定理可写成:
m1 = c^d mod p
m2 = c^d mod q
这时候n的位数降低了,但d的位数依旧很大
利用欧拉函数:
c^d mod p = c^(d mod phi(p)) mod p = c^(d mod (p-1)) mod p
同理:
c^d mod q = c^(d mod phi(q)) mod q = c^(d mod (q-1)) mod q
令 dp = d mod (p-1) = e^(-1) mod (p-1)
同理 dq = d mod (q-1) = e^(-1) mod (q-1)
m1 = c^dp mod p
m2 = c^dq mod q
最后RSA的求解过程为:
qlnv = q^(-1) mod p
h = qlnv * (m1-m2) mod p
m = m2 + h * q
最后的求解过程可以写成:
S = CRT(m1,m2) = m2+((m1-m2)*(q^(-1) mod p))*q
1 | from Crypto.Util.number import * |
week3:
1.Rabin’s RSA:
e=2
,且结合题目,是**Rabin加密
**
先yafu分解出p,q
1 | from Crypto.Util.number import * |
或者利用轩禹CTF-RSA工具中自带的rabin算法:
2.babyrandom:
LCG伪随机数的参数恢复
附件中可见:
1 | def GetRandom(): |
利用线性同余
得到随机数
有结论
a = (X~n~+2 - X~n+1~)(X~n+1~ - X~n~)^-1^ (mod m)
b = X~n+1~ - aX~n~ (mod m)
1 | from Crypto.Util.number import * |
3.knapsack:
4.小明的密码题:
Coppersmith攻击(已知m的高位攻击)
C = m^e mod N
并且我们假设我们知道m的很大一部分m~0~,即 m = m0+x
,但是我们不知道x。
e足够小,且部分明文泄露时,可以采用Coppersmith单变量等式的攻击:
c = m^e mod n = (mbar + x0)^e mod n
其中 mbar = (m>>kbits) <<kbits
当|x~0~|<=N^1/e^时,可以在log N和e的多项式时间内求出x~0~
1 | #Sage |
5.Door:
6.eazy_crt:
RSA-CRT fault attack
:
1 | from Crypto.Util.number import * |
DASCTF2024八月开学季!
1.EZsquares:
1 | #Sage |
SU2023:
1.sign1n:
题目给了WHATF等式,等式两边同乘e3即可求出kphi,尝试用kphi和n分解n;其次在gift函数中容易得到r=2,若r不为2则输出结果必为合数。然后就是已知kphi,分解n
1 | from Crypto.Util.number import * |
2024长城杯(复现):
1.RandomRSA:
1 | from gmpy2 import mpz, isqrt, powmod, invert, is_prime,jacobi |