近期比赛复现Vol.2

0xGame2023

Vigenere

0dGmqk{79ap4i0522g0a67m6i196he52357q60f}

维吉尼亚解密，根据flag头手动爆一下密码即可，密码为game。

密码，觅码，先有*再密

from secret import flag #从中导入秘密的flag，这是我们要破解的信息
from Crypto.Util.number import bytes_to_long #从函数库导入一些编码函数
from base64 import b64encode

#hint:也许下列函数库会对你有些帮助，但是要怎么用呢……
from base64 import b64decode
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

flag = flag.encode()
lent = len(flag)
flag = [flag[i*(lent//4):(i+1)*(lent//4)] for i in range(4)]#将flag切割成四份

c1 = bytes_to_long(flag[0])
c2 = ''.join([str(bin(i))[2:] for i in flag[1]])
c3 = b64encode(flag[2])
c4 = flag[3].hex()
print(f'c1?= {pow(c1,5)}\nc2 = {c2}\nc3 = {c3}\nc4 = {c4}')

'''
c1?= 2607076237872456265701394408859286660368327415582106508683648834772020887801353062171214554351749058553609022833985773083200356284531601339221590756213276590896143894954053902973407638214851164171968630602313844022016135428560081844499356672695981757804756591891049233334352061975924028218309004551
c2 = 10010000100001101110100010100111101000111110010010111010100001101110010010111111101000011110011010000001101011111110011010011000101011111110010110100110100000101110010010111101100101011110011110111100
c3 = b'lueggeeahO+8jOmCo+S5iOW8gOWni+aIkQ=='
c4 = e4bbace79a8443727970746fe68c91e68898e590a72121217d
'''
#全是乱码，那咋办嘛？

一道极其无聊的签到题，根据题目代码逆回去即可，注意到这里的flag为中文，如果为bytes类型的输出需要进行decode才能得到中文结果。

BabyRSA

from Crypto.Util.number import *
from random import getrandbits
from secret import flag

def getN():
	N = 1
	for i in range(16):
		tmp = getPrime(32)
		N *= tmp
	return N

mask = getrandbits(256)
e = 65537
n = getN()
m = bytes_to_long(flag)
c = pow(m*mask,e,n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f'mask = {mask}')


'''
n = 93099494899964317992000886585964221136368777219322402558083737546844067074234332564205970300159140111778084916162471993849233358306940868232157447540597
e = 65537
c = 54352122428332145724828674757308827564883974087400720449151348825082737474080849774814293027988784740602148317713402758353653028988960687525211635107801
mask = 54257528450885974256117108479579183871895740052660152544049844968621224899247
'''

比较简单：

from Crypto.Util.number import *
import gmpy2,sympy

n = 93099494899964317992000886585964221136368777219322402558083737546844067074234332564205970300159140111778084916162471993849233358306940868232157447540597
e = 65537
c = 54352122428332145724828674757308827564883974087400720449151348825082737474080849774814293027988784740602148317713402758353653028988960687525211635107801
mask = 54257528450885974256117108479579183871895740052660152544049844968621224899247

phi=int(sympy.totient(n))
d = gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m//mask))

Take my bag!

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

def encrypt(m):
	m = str(bin(m))[2:][::-1]
	enc = 0
	for i in range(len(m)):
		enc += init[i] * int(m[i]) % n
	return enc

w = getPrime(64)
n = getPrime(512)
init = [w*pow(3, i) % n for i in range(512)]

c = encrypt(bytes_to_long(flag))

print(f'w={w}')
print(f'n={n}')
print(f'c={c}')

'''
w=16221818045491479713
n=9702074289348763131102174377899883904548584105641045150269763589431293826913348632496775173099776917930517270317586740686008539085898910110442820776001061
c=4795969289572314590787467990865205548430190921556722879891721107719262822789483863742356553249935437004378475661668768893462652103739250038700528111
'''

观察发现这是一个简单的背包加密，init背包向量可以自己求出，利用到超递增背包向量直接贪婪算法求解：

from Crypto.Util.number import *

w = 16221818045491479713
n = 9702074289348763131102174377899883904548584105641045150269763589431293826913348632496775173099776917930517270317586740686008539085898910110442820776001061
c = 4795969289572314590787467990865205548430190921556722879891721107719262822789483863742356553249935437004378475661668768893462652103739250038700528111
init = [w*pow(3, i) % n for i in range(512)]
m=''
for i in init[::-1]:
    if c>=i:
        c=c-i
        m+='1'
    else:
        m+='0'
print(long_to_bytes(int(m,2)))

猜谜

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

def dec(text):
	text = text.decode()
	code = 'AP3IXYxn4DmwqOlT0Q/JbKFecN8isvE6gWrto+yf7M5d2pjBuk1Hh9aCRZGUVzLS'
	unpad = 0
	tmp = ''
	if (text[-1] == '=') & (text[-2:] != '=='):
		text = text[:-1]
		unpad = -1
	if text[-2:] == '==':
		text = text[:-2]
		unpad = -2
	for i in text:
		tmp += str(bin(code.index(i)))[2:].zfill(3)
	tmp = tmp[:unpad]
	result = long_to_bytes(int(tmp,2))
	return result

def enc(text):
	code = 'AP3IXYxn4DmwqOlT0Q/JbKFecN8isvE6gWrto+yf7M5d2pjBuk1Hh9aCRZGUVzLS'
	text = ''.join([str(bin(i))[2:].zfill(8) for i in text])
	length = len(text)
	pad = b''
	if length%3 == 1:
		text += '00'
		pad = b'=='
	elif length%3 == 2:
		text += '0'
		pad = b'='
	result = [code[int(text[3*i:3*(i+1)],2)] for i in range(0,len(text)//3)]
	return ''.join(result).encode()+pad

def encrypt(flag):
	result = b''
	for i in range(len(flag)):
		result += (key[i%7]^(flag[i]+i)).to_bytes(1,'big')
	return result


c = enc(encrypt(flag))
print(f'c = {c}')

'''
c = b'IPxYIYPYXPAn3nXX3IXA3YIAPn3xAYnYnPIIPAYYIA3nxxInXAYnIPAIxnXYYYIXIIPAXn3XYXIYAA3AXnx='
'''

这道加密题比较有意思：注意到我们知道flag头是0xGame{，所以可以通过这个头求解得到7位key：

from Crypto.Util.number import *

c = 'IPxYIYPYXPAn3nXX3IXA3YIAPn3xAYnYnPIIPAYYIA3nxxInXAYnIPAIxnXYYYIXIIPAXn3XYXIYAA3AXnx'
code = 'AP3IXYxn4DmwqOlT0Q/JbKFecN8isvE6gWrto+yf7M5d2pjBuk1Hh9aCRZGUVzLS'
num=''
for i in c:
    num+=bin(code.index(i))[2:].zfill(3)
num=num[:len(num)-1]
res=b'0xGame{'
num=long_to_bytes(int(num,2))
key=b''
for i in range(len(res)):
    key+=long_to_bytes((res[i]+i)^num[i])
for i in range(len(num)):
    print(chr((num[i]^key[i%7])-i),end='')

What’s CBC?

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

def bytes_xor(a,b):
	a,b=bytes_to_long(a),bytes_to_long(b)
	return long_to_bytes(a^b)

def pad(text):
	if len(text)%8:
		return text
	else:
		pad = 8-(len(text)%8)
		text += pad.to_bytes(1,'big')*pad
		return text

def Encrypt_CBC(text,iv,key):
	result = b''
	text = pad(text)
	block=[text[_*8:(_+1)*8] for _ in range(len(text)//8)]
	for i in block:
		tmp = bytes_xor(iv,i)
		iv = encrypt(tmp,key)
		result += iv
	return result

def encrypt(text,key):
	result = b''
	for i in text:
		result += ((i^key)).to_bytes(1,'big')
	return result

iv = b'11111111'
enc = (Encrypt_CBC(flag,iv,key))
print(f'enc = {enc}')

#enc = b"\x8e\xc6\xf9\xdf\xd3\xdb\xc5\x8e8q\x10f>7.5\x81\xcc\xae\x8d\x82\x8f\x92\xd9o'D6h8.d\xd6\x9a\xfc\xdb\xd3\xd1\x97\x96Q\x1d{\\TV\x10\x11"

这题的CBC加密模式中，每轮的IV就是上一轮的加密结果，还是根据0xGame{flag头来得到key，这题的块长度是8，不够八位，前七位key得到是b'\x8f\x8f\x8f\x8f\x8f\x8f\x8f'，可以大胆猜测最后一位也是b'\x8f'，利用key和IV求得剩下几块明文：

from Crypto.Util.number import *

def bytes_xor(a,b):
	a,b=bytes_to_long(a),bytes_to_long(b)
	return long_to_bytes(a^b)

enc = b"\x8e\xc6\xf9\xdf\xd3\xdb\xc5\x8e8q\x10f>7.5\x81\xcc\xae\x8d\x82\x8f\x92\xd9o'D6h8.d\xd6\x9a\xfc\xdb\xd3\xd1\x97\x96Q\x1d{\\TV\x10\x11"
iv=b'11111111'
m1=b'0xGame{0'
key=b'\x8f\x8f\x8f\x8f\x8f\x8f\x8f\x8f'
for i in range(0,len(enc)-8,8):
    print(bytes_xor(bytes_xor(enc[i:i+8],enc[i+8:i+16]),key))

中间的那个人

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'
'''

一道比较好的DH入门题目，由于私钥比较小可以直接分解离散对数得到，根据题目代码直接求flag即可：

from Crypto.Cipher import AES
from hashlib import sha256
from Crypto.Util.number import *

g=2
p=250858685680234165065801734515633434653
B=33067794433420687511728239091450927373
A=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'
a=discrete_log_lambda(Mod(A,p), Mod(2, p), bounds=(0, 2^32))
b=discrete_log_lambda(Mod(B,p), Mod(2, p), bounds=(0, 2^32))
key = pow(A,b,p)
key = sha256(long_to_bytes(int(key))).digest()
iv = b"0xGame0xGameGAME"
aes = AES.new(key, AES.MODE_CBC, iv)
dec = aes.decrypt(enc)
print(dec)

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
'''

题目给了个gift，可以通过gift求解pq，然后进行CRT，这题还存在一个不互素问题，一次CRT由于flag比较长不能在模n_下求得，所以还需再一次求个不互素解后的CRT：

from Crypto.Util.number import *
from sympy import *
from libnum import *
import gmpy2

mygift=[15925416640901708561793293991573474917595642805739825596593339102414328214313430010166125066639132916608736569443045051644173933089503934675628814467277922, 18342424676996843423829480445042578097182127446865571536445030052846412665700132683433441858073625594933132038175200824257774638419166516796318527302903098]
mq_=6229615098788722664392369146712291169948485951371133086154028832805750551655072946170332335458186479565263371985534601035559229403357396564568667218817197
mp_=7514598449361191486799480225087938913945061715845128006069296876457814528347371315493644046029376830166983645570092100320566196227210502897068206073043718
n=63329068473206068067147844002844348796575899624395867391964805451897110448983910133293450006821779608031734813916287079551030950968978400757306879502402868643716591624454744334316879241573399993026873598478532467624301968439714860262264449471888606538913071413634346381428901358109273203087030763779091664797
n_=84078907800136966150486965612788894868587998005459927216462899940718213455112139441858657865215211843183780436155474431592540465189966648565764225210091190218976417210291521208716206733270743675534820816685370480170120230334766919110311980614082807421812749491464201740954627794429460268010183163151688591417
c=12623780002384219022772693100787925315981488689172490837413686188416255911213044332780064192900824150269364486747430892667624289724721692959334462348218416297309304391635919115701692314532111050955120844126517392040880404049818026059951326039894605004852370344012563287210613795011783419126458214779488303552
e=260792700

p, q = symbols('p q')
f1 = p + q - mygift[0]
f2 = p * q - n
solutions = solve((f1, f2), (p, q))
p,q=solutions[0]
p_, q_ = symbols('p_ q_')
f1 = p_ + q_ - mygift[1]
f2 = p_ * q_ - n_
solutions = solve((f1, f2), (p_, q_))
p_,q_=solutions[0]
m_4=solve_crt([mp_,mq_],[p_,q_])
phi=int((p-1)*(q-1))
b=gmpy2.gcd(e,phi)
a=e//b
d=gmpy2.invert(a,phi)
res=pow(c,d,n)
m_4=solve_crt([m_4,res],[n_,n])
print(long_to_bytes(gmpy2.iroot(int(m_4),4)[0]))

EzRSA

呃，好好出题不好吗，为什么要整这么个大缝合怪……

from challenges.challenge1 import RSAServe as challenge1
from challenges.challenge2 import RSAServe as challenge2
from challenges.challenge3 import RSAServe as challenge3
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
import socketserver
import signal


SCORE = [0, 0, 0]
BANNER = """
 ____  ____    _    
|  _ \/ ___|  / \   
| |_) \___ \ / _ \  
|  _ < ___) / ___ \ 
|_| \_\____/_/   \_\

Here are four challenges(1, 2, 3), solve them all then you can get flag.
"""
MEMU = """
/----------------------------\\
|          options           |
| 1. get public key          |
| 2. get cipher text         |
| 3. check                   |
\\---------------------------/
"""

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 Serve(self, S):
        self.send(MEMU.encode())
        while True:
            option = self.recv()
            if option == b'1':
                pubkey = S.pubkey()
                for s in pubkey:
                    self.send(str(s).encode())
            elif option == b'2':
                c = S.encrypt()
                self.send(c.encode())
            elif option == b'3':
                usr_answer = self.recv(b"input your answer: ")
                return S.check(usr_answer)
            else:
                self.send(b"invaild option")

    def handle(self):
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(300)
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return
        self.send(BANNER.encode())
        while True:
            self.send(f'your score {sum(SCORE)}'.encode())
            if sum(SCORE) == 3:
                self.send(f"here are flag:{flag}".encode())
                break
            self.send(b'select challange{1,2,3}')#
            code = self.recv()
            if code == b'1':
                S = challenge1()
                res = self.Serve(S)
                if res == True:
                    SCORE[0] = 1
                    self.send(b'Conguration!You are right!')
            elif code == b'2':
                S = challenge2()
                res = self.Serve(S)
                if res == True:
                    SCORE[1] = 1
                    self.send(b'Conguration!You are right!')
            elif code == b'3':
                S = challenge3()
                res = self.Serve(S)
                if res == True:
                    SCORE[2] = 1
                    self.send(b'Conguration!You are right!')
            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', 10006
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

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

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

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

刚开始看交互还以为整了个多大的活，结果发现是个大缝合怪。

task1提供：

$$gift\equiv g^{r(p-1)}\pmod n$$

所以费马小定理得到：

$$gift-1=kp$$

可以和$n$求公因子分解，就解出了flag1。

task2是NCTF2019的childRSA原题，$p-1$光滑数算法。

task3分解两个$n$的连分数可以得到两个$q$，进而求解。

分别计算三个题目得到这个题的flag，太懒了没写交互脚本。

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
'''

LFSR就是按照状态位计算，生成新的状态位。模二下的异或和按位与运算就是加法和乘法。

对于关键加密代码：

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

实质上就是：

for i in range(128):
    output = output + (state[i] * mask[i])

所以如果有一个state向量，一个mask向量，得到的output就是两个向量相乘的结果。

$$state×mask=output$$

进而，有一个state矩阵，一个mask向量，通过计算，得到的就是outputstate向量。

可以通过构造矩阵求解mask向量：

$$state×mask=outputState$$ $$mask=outputState×state^{-1}$$

from Crypto.Util.number import *

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

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]
outputState =string2bits('1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110')
states = initState + outputState

s = [states[i : i + 128] for i in range(128)]
S = Matrix(GF(2), 128, 128, s)
o = [outputState[i] for i in range(128)]
O = Matrix(GF(2), 128, 1, o)

secret = S.inverse()*O

print('0xGame{'+long_to_bytes(int(secret.str().replace('\n','').replace('[','').replace(']',''),2)).decode()+'}')

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()

这题提到了一个之前没了解过的Fault Injection攻击。

Fault Injection攻击是啥呢，通俗地来说，就是将要攻击的目标（芯片、算法）看作是一个黑盒子，在能对黑盒内部的一些数据属性，进行一定程度的、可控的干涉影响的条件下，人为地构造一些错误，并通过观察这个黑盒在错误情况下的输出，来反推黑盒里的一些数据属性。

这个题目就是说我们可以人为反转私钥$d$的一个比特位，让某位的$0$为$1$或者$1$为$0$，但是我们并不知道这一位初始是$0$还是$1$。

假设第$i$个比特位为$0$，做手脚之后变为了$1$，记为：

$$d'=d+2^i$$

设我们输入的构造密文$c$在篡改了私钥后的输出为$m’$。得到：

$$\frac{m'}{m}=\frac {c^{d'}}{c^d}=\frac {c^{d+2^i}}{c^d}=\frac {c^d\cdot c^{2i}}{c^d}=c^{2i}\pmod n$$

假设第$i$个比特位为$1$，做手脚之后变为了$0$，记为：

$$d'=d-2^i$$

同理：

$$\frac{m'}{m}=\frac {c^{d'}}{c^d}=\frac {c^{d-2^i}}{c^d}=\frac {c^d\cdot c^{-2i}}{c^d}=c^{-2i}\pmod n$$

所以，根据分别在不同的$d$下得到的输出比值可以反推第$i$位，反复交互可以恢复$d$：

自己跑超时了，贴个官方的wp吧。

from pwn import *
import itertools
import hashlib
import string
from tqdm import tqdm

def proof(io):
    io.recvuntil(b"XXXX+")
    suffix = io.recv(16).decode("utf8")
    io.recvuntil(b"== ")
    cipher = io.recvline().strip().decode("utf8")
    for i in itertools.product(string.ascii_letters+string.digits, repeat=4):
        x = f"{i[0]}{i[1]}{i[2]}{i[3]}"
        proof=hashlib.sha256((x+suffix).encode()).hexdigest()
        if proof == cipher: break
    print(x)
    io.sendlineafter(b"XXXX:",x.encode())

f = open('data.txt','a')
io = remote('43.139.107.237',10005)
proof(io)
io.recvuntil(b'>')
io.sendline(b'S')
io.recvuntil(b'>')
io.sendline(b'test')
n = int(io.recvline())
e = int(io.recvline())
c = int(io.recvline())
for i in tqdm(range(1023)):
    io.recvuntil(b'>')
    io.sendline(b'F')
    io.recvuntil(b'>')
    io.sendline(f'{c}'.encode())
    io.recvuntil(b'>')
    io.sendline(f'{i}'.encode())
    io.recvline()
    m_ = int(io.recvline())
    f.write(str(m_)+'\n')
io.close()
f.close()
print(f'n={n}')
print(f'c={c}')

from Crypto.Util.number import *

m = b'test'
m = bytes_to_long(m)
n=97914749446436063122542581376873112820400732267124998400088179058780712855378248201542023213009277089224170180542304344638059090556781844777641757174279080863658472878763702075705376304717343862101956239090701126225622317784075619757963099253602226642056966461019740454740445226152574361794251236011891077789
c=73133825445675329950286077126832004352164006658709453405485979363609175208129785294437379266100324978770868694885347204515053234232666436453863941132493106687387106354265743735994029551983269772204386433432638435914078485461320417024614354676213557287698752845797412775400104995650602775848941301838035593870
e = 65537
dbin = ''
with open('data.txt','r') as f:
    for i in tqdm(range(1023)):
        m_ = int(f.readline())
        h = (inverse(m,n)*m_)%n
        test = pow(c,2**i,n)
        if h == test:
            dbin += '0'
        elif h == inverse(test,n):
            dbin += '1'
d = eval('0b'+dbin[::-1])
if (pow(c,d,n)==m):
    print(d)

EzECC

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

flag = b'0xGame{' + msg + b'}'

q = getPrime(80)
a,b= [random.randrange(1,q-1) for i in range(2)]

def add(P,Q):
	if P[0] != Q[0] and P[1] != Q[1]:
		t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
	else:
		t = ((3*P[0]*P[0]+a) * inverse(2*P[1],q))%q

	x3 = t*t - P[0] - Q[0]
	y3 = t*(P[0] - x3) - P[1]
	return (x3%q, y3%q)

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

assert len(msg)%2==0
m1=bytes_to_long(msg[:len(msg)//2])
m2=bytes_to_long(msg[len(msg)//2:])

k = random.getrandbits(64)
G = (641322496020493855620384 , 437819621961768591577606)
K = mul(k,G)

M = (m1,m2)
r = random.getrandbits(16)

C_1 = add(M,mul(r,K))
C_2 = mul(r,G)

print(f'q={q}\na={a}\nb={b}\n')
print(f'G = {G}\nK = {K}\nC_1={C_1}\nC_2={C_2}')

'''
q=1139075593950729137191297
a=930515656721155210883162
b=631258792856205568553568

G = (641322496020493855620384, 437819621961768591577606)
K = (781988559490437792081406, 76709224526706154630278)
C_1=(55568609433135042994738, 626496338010773913984218)
C_2=(508425841918584868754821, 816040882076938893064041)
'''

一道比较容易的ECC，由于参数比较小，里面的几个参数都可以直接用sage分解离散对数求解，这题的$C_1$点采用它的算法居然还不是落在实际的椭圆曲线上的，直接用他的add函数做个减法就行了：

q=1139075593950729137191297
a=930515656721155210883162
b=631258792856205568553568
E=EllipticCurve(GF(q),[a,b])
G = E(641322496020493855620384, 437819621961768591577606)
K = E(781988559490437792081406, 76709224526706154630278)
C_2=E(508425841918584868754821, 816040882076938893064041)
r=G.discrete_log(C_2)
R=r*K

def add(P,Q):
	if P[0] != Q[0] and P[1] != Q[1]:
		t = ((Q[1]-P[1]) * inverse_mod(Q[0]-P[0],q)) %q
	else:
		t = ((3*P[0]*P[0]+a) * inverse_mod(2*P[1],q))%q

	x3 = t*t - P[0] - Q[0]
	y3 = t*(P[0] - x3) - P[1]
	return (x3%q, y3%q)


revR=(int(R.xy()[0]),int(-R.xy()[1]%q))
C_1=(55568609433135042994738, 626496338010773913984218)

from Crypto.Util.number import *
print(b'0xGame{'+long_to_bytes(add(C_1,revR)[0])+long_to_bytes(add(C_1,revR)[1])+b'}')

LLL-FirstBlood

from random import randrange
from Crypto.Util.number import getPrime,bytes_to_long
from secret import flag
assert len(flag) % 4 == 0

length = len(flag)//4
m = [bytes_to_long(flag[i*length:(i+1)*length]) for i in range(4)]
p = getPrime(int(128))

def MakeMask(n,p):
    upper = identity_matrix(n)
    low = identity_matrix(n)
    for i in range(n-1):
        for j in range(i+1, n):    
            upper[i, j] = randrange(1, p)
            low[j, i] = randrange(1, p)
    result = upper * low
    assert det(result) == 1
    return result

def Matrix2List(x):return [list(i) for i in x]

noise = [[randrange(1, p) for i in range(4)] for _ in range(4)]
noise[0] = m
M = matrix(noise)
A = MakeMask(4,p)
C = A*M

print(f'p={p}')
print(f'C={Matrix2List(C)}')

'''
p=198880159035681668071031460916089145469
C=[[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428, 2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772, 3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675, 3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798, 3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742, 4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283, 5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], [1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251, 2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244, 3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359, 3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], [9883814543195849013523934427451407019514807606993414569626142656857168165339, 13190422499129347541373922929251088892868361241120937213742340947017395215646, 18832738552342488056498211782604832513006649329982003661701684946590064734701, 22323329751908690611034666068697427811613727429398087082295754189068333861152]]
'''

当时做这个题凭直觉一下就出了，现在来好好看一下：

result矩阵是一个由对角单位矩阵产生的一个行列式为1的矩阵，M是一个由flag行向量和三个noise向量组成的矩阵。flag行向量应该是要相对比较小的。

又有：

$$C=A\times M$$

能用LLL求得其最短向量flag：

from Crypto.Util.number import *
C=[[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428, 2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772, 3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675, 3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798, 3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742, 4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283, 5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], [1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251, 2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244, 3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359, 3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], [9883814543195849013523934427451407019514807606993414569626142656857168165339, 13190422499129347541373922929251088892868361241120937213742340947017395215646, 18832738552342488056498211782604832513006649329982003661701684946590064734701, 22323329751908690611034666068697427811613727429398087082295754189068333861152]]
C=Matrix(C)
print(b''.join(long_to_bytes(abs(i)) for i in C.LLL()[0]))

EzMatrix

from Crypto.Util.number import getPrime
from random import randint
from secert import secert,flag
from hashlib import md5
def n2b(n):return md5(str(n).encode()).hexdigest()

assert secert < pow(2,64)
assert flag == '0xGame{'+n2b(secert)+'}'

def Martix2list(Martix):
    result = []
    Martix = list(Martix)
    for i in Martix:
        result.append(list(i))
    return result

A=[[12143520799533590286, 1517884368, 12143520745929978443, 796545089340, 12143514553710344843, 28963398496032, 12143436449354407235, 158437186324560, 12143329129091084963, 144214939188320, 12143459416553205779, 11289521392968],[12143520799533124067, 1552775781, 12143520745442171123, 796372987410, 12143514596803995443, 28617862048776, 12143437786643111987, 155426784993480, 12143333265382547123, 140792203111560, 12143460985399172467, 10983300063372],[12143520799533026603, 1545759072, 12143520746151921286, 781222462020, 12143514741528175043, 27856210942560, 12143440210529480891, 150563969013744, 12143339455702534403, 135941365971840, 12143463119774571623, 10579745342712],[4857408319806885466, 2428704161425648657, 12143520747462241175, 758851601758, 12143514933292307603, 7286139389566980165, 9714738936567334300, 144947557513044, 12143346444338047691, 130561054163540, 4857352974113333366, 2428714303424782417],[12143520799533339320, 1476842796, 12143520749060275613, 733281428880, 12143515144091549812, 25896324662208, 12143446129977471347, 139126289668080, 12143353609086952433, 125093278125816, 12143467808884068695, 9705993135696],[3469577371288079926, 5204366058378782250, 12143520750775862343, 706665985740, 12143515359139397843, 24876891455539, 12143449149385190675, 5204499435641729607, 1734628523990131469, 119757210113970, 12143470097256549947, 9282407958928],[10986995009101166671, 1734788687033207505, 12143520752514668698, 680173911560, 12143515570582515443, 23883386182656, 12143452072344092516, 10408859957710764174, 8673790006740000925, 4047954924507284041, 12143472277719610437, 8879790035168],[12143520799534210329, 8095680534365818753, 12143520754224346525, 6071761054204856029, 12143515774342357443, 22931775530664, 12143454859049102627, 122586336122081, 12143373761302849103, 109840689548590, 8095634066844843878, 8500892291801],[2428704159899526175, 7286112481016467893, 12143520755876491019, 629765964828, 12143515968446948123, 9714838668887734012, 4857345013259425502, 117630592711632, 12143379764863568374, 105318302849760, 2428659620509049335, 7286120625945355053],[7286112479717322389, 7286112480971640825, 12143520757456628435, 606320684970, 12143516152115449139, 4857429497934652454, 4857347490735050126, 112978994964264, 12143385390297217523, 101086824360217, 7286069740980100293, 7286120294834973633],[7727695054246476847, 1202487728, 12143520758958480293, 584144077140, 12143516325240923843, 20377952745696, 12143462294760579275, 108622249048560, 12143390651947217363, 97133513961120, 12143479741445599772, 8831658996900830432],[12143520799535388887, 1161628182, 12143520760380594623, 563225247585, 12143516488091679443, 19626876325056, 12143464472820678035, 104545135017180, 12143395570399006523, 93441517429260, 12143481309754543787, 7218375794633]]# 12*12
p = 12143520799543738643
A = Matrix(GF(p),A)
enc = A**secert

def Martix2list(Martix):
    result = []
    Martix = list(Martix)
    for i in Martix:
        result.append(list(i))
    return result

with open('enc.txt','w') as f:
    f.write(str(Martix2list(enc)))

这题能找到原题，照着学了：

GDG Algiers CTF两道矩阵题wp - 华盟学院 (aqtd.com)

LLL-SecondBlood（赛后）

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

m = bytes_to_long(flag)
q = getPrime(512)
assert m.bit_length() == 318

def encrypt(m):
	mask,noise = getPrime(511),getPrime(50)
	mask_.append(mask)
	noise_.append(noise)
	c = (mask*m + noise)%q
	return c

noise_,mask_  =[[] for _ in range(2)]
c_ = [encrypt(m) for i in range(4)]

print(f'q = {q}\nmask = {mask_}\nc_ = {c_}')

'''
q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]
'''

$$c=(mask\times m+noise)\bmod q$$

展开：

$$mask\times m+noise = c+kq$$ $$mask\times m-c-kq=-noise$$

左边是较大的已知参数，右边是较小的位置的质数。构造：

$$\begin{bmatrix}m&k_1&k_2&k_3&k_4&1\end{bmatrix}\begin{bmatrix}-mask_1&-mask_2&-mask_3&-mask_4&1&0\\q&0&0&0&0&0\\0&q&0&0&0&0\\0&0&q&0&0&0\\0&0&0&q&0&0\\c_1&c_2&c_3&c_4&0&2^{341}\end{bmatrix}$$ $$=\begin{bmatrix}noise_1&noise_2&noise_3&noise_4&m&2^{341}\end{bmatrix}$$

进行格基规约：

from Crypto.Util.number import *

q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]

L=matrix(6,6)
for i in range(4):
    L[0,i]=-mask[i]
    L[5,i]=c_[i]
L[0,4]=1
for i in range(4):
    L[i+1,i]=q
L[5,5]=2^341

print(long_to_bytes(int(L.LLL()[0][4])))

此外，这道题还可以直接使用二元coppersmith进行求解：

因为未知量的位数都比较小，考虑使用多元Coppersmith，思路是在在有限域中解方程，可以通过展开和一定的方式换到整数域上，把问题变成简单的解方程问题（利用牛顿迭代法），然后再利用LLL算法去对构造的数学式子进行求解。

总而言之就是，实现有限域求根的算法（前提是这个根必须要比模数小很多）。因为求根的时候用到了LLL算法去规约基向量，得到的结果也是一组基（性质更好的），这种问题就被称之为SVP（最短向量）问题。

from Crypto.Util.number import *
import itertools

q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())

    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

A=mask[0]
c=c_[0]
PR.<m,noise>=Zmod(q)[]
f=A*m-c+noise
r=small_roots(f,(2^320,2^50),4,2)
print(long_to_bytes(int(r[0][0])).decode())

Normal ECC

from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from random import getrandbits
from hashlib import md5
from secret import flag,M

def MD5(m):return md5(str(m).encode()).hexdigest()
assert '0xGame{'+MD5(M[0])+'}' == flag
p = 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a = 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b = 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
assert p>a
assert p>b
E = EllipticCurve(GF(p),[a,b])
assert E.order() == p
M = E(M)

G = E.random_point()
k = getPrime(int(128))
K = k*G
r = getrandbits(64)

C1 = M + r*K
C2 = r*G

print(f'p={p}\na={a}\nb={b}')
print(f'G={G.xy()}')
print(f'K={K.xy()}')
print(f'C1={C1.xy()}')
print(f'C2={C2.xy()}')

'''
p=11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a=490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b=7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
G=(4045939664332192284605924284905750194599514115248885617006435833400516258314135019849306107002566248677228498859069119557284134574413164612914441502516162, 2847794627838984866808853730797794758944159239755903652092146137932959816137006954045318821531984715562135134681256836794735388745354065994745661832926404)
K=(9857925495630886472871072848615069766635115253576843197716242339068269151167072057478472997523547299286363591371734837904400286993818976404285783613138603, 9981865329938877904579306200429599690480093951555010258809210740458120586507638100468722807717390033784290215217185921690103757911870933497240578867679716)
C1=(4349662787973529188741615503085571493571434812105745603868205005885464592782536198234863020839759214118594741734453731681116610298272107088387481605173124, 10835708302355425798729392993451337162773253000440566333611610633234929294159743316615308778168947697567386109223430056006489876900001115634567822674333770)
C2=(5193866657417498376737132473732737330916570240569047910293144235752602489388092937375844109374780050061859498276712695321973801207620914447727053101524592, 684299154840371832195648774293174908478389728255128448106858267664482339440737099810868633906297465450436417091302739473407943955874648486647511119341978)
'''

$P$阶数和$p$相同，使用smartattack梭哈：

from hashlib import md5

p=11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a=490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b=7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466

E = EllipticCurve(GF(p),[a,b])
C1=E(4349662787973529188741615503085571493571434812105745603868205005885464592782536198234863020839759214118594741734453731681116610298272107088387481605173124, 10835708302355425798729392993451337162773253000440566333611610633234929294159743316615308778168947697567386109223430056006489876900001115634567822674333770)
C2=E(5193866657417498376737132473732737330916570240569047910293144235752602489388092937375844109374780050061859498276712695321973801207620914447727053101524592, 684299154840371832195648774293174908478389728255128448106858267664482339440737099810868633906297465450436417091302739473407943955874648486647511119341978)
G=E(4045939664332192284605924284905750194599514115248885617006435833400516258314135019849306107002566248677228498859069119557284134574413164612914441502516162, 2847794627838984866808853730797794758944159239755903652092146137932959816137006954045318821531984715562135134681256836794735388745354065994745661832926404)

def SmartAttack(P,Q,p):
    E = P.curve()
    
    # 创建一个拓展p-adic域,构造一个拓展p-adic椭圆曲线
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
    
    # 对输入点P,Q进行提升
    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break
    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break
    
    # 进行点倍乘操作并提取结果的坐标
    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp
    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()
    
    # 计算比值k
    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

r=SmartAttack(G,C2,p)
M=C1-r*C2
def MD5(m):return md5(str(m).encode()).hexdigest()
flag='0xGame{'+MD5(M[0])+'}'
print(flag)

鹏程杯 2023

Neltharion_and_Arthas

import binascii
import hashlib
from flag import flag
from Crypto.Cipher import AES
from Crypto.Util import *
import os

key1 = os.urandom(32)
key2 = b'tn*-ix6L*tCa*}i*'
key_len = len(key2)
assert flag.startswith(b'flag{')
assert (flag[13] == 45 and flag[18] == 45 and flag[23] == 45 and flag[28] == 45)
flag1 = b"2023: "+flag[:13]+flag[14:18]+flag[19:23]
flag2 = 'a3eae82b4c491e0e'

h = binascii.unhexlify(hashlib.sha256(key2).hexdigest())[:11]
gift1 = b'***********************************************************************************************'
gift2 = b'I tell you this, for when my days have come to an end , you, shall be King.'+h


def encrypt1(message, key):
    cipher = AES.new(key, AES.MODE_CTR, counter=Counter.new(128))
    ciphertext = cipher.encrypt(message)
    return ciphertext.hex()


def encrypt2(message, key, iv):
    padding = bytes((key_len - len(message) % key_len) * '&', encoding='utf-8')
    message += padding
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(message)
    return ciphertext.hex()


print("enc_gift1 = "+encrypt1(gift1, key1))
print("enc_flag = "+encrypt1(flag1, key1))
print("enc_gift2 = "+encrypt2(gift2, key2, flag2))

# enc_gift1 = bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca
# enc_flag = c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df
# enc_gift2 = ********c********b**************4***5********3****6a*****a**2********c*8******7***********3***5***2********e*5*************a******5**c***74***********fee046b4d2918096cfa3b76d6622914395c7e28eef

先来看看以前没怎么了解的CTR模式：

发现这个比起其他的AES有个特点是key和计数器进行块运算，而密文和明文只参与了异或运算。

assert flag.startswith(b'flag{')
assert (flag[13] == 45 and flag[18] == 45 and flag[23] == 45 and flag[28] == 45)
flag1 = b"2023: "+flag[:13]+flag[14:18]+flag[19:23]

print("enc_gift1 = "+encrypt1(gift1, key1))
print("enc_flag = "+encrypt1(flag1, key1))

两次CTR采用了相同的key进行加密，异或的值是一致的，根据前面一堆乱七八糟的构造可以得到flag1的已知：2023: flag{，这总共是11位，相当于我们可以知道gift1的11位，进行异或：

from pwn import *

enc_gift1 = 'bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca'
enc_flag = 'c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df'

enc_flag=bytes.fromhex(enc_flag)
enc_gift1=bytes.fromhex(enc_gift1)[:len(enc_flag)]

ans = xor(b"2023: flag{",xor(enc_gift1,enc_flag))[:11]
print(ans)

根据输出的结果去百度搜索可以找到原台词：I am Deathwing, the destroyer, the end of all things,inevitable,indomitable,I am the cataclysm，根据这个台词就可以恢复flag的前部分，flag根据题目已知的应该是个uuid：

from pwn import *

enc_gift1 = 'bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca'
enc_flag = 'c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df'

enc_flag=bytes.fromhex(enc_flag)
enc_gift1=bytes.fromhex(enc_gift1)[:len(enc_flag)]

ans = (xor(b"I am Deathwing, the destroyer, the end of all things,inevitable,indomitable,I am the cataclysm",xor(enc_gift1,enc_flag)))
print(ans)

得到前半部分flag。

后半部分采用CBC模式，key2一开始没发现，居然需要爆破其中四位，填充和key2都可以求得，直接爆破即可，根据输出2的已知部分即可得到一组唯一正确的key2，然后恢复CBC的iv向量，得到flag的后半部分：

import string
from tqdm import tqdm
from Crypto.Cipher import AES
from Crypto.Util.number import *
import hashlib,binascii
from pwn import *

str=string.printable
enc_6=long_to_bytes(0x918096cfa3b76d6622914395c7e28eef)
key_len = 16

for a in tqdm(str):
    for b in tqdm(str):
        for c in str:
            for d in str:
                key2 = b'tn'+a.encode()+b'-ix6L'+b.encode()+b'tCa'+c.encode()+b'}i'+d.encode()
                h=binascii.unhexlify(hashlib.sha256(key2).hexdigest())[:11]
                gift2= b'I tell you this, for when my days have come to an end , you, shall be King.'+h
                padding = bytes((key_len - len(gift2) % key_len) * '&', encoding='utf-8')
                gift2 += padding
                cipher = AES.new(key2, AES.MODE_ECB)
                ciphertext = cipher.decrypt(enc_6)
                enc_5=long_to_bytes(bytes_to_long(ciphertext)^bytes_to_long(gift2[-16:]))
                if enc_5.hex()[-10:]=='fee046b4d2':
                    print(key2)

key2 = b'tn5-ix6L#tCaG}i6'

enc_6=long_to_bytes(0x918096cfa3b76d6622914395c7e28eef)


key_len = 16
key2 = b'tn5-ix6L#tCaG}i6'
h=binascii.unhexlify(hashlib.sha256(key2).hexdigest())[:11]
gift2= b'I tell you this, for when my days have come to an end , you, shall be King.'+h
padding = bytes((key_len - len(gift2) % key_len) * '&', encoding='utf-8')
gift2 += padding
head=long_to_bytes(0x918096cfa3b76d6622914395c7e28eef)
cipher = AES.new(key2, AES.MODE_ECB)
ciphertext = cipher.decrypt(head)
enc_b=xor(ciphertext,gift2[-16:])
for i in range(1,6):
    enc_a=enc_b
    cipher = AES.new(key2, AES.MODE_ECB)
    ciphertext = cipher.decrypt(enc_a)
    enc_b=xor(ciphertext,gift2[-16*(i+1):-16*i])
    
print(enc_b)

将得到的输出组合为uuid即可。

LeakyRSA

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

nbits=512
p=getPrime(nbits)
q=getPrime(nbits)

leakBits = 262
leak = (p ^ q)  >> (nbits - leakBits)

n=p*q
e=65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(p)
print(q)
print("n=%d" %n)
print("c=%d" %c)
print("leak=%d" %leak)
# n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923      
# c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691      
# leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321

题目给了leak = (p ^ q) >> (nbits - leakBits)，我们知道了$p\oplus q$的前262位，可以恢复高位。

提供一种大佬的方法，可以对$p\oplus q$，进行剪枝爆破，根据四个限定条件可以逐位求出：

每当我们选择一个$p$的比特，那么$q$的比特也能确定。

根据测试可以发现，当我们确定的$pq$部分进行相乘的结果，高位一半的数是和$n$对应高位是相同的：

tmp>>(tmp.bit_length()-i//2)== n>>(n.bit_length()-i//2)

当我们确定了$p,q$的高位，剩下的全部补$0$，那么相乘的结果应该是要小于$n$；同样，剩下的全部补$1$，那么相乘的结果应该大于$n$：

(int(pnew.ljust(512,'0'),2)*int(qnew.ljust(512,'0'),2) < n)
(int(pnew.ljust(512,'1'),2)*int(qnew.ljust(512,'1'),2) > n)

from Crypto.Util.number import *

def xor(a,b):
    tmp = ""
    for i,j in zip(a,b):
        tmp+=str(ord(i)^ord(j))
    return tmp


nbits = 512
leakBits = 262

leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321
leak = bin(leak)[2:].rjust(262,'0')
n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923      

p='1'
q='1'

P=[p]
Q=[q]
for i in range(261):
    PP=[]
    QQ=[]
    for a in '01':
        for b in '01':
            for pnew,qnew in zip(P,Q):
                pnew = pnew+a
                qnew = qnew+b
                tmp = int(pnew,2)*int(qnew,2)
                #print(tmp)
                if xor(pnew,qnew) == leak[:2+i] and  tmp>>(tmp.bit_length()-i//2)== n>>(n.bit_length()-i//2) and (int(pnew.ljust(512,'0'),2)*int(qnew.ljust(512,'0'),2) < n)  and (int(pnew.ljust(512,'1'),2)*int(qnew.ljust(512,'1'),2) > n) :
                    PP.append(pnew)
                    QQ.append(qnew) 
    print(len(P))
    P = PP.copy()
    Q = QQ.copy()
print(P)

最终得到的是10个$p,q$，还需要解一个coppersmith，由于存在$p,q$两个质数，所以理论上应该是有两个解，修改一下相关参数，如果epsilon需要调到很小的话不如直接爆破几位增大一下epsilon可以提升速度：

from Crypto.Util.number import *
from tqdm import *

P = ['1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101010100100000010', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110011001101000010', '1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101100010000100010', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110101111001100010', '1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101100010000001010', '1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101010100100000011', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110011001101000011', '1000001000011100010101010110000111101011000100111100000111111100011001101101101110100111101010111011001100111101001100010011110010100000001100010100110110000110000100101000111110110000101100100010111111001101001000001001111101111010000011111000101100010000100011', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110101111001100011', '1100111011010111101010100001110101111111100110111010101010011101100000101101010010101000010011001110110001011011011010000000100000111100111011101111100011110110111000000101100100101100100011111110011000101011011010100011001010101100111000100100110011001101101011']
n = 73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923

R.<x> = Zmod(n)[]
for pbar in tqdm(P[::-1]):
    for i in range(32):

        tmp = int(pbar,2)<<5
        tmp+=i
        f = tmp*2**245 + x
        xx = f.monic().small_roots(X=2^245,beta=0.47,epsilon=0.02)
        if xx:
            p = f(xx[0])
            print(p)

# 6814449132912466352143200200256605077873329465758477832056090562012411200107156482645933890997787435093806046493913273252717701817613907418845774345791241

c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691      
n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923      
p=6814449132912466352143200200256605077873329465758477832056090562012411200107156482645933890997787435093806046493913273252717701817613907418845774345791241
q=n//p
d = inverse(65537,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

colorful_matrix（赛后）

import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import gmpy2
import os
import hashlib
def xor(a, b):
    return bytes([a[i%len(a)] ^ b[i%len(b)] for i in range(max(len(a), len(b)))])
flag = b'flag{xxxxxx}'
key1 = hashlib.md5(os.urandom(16)).hexdigest().encode()
key2 = hashlib.md5(os.urandom(16)).hexdigest().encode()
num1 = 5
p = int(gmpy2.next_prime(bytes_to_long(key1 + os.urandom(64))))
ms = [random.getrandbits(256) for _ in range(num1)]
qs = [getPrime(1024) for _ in range(num1)]
ns = [p * qs[_] + ms[_] for _ in range(num1)]

num2 = 37
x = bytes_to_long(key2 + os.urandom(32))
A = []
B = []
for i in range(num2):
    a = random.getrandbits(512)
    b = a * x % p
    gift = (2 ** 128 - 1) * 2 ** 400
    A.append(a)
    B.append((b & gift) >> 400)

iv = long_to_bytes(random.getrandbits(128))
key = xor(key1,key2)
aes = AES.new(key1,AES.MODE_CBC,iv)
enc = aes.encrypt(pad(flag,48))
print(f'ns = {ns}')
print(f'A = {A}')
print(f'B = {B}')
print(f'enc = {enc}')
# ns = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]
# A = [12789809461864875489953273982997537541385904671489556544122095227619591140533414669794423644619127980362623481580128258914287474542792728686579090501397390, 10463950513938701625808784986819665844287315724639315128677227520960105897990256530542006653611594269012930935073966767351788182657861624733138283749460454, 5253244650607533810967862436125419800679723144526973463211784033045021824966560017919956773745212139142517766154626849426827164032731516615725539069585525, 5644589184984504085855423002268477365020278981591337230721358313393863912025011466727192648804002734561676112555123877764178690726130713927642577324443238, 4231732567865883627242742552738439372803539125622706171540910152922080004603138662537022248675968288205781990968838888633816697065257733344028576518431020, 2483388920404524165854675814798022834892112957478917588986471421083048888193527751575039626887367465858751417977246719312923814782809309525841102293919541, 3252353812256192711411255830105475125944842449239880454539397067913664088094160819193268643401968970009466652179043139341471403913410402646923633696154454, 11575010486066232687430367040977113580882826853104996856464797182632266635060724100357205810604915010810884387573114266349621457564659060272935537811111850, 116107444921917032985259963199427176510900273385517435613848456370557161312731449337837406563733552524777525870560544042690403987311424820755256727586807, 5859050133610438843641532306693688255014116940390205022708310454673159702673207152462501010791971695002865650407033762568636006764435795015869726867643634, 5954075553161305677556950650395792531753502207483036473422070018485916621872566706504374038792527687442272405589975343003802956899043321092006127828986114, 4571747544457157571652286537158051402285727327066029382085461714597609990601683125994983291866807816649968826930652068427193317966970789937746419206862747, 7166507561570980603812241332170524724051295937096000768984168029904561160020043035660087151672164814332446644696618077835020463308343415953131944864257266, 4852042788460566411381271873349329096978244586097817622748766708426751073559942708861852208085367014057217116211249133109246735634468823924185525972777655, 11962941918999276757181090570698839032103646409734781047194175833198626142790676141060052011581957980660140931408560130449153056874213033784715711461403345, 10324508881746579337486319574059121005227580732153432145860775835052420139026016902518605634385512021513380467928195663920843022679549517463264144660593354, 13276257094435850052122403884510025189232513948002582716865201271569293297601525601586036713056700716929820641888489806178376555435219630186396004003438962, 6525051273399089095687950615197786094425890004112675057642687348101531212837185750558500720306108976630502328600886080197626115513445112562084719104488315, 12922888505610354933000354792496863801007995464403098763485264334670452387681468617068312646367483171083114539083453125614861357751571161533921864394641576, 9489726784141062031514945333087338495823600723655465328127755755022980083351477888038160719541864899912899592065620071698977397662002448273876711116012763, 10630316198843195148937849513165933809121991192035364160395429088101265852052098101114542104327663563661384303617672183366879116750889320604308038959012109, 12675564142993964272844760955973914547747654087592111324261755301551267959231076883765863344473167582531968290671984039948163579495803204811731286282708940, 11847724105274460405216443356582445218232627275228120716891711887600046501095390733716854871561352002320819466803698088448952127166615410820121973485089326, 5131676593756685549522564504727003861447389891839469018437277330988047271086971907217360711863971849879439418231726349935396008040776952541710218842744018, 8049060452950901277510497437779182190254362319091882684392717180429468875432078713802857488901441344429723298843967365750616860588029426099852763482179470, 2365060249260571713545479629411006471094806409182638354076861269679377537605360223984548798658469783472746989448405310909017645138161178501458084966625559, 7467521246204465304438401242342633361751371318557249418344587207503257890765643838557008735305668588521988487342275527781708126255070883848829062790678347, 5841608816993144092409175658260479687582056537041472535819914412630519543198558564258699185557903902095773598614097026740427138629173672250387442834578787, 3935779917509948624841228665498558015416911059417306651751360048412619176423173794541812556512582747588138532941031730797102738268660078594473168666677171, 1459083415233950534805962555425717865938763752937036513111696179351002303817986848490146888626704327653287774806488952733813718461674376764427084478395399, 6426876689549337938550615491086475536072547585103523407263007393570982327518298678278232288342601754164640081474537962710401178482959474762541185760732929, 5241364650650467046722868257809607948071188801137204831449976666385482519613365369974704486723941517654753205012497273820309153659423928739972270634209996, 6387483223002092292686097811446217867743566298067033295601210265979889577756648605354064672061975949925472022416479935990178719227937307079186916383092053, 170562164015232424518655058158727202269056868720093972639058422975773575660534168774299548952867348396798580779605954510297102765330549642318362861226163, 10004133230245713370426176448219282796530473722412487408402635996842671302539458739305597027107498342509248085998067976408732789438099488867425813748783724, 12325342879747412722323355648741345730921040452129462974449188258885453690169624888480720109964630270938743431623479816739889661554987977051169401841580388, 641543989928732942291347866597230552820621633110802944556141221591498546555080480758772801043509130524233886009444044150447511986129019395067102094826363]
# B = [108715652691370707411987210267535348806, 131676833696101475747102644851662113271, 122436706338521558335484593966234623745, 255864866572301552398412638474857375629, 81098761191414480003681301866161112100, 322322463176364397336266169283851913620, 198167679309202772183020662350938553923, 326360662842236388778385468938922853242, 241812832858991643670485138860832357660, 69768236619183466076110136290750715548, 32383134960394164339076842474280712870, 147747232748027508904245311745435517130, 25327826075608705748116808975774398964, 65295332681674581261444632606267440749, 236756211690281667988216748814564193312, 106435149910135092172124474857722935730, 270727089812520941022075406571244846193, 206881193220261276126028739930244917728, 131961838897694897398340205404861333362, 219211823942216355573832791993673934321, 150960424777134558142309786444952807101, 51112048255939343109218372373173385772, 182065623911902509203036774197184164110, 168420344895532090057957641972492853410, 301808673225362418769168353084541667053, 132272458662433671393247350648662880688, 495672626901999558635736361346563007, 182444159345379042372018248514964944782, 144584137563407779776361378564517880036, 338518705859818740467225748906995999694, 205885429741815676881969528495365151019, 233897982464483450790005953366237992668, 279307677123402840425362992920185630901, 133493426228159673166382443820069696429, 316624110847744871475435405969944304329, 187931604382397525131117897387179435812, 220019728924915067987393012581921164417]
# enc = b'cTmkMb\xfc\x05|\x1d\xc7\x13\xbaSe\xe0\xbd\xc0\xd9\xa3\x8cwo\x82yN[B&\x80\xd7KPwQ`\x9c\xbf<y\x8e\x8a\x97e\xa074\xb2'

发现：

p = int(gmpy2.next_prime(bytes_to_long(key1 + os.urandom(64))))
ms = [random.getrandbits(256) for _ in range(num1)]
qs = [getPrime(1024) for _ in range(num1)]
ns = [p * qs[_] + ms[_] for _ in range(num1)]

这种情况叫做AGCD问题（近似 GCD 问题）：

$$n_i=pq_i+r_i$$

可以构造格子：

$$M=\begin{bmatrix}2^{256}&n_1&n_2&n_3&n_4\\&-n_0&&&\\&&-n_0&&\\&&&-n_0\\&&&&-n_0\end{bmatrix}$$

存在最短向量：

$$v=(q_0,q_1,...,q_t)M=(q_02^{256},q_0r_1-q_1r_0,...,q_0r_t-q_tr_0)$$

ns = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]
x0,x1,x2,x3,x4 = ns

B = matrix(ZZ,[[2^256,x1,x2,x3,x4],[0,-x0,0,0,0],[0,0,-x0,0,0],[0,0,0,-x0,0],[0,0,0,0,-x0]])
L = B.LLL()
ans= L[0][0] // 2^256

p0 = abs(ans)
p = (x0 // p0)

# p = 293423658885957174953198318664231534672400520068303593221989900395768107225130267646792968959460384248015583618158947268381852534151783869878808621629530642974652628810907251607210136313789978156955302211733219987661815438401343683
key1 = long_to_bytes(int(p))[:32]

进而可以得到$ms$，$ms=ns\bmod p$。

num2 = 37
x = bytes_to_long(key2 + os.urandom(32))
A = []
B = []
for i in range(num2):
    a = random.getrandbits(512)
    b = a * x % p
    gift = (2 ** 128 - 1) * 2 ** 400
    A.append(a)
    B.append((b & gift) >> 400)

iv = long_to_bytes(random.getrandbits(128))

检查一下生成位数，猜测可以使用随机数预测得到$iv$，发现这题的加密用到的是key1，跟key2毫无关系，所以直接求即可：

aes = AES.new(key1,AES.MODE_CBC,iv)
enc = aes.encrypt(pad(flag,48))

import random
from Crypto.Util.number import *
from Crypto.Cipher import AES
from extend_mt19937_predictor import ExtendMT19937Predictor

ns = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970, 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852, 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406, 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918, 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848]
p = 293423658885957174953198318664231534672400520068303593221989900395768107225130267646792968959460384248015583618158947268381852534151783869878808621629530642974652628810907251607210136313789978156955302211733219987661815438401343683
ms = [i%p for i in ns]
x = []
for each in ms:
    tmp = each
    while tmp >0:
        x.append(tmp%(2**32))
        tmp >>= 32


A = [12789809461864875489953273982997537541385904671489556544122095227619591140533414669794423644619127980362623481580128258914287474542792728686579090501397390, 10463950513938701625808784986819665844287315724639315128677227520960105897990256530542006653611594269012930935073966767351788182657861624733138283749460454, 5253244650607533810967862436125419800679723144526973463211784033045021824966560017919956773745212139142517766154626849426827164032731516615725539069585525, 5644589184984504085855423002268477365020278981591337230721358313393863912025011466727192648804002734561676112555123877764178690726130713927642577324443238, 4231732567865883627242742552738439372803539125622706171540910152922080004603138662537022248675968288205781990968838888633816697065257733344028576518431020, 2483388920404524165854675814798022834892112957478917588986471421083048888193527751575039626887367465858751417977246719312923814782809309525841102293919541, 3252353812256192711411255830105475125944842449239880454539397067913664088094160819193268643401968970009466652179043139341471403913410402646923633696154454, 11575010486066232687430367040977113580882826853104996856464797182632266635060724100357205810604915010810884387573114266349621457564659060272935537811111850, 116107444921917032985259963199427176510900273385517435613848456370557161312731449337837406563733552524777525870560544042690403987311424820755256727586807, 5859050133610438843641532306693688255014116940390205022708310454673159702673207152462501010791971695002865650407033762568636006764435795015869726867643634, 5954075553161305677556950650395792531753502207483036473422070018485916621872566706504374038792527687442272405589975343003802956899043321092006127828986114, 4571747544457157571652286537158051402285727327066029382085461714597609990601683125994983291866807816649968826930652068427193317966970789937746419206862747, 7166507561570980603812241332170524724051295937096000768984168029904561160020043035660087151672164814332446644696618077835020463308343415953131944864257266, 4852042788460566411381271873349329096978244586097817622748766708426751073559942708861852208085367014057217116211249133109246735634468823924185525972777655, 11962941918999276757181090570698839032103646409734781047194175833198626142790676141060052011581957980660140931408560130449153056874213033784715711461403345, 10324508881746579337486319574059121005227580732153432145860775835052420139026016902518605634385512021513380467928195663920843022679549517463264144660593354, 13276257094435850052122403884510025189232513948002582716865201271569293297601525601586036713056700716929820641888489806178376555435219630186396004003438962, 6525051273399089095687950615197786094425890004112675057642687348101531212837185750558500720306108976630502328600886080197626115513445112562084719104488315, 12922888505610354933000354792496863801007995464403098763485264334670452387681468617068312646367483171083114539083453125614861357751571161533921864394641576, 9489726784141062031514945333087338495823600723655465328127755755022980083351477888038160719541864899912899592065620071698977397662002448273876711116012763, 10630316198843195148937849513165933809121991192035364160395429088101265852052098101114542104327663563661384303617672183366879116750889320604308038959012109, 12675564142993964272844760955973914547747654087592111324261755301551267959231076883765863344473167582531968290671984039948163579495803204811731286282708940, 11847724105274460405216443356582445218232627275228120716891711887600046501095390733716854871561352002320819466803698088448952127166615410820121973485089326, 5131676593756685549522564504727003861447389891839469018437277330988047271086971907217360711863971849879439418231726349935396008040776952541710218842744018, 8049060452950901277510497437779182190254362319091882684392717180429468875432078713802857488901441344429723298843967365750616860588029426099852763482179470, 2365060249260571713545479629411006471094806409182638354076861269679377537605360223984548798658469783472746989448405310909017645138161178501458084966625559, 7467521246204465304438401242342633361751371318557249418344587207503257890765643838557008735305668588521988487342275527781708126255070883848829062790678347, 5841608816993144092409175658260479687582056537041472535819914412630519543198558564258699185557903902095773598614097026740427138629173672250387442834578787, 3935779917509948624841228665498558015416911059417306651751360048412619176423173794541812556512582747588138532941031730797102738268660078594473168666677171, 1459083415233950534805962555425717865938763752937036513111696179351002303817986848490146888626704327653287774806488952733813718461674376764427084478395399, 6426876689549337938550615491086475536072547585103523407263007393570982327518298678278232288342601754164640081474537962710401178482959474762541185760732929, 5241364650650467046722868257809607948071188801137204831449976666385482519613365369974704486723941517654753205012497273820309153659423928739972270634209996, 6387483223002092292686097811446217867743566298067033295601210265979889577756648605354064672061975949925472022416479935990178719227937307079186916383092053, 170562164015232424518655058158727202269056868720093972639058422975773575660534168774299548952867348396798580779605954510297102765330549642318362861226163, 10004133230245713370426176448219282796530473722412487408402635996842671302539458739305597027107498342509248085998067976408732789438099488867425813748783724, 12325342879747412722323355648741345730921040452129462974449188258885453690169624888480720109964630270938743431623479816739889661554987977051169401841580388, 641543989928732942291347866597230552820621633110802944556141221591498546555080480758772801043509130524233886009444044150447511986129019395067102094826363]
for each in A:
    tmp = each
    while tmp >0:
        x.append(tmp%(2**32))
        tmp >>= 32

print(len(x))
predictor = ExtendMT19937Predictor()
for i in x:
    predictor.setrandbits(i,32)

enc = b'cTmkMb\xfc\x05|\x1d\xc7\x13\xbaSe\xe0\xbd\xc0\xd9\xa3\x8cwo\x82yN[B&\x80\xd7KPwQ`\x9c\xbf<y\x8e\x8a\x97e\xa074\xb2'

key1 = b'0b5e732a48fc8c6f5ac6366212d2bc59'
iv = long_to_bytes(predictor.predict_getrandbits(128))
aes = AES.new(key1,AES.MODE_CBC,iv)
enc = aes.decrypt(enc)
print(enc)

SecretShare（赛后）

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

n = 21
t = 21


A = [secret]
for i in range(n-1):
    A.append(random.getrandbits(1024))

X = []
for i in range(n):
    X.append(random.getrandbits(1024))

p = getPrime(1026)

def f(x):
    res = 0
    tmp = 1
    for i in range(n):
        res = (res + tmp * A[i]) % p 
        tmp = tmp *x  % p
    return res % p
# res = a0+a1*x+a2*x^2+a3*x3+...+a20*x20

R = []
for i in range(n):
    R.append(f(X[i]))

P = secret
Q = getPrime(1024)
N = P * Q
m = bytes_to_long(flag)
e = 65537
c = pow(m, e, N)
phi=(P - 1) * (Q - 1)
d = pow(e,-1,phi)
print(long_to_bytes(pow(c,d,N)))

fi = open('output.txt','w')
for i in range(t-1):
    fi.write(str(X[i])+' '+str(R[i])+'\n')
print("leak = %d"%R[-1])
print("p = %d"%p)
print("c = %d"%c)
print("N = %d"%N)

# leak = 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257
# p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029   
# c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912
# N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891

题目给了提示：

$$r\equiv a_0+a_1x+a_2x^2+...+a_{20}x^{20}\pmod p$$

已知的$A,X$都是21个1024位的数，$X$为全随机，直接顺着恢复即可：

$$a_0\equiv r-(a_1x+a_2x^2+...+a_{20}x^{20})\pmod p$$

from extend_mt19937_predictor import ExtendMT19937Predictor
from Crypto.Util.number import *
import gmpy2


with open("output.txt") as f:
    data = f.read().split("\n")[:-1]
X = []
R = []
for each in data:
    tm = each.split(" ")
    X.append(int(tm[0]))
    R.append(int(tm[1]))
print(len(X))

predictor = ExtendMT19937Predictor()
for i in range(len(X)):
    predictor.setrandbits(X[i], 1024)
_ = [predictor.backtrack_getrandbits(1024) for _ in range(len(X))]
A = []
for i in range(20):
    A.append(predictor.backtrack_getrandbits(1024))
A = A[::-1]

x = X[0]
res = R[0]
p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029
for i in range(1, 21):
    res = (res - A[i - 1] * x**i) % p

N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891
p = res
q = N // res
n = p * q
c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912
e = 65537
d = gmpy2.invert(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))

from extend_mt19937_predictor import ExtendMT19937Predictor这个库提供了回溯随机数的功能，但是如果想直接预测之前的随机数，需要先填充掉所有传入的随机数，接下来回溯的随机数就是预测之前的随机数：

predictor = ExtendMT19937Predictor()
for i in range(len(X)):
    predictor.setrandbits(X[i], 1024)
_ = [predictor.backtrack_getrandbits(1024) for _ in range(len(X))]
A = []
for i in range(20):
    A.append(predictor.backtrack_getrandbits(1024))