积累一种攻击。
题目关键部分：
def special_rsa(self):
kbits = 37
abit = 62
M = 962947420735983927056946215901134429196419130606213075415963491270
while True:
k = getRandomNBitInteger(kbits)
a = getRandomNBitInteger(abit)
p = k * M + pow(0x10001, a, M)
if isPrime(p):
break
while True:
l = getRandomNBitInteger(kbits)
b = getRandomNBitInteger(abit)
q = l * M + pow(0x10001, b, M)
if isPrime(q):
break
n = p * q
self.send(b'n = ' + str(n).encode())
flag = open('flag', 'rb').read()
m = bytes_to_long(flag)
c = pow(m, 0x10001, n)
self.send(b'c = ' + str(c).encode())
self.request.close()
可以看到p、q的生成方式：
$p=k\cdot M + 65537^a \mod M$
$q=l\cdot M + 65537^b \mod M$
M是光滑数。
在GitHub上找到攻击方法。jvdsn/crypto-attacks: Python implementations of cryptographic attacks and utilities. (github.com)
在roca.py文件末尾加上代码：
# Some logging so we can see what's happening.
logging.basicConfig(level=logging.DEBUG)
M = 962947420735983927056946215901134429196419130606213075415963491270
N = 14481363580917358871472996410471767154481047067466167591298208947805462002275531552979475988627964256677709787930755013972295770123571982960720640872341517
p_, q_ = factorize(N, M, 5, 6)
print(f"Found p = {p_} and q = {q_}")
其中参数5和6的选择是根据n的位数决定的，具体的有：
当n位数为512bit时，m = 5，t = 6
当n位数为1024bit时，m = 4，t = 5
当n位数为2048bit时，m = 6，t = 7
当n位数为3072bit时，m = 25，t = 26
当n位数为4096bit时，m = 7，t = 8
论文可参考：
接着执行roca.py文件，这里涉及到
在sagemath上执行py文件。
我用的是pycharm，改好脚本后。
打开路径：
...\SageMath 9.3\runtime\opt\sagemath-9.3\src
建一个工作文件夹，把脚本代码放进去（我这里是把在GitHub上下载的攻击方法集合全部复制进去了）。
接着打开SageMath 9.3 Shell，看自己的版本号，注意是Shell，不是SageMath 9.3。
打开roca.py所在文件夹：
cd 'D:\sagemath\SageMath 9.3\runtime\opt\sagemath-9.3\src\My_sage\crypto-attacks-master\attacks\factorization'
运行：
python ./roca.py
脚本中可能会有些问题需要修改。
整个运行过程很慢，最终能分解出p、q来。
题目参考：
20220423-DASxFATE-CryptoSecPartWriteUp | 4XWi11’s Blog
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com