[0xgame 2023] week2-Crypto

中间的那个人

题目描述：

from secret import flag
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *

p = getPrime(128)
g = 2
A = getrandbits(32)
B = getrandbits(32)

Alice = pow(g,A,p)
Bob = pow(g,B,p)
key = pow(Alice,B,p)
key = sha256(long_to_bytes(key)).digest()

iv = b"0xGame0xGameGAME"
aes = AES.new(key, AES.MODE_CBC, iv)
enc = aes.encrypt(flag)
print(f'g={g}\np={p}')  #we tell
print(f'Bob={Bob}')     #Bob tell
print(f'Alice={Alice}') #Alice tell

print(f'enc={enc}')#Here is they secret

'''
g=2
p=250858685680234165065801734515633434653
Bob=33067794433420687511728239091450927373
Alice=235866450680721760403251513646370485539
enc=b's\x04\xbc\x8bT6\x846\xd9\xd6\x83 y\xaah\xde@\xc9\x17\xdc\x04v\x18\xef\xcf\xef\xc5\xfd|\x0e\xca\n\xbd#\x94{\x8e[.\xe8\xe1GU\xfa?\xda\x11w'
'''

题目分析：
离散对数求解B后得flag
exp:

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
g=2
p=250858685680234165065801734515633434653
Bob=33067794433420687511728239091450927373
Alice=235866450680721760403251513646370485539
enc=b's\x04\xbc\x8bT6\x846\xd9\xd6\x83 y\xaah\xde@\xc9\x17\xdc\x04v\x18\xef\xcf\xef\xc5\xfd|\x0e\xca\n\xbd#\x94{\x8e[.\xe8\xe1GU\xfa?\xda\x11w'
Z = Zmod(p)
B = ZZ(discrete_log(Z(Bob),Z(2)))
print(B)

B = 1620639479
key = pow(Alice,B,p)
key = sha256(long_to_bytes(int(key))).digest()
iv = b"0xGame0xGameGAME"
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(enc)
print(flag)
# 0xGame{51393fe1fd5fc2df1bf018d06f0fa11d}

What’s CRT?

题目描述：

from Crypto.Util.number import *
from secert import flag

m = bytes_to_long(flag)
e = 260792700
q,p,q_,p_ = [getPrime(512) for _ in range(4)]
gift = [q+p,q_+p_]
n,n_ = q*p,q_*p_
mq_ = pow(m,4,q_)
mp_ = pow(m,4,p_)
c = pow(m,e,n)

print(f'mygift={gift}\nmq_={mq_}\nmp_={mp_}\nn={n}\nn_={n_}\nc={c}')
'''
mygift=[15925416640901708561793293991573474917595642805739825596593339102414328214313430010166125066639132916608736569443045051644173933089503934675628814467277922, 18342424676996843423829480445042578097182127446865571536445030052846412665700132683433441858073625594933132038175200824257774638419166516796318527302903098]
mq_=6229615098788722664392369146712291169948485951371133086154028832805750551655072946170332335458186479565263371985534601035559229403357396564568667218817197
mp_=7514598449361191486799480225087938913945061715845128006069296876457814528347371315493644046029376830166983645570092100320566196227210502897068206073043718
n=63329068473206068067147844002844348796575899624395867391964805451897110448983910133293450006821779608031734813916287079551030950968978400757306879502402868643716591624454744334316879241573399993026873598478532467624301968439714860262264449471888606538913071413634346381428901358109273203087030763779091664797
n_=84078907800136966150486965612788894868587998005459927216462899940718213455112139441858657865215211843183780436155474431592540465189966648565764225210091190218976417210291521208716206733270743675534820816685370480170120230334766919110311980614082807421812749491464201740954627794429460268010183163151688591417
c=12623780002384219022772693100787925315981488689172490837413686188416255911213044332780064192900824150269364486747430892667624289724721692959334462348218416297309304391635919115701692314532111050955120844126517392040880404049818026059951326039894605004852370344012563287210613795011783419126458214779488303552
'''

题目分析：
$已知n和p + q，得到p-q = [(p + q)^2-4 * n]^{1/2}，解出p,q\\ 同理求出p\_,q\_\\ 已知m^4 = mq\_ \mod q\_ ①\\ 已知m^4 = mp\_ \mod p\_ ②\\ 又gcd(e,(p - 1) * (q - 1)) = 4\\ 得到d = invert(e // 4,(p - 1) * (q - 1))\\ 得到m^4 = c^d \mod n ③\\ ①, ②, ③进行crt得到m^4，开方得到flag$
exp:

from gmpy2 import *
from Crypto.Util.number import *
from libnum import *
mq_=6229615098788722664392369146712291169948485951371133086154028832805750551655072946170332335458186479565263371985534601035559229403357396564568667218817197
mp_=7514598449361191486799480225087938913945061715845128006069296876457814528347371315493644046029376830166983645570092100320566196227210502897068206073043718
n=63329068473206068067147844002844348796575899624395867391964805451897110448983910133293450006821779608031734813916287079551030950968978400757306879502402868643716591624454744334316879241573399993026873598478532467624301968439714860262264449471888606538913071413634346381428901358109273203087030763779091664797
n_ =84078907800136966150486965612788894868587998005459927216462899940718213455112139441858657865215211843183780436155474431592540465189966648565764225210091190218976417210291521208716206733270743675534820816685370480170120230334766919110311980614082807421812749491464201740954627794429460268010183163151688591417
c=12623780002384219022772693100787925315981488689172490837413686188416255911213044332780064192900824150269364486747430892667624289724721692959334462348218416297309304391635919115701692314532111050955120844126517392040880404049818026059951326039894605004852370344012563287210613795011783419126458214779488303552
paddq = 15925416640901708561793293991573474917595642805739825596593339102414328214313430010166125066639132916608736569443045051644173933089503934675628814467277922
p_addq_ = 18342424676996843423829480445042578097182127446865571536445030052846412665700132683433441858073625594933132038175200824257774638419166516796318527302903098

p_q_ = iroot((paddq) ** 2 - 4 * n,2)[0]
p = (paddq + p_q_) // 2
q = n // p
phi = (p - 1) * (q - 1)
d4 = invert(260792700 // 4,phi)
m4 = pow(c,d4,n)

p_q_1 = iroot((p_addq_) ** 2 - 4 * n_,2)[0]
p_ = (p_addq_ + p_q_1) // 2
q_ = n_ // p_
m = iroot(solve_crt([mp_,mq_,m4],[q_,p_,n]),4)[0]
print(long_to_bytes(m))
# 0xGame{7881ed67088e9f72b860f8c376599785}

EzLFSR

题目描述：

from Crypto.Util.number import *
from secret import flag,secret

assert flag == b'0xGame{'+secret+b'}'

def make_mask(m):
    tmp = str(bin(bytes_to_long(m)))[2:].zfill(128)
    return tmp

def string2bits(s):
    return [int(b) for b in s]

def bits2string(bs):
    s = [str(b) for b in bs]
    return ''.join(s)

def lfsr(state, mask):
    assert(len(state) == 128)
    assert(len(mask)  == 128)

    output = 0
    for i in range(128):
        output = output ^ (state[i] & mask[i])

    return output

if __name__ == '__main__':
    initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
    secret = make_mask(secret)
    mask = string2bits(secret)

    for b in secret: assert(b == '0' or b == '1')
    assert(len(secret) == 128)

    for i in range(256):
        state = initState[i:]
        output = lfsr(state, mask)
        initState += [output]

    outputState = bits2string(initState[128:])
    print('outputState =', outputState)

'''
outputState = 1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110
'''

题目分析：
$二进制形式：\\ mask = m_{128}m_{127}m_{126}...m_{2}m_1\\ State_1 = S_{128}S_{127}S_{126}...S_{2}S_1\\ out_1 = (S_{128} \& m_{128}) \oplus (S_{127} \& m_{127}) \oplus ... \oplus (S_{2} \& m_{2}) \oplus (S_{1} \& m_{1})\\ State_2 = S_{127}S_{126}S_{125}...S_{2}S_1out_1\\ out_2 = (S_{127} \& m_{128}) \oplus (S_{126} \& m_{127}) \oplus ... \oplus (S_{1} \& m_{2}) \oplus (out_{1} \& m_{1})\\ 以此类推，得到GF(2)上的矩阵乘法式：\\ \begin{pmatrix} S_{128}&S_{127}&\cdots&S_2&S_1\\ S_{127}&S_{126}&\cdots&S_1&out_1\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ out_{127}&out_{128}&\cdots&out_{253}&out_{254}\\ out_{128}&out_{129}&\cdots&out_{24}&out_{255} \end{pmatrix}_{256 * 128} * \begin{pmatrix} m_{128}\\ m_{127}\\ \cdots\\ m_{2}\\ m_{1} \end{pmatrix}_{128 * 1} = \begin{pmatrix} out_1\\ out_2\\ \cdots\\ out_{255}\\ out_{256} \end{pmatrix}_{256 * 1}\\ \ \\ 相当于求解Ax = B中的x，其中A,B均可通过转换得到，就是矩阵乘法的求解$
exp:

init = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
R = 0b01011001100001001000111001101101001010100101101011111111011010011010100000110101000111111101101010011110011110101101000000110100
output = 0b1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110
c = '1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110'
c  = [int(i) for i in c]

from Crypto.Util.number import *
from gmpy2 import *
R = 0b01011001100001001000111001101101001010100101101011111111011010011010100000110101000111111101101010011110011110101101000000110100
output = 0b1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110

R_list = [R]
for i in range(1, 256):
    R = ((R << 1) ^^ (output >> 255)) & 0xffffffffffffffffffffffffffffffff
    output = (output << 1) & (2 ** 256 - 1)
    R_list.append(R)

R_binary_list = [list(format(R, '0>128b')) for R in R_list]
R_int_list = [[int(bit) for bit in binary] for binary in R_binary_list]
Rt = matrix(Zmod(2),R_int_list).transpose()

c = matrix(Zmod(2),c)
m = Rt.solve_left(c).list()
m = int(''.join(str(i) for i in m),2)
print(long_to_bytes(m))
# Rec0ver_the_M@sk

Fault!Fault!

题目描述：

from Crypto.Util.number import *
import socketserver
import signal
from secret import flag
import random
import os
import string
from hashlib import sha256
from string import ascii_uppercase
from random import shuffle,choice,randint
import os

q = getPrime(512)
p = getPrime(512)
e = 65537
n = q*p
phi = (q-1)*(p-1)
d = inverse(e,phi)

def decrypt(c,d,n,index):
    """something go wrong"""
    d_ = d^(1<<(index))
    m_ = pow(c,d_,n)
    return str(m_)

MEMU = """
    Welc0me_2_0xGame2023!
/----------------------------\\
|          options           |
| [S]ign                     |
| [F]ault injection          |
| [C]heck answer             |
\\---------------------------/
"""

class Task(socketserver.BaseRequestHandler):
    def proof_of_work(self):
        '''验证函数'''
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def timeout_handler(self, signum, frame):
        raise TimeoutError

        '''以上是交互部分'''
    def handle(self):
        '''题干'''
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(300)
        self.send(MEMU)
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return

        self.send(MEMU.encode())
        while True:
            code = self.recv()
            if code == b'S':
                self.send(b'What you want to sign?:')
                m = bytes_to_long(self.recv())
                c = pow(m,e,n)
                self.send(f'{n}\n{e}\n{c}'.encode())
                
            elif code == b'F':
                self.send(b'Give me the Signatrue:')
                Signatrue = int(self.recv())
                self.send(b'Where you want to interfere?')
                index = int(self.recv())
                self.send(b'The decrypt text:')
                self.send(decrypt(Signatrue,d,n,index).encode())

            elif code == b'C':
                self.send(b'Give me the private key:')
                ans = int(self.recv())
                if ans == d:
                    self.send(b'Here is your flag:')
                    self.send(flag)
                    
            else:
                self.send(b'invaild input')

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

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

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10005
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

题目分析：

m,n,e,c已知，求d

关键在这串：

def decrypt(c,d,n,index):
    """something go wrong"""
    d_ = d^(1<<(index))
    m_ = pow(c,d_,n)
    return str(m_)

d其中一位取反得到d_
所以我们从低位往高位爆，得到所有的c_
如果c_ * pow(c,-2 ** i,n) % n = long_to_bytes(m),说明d - > d_是0 -> 1,得到d的第i位为0
如果c_ * pow(c,2 ** i,n) % n = long_to_bytes(m),说明d - > d_是1 -> 0,得到d的第i位为1
如此即可得到d的所有bit，转int解出d得到flag
exp:

import hashlib
import string
from pwn import *
ip = '43.139.107.237'
port = 10005
r = remote(ip,port)

def proof_of_work():
    r.recvuntil(b'XXXX+')
    suffix = r.recv(16).decode()
    r.recvuntil(b'== ')
    shaa = r.recv(64).decode()

    def f(x):
        hashresult = hashlib.sha256(x.encode() + suffix.encode()).hexdigest()
        return hashresult == shaa

    prefix = util.iters.mbruteforce(f,string.ascii_letters + string.digits,4)
    r.sendline(prefix.encode())

    r.sendlineafter(b'> ',b'S')
    r.sendlineafter(b'> ',b'1')
    n = int(r.recvline().decode().strip())
    e = int(r.recvline().decode().strip())
    c = int(r.recvline().decode().strip())
    d = ''
    for i in range(0,1025):
        r.sendlineafter(b'> ',b'F')
        r.sendlineafter(b'> ',str(c).encode())
        r.sendlineafter(b'>',str(i).encode())
        r.recvline()
        c_ = int(r.recvline().decode().strip())
        t = c_ * pow(c,-2 ** i,n) % n

        if t == 49:
            d = '0' + d
        else:
            d = '1' + d
        print(i)
    print(d)
    d = int(d,2)
    r.sendlineafter(b'> ',b'C')
    r.sendlineafter(b'> ',str(d).encode())
    r.recvline()
    print(r.recvline().decode().strip())
    return
    
proof_of_work()
r.interactive
# 0xGame{F@ult_Milest0ne!!}

EzRSA

题目描述：
challenge1.py:

from Crypto.Util.number import *
from secret import flag1
import random

class RSAServe:
    def __init__(self) -> None:
        self.e = 65537
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.n = self.q*self.p
        self.g, self.r1 = [random.randint(1, self.q*self.p) for _ in range(2)]
        self.gift = pow(self.g, self.r1 * (self.p - 1), self.n)
        self.m = flag1

    def encrypt(self):
        m_ = bytes_to_long(self.m)
        c = pow(m_, self.e, self.p*self.q)
        return hex(c)

    def check(self, msg):
        return msg == self.m

    def pubkey(self):
        return self.p*self.q, self.e,self.gift

challenge2.py:

from Crypto.Util.number import *
from secret import flag2
from random import choice

class RSAServe:
    def __init__(self) -> None:
        self.e = 65537
        self.m = flag2
        self.p = self.GetMyPrime(1024)
        self.q = self.GetMyPrime(1024)

    def GetMyPrime(self,bits):
        while True:
            n = 2
            while n.bit_length() < bits:
                a = choice(sieve_base)
                n *= a
            if isPrime(n + 1):
                return n + 1

    def encrypt(self):
        m_ = bytes_to_long(self.m)
        c = pow(m_, self.e, self.p*self.q)
        return hex(c)

    def check(self, msg):
        return msg == self.m

    def pubkey(self):
        return self.p*self.q, self.e

challenge3.py:

from Crypto.Util.number import *
from secret import flag3
from random import choice
from sympy import *
class RSAServe:
    def __init__(self) -> None:
        self.e = 65537
        self.m = flag3
        self.p = getPrime(896)
        self.n1 = self.getN()
        self.n2 = self.getN()

    def getN(self):
        q = getPrime(128)
        self.p = nextprime(self.p)
        return q*self.p

    def encrypt(self):
        m_ = bytes_to_long(self.m)
        c = pow(m_, self.e, self.n2)
        return hex(c)

    def check(self, msg):
        return msg == self.m

    def pubkey(self):
        return self.n1, self.n2 , self.e

题目分析：
part1:
费马小定理
$\begin{align*} gift &\equiv g^{r1 * (p - 1)} \mod n \\ &\equiv (g^{p-1})^{r1} \mod n \\ &\equiv 1 \mod p \\ \end{align*}\\ p = gcd(gift - 1,n)\\ 之后便是常规的rsa解密了$
exp1:

n = 
p = 
gift = 
e = 
c = 
p = gcd(gift - 1,n)
q = n // p
phi = (p - 1)*(q - 1)
d = invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m)) # b"Fermat's little theorem?"

part2:
Pollard’s p-1光滑
exp2:

n = 
e = 
c = 
def Pollards_p_1(N):
    n = 2
    a = 2
    while True:
        a = pow(a,n,N)
        res = gcd(a-1,N)
        print(n)
        if res != 1 and res != N:
            print('p = ',res)
            return res
        n += 1
p = Pollards_p_1(n)
q = n // p
phi = (p-1)*(q-1)
d = invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m)) # b'EzFactor!'

part3:
$p\\ n2 = q2 * (p + x)\\ \frac{n1}{n2} = \frac{q1 * p} {q2 * (p + x)} \approx \frac{q1}{q2}\\ 连分数求解得到q2$
exp3:

n1 = 
n2 = 
e = 
c = 
def continuedFra(x, y):
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf

def gradualFra(cf):
    numerator = 0 # 分子
    denominator = 1 # 分母
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator

def getGradualFra(cf):
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(e, n):
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for q2, k in gf:
        if isPrime(q2) and q2.bit_length() == 128:
            print(q2,q2.bit_length())
            return q2

q2 = wienerAttack(n1, n2)
p2 = n2 // q2
phi = (p2 - 1) * (q2 - 1)
d = inverse(e,phi)
print(long_to_bytes(pow(c,d,n2))) # Continued fractionnnn

完整exp:

import hashlib
import string
from gmpy2 import *
from Crypto.Util.number import *
from pwn import *
ip = '43.139.107.237'
port = 10006
r = remote(ip,port)
def proof_of_work():
    r.recvuntil(b'XXXX+')
    suffix = r.recv(16).decode()
    r.recvuntil(b'== ')
    shaa = r.recv(64).decode()

    def f(x):
        hashresult = hashlib.sha256(x.encode() + suffix.encode()).hexdigest()
        return hashresult == shaa

    prefix = util.iters.mbruteforce(f,string.ascii_letters + string.digits,4)
    r.sendline(prefix.encode())

    r.sendlineafter(b'> ',b'1')
    r.sendlineafter(b'> ',b'1')
    n = int(r.recvline().decode().strip())
    e = int(r.recvline().decode().strip())
    gift = int(r.recvline().decode().strip())
    r.sendlineafter(b'> ',b'2')
    c = int(r.recvline().decode().strip()[2:],16)
    def decrypt1(n,e,gift,c):
        p = gcd(gift - 1,n)
        q = n // p
        d = inverse(e,(p - 1) * (q - 1))
        m = long_to_bytes(pow(c,d,n))
        return m
    r.sendlineafter(b'> ',b'3')
    r.sendlineafter(b'answer: ',decrypt1(n,e,gift,c))

    r.sendlineafter(b'> ',b'2')
    r.sendlineafter(b'> ',b'1')
    n = int(r.recvline().decode().strip())
    e = int(r.recvline().decode().strip())
    r.sendlineafter(b'> ',b'2')
    c = int(r.recvline().decode().strip()[2:],16)
    def decrypt2(N,e,c):
        n = 2
        a = 2
        while True:
            a = pow(a,n,N)
            p = gcd(a-1,N)
            if p != 1 and p != N:
                q = N // p
                d = inverse(e, (p - 1) * (q - 1))
                m = long_to_bytes(pow(c, d, N))
                return m
            n += 1
    r.sendlineafter(b'> ',b'3')
    r.sendlineafter(b'answer: ', decrypt2(n, e, c))

    r.sendlineafter(b'> ', b'3')
    r.sendlineafter(b'> ', b'1')
    n1 = int(r.recvline().decode().strip())
    n2 = int(r.recvline().decode().strip())
    e = int(r.recvline().decode().strip())
    r.sendlineafter(b'> ', b'2')
    c = int(r.recvline().decode().strip()[2:],16)
    def decrypt3(n1,n2,e,c):
        def continuedFra(x, y):

            cf = []
            while y:
                cf.append(x // y)
                x, y = y, x % y
            return cf

        def gradualFra(cf):

            numerator = 0  # 分子
            denominator = 1  # 分母
            for x in cf[::-1]:
                # 这里的渐进分数分子分母要分开
                numerator, denominator = denominator, x * denominator + numerator
            return numerator, denominator

        def getGradualFra(cf):

            gf = []
            for i in range(1, len(cf) + 1):
                gf.append(gradualFra(cf[:i]))
            return gf

        def wienerAttack(e, n):

            cf = continuedFra(e, n)
            gf = getGradualFra(cf)
            for q2, k in gf:
                if isPrime(q2) and q2.bit_length() == 128:
                    print(q2, q2.bit_length())
                    return q2

        q2 = wienerAttack(n1, n2)
        p2 = n2 // q2
        phi = (p2 - 1) * (q2 - 1)
        d = inverse(e, phi)
        m = long_to_bytes(pow(c,d,n2))
        return m

    r.sendlineafter(b'> ', b'3')
    r.sendlineafter(b'answer: ', decrypt3(n1,n2, e, c))
    r.recvuntil(b'flag:')
    print(r.recvline().decode().strip())
    return 

proof_of_work()
r.interactive()
# 0xGame{a1425c9ce44989ffd64968130ee2f9fd}