2023-0CTF/TCTF-wp-crypto

只解出一个题，还是得多加努力啊。最近事情也不少，后几个题目要复现的话估计也只能等到寒假了。

Double RSA 0

题目描述：

A baby RSA challenge.

CN: nc chall.ctf.0ops.sjtu.cn 32226
EU: nc eu.chall.ctf.0ops.sjtu.cn 32226

题目：

#!/usr/bin/env python3

import random
import signal
import socketserver
import string
from Crypto.Util.number import *
from hashlib import sha256
from secret import FLAG
from os import urandom

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

class LCG:
    def __init__(self):
        self.init()

    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):
        while True:
            p = getPrime(2 * P_BITS)
            if p.bit_length() == 2 * P_BITS:
                self.p = p
                break
        self.b = getRandomRange(1, self.p)
        self.a = [getRandomRange(1, self.p) for _ in range(6)]
        self.s = [getRandomRange(1, self.p) for _ in range(6)]

class RSA:
    def __init__(self, l, p = 0, q = 0):
        self.l = l
        if not p:
            while True:
                p = getPrime(P_BITS)
                if p.bit_length() == P_BITS:
                    self.p = p
                    break
            while True:
                p = getPrime(P_BITS)
                if p.bit_length() == P_BITS:
                    self.q = p
                    break
        else:
            self.p = abs(p)
            self.q = abs(q)
        self.e = getPrime(E_BITS)
        self.check()

    def enc(self, m):
        return pow(m, self.e, self.n)

    def noisy_enc(self, m, r = 1):
        if r:
            self.refresh()
        return pow(m, self.e ^ self.l.next(), self.n)

    def dec(self, c):
        return pow(c, self.d, self.n)
        
    def check(self):
        assert self.p.bit_length() == P_BITS
        assert self.q.bit_length() == P_BITS
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        assert self.e.bit_length() >= E_BITS
        assert self.e < self.phi
        assert GCD(self.e, self.phi) == 1
        self.d = inverse(self.e, self.phi)
        assert self.d.bit_length() >= E_BITS
        for _ in range(20):
            x = self.l.next() % self.n
            assert self.dec(self.enc(x)) == x

    def refresh(self):
        self.e = (self.e ^ self.l.next()) % (2**E_BITS)

class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)

    def proof_of_work(self):
        random.seed(urandom(16))
        proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
        self.dosend('Give me XXXX:')
        x = self.request.recv(10)
        x = x.strip().decode('latin-1')
        if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest:
            return False
        return True

    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass
    
    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def recvn(self, sz):
        r = sz
        res = b''
        while r > 0:
            res += self.request.recv(r)
            if res.endswith(b'\n'):
                r = 0
            else:
                r = sz - len(res)
        res = res.strip()
        return res

    def recv_hex(self, l):
        return int(self.recvn(l + 1), 16)

    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(60)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                return

            signal.alarm(20)
            self.dosend('Give me your RSA key plz.')
            pq = [self.recv_hex(P_BITS // 4) for _ in range(2)]
            lcg = LCG()
            alice = RSA(lcg)
            bob = RSA(lcg, *pq)
            secrets = getRandomNBitInteger(P_BITS // 8)
            secrets_ct = alice.enc(secrets)
            self.dosend('{}\n{}'.format(alice.e, alice.n))
            self.dosend('{}\n{}\n{}\n{}'.format(lcg.p, lcg.a, lcg.b, lcg.s))
            
            CNT = 0
            while CNT < CNT_MAX:
                self.dosend('pt: ')
                pt = self.recv_hex(P_BITS // 2)
                if pt == 0:
                    break
                ct = alice.noisy_enc(pt)
                ct = bob.noisy_enc(ct)
                self.dosend('ct: ' + hex(ct))
                CNT += 1
            print(secrets_ct)
            secrets_ct = bob.noisy_enc(secrets_ct)
            self.dosend('secrets_ct: ' + hex(secrets_ct))
            lcg.init()
            bob = RSA(lcg, *pq)
            self.dosend('{}\n{}\n{}\n{}'.format(lcg.p, lcg.a, lcg.b, lcg.s))

            seen = set()
            while CNT < CNT_MAX:
                self.dosend('ct: ')
                ct = self.recv_hex(P_BITS // 2)
                if ct == 0:
                    break
                pt = alice.dec(ct)
                if pt in seen:
                    self.dosend('You can only decrypt each ciphertext once.')
                    self.request.close()
                else:
                    seen.add(pt)
                pt = bob.noisy_enc(pt)
                self.dosend('pt: ' + hex(pt))
                CNT += 1            
            
            guess = self.recv_hex(P_BITS // 4)
            if guess == secrets:
                self.dosend('Wow, how do you know that?')
                self.dosend('Here is the flag: ' + FLAG)
            else:
                self.dosend('Wrong!')
        except TimeoutError:
            self.dosend('Timeout!')
        except:
            self.dosend('GG')
        self.request.close()

class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 32226
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

这次比赛基于Double RSA系列一共出了四道题，这一道题是这一系列的第一道目。相比于另外几道应该涉及到Lattice的题，这一道题目其实就是一个trick。

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

• 首先定义一个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

#flag{All_Crypto_challenges_in_0CTF/TCTF2023_are_solvable_on_laptop_good_luck_and_have_fun}

*Double RSA1

(坑啊，有一个小区别没注意到，直接导致了这题没做出来(╯°Д°)╯︵ ┻━┻)

回到题目吧，这一题与Double RSA0有以下几个区别：

• LCG类的参数大小有区别，上一题是1024bit的数量级，这一题是512bit的数量级(就是这一点没注意到，实在没想到会在这里设置一个可操作点)
• 最大交互次数从7提高到了70
• 不再提供alice的公钥对(na,ea)
• 第一种交互不再提供lcg的初始状态
• 第二种交互完全不提供lcg的任何参数

而我们要实现的目标与第一题是一样的，利用两种交互去得到secret的值并发送给靶机从而得到flag，但是这一题未知的参数有点多，又该怎么样转换思路实现呢？

首先，发送给靶机的bob的私钥对(p,q)肯定是不变的，依然要选择光滑数便于离散对数求解。

然后就是第一种交互，这里我们没有alice的公钥对(na,ea)，但是由第一题的trick可知(其实第一题有公钥的情况下完全不需要trick，我当时也是为了后面的题目考虑了一下)，我们完全可以传-1给靶机，那么经alice的扰动加密后得到的只有1或An-1两种。而如果是1，那么bob扰动加密得到的结果肯定也是1，因此如果靶机返回的结果不是1的话，那么我们得到的肯定是以下的值：

$$c_i = (n_a-1)^{e_b \oplus noise_i} \quad(mod\;n_b)$$

我们可以多次交互，因此我们可以得到多组上述结果，然后接下来就是如何利用这一结果。我们首先把整个指数看作一个数xi：

$$x_i = e_b \oplus noise_i$$

然后这一题与上一题的区别就体现出来了：xi是一个512bit数量级的值而不再是1024bit，也就是说他在模phinb下是一个小量。为了利用这一点，我们选取模phinb下的一个生成元g，那么就有：

$$n_a-1 = g^y$$ $$c_i = g^{z_i}$$

代回到刚才的式子中，就有：

$$g^{z_i} = g^{yx_i} \quad(mod\;n_b)$$

这个时候就可以把底数g摘掉，而由于g是生成元，因此指数上群阶为phinb，所以有：

$$z_i = yx_i \quad(mod\;\phi(n_b))$$

这个时候应该发现，上面的式子中，zi和phinb我们已知，但是y和xi我们并不知道，但是我们知道的是，y在每一组式子中都不变，且xi是一个小量，因此这里完全可以用HNP解出y和xi，具体实现如下，我们移项得到：

$$x_i = z_iy^{-1}\quad(mod\;\phi(n_b))$$

展开为等式：

$$x_i = z_iy^{-1}+k_i\phi(n_b)$$

因此我们可以构造以下格：

$$\left( \begin{matrix} \phi(n_b) & & & & & \\ &\phi(n_b) & & & & \\ & &... & & & \\ & & &\phi(n_b) & & \\ & & & &\phi(n_b) & \\ z_0 &z_1 &... &z_{n-1} &z_n &1\\ \end{matrix} \right)$$

这个格具有如下关系：

$$(k_0,k_1,...,k_{n-1},k_n,y^{-1}) \left( \begin{matrix} \phi(n_b) & & & & & \\ &\phi(n_b) & & & & \\ & &... & & & \\ & & &\phi(n_b) & & \\ & & & &\phi(n_b) & \\ z_0 &z_1 &... &z_{n-1} &z_n &1\\ \end{matrix} \right) = (x_0,x_1,...,x_{n-1},x_n,y^{-1})$$

然后配平一下数量级就可以规约出所有xi，进一步就能得到y，也就能得到na的值。

然后在第一次交互结束后，bob会将扰动加密后的secret_ct发送给我们，我们需要解开这一层扰动加密才能获得alice公钥加密后的secret值，为此我们需要知道这一次bob扰动加密的加密指数值，再为此，我们需要知道lcg的当前状态，才能向后预测下一个状态。此时我们就需要关注一下LCG的具体实现过程：

$$s_{i+6} = a_0s_{i} + a_1s_{i+1} + a_2s_{i+2} + a_3s_{i+3} + a_4s_{i+4} + a_5s_{i+5} + b \quad(mod\;p)$$

其实这个结构我之前看maple的博客有看到过叫做MRG (Multiple Recursive Generator)，是一种LCG的延申。而容易想到，这既然也是一个线性递推过程，那么就可以用矩阵表示如下：

$$\left( \begin{matrix} s_1\\ s_2\\ s_3\\ s_4\\ s_5\\ s_6\\ 1\\ \end{matrix} \right) = \left( \begin{matrix} &1&&&&&\\ &&1&&&&\\ &&&1&&&\\ &&&&1&&\\ &&&&&1&\\ a_0&a_1&a_2&a_3&a_4&a_5&b\\ &&&&&&1\\ \end{matrix} \right) \left( \begin{matrix} s_0\\ s_1\\ s_2\\ s_3\\ s_4\\ s_5\\ 1\\ \end{matrix} \right) \quad(mod\;p)$$

因此，往后的每一次的状态，其实都可以用初始状态来表示，也就是：

$$\left( \begin{matrix} s_{i}\\ s_{i+1}\\ s_{i+2}\\ s_{i+3}\\ s_{i+4}\\ s_{i+5}\\ 1\\ \end{matrix} \right) = \left( \begin{matrix} &1&&&&&\\ &&1&&&&\\ &&&1&&&\\ &&&&1&&\\ &&&&&1&\\ a_0&a_1&a_2&a_3&a_4&a_5&b\\ &&&&&&1\\ \end{matrix} \right)^i \left( \begin{matrix} s_0\\ s_1\\ s_2\\ s_3\\ s_4\\ s_5\\ 1\\ \end{matrix} \right) \quad(mod\;p)$$

这一点又要怎么利用呢，我们注意到刚才我们利用HNP得到了多个xi的值，而xi又满足：

$$x_i = e_b \oplus noise_i$$

而eb仅有EBITS，因此xi其实会泄露noisei的高(PBITS-EBITS)个bit，而我们知道noisei是MRG的一个状态，也就是说我们能获得多个MRG状态的高位。同时，我们很清楚我们获得的noisei是MRG的第几个状态，那么我们又可以构造一个HNP来直接恢复这个MRG的初始状态，恢复过程如下：

由刚才的MRG递推矩阵表示知道，我们要想获得任意的si，我们只需要让递推矩阵自乘相应的次数，然后取得到矩阵的倒数第二行去乘上初始状态向量(s0,s1,s2,s3,s4,s5,1)就可以了。因此，我们得到的每个state其实都满足以下式子：

$$state = t_0s_{0} + t_1s_{1} + t_2s_{2} + t_3s_{3} + t_4s_{4} + t_5s_{5} + t_6 \quad(mod\;p)$$

其中，t0-t6就是矩阵自乘对应次数后倒数第二行的值，而由于我们知道state的部分高位就是xi的高位，因此我们可以拆分成如下式子：

$$x_{ih} + state_{l} = t_0s_{0} + t_1s_{1} + t_2s_{2} + t_3s_{3} + t_4s_{4} + t_5s_{5} + t_6 + k_ip$$

其中，xih是xi的高位，statel是每个state未知的低位。那么利用多组上述式子我们构造如下的格：

$$\left( \begin{matrix} 1&&&&&&&&t_{i0}&...&t_{j0}\\ &1&&&&&&&t_{i1}&&t_{j1}\\ &&1&&&&&&t_{i2}&&t_{j2}\\ &&&1&&&&&t_{i3}&&t_{j3}\\ &&&&1&&&&t_{i4}&&t_{j4}\\ &&&&&1&&&t_{i5}&&t_{j5}\\ &&&&&&1&&t_{i6}&&t_{j6}\\ &&&&&&&1&-x_{ih}&&-x_{jh}\\ &&&&&&&&p&&\\ &&&&&&&&&...&\\ &&&&&&&&&&p\\ \end{matrix} \right)$$

这个格具有如下线性关系：

$$(s_0,s_1,s_2,s_3,s_4,s_5,1,1,k_i,...,k_j) \left( \begin{matrix} 1&&&&&&&&t_{i0}&...&t_{j0}\\ &1&&&&&&&t_{i1}&&t_{j1}\\ &&1&&&&&&t_{i2}&&t_{j2}\\ &&&1&&&&&t_{i3}&&t_{j3}\\ &&&&1&&&&t_{i4}&&t_{j4}\\ &&&&&1&&&t_{i5}&&t_{j5}\\ &&&&&&1&&t_{i6}&&t_{j6}\\ &&&&&&&1&-x_{ih}&&-x_{jh}\\ &&&&&&&&p&&\\ &&&&&&&&&...&\\ &&&&&&&&&&p\\ \end{matrix} \right) = (s_0,s_1,s_2,s_3,s_4,s_5,1,1,state_{il},...state_{jl})$$

然后配平一下系数，就可以在规约向量中找到初始状态，从而可以预测之后的所有state，进而得到bob的扰动加密的指数，解得alice公钥加密后的secret值，记为ct。

而第二种交互中，我们并不需要向后预测state，而直接一直发送ct的不同幂次，然后类似于上面得到xi的过程构造HNP就可以直接规约出每个加密指数了，然后就可以解出secret。具体来说，比如我们发送ct和ct^2，就分别得到：

$$c_0 = secret^{e_b \oplus noise_0} \quad(mod\;n_b)$$ $$c_1 = secret^{2(e_b' \oplus noise_1)} \quad(mod\;n_b)$$

仍选择生成元g，把这个式子化到指数上阶为phinb的群下，令：

$$c_0 = g^{t_0} \quad(mod\;n_b)$$ $$c_1 = g^{t_1} \quad(mod\;n_b)$$ $$secret = g^{s} \quad(mod\;n_b)$$

依然把扰动加密指数看作一个整体xi，就有：

$$t_0 = sx_0 \quad(mod\;\phi(n_b))$$ $$t_1 = 2sx_1 \quad(mod\;\phi(n_b))$$

同理，就可以获得多组：

$$t_k = (k+1)sx_k \quad(mod\;\phi(n_b))$$

就可以构造HNP了。

而最终实施以上想法的时候其实还会遇到诸多问题，比如模phinb下的群其实并不存在生成元，因此只能退而求其次选一个模phinb/4的生成元，但是这就有可能覆盖不到所有元素，同时最后得到加密指数求解d时也可能会遇到逆元不存在的问题。此外，为了尽可能保证能规约出向量且用更少的次数，我自己测试了一下高斯启发式，发现最少选17，可以稍微多取一点(并且限时20s，再选大点我的小破电脑在这个时间跑不出来)因为选17也就存在较大的可能规约不出的问题。

同时第二个交互要注意我们发送的解密密文是模an下的，然而最后会在模bn下加密，所以要让解密的密文小于bn本身才行，这就要求an小于bn，且发送的幂次不能超过16，而经测试选6就基本能百分百规约出目标向量了。

综上，exp是概率性的，我自己跑了十几二十次的样子。

exp(很冗长)：

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

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

p = 9215910043967720220529428986935011579546841436682673719126600536075021144888438343914167585417604062785693699766893078715324176578589541812924453669152723
q = 9809580353448670071308762148705170648526275547322550022463132456160439721179502787638698716811955251066468003973037004329477541185255363945737432751140919
n = p*q
phi = (p-1)*(q-1)
#choose g as 29(cyclic group of phi/4)
g = 29

def proof_of_work(r):
    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

#tools:DLP
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)//2,(q-1)//2]
    clist = [modp,modq]
    M = crt(modlist,clist)[0]
    return M

#tools:HNP1
def HNP1(p,q,zlist):
    cyclic = (p-1)*(q-1) // 4
    T = len(zlist)
    L = Matrix(ZZ,T+1,T+1)
    K = 2^(P_BITS-2)
    for i in range(T):
        L[i,i] = cyclic*K
        L[-1,i] = zlist[i][0]*K
    L[-1,-1] = 1
    
    res = L.LLL()[1]
    print(res)
    xi = []
    for i in range(len(res[:-1])):
        xi.append((abs(res[:-1][i]) // K , zlist[i][1]))
    y = zlist[0][0]*inverse(xi[0][0],cyclic) % cyclic
    an = powmod(g,y,n)+1
    if(an % 2 == 0):
        an += n

    return xi,an

#tools:HNP2
def HNP2(p,q,zlist):
    cyclic = (p-1)*(q-1) // 4
    T = len(zlist)
    L = Matrix(ZZ,T+1,T+1)
    K = 2^(P_BITS-2)
    for i in range(T):
        L[i,i] = cyclic*K
        L[-1,i] = zlist[i]*K
    L[-1,-1] = 1
    
    res = L.LLL()[1]
    print(res)
    xi = []
    for i in range(len(res[:-1])):
        xi.append(abs(res[:-1][i]) // K)

    return xi

#tools:recover_MRG
def recover_MRG(a,b,p,zlist):   
    #MRG对应的线性递推矩阵
    MRG_lattice = Matrix(Zmod(p),7,7)
    for i in range(5):
        MRG_lattice[i,i+1] = 1
    for i in range(6):
        MRG_lattice[5,i] = a[i]
    MRG_lattice[5,-1] = b
    MRG_lattice[-1,-1] = 1

    #Lattice to recover init_state
    T = len(zlist)
    L = Matrix(ZZ,T+8,T+8)

    K = 2^(P_BITS-E_BITS)
    for i in range(T):
        temp = (MRG_lattice^(zlist[i][1]+1))[5]
        for j in range(7):
            L[j,i+8] = int(temp[j])*K
        L[i+8,i+8] = p*K
        L[7,i+8] = -(zlist[i][0]>>E_BITS<<E_BITS)*K
    for i in range(6):
        L[i,i] = 1
    L[6,6] = 2^P_BITS
    L[7,7] = 2^P_BITS

    res = L.LLL()[6]
    init_state = []
    for i in res[:6]:
        if(i < 0):
            init_state.append(p+i)
        else:
            init_state.append(i)
    return init_state
        

r = remote("chall.ctf.0ops.sjtu.cn",32225)
proof_of_work(r)


#part1:get parameter
r.recvuntil(b'Give me your RSA key plz.')
r.sendline(hex(p)[2:].encode() + b" " + hex(q)[2:].encode())
r.recvline()
lcg_p = int(r.recvline().strip().decode())
lcg_a = eval(r.recvline().strip().decode())
lcg_b = int(r.recvline().strip().decode())


#part2:HNP and recover init_MRG_state
count = 2
#先把六个初始state排掉
for i in range(2):
    r.recvuntil(b"pt: ")
    r.sendline(b"-1")
    r.recvuntil(b"ct: ")

count = 2
Zlist = []
ctlist = []
T = 21
while(1):
    if(len(Zlist) == T):
        r.sendline(b"0")
        break
    #每一次noisy_enc会更新四次lcg的state
    count += 4
    r.recvuntil(b"pt: ")
    r.sendline(b"-1")
    r.recvuntil(b"ct: ")
    ct = int(r.recvline().strip().decode()[2:],16)
    if(ct == 1):
        continue
    else:
        ctlist.append(ct)
        zi = DLP(g,ct,p,q)
        Zlist.append((zi,count))

Zstatelist,an = HNP1(p,q,Zlist)
init_state = recover_MRG(lcg_a,lcg_b,lcg_p,Zstatelist)

#part3:gen next_state to get alice_enc(secret_ct)
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
lcg = LCG(lcg_a,lcg_b,lcg_p,init_state)
r.recvuntil(b'secrets_ct: ')
secret_ct1 = int(r.recvline().strip().decode()[2:],16)

#获取最后一次的扰动加密指数,并得到alice加密后的secret_ct
print(an > n)
last_exponent_noise = DLP(an-1,ctlist[-1],p,q)
for i in range(count+6):
    temp = lcg.next()
last_exponent = last_exponent_noise ^^ lcg.next()
print(len(bin(last_exponent)))
last_exponent =(lcg.next() ^^ last_exponent) % (2**E_BITS)
d1 = inverse(lcg.next() ^^ last_exponent,(p-1)*(q-1))
need_dec = pow(secret_ct1,d1,n)


#part4:HNP2 to get noisy_exponent
P_BITS = 512
E_BITS = int(P_BITS * 2 * 0.292) + 30
CNT_MAX = 70

p = 9215910043967720220529428986935011579546841436682673719126600536075021144888438343914167585417604062785693699766893078715324176578589541812924453669152723
q = 9809580353448670071308762148705170648526275547322550022463132456160439721179502787638698716811955251066468003973037004329477541185255363945737432751140919
n = p*q
phi = (p-1)*(q-1)
#choose g as 29(cyclic group of phi/4)
g = 29

Zlist2 = []
ctlist2 = []
T = 6
for i in range(T):
    r.recvuntil(b"ct: ")
    r.sendline(hex(int(pow(need_dec,i+1,an)))[2:].encode())
    r.recvuntil(b"pt: ")
    ct = int(r.recvline().strip().decode()[2:],16)
    ctlist2.append(ct)
    zi = DLP(g,ct,p,q)
    Zlist2.append(zi)
r.recvuntil(b"ct: ")
r.sendline(b"0")

#part5:get flag
xi = HNP2(p,q,Zlist2)
d2 = inverse(xi[0],(p-1)*(q-1))
secret = pow(ctlist2[0],d2,n)
print(Zlist2)
print(secret)
r.sendline(hex(int(secret))[2:].encode())
r.recvline()
r.recvline()
print(r.recvline())


#flag{DLP_and_HNP_s0_345y}