type
status
date
summary
password
category
slug
icon
RSA+数学???🥹🥹🥹🥹
非常规RSA
2022 ACTF impossible RSA
爆破k求解
因为p,q都是未知，n,e,c是已知量，根据未知量与已知量的关系，经过变换将等式的一边全部转成已知,进而进行爆破：
2022 ACTF RSA LEAK
题解：
leak→爆破出rp,rq
中间相遇攻击
假设 E 和 D 分别是加密函数和解密函数，k1 和 k2 分别是两次加密使用的密钥，则我们有
则我们可以推出
那么，当用户知道一对明文和密文时
- 攻击者可以枚举所有的 k1，将 P 所有加密后的结果存储起来，并按照密文的大小进行排序。
- 攻击者进一步枚举所有的k2，将密文 C 进行解密得到 C1，在第一步加密后的结果中搜索 C1，如果搜索到，则我们在一定程度上可以认为我们找到了正确的 k1 和 k2。
- 如果觉得第二步中得到的结果不保险，则我们还可以再找一些明密文对进行验证。
假设 k1 和 k2 的密钥长度都为 n，则原先我们暴力枚举需要 ，现在我们只需要
输入的rp,rq都只有24位，这里就可以进行爆破，爆破的条件是长度要小于24位
中间相遇爆破：（复杂度降低了）
代码1
代码2
求p,q
因为a和b都很大，直接开四次方是可以直接算出a*b
记 p*q=t,求pp,qq
pp=nextprime(p+rp)
qq=nextprime(q+rq)
两边同时乘以p，消掉q
k1,k2爆破，利用求根公式求解关于p的一元二次方程
GKCTF 2021 RRRRsa
题解
c1 = pow(p,e1,n1),求p
利用二项式定理展开hint1,可将含p*q的项消除。
而hint2的化简可利用费马定理:
可得
模q1
消元,消p1
c2= pow(q,e2,n2),求q
东华杯fermat's revenge
这道题和上面这道可以说结构很像
这里只有一个hint
p = getPrime(1024)q = getPrime(1024)2022 zer0pts CTF Anti-Fermat
题解
q = next_prime(p ^ ((1<<1024)-1))
如果a>b,，且a为0b1111111111(二进制全为1）,那么a^b=a-b
所以((1<<1024)-1)^p=(1<<1024-1)-p
设p^((1<<1024)-1)的下一个素数与p^((1<<1024)-1)相差r（nextprime影响的是非常低位的数据）
则
得到
得到t=p-q
爆破P,条件n%p==0
2022 *ctf crypto Ezrsa
对N开方得到p的高位，异或关系得到p中间几位，coppersmith得到p的低位。
p的高位
🤭方法一：
p,q很接近，直接对n开方求的P的高位
将n的前248位开方
对n开方，取高124位
🤭方法二：
p的中间几位
方法一：
测试
因为异或随机数是在最后300位上，所以125-900位的p，q之和为一个定值，而这一段上p，q的每一位是相反的，因此可以将这一段设为极端情况——p全为1，q全为0。根据基本不等式，p、q的差值越大，积就越大，而最后300位还要继续将q增大。根据这几点可以爆破125-924位，当p*q<n 时，表示这个位置的数正确
方法二：
根据异或的性质，由于异或1,可以得出p,q 的中间600bit的二进制是相反的，所以中间位p+q是固定的(二进制和为1）
方法三：
二分法逼近p,q
p的低位
coppersmith攻击
已知p的高（124+600）bit
拓展
补上bin(adlit(a))函数前的那个0，不难看出两个二进制数是相反的，adlit函数就是对一个数的二进制数进行取反。跟*CTF中间的600位一样。
p+adlit（p）=2^(nbit)-1
羊城杯 2020 RRRRRRRSA
p2 = random.randrange(p1, p1 + bound) , 说明p1,p2相差很小
连分数展开,可以找到q1,q2
🍹总结
有关数学的RSA
- q = inverse(e, p)
- 数据小的数要进行爆破；
- 通过对等式两边同时进行加减乘除等变化，使得等式除了可爆破的变量外，只有一个变量的方程
- 利用求根公式求解方程的根
- 中间相遇爆破可缩短爆破时间
- 二分法逼近
- 当a=b^t+c,b^t特别大时,可以直接开方求出b
- 通过自己生成几个样例来测试数据，有些小数可以直接忽略
- 给一个hint，它和p和q之间有直接关系。尝试mod p或者mod q看一下，利用已知的条件，在同余式中消去另一个因数(消元)，建议把题目给的条件组合组合，在我们规定的mod p或者mod q的条件下，看看都是什么结果。
📎 参考