攻防世界 crypto rsarsa

原题地址：https://adworld.xctf.org.cn/challenges/details?hash=08957e3e-3b35-11ed-abf3-fa163e4fa609&task_category_id=5

原题代码如下：

# Sage
for _ in range(3):
    p = random_prime(2^1024)
    q = random_prime(2^1024)
    n = p*q
    p1=p>>724
    ct=n * inverse_mod(q % (2 ** 265), 2^265) % 2^265
    print('p1=',p1)
    print('ct=',ct)
    print("n=",n)
    e = 65537
    alarm(80)
    m = randint(2,n-1)
    c=pow(m,e,n)
    print('c=', c)
    print('---------------------------------------------')
    m1 = int(input("m="))
    print('---------------------------------------------')
    print()
    if m1!=m:
        print("Nope")
        exit()

print(open("flag.txt","r").read())

分析题目，取两个1024位大质数p、q相乘得n，输出p的高300位p1和处理q得到的ct。m任取（所以不能通过自然语言判断）后加密为c并输出。我们的任务是通过p1、ct和n推出p、q来解密m。验证3轮都正确后输出flag。

线性同余方程的解法

首先对ct进行分析可得线性同余方程组：

$\text{设} q_1 = q \space mod \space 2^{265} \\ \text{设} i=inverse(q_1, 2^{265}) \\ \text{则有} \begin{cases} ct = n \times i \space mod \space 2^{265} \\ 1 \equiv q_1 \times i \space mod \space 2^{265} \end{cases}$

对于线性同余方程 $ax \equiv b \space (mod \space n)$ ：
若 $d = gcd(a, n)$ ， $d$ 整除 $b$ ，那么 $\frac b d$ 为整数。由裴蜀定理，存在整数对 $(r,s)$ （可用扩展欧几里得算法求得）使得 $ar+sn=d$ ，因此 $x_0=r \times \frac b d$ 是方程 (1) 的一个解。其他的解都关于 $\frac n d$ 与 $x$ 同余。即 $x \equiv x_0+(\frac n d) \times t \space (mod \space n) \space (0 \leqslant t \leqslant d-1)$ 。

根据上述线性同余方程的求解方法，可以求得 $i=r \times ct \space mod \space 2^{265}$ ，进而求得 $q_1=inverse(i,2^{265})$ 。

代码如下：

import gmpy2
from Crypto.Util.number import *

def ext_gcd(a, b): #扩展欧几里得算法    
    if b == 0:          
        return 1, 0, a
    else:         
        x, y, gcd = ext_gcd(b, a % b)        
        x, y = y, (x - (a // b) * y)        
        return x, y, gcd

ct = int(input("ct="))
n = int(input("n="))
i = (ext_gcd(n,2**265)[0] * ct) % 2**265
q1 = gmpy2.invert(i,2**265)
print(q1)

至此，我们已经获得了p的高300位p1和q的低265位q1。

Coppersmith已知高位攻击

知道p或q的高位为其位数的约一半时即可
已知e/n，爆破1024位的p，至少需要知道570位二进制。

网上搜了搜发现有道数据一模一样的题：鹤城杯2021 Crypto babyrsa
原理是知道n和q的低265位可以求出p的低265位，结合p的高300位就是565位，爆破剩下5位。

跑脚本罢。

摘录代码如下：

from gmpy2 import *
from Crypto.Util.number import *
 
p1 = 
q1 = 
n = 
mod=pow(2,265)
p0=n*invert(q1,mod)%mod
pbar=(p1<<724)+p0
PR.<x> = PolynomialRing(Zmod(n))
 
for i in range(32):
    f=pbar+x*mod*32
    f=f.monic()
    pp=f.small_roots(X=2^454,beta=0.4)
    if(pp):
        break
    pbar+=mod
 
p=pbar+pp[0]*32*mod
assert n%p==0
print(p)