[TCTF 2023]Double RSA 0 tangcuxiaojkuai的WriteUp

简单描述一下题目内容，首先是类的定义：

首先定义一个LCG类，其具体实现与熟知的那种LCG有一点区别，不过由于这一道题目中会给出LCG的所有参数，所以只需要对该类做调用就可以求出之后的所有state，因此并不需要过于关注LCG的具体实现。
然后定义一个RSA类，他具有正常RSA的生成参数、加密解密等一切功能，此外还有一些额外的功能与限制：
- 会经过check来保证解密指数安全(无法用低解密指数等攻击方式)
- 定义了一个noisy_enc函数，每次调用该函数，会利用LCG对加密指数e做一个更新，并且再加一个noise后对指定明文做RSA加密。具体来说，令noise_i表示LCG的一个状态，则一次noisy_enc加密过程如下：

e = e \oplus noise_i \quad(mod\;2^{EBITS})

c = m^{e \oplus noise_{i+1}} \quad(mod\;n)

类定义完毕后正式进入题目，任务如下：

通过proof
发送给靶机端一个RSA私钥对(p,q)
靶机端生成一个LCG类对象lcg
靶机用lcg对象生成一个RSA类对象alice，同样的，用lcg对象以及刚才传入的RSA私钥对(p,q)生成一个RSA类对象bob
然后，靶机生成一个secret后，用alice的公钥对其进行加密得到secret_ct，并发送给我们alice的公钥e和n，并且发送给我们lcg的全部参数

到这一步我们先整理一下我们的已知信息：

alice：已知e，n，未知p，q
bob：已知p，q，n，未知e
lcg：已知当前全部参数，可以计算出以后的所有state

然后继续回到题目，接下来进行到核心的交互部分，我们有总计不超过七次机会来进行如下几种交互：

首先是第一种交互，我们可以输入一段明文的十六进制pt，靶机会返回给我们如下信息：

ct = bob.noisy_enc(alice.noisy_enc(pt))

输入0可以退出第一种交互，退出后靶机会给我们发送：

bob.noisy_enc(secrets_ct)

发送完毕后，靶机重新生成lcg用于重新初始化bob的RSA类对象，当然同样给我们发送了lcg的全部参数。然后进入第二种交互，每次交互我们可以输入一段密文ct(不能重复)，然后靶机会返回给我们：

bob.noisy_enc(alice.dec(ct))

依然是输入0退出交互，退出后我们可以输入secret值，如果与靶机的secret相等，则可以获得flag

没想到光是说一遍题目内容就写了这么多。。。任务的确还是有一点复杂，可以多理几遍把这个过程搞清楚。

那么接下来进入解题环节，一言以蔽之——**我们的目标是利用开始发送给靶机的RSA私钥对(p,q)，以及后面最多七次的交互，求出secret值。**而我们对于secret的了解在一开始只有：

bob.noisy_enc(alice.enc(secret))

也就是：

[secret^{e_a} \quad(mod\;n_a)]^{e_b \oplus noise_i} \quad(mod\;n_b)

我们要想办法解开这两层加密，为此我们需要解出外层的加密指数值。而想要解出这一层我们需要利用两种交互，可以发现，第一层交互，我们可以输入pt得到：

ct = [pt^{e_a\oplus noise_i} \quad(mod\;n_a)]^{e_b \oplus noise_j} \quad(mod\;n_b)

然后这里就是本题目的核心trick，内层的加密值看上去我们并不知道，但是实际上我们如果令：

pt = n_a-1

那么当内层加密指数为奇数时，其内层的加密结果其实就是：

-1 \equiv pt^{e_a\oplus noise_i} \quad(mod\;n_a)

所以内层的加密结果我们就可以脱掉，得到：

ct = (n_a-1)^{e_b \oplus noise_j} \quad(mod\;n_b)

此时，对于这个等式，我们有：

n_a-1,ct,n_b

所以求解指数变成了一个离散对数问题，而组成nb的私钥p、q是我们可以控制的，所以为了使这个离散对数易求，我们可以选择p-1光滑的素数来组成nb，这样我们就可以求解离散对数问题得到以下两个值：

e_b \oplus noise_j \quad(mod\; p-1)

e_b \oplus noise_j \quad(mod\;q-1)

然后crt组合就能得到：

e_b \oplus noise_j \quad(mod\; lcm(p-1,q-1))

然后再爆破几位就可以得到数量级为1024bit的

e_b \oplus noise_j

了。而由于lcg全部参数都已知，因此我们可以知道任意noise的值，因此我们就可以知道第一层交互每一次的加密指数值，所以对于退出第一层交互后提供给我们的信息：

bob.noisy_enc(secrets_ct)

我们就可以解开这一层bob.noisy_enc，得到secrets_ct，其实也就得到了：

secrets_{ct} = secrets^{e_a} \quad(mod\;n_a)

然后，我们进入第二层交互，把这个值发送给靶机端，靶机端会用alice的私钥解密该信息后，再用更新后的bob对象去noisyenc一遍。而这里的trick其实和第一层是一模一样的，因此我们像第一层交互一样如法炮制，就可以得到更新后的bob的加密指数，然后由于我们有bob的私钥p，q，因此可以RSA解密得到secret，之后发送给靶机就可以了。

当然，这个解法需要满足的条件不少：首先就是trick那一步需要加密指数为奇数，所以把noise看作纯随机数的话，两次利用trick均成功的概率就只有1/4，同时我们最后解密还需要e和phi互素(当然不互素也可以用AMM解，但是限时20s，时间很紧，并且会加大脚本工作量，所以不如反复重连靶机)，就进一步降低了成功概率。但是实际上最多十几次一般也就可以成功一次了。

exp：

from Crypto.Util.number import *
from random import choice
from Pwn4Sage.pwn import *
from tqdm import *
from hashlib import sha256,sha1
import string

P_BITS = 512
E_BITS = int(P_BITS * 2 * 0.292) + 30
CNT_MAX = 7

class LCG:
    def __init__(self,a,b,p,s):
        self.init(a,b,p,s)

    def next(self):
        out = self.s[0]
        self.s = self.s[1: ] + [(sum([i * j for (i, j) in zip(self.a, self.s)]) + self.b) % self.p]
        return out

    def init(self,a,b,p,s):
        self.a = a
        self.b = b
        self.p = p
        self.s = s

#part1 gen_prime
def gen_prime(nbits):
    while True:
        p = 1
        while(int(p).bit_length() < nbits-1):
            p *= choice(sieve_base[1:]) 
        prime = 2*p + 1      
        if isPrime(int(prime)) and int(prime).bit_length() == P_BITS:
            return int(prime)

#p = gen_prime(P_BITS)
#q = gen_prime(P_BITS)
p = 9215910043967720220529428986935011579546841436682673719126600536075021144888438343914167585417604062785693699766893078715324176578589541812924453669152723
q = 9809580353448670071308762148705170648526275547322550022463132456160439721179502787638698716811955251066468003973037004329477541185255363945737432751140919
n = p*q


while(1):
    try:
        #part2 proof_of_work
        def proof_of_work():
            table = string.digits + string.ascii_letters
            temp = r.recvuntil(b"sha256(XXXX + ")
            temp = r.recvline()
            suffix = temp[:16].decode()
            hex1 = temp[20:].strip().decode()
            for i in tqdm(table):
                for j in table:
                    for k in table:
                        for m in table:
                            temp1 = i+j+k+m
                            if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
                                r.sendline(temp1.encode())
                                return
                            
        r = remote("chall.ctf.0ops.sjtu.cn",32226)
        proof_of_work()


        #part3 something to deal with
        from sympy.ntheory.modular import crt
        def DLP(m,c,p,q):
            modp = discrete_log(mod(c,p),mod(m,p))
            modq = discrete_log(mod(c,q),mod(m,q))
            modlist = [p-1,q-1]
            clist = modp,modq
            M = crt(modlist,clist)[0]
            return M


        r.recvuntil(b'Give me your RSA key plz.')
        r.sendline(hex(p)[2:].encode() + b" " + hex(q)[2:].encode())
        r.recvline()
        A_e = int(r.recvline().strip().decode())
        A_n = int(r.recvline().strip().decode())
        lcg_p = int(r.recvline().strip().decode())
        lcg_a = eval(r.recvline().strip().decode())
        lcg_b = int(r.recvline().strip().decode())
        lcg_s = eval(r.recvline().strip().decode())
        temp_LCG = LCG(lcg_a,lcg_b,lcg_p,lcg_s)
        temp_LCG.next()
        temp_LCG.next()
        temp_LCG.next()
        seed1 = temp_LCG.next()

        r.recvuntil(b"pt: ")
        r.sendline(hex(A_n-1)[2:].encode())
        r.recvuntil(b"ct: ")
        ct = int(r.recvline().strip().decode()[2:],16)
        noisy_e1 = DLP(A_n-1,ct,p,q)
        if(noisy_e1 == 0):
            r.close()
            continue
        for i in range(8):
            e1 = (noisy_e1 + i*((p-1)*(q-1) // 4)) ^^ seed1
            if(len(bin(int(e1))) < 512):
                print(e1)
                break
        r.sendline(b"0")
        r.recvuntil(b'secrets_ct: ')
        secret_ct1 = int(r.recvline().strip().decode()[2:],16)
        e1 =(e1 ^^ temp_LCG.next()) % (2**E_BITS)
        d1 = inverse(temp_LCG.next() ^^ e1,(p-1)*(q-1))
        need_dec = pow(secret_ct1,d1,n)

        lcg_p = int(r.recvline().strip().decode())
        lcg_a = eval(r.recvline().strip().decode())
        lcg_b = int(r.recvline().strip().decode())
        lcg_s = eval(r.recvline().strip().decode())
        temp_LCG = LCG(lcg_a,lcg_b,lcg_p,lcg_s)
        temp_LCG.next()
        seed2 = temp_LCG.next()

        r.recvuntil(b"ct: ")
        r.sendline(hex(int(A_n-1))[2:].encode())
        r.recvuntil(b"pt: ")
        pt = int(r.recvline().strip().decode()[2:],16)
        noisy_e2 = DLP(A_n-1,pt,p,q)
        if(noisy_e2 == 0):
            r.close()
            continue
        for i in range(8):
            e2 = (noisy_e2 + i*((p-1)*(q-1) // 4)) ^^ seed2
            if(len(bin(int(e2))) < 512):
                print(e2)
                break
        e2 =(e2 ^^ temp_LCG.next()) % (2**E_BITS)
        d2 = inverse(temp_LCG.next() ^^ e2,(p-1)*(q-1))

        
        #part4 get flag
        r.recvuntil(b"ct: ")
        r.sendline(hex(int(need_dec))[2:].encode())
        r.recvuntil(b"pt: ")
        pt = int(r.recvline().strip().decode()[2:],16)
        secret = pow(pt,d2,n)
        print(secret)

        r.recvuntil(b"ct: ")
        r.sendline(b"0")
        r.sendline(hex(int(secret))[2:].encode())
        r.recvline()
        r.recvline()
        print(r.recvline())
    except:
        r.close()
        pass

不过其实有alice的公钥的话，并不需要去搏这个概率，可以任意伪造密文，只是之后的题目没有alice的公钥，就只能利用这个trick传-1