2024-强网杯-wp-crypto

今年最后一个大比赛！题目质量总体来说没有让人失望，seal是真的一点都不了解，有机会的话学一学来复现下。

EasyRSA

题目描述：

easy的RSA。

题目：

#encoding:utf-8
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2

class RSAEncryptor:
	def __init__(self):
		self.g = self.a = self.b = 0
		self.e = 65537
		self.factorGen()
		self.product()

	def factorGen(self):
		while True:
			self.g = getPrime(500)
			while not gmpy2.is_prime(2*self.g*self.a+1):
				self.a = random.randint(2**523, 2**524)
			while not gmpy2.is_prime(2*self.g*self.b+1):
				self.b = random.randint(2**523, 2**524)
			self.h = 2*self.g*self.a*self.b+self.a+self.b
			if gmpy2.is_prime(self.h):
				self.N = 2*self.h*self.g+1
				print(len(bin(self.N)))
				return

	def encrypt(self, msg):
		return gmpy2.powmod(msg, self.e, self.N)


	def product(self):
		with open('/flag', 'rb') as f:
			self.flag = f.read()
		self.enc = self.encrypt(self.flag)
		self.show()
		print(f'enc={self.enc}')

	def show(self):
		print(f"N={self.N}")
		print(f"e={self.e}")
		print(f"g={self.g}")


RSAEncryptor()

题目的RSA由如下素数组成：

$p = 2ga + 1$ $q = 2gb + 1$

其中$g \approx n^{0.244}$。

这显然是个已知g的Common Prime RSA攻击，找到板子：

Common Prime RSA 笔记 | 独奏の小屋 (hasegawaazusa.github.io)

其中bsgs那一行可能是sage版本问题会报错，搜下sage文档的bsgs参数然后照着改掉就好。

exp：

N=18609249586511447022929188601029606630816796460795187470065452150283160549624372398383148374249992521068549349516037511009027303530058706112191091689108542770802393390942693648814845389265858611340109158309645284100825624911741650444467173946569096983438455034895955228543351436008546035535031019474847660151534447157873386841134028651786166708821300066332734338450150803713659027324704224480646285707278634645234095122804559045312923819794776928194098487972764363649361713512731460059740929840789043447155551107435766468071813945331313861835289050624825980714650042186547867057986370794200778277570803957071502251887
e=65537
g=2157382166227048008151606160068683153029902706798753603550075684775242674106840467207794609506075603345430902709796320595040305496549488048759451499003
enc=1706676139782916859705617140716929473350550599143215409850324617375385155893376548401557158261122335220199922229225746433590875391358929714141838314015655361989993985070285957305126847445442699828095001203266978036575956723172054402632901673504599481917025056824986547174258708944098866240451432510310007060414500907941107101001004474036283249456230343043785187819423163986135104740039129111213967847515011092231384245986891933365405336421413444499204268699546739391271911481490278065027465465222639265899471823742196086481403499948301061349936225773314002398442541447810628796808530412232638250097430811300924120316
gamma = 500/(1024*2)
cbits = ceil(nbits * (0.5 - 2 * gamma))

M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF.random_element()
y = x ^ (2 * g)
# c的范围大概与N^(0.5-2*gamma)很接近
c = bsgs(y, y ^ u, (2**(cbits-1), 2**(cbits+1)), operation='*')
#(a, b, bounds, operation='*', identity=None, inverse=None, op=None)
ab = u - c
apb = v + 2 * g * c
P.<x> = ZZ[]
f = x ^ 2 - apb * x + ab
a = f.roots()
if a:
    a, b = a[0][0], a[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N

from Crypto.Util.number import *
print(long_to_bytes(int(pow(enc,inverse(e,(p-1)*(q-1)),N))))


#flag{a4fc2d54-0ab3-492a-a82b-762705d83cff}

apbq

题目描述：

1	I obtained several sets of ap + bq through channel measurement. Can you solve it?

题目：

from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys

class RSA():
    def __init__(self, privatekey, publickey):
        self.p, self.q, self.d = privatekey
        self.n, self.e = publickey

    def encrypt(self, plaintext):
        if isinstance(plaintext, bytes):
            plaintext = bytes_to_long(plaintext)
        ciphertext = pow(plaintext, self.e, self.n)
        return ciphertext

    def decrypt(self, ciphertext):
        if isinstance(ciphertext, bytes):
            ciphertext = bytes_to_long(ciphertext)
        plaintext = pow(ciphertext, self.d, self.n)
        return plaintext

def get_keypair(nbits, e = 65537):
    p = getPrime(nbits//2)
    q = getPrime(nbits//2)
    n = p * q
    d = inverse(e, n - p - q + 1)
    return (p, q, d), (n, e)

if __name__ == '__main__':
    pt = './output.txt'
    fout = open(pt, 'w')
    sys.stdout = fout

    block_size = ceil(len(flag)/3)
    flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
    e = 65537

    print(f'[+] Welcome to my apbq game')
    # stage 1
    print(f'┃ stage 1: p + q')
    prikey1, pubkey1 = get_keypair(1024)
    RSA1 = RSA(prikey1, pubkey1)
    enc1 = RSA1.encrypt(flag[0])
    print(f'┃ hints = {prikey1[0] + prikey1[1]}')
    print(f'┃ public key = {pubkey1}')
    print(f'┃ enc1 = {enc1}')
    print(f'----------------------')

    # stage 2
    print(f'┃ stage 2: ai*p + bi*q')
    prikey2, pubkey2 = get_keypair(1024)
    RSA2 = RSA(prikey2, pubkey2)
    enc2 = RSA2.encrypt(flag[1])
    kbits = 180
    a = [getRandomNBitInteger(kbits) for i in range(100)]
    b = [getRandomNBitInteger(kbits) for i in range(100)]
    c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
    print(f'┃ hints = {c}')
    print(f'┃ public key = {pubkey2}')
    print(f'┃ enc2 = {enc2}')
    print(f'----------------------')

    # stage 3
    print(f'┃ stage 3: a*p + q, p + bq')
    prikey3, pubkey3 = get_keypair(1024)
    RSA3 = RSA(prikey3, pubkey3)
    enc3 = RSA2.encrypt(flag[2])
    kbits = 512
    a = getRandomNBitInteger(kbits)
    b = getRandomNBitInteger(kbits)
    c1 = a*prikey3[0] + prikey3[1]
    c2 = prikey3[0] + b*prikey3[1] 
    print(f'┃ hints = {c1, c2}')
    print(f'┃ public key = {pubkey3}')
    print(f'┃ enc3 = {enc3}')

题目分成三部分，均需要根据已知数据得到p，q。

part1

给出额外信息：

$hint = p + q$

这个没啥好说的，联立消元解方程。

from Crypto.Util.number import *

#stage1
hint1 = 18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
n1, e1 = (89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589, 65537)
enc1 = 23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247

PR.<p,q> = PolynomialRing(ZZ)
f1 = p*q - n1
f2 = p+q - hint1
res = f1.sylvester_matrix(f2,q).det().univariate_polynomial().roots(multiplicities=False)
p1 = res[0]
q1 = res[1]

print(long_to_bytes(int(pow(enc1, inverse(e1,(p1-1)*(q1-1)), n1))))

#flag{yOu_can_

part2

给出额外信息：

$h_i = a_ip + b_iq$

总共有100组数据，其中p，q都是512bit的，而ai，bi则显得比较小，仅有180bit。

直接规约

由于有180bit这样的小量存在，这就自然让人想到造格，为了使目标向量较短，所以当然要消去p、q才行。因此固定前两组数据，将3-100组数据和前两组数据分别做两次消元，就可以得到一个只含a1，a2，ai，b1，b2，bi的等式如下：

$a_1a_ib_2h_1 - a_1a_2b_ih_1 - a_1a_ib_1h_2 + a_1^2b_ih_2 + a_1a_2b_1h_i + a_1^2b_2h_i = 0$

提出共有的系数a1，也就是：

$(a_ib_2 - a_2b_i)h_1 + (a_1b_i- a_ib_1)h_2 + (a_2b_1 + a_1b_2)h_i = 0$

显然作为系数的$a_jb_k \pm a_kb_j$只有360bit左右，是个小量，因此将所有数据放入格中就可以把他们规约出来。

之后的问题是如何由规约出的这些和差来求出所有a、b来，这一部分可以参考maple的做法，大致思路是把这三个等式做groebner_basis，由于等式不够，所以肯定不能得到a、b的值，但是却可以得到a、b的线性等式，因此可以再做一次LLL后gcd解决：

DownUnderCTF 2023 Writeups | 廢文集中區 (maple3142.net)

#stage2
from re import findall
from subprocess import check_output
from itertools import *

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

hint2 =
n2, e2 = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
enc2 = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244

h = hint2
nums = 98
L = Matrix(ZZ, 1+nums*2, 1+nums*3)
for i in range(1+nums*2):
    L[i,i] = 1
for i in range(nums):
    L[0,1+nums*2+i] = h[i+2]
    L[2*i+1,1+nums*2+i] = h[0]
    L[2*i+2,1+nums*2+i] = h[1]
L[:,-nums:] *= 2^512
L = flatter(L)



v,t,u = L[0,0],L[0,1],L[0,2]
a1s, a2s, a3s, b1s, b2s, b3s = QQ["a1,a2,a3,b1,b2,b3"].gens()
for sign in product((-1, 1), repeat=3):
    I = ideal(
        [
            a3s * b2s - a2s * b3s + sign[0] * t,
            a3s * b1s - a1s * b3s + sign[1] * u,
            a2s * b1s - a1s * b2s + sign[2] * v,
        ]
    )
    if I.dimension() != -1:
        print(sign)
        print("dim", I.dimension())

        def step2(f):
            # this f is in the form of k1*a1+k2*a2+k3*a3==0
            # for some reason, k1*b1+k2*b2+k3*b3==0 also holds
            # use LLL to find it
            print("=" * 40)
            print(f)
            L = matrix(f.coefficients()).T.augment(matrix.identity(3))
            L[:, 0] *= n2
            L = L.LLL()
            print(L[0])
            print(L[1])
            v1 = L[0]
            v2 = L[1]
            xs = []
            for c1, c2 in product((-2, -1, 0, 1, 2), repeat=2):
                v = c1 * v1 + c2 * v2
                _, x1, x2, x3 = v
                if all([0 <= x <= 2**180 for x in (x1, x2, x3)]):
                    xs.append((x1, x2, x3))
            # we don't know which one is correct pair of (a1, a2, a3) and (b1, b2, b3)
            # just try all combinations
            for g1, g2 in combinations(xs, 2):
                a1r, a2r, a3r = g1
                b1r, b2r, b3r = g2
                q = gcd(a2r * h[0] - a1r * h[1], n2)
                if 1 < q < n2:
                    p = n2 // q
                    e = 0x10001
                    d = inverse_mod(e, (p - 1) * (q - 1))
                    m = pow(enc2, d, n2)
                    flag = int(m).to_bytes(1024, "big").strip(b"\x00")
                    print(p,flag)
                    exit()

        step2(I.groebner_basis()[1])

#s0lve_the_@pb

正交格

赛后听群友讨论，发现这个题用正交格的确更加简单，因为hint中的一个值其实就是：

$(a_i,b_i) \left(\begin{matrix} p\\ q\\ \end{matrix} \right) = (h_i)$

我们有一百组等式，因此可以拼起来得到：

$AB_{100 \times 2} \left(\begin{matrix} p\\ q\\ \end{matrix} \right) = H_{100 \times 1}$

接下来就是正交格的常规操作，找到矩阵$M$使得：

$MH = \textbf{0}$

那么有：

$M\cdot AB \cdot \left(\begin{matrix} p\\ q\\ \end{matrix} \right) = \textbf{0}$

而$AB$比较短，因此预期可以对$M$的右核做LLL找到$AB$，从而做GCD恢复p、q。

实际上找到的是B和与B约减过的A

from Crypto.Util.number import *

hint2 = 
n, e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
c = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244


######################################################################################### recover A,B using orthogonal Lattice
L = block_matrix(ZZ,[
    [1,Matrix(ZZ,hint2).T],
])
L = L.LLL()

M = []
for i in L:
    if(i[-1] == 0):
        M.append(i[:-1])
M = Matrix(ZZ,M)

Ker = M.right_kernel().basis()
Ker = Matrix(ZZ, Ker)
AB = Ker.LLL()

B = list(map(abs, AB[1]))
A = [i+j for i,j in zip(AB[0], B)]


######################################################################################### recover p,q
p = GCD(n, hint2[0]*B[1]-hint2[1]*B[0])
q = n // p
print(long_to_bytes(int(pow(c, inverse(e,(p-1)*(q-1)), n))))


#s0lve_the_@pb

part3

给出额外信息：

$c_1 = ap + q$ $c_2 = p + bq$

其中a，b和p，q均为512bit的数字。

两个式子显然可以构造出一个模n下的等式：

$(c_1 - q)(c_2 - p) = 0 \quad(mod\;n)$

展开之后可以发现，p、q的乘积又被消掉了，所以整个式子其实是线性的：

$c_1c_2 - c_1p - c_2q = 0 \quad(mod\;n)$

这个等式中，两个未知量p、q仅有模数n的一半bit而已，很接近LLL可以规约出来的范围，小范围爆破一下：

$c_1c_2 - c_1(2^2p_h + i) - c_2(2^2q_h + j) = 0 \quad(mod\;n)$

然后LLL就可以找到p、q了。

from Crypto.Util.number import *

#stage3
hint3 = (68510878638370415044742935889020774276546916983689799210290582093686515377232591362560941306242501220803210859757512468762736941602749345887425082831572206675493389611203432014126644550502117937044804472954180498370676609819898980996282130652627551615825721459553747074503843556784456297882411861526590080037, 117882651978564762717266768251008799169262849451887398128580060795377656792158234083843539818050019451797822782621312362313232759168181582387488893534974006037142066091872636582259199644094998729866484138566711846974126209431468102938252566414322631620261045488855395390985797791782549179665864885691057222752)
n3,e3 = (94789409892878223843496496113047481402435455468813255092840207010463661854593919772268992045955100688692872116996741724352837555794276141314552518390800907711192442516993891316013640874154318671978150702691578926912235318405120588096104222702992868492960182477857526176600665556671704106974346372234964363581, 65537)
enc3 = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
c1,c2 = hint3

brute = 2
for i in range(2^brute):
    for j in range(2^brute):
        L = Matrix(ZZ, [
            [1,0,0,2^brute*c1],
            [0,1,0,2^brute*c2],
            [0,0,2^(512-brute),c1*i+c2*j-c1*c2],
            [0,0,0,n3]
        ])
        L[:,-1:] *= n3
        res = L.LLL()[0]

        p = 2^brute*abs(res[0])+i
        if(n3 % p == 0):
            print(p)

但是，素数明明分解掉了，为什么求不出明文？然后仔细看源代码发现有乌龙：

1 2	RSA3 = RSA(prikey3, pubkey3) enc3 = RSA2.encrypt(flag[2])

第三部分还是用第二部分的密钥加密的，所以其实不做第三部分也行。

21_steps

题目描述：

1	weight it in 21 steps!

题目：

import re
import random
from secrets import flag
print(f'Can you weight a 128 bits number in 21 steps')
pattern = r'([AB]|\d+)=([AB]|\d+)(\+|\-|\*|//|<<|>>|&|\^|%)([AB]|\d+)'

command = input().strip()
assert command[-1] == ';'
assert all([re.fullmatch(pattern, i) for i in command[:-1].split(';')])

step = 21
for i in command[:-1].split(';'):
    t = i.translate(str.maketrans('', '', '=AB0123456789'))
    if t in ['>>', '<<', '+', '-', '&', '^']:
        step -= 1
    elif t in ['*', '/', '%']:
        step -= 3
if step < 0:exit()

success = 0
w = lambda x: sum([int(i) for i in list(bin(x)[2:])])
for _ in range(100):
    A = random.randrange(0, 2**128)
    wa = w(A)
    B = 0
    try : exec("global A; global B;" + command)
    except : exit()
    if A == wa:
        success += 1

if success == 100:
    print(flag)

整个题目任务就是：

输入不超过21条如下格式的指令：
$A = A \odot B$

如果是乘除或者模的话，一条更比三条强
用这些指令计算出一个128bit以内数字的汉明重量

搜一下hamming weight algorithm之类的关键词，可以找到：

algorithm - Calculating Hamming Weight in O(1) - Stack Overflow

这是32bit的版本，改成128bit之后再转指令就行。

exp：

from Crypto.Util.number import *
from pwn import *


def popcountRE(A):
    B = 0
    B = A >> 1
    B = B & 113427455640312821154458202477256070485
    A = A - B
    #x -= (x >> 1) & 0x55555555555555555555555555555555
    B = A >> 2
    B = B & 68056473384187692692674921486353642291
    A = A & 68056473384187692692674921486353642291
    A = A + B
    #x = (x & 0x33333333333333333333333333333333) + ((x >> 2) & 0x33333333333333333333333333333333)
    B = A >> 4
    A = A + B
    A = A & 20016609818878733144904388672456953615
    #x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
    A = A * 1334440654591915542993625911497130241
    A = A & 340282366920938463463374607431768211455
    A = A >> 120
    #return ((x * 0x01010101010101010101010101010101) & 0xffffffffffffffffffffffffffffffff) >> 120
    return A

instructions=[
    "B=A>>1",
    "B=B&113427455640312821154458202477256070485",
    "A=A-B",
    "B=A>>2",
    "B=B&68056473384187692692674921486353642291",
    "A=A&68056473384187692692674921486353642291",
    "A=A+B",
    "B=A>>4",
    "A=A+B",
    "A=A&20016609818878733144904388672456953615",
    "A=A*1334440654591915542993625911497130241",
    "A=A&340282366920938463463374607431768211455",
    "A=A>>120",
]

msg=";".join(instructions) + ";"
command=msg

sh = remote("47.94.195.201", 38958)
sh.recvuntil(b'Can you weight a 128 bits number in 21 steps')
sh.sendline(command.encode())
print(sh.recvline())
print(sh.recvline())


#flag{you_can_weight_it_in_21_steps!}

traditional_game

题目描述：

1	Since you've made it here, let's now play a Traditional Game from 1997.

题目：

from Crypto.Util.number import getPrime,bytes_to_long
from secret import secret,flag
import random
import time
import os
import signal

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 300
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

random.seed(secret + str(int(time.time())).encode())

class RSA:
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.e = getPrime(128)
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        self.d = pow(self.e, -1, self.phi)  

    def get_public_key(self):
        return (self.n, self.e)
    
    def get_private_key(self, blind_bit=None, unknown_bit=None):
        if blind_bit is not None and unknown_bit is not None:
            blind = getPrime(blind_bit)
            d_ = ((int(self.d >> unknown_bit) // blind * blind) << unknown_bit) + int(self.d % blind)
            return (d_, blind)
        else:
            return (self.d, 0)
    
    def encrypt(self, m):
        if type(m) == bytes:
            m = bytes_to_long(m)
        elif type(m) == str:
            m = bytes_to_long(m.encode())
        return pow(m, self.e, self.n)
    
    def game(self,m0,m1,b):   
        return self.encrypt([m0,m1][b]) 


rsa = RSA()
token = os.urandom(66) 

print( "[+] Welcome to the game!")
print(f"[+] rsa public key: {rsa.get_public_key()}")

coins = 100
price = 100
while coins > 0:
    print("=================================")
    b = random.randint(0,1)
    c = rsa.game(
        b'bit 0:' + os.urandom(114), 
        b'bit 1:' + os.urandom(114), 
        b)
    print("[+] c:",c)
    guessb = int(input("[-] b:"))
    coins -= 1
    if guessb == b:
        price -= 1
        print("[+] correct!") 
    else: 
        print("[+] wrong!") 

if price != 0: 
    print("[-] game over!")
    exit()

blind_bit = 40
unknown_bit = 365

d_,blind = rsa.get_private_key(blind_bit, unknown_bit)

print( "[+] Now, you have permission to access the privkey!")
print(f"[+] privkey is: ({d_},{blind}).")
print(f"[+] encrypt token is: {rsa.encrypt(bytes_to_long(token))}")

guess_token = bytes.fromhex(input("[-] guess token:"))
if guess_token == token:
    print("[+] correct token, here is your flag:",flag)
else:
    print("[-] wrong token")

题目分为两个部分，第一个部分是要连续猜对100次硬币，第二部分是要解一个leak了d部分数据的RSA。

part1

第一部分主要代码为：

coins = 100
price = 100
while coins > 0:
    print("=================================")
    b = random.randint(0,1)
    c = rsa.game(
        b'bit 0:' + os.urandom(114), 
        b'bit 1:' + os.urandom(114), 
        b)
    print("[+] c:",c)
    guessb = int(input("[-] b:"))
    coins -= 1
    if guessb == b:
        price -= 1
        print("[+] correct!") 
    else: 
        print("[+] wrong!") 

if price != 0: 
    print("[-] game over!")
    exit()

每一轮的硬币值是randint(0,1)产生的，而random初始种子的设定是：

1	random.seed(secret + str(int(time.time())).encode())

虽然和时间有关，但是可以看到在前面还附加了一个秘密值secret，这是我们不知道的，因此不能通过本地时间来预测b的值。

然而，由于时间戳做了int处理，因此如果在同一秒内连接上靶机的话，随机数种子就会完全相同。所以做法也很简单，同时开两个靶机，一个随便发数据，去拿到所有的b，另一个把这些正确的b发过去就好了。

从c判断出b我觉得应该不太可行

part2

第二部分要解一个按如下方式泄露私钥d部分数据的RSA：

class RSA:
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.e = getPrime(128)
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        self.d = pow(self.e, -1, self.phi)  

    def get_public_key(self):
        return (self.n, self.e)
    
    def get_private_key(self, blind_bit=None, unknown_bit=None):
        if blind_bit is not None and unknown_bit is not None:
            blind = getPrime(blind_bit)
            d_ = ((int(self.d >> unknown_bit) // blind * blind) << unknown_bit) + int(self.d % blind)
            return (d_, blind)
        else:
            return (self.d, 0)

我们会有d_和blind，记blind为$B$，从这两个数据我们可以把d表示成如下形式：

$d = 2^{365}Bd_h + Bd_m + d_l$

其中dm是未知的，为365bit左右。

dh和dl可以用d_通过如下方式计算出来：
1
2
dh = (d_ >> unknown_bit) // blind
dl = d_ % blind

注意到e是128bit，我们又有d的近似高位，因此我们可以用：

$ed_h \approx kn$ $k \approx \frac{ed_h}{n}$

测试一下可以发现这样近似的k和准确的k仅仅差1。

而为了利用上d的已知信息，仍然老规矩利用下面的等式：

$ed = 1 + k\phi(n)$

将已知的d部分数据和n代入：

$e(2^{365}Bd_h + Bd_m + d_l) = 1 + k(n+1-(p+q))$

移项整理一下得到：

$e(2^{365}Bd_h + d_l) - k(n+1) - 1+ eBd_m + k(p+q) = 0$

那么就有：

$M = e(2^{365}Bd_h + d_l) - k(n+1) - 1$ $eBd_m + k(p+q) = 0 \quad(mod\;M)$

这是一个线性等式，而且模数M比起dm，p+q这两个未知量来说显得相当大，因此可以考虑造格LLL求解，这一部分测试代码如下：

from Crypto.Util.number import *

################################################################################# gen data
p = getPrime(512)
q = getPrime(512)
e = getPrime(128)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)  
blind_bit = 40
unknown_bit = 365
if blind_bit is not None and unknown_bit is not None:
    blind = getPrime(blind_bit)
    d_ = ((int(d >> unknown_bit) // blind * blind) << unknown_bit) + int(d % blind)


################################################################################# get k,dh,dl
k = (e*d_ - 1) // n + 1
dh = (d_ >> unknown_bit) // blind
dl = d_ % blind


################################################################################# LLL
M = e*(2^unknown_bit*blind*dh+dl) - k*(n+1) - 1
K = 2^(513-unknown_bit)
L = matrix(ZZ,[
    [K,0,e*blind],
    [0,1,k],
    [0,0,M]
])
L[:,-1:] *= M
L = L.LLL()
L[:,:1] /= K

for i in L:
    print(i)

然而会发现，我们预期的向量似乎并不在LLL之后的向量中：

$(d_m,p+q,0)$

而出现在第一行的是仅有128bit左右的向量，第二行虽然数量级与目标向量相近，但是与我们的目标向量有较大的误差。记第二行向量为：

$(x,y,0)$

那么p+q和实际y的差值大约有405bit，刚好是unknownbit+blindbit=365+40。

此时我们可以得到第一个信息，由于误差是405bit左右，那么由第二行向量可以获得p+q的100出头的高位。

那么低位呢？此时需要想一下LLL之后的第一行究竟是什么，为什么会有一个更短的向量在目标向量之前，回顾一下造格的等式：

$eBx + ky = 0 \quad(mod\;M)$

可以发现由于系数比起我们想要的根来说更小，所以下面这种形式当然也是解：

$x = -k$ $y = eB$

LLL之后的第一行正是这样的向量：

$\pm (-k, eB , 0)$

而第二行的误差就来自于与这个短向量进行约减，也就是说LLL得到的第二行其实应该是：

$(x,y,0) = t(-k, eB , 0) + (d_m,p+q,0)$

因此我们有：

$y = p+q \quad(mod\;eB)$

因此我们可以拿到p+q模eB下的值，此时我们等价于拥有了p+q的高低位，转化成已知p的高低位copper即可。

这个高低位并不是二进制位，而是模eB意义下的，这个转化也很简单，有兴趣的师傅还可以看一看我出的这个题目：

[tangcuxiaojkuai]easy_copper2 | NSSCTF

exp：

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


################################################################################# data
n, e = 85326799303014496026064371730108772674311332235197622668632563161991602151711567135121280447576711444698674128128361298108919951648223986067215747231280671858955299505770967232491254103263536714363392698361887554304255293991522369123049450389169430042203506125207632731477059899911948136482137033584148217327, 254105853966712863308295955275449077351
d_, blind = 21378651607895524021279554589638483737491146093477974150650211288463988209605132503571807152155799637952833578907915487652394101057156932695702372344185513500134378667094923442647974423915643213700386663283702204046537471425141802799603607927835879677131664511051343930330150649244588933823965535065854996174,1033378191583
c = 53742732129028328063112055299975805421399396945032126712022723372351554830940247890238890674346304685771599765645061449905866414886468887177488826724343823941484173305683401484367061591100780027467534437239106132736115748345075082986831034406103970493456683245813494600511020286115561513979129441895596164513


################################################################################# get k,dh,dl
blind_bit = 40
unknown_bit = 365
k = (e*d_ - 1) // n + 1
dh = (d_ >> unknown_bit) // blind
dl = d_ % blind


################################################################################# LLL
M = e*(2^unknown_bit*blind*dh+dl) - k*(n+1) - 1
K = 2^(513-unknown_bit)
L = matrix(ZZ,[
    [K,0,e*blind],
    [0,1,k],
    [0,0,M]
])
L[:,-1:] *= M
L = L.LLL()
L[:,:1] /= K
pqh = L[1][1] // (e*blind) * (e*blind)
pql = L[1][1] % (e*blind)


################################################################################# copper
############################################### get ph
PR.<x> = PolynomialRing(RealField(1000))
f = x*(pqh-x) - n 
ph = int(f.roots()[0][0]) // (e*blind) * (e*blind)
############################################### get pl
R.<x> = PolynomialRing(Zmod(e))
fe = x*(pql-x) - n
rese = fe.roots()

R.<x> = PolynomialRing(Zmod(blind))
fb = x*(pql-x) - n
resb = fb.roots()

for i in rese:
    for j in tqdm(resb):
        nlist = [e,blind]
        clist = [int(i[0]),int(j[0])]
        pl = int(crt(clist,nlist))

        ############################################### get p
        PR.<x> = PolynomialRing(Zmod(n))
        f = ph + e*blind*x + pl
        f = f.monic()
        res = f.small_roots(X=2^(512-105-167+3), beta=0.499, epsilon=0.02)
        if(res != []):
            p = int(ph + e*blind*res[0] + pl)
            q = n // p
            phi = (p - 1) * (q - 1)
            d = inverse(e, phi)
            print(long_to_bytes(int(pow(c, d, n))).hex())
            assert n % p == 0
            break


#0a00d817e70c0e83bcabd4d38d88a7e08c5427eeaa68e289741dca172597e73b2713ca3f88f8c5205a2cc136cad8bbb6f82d8b35e2efd23cad8cfed470db99e77a81
#flag{eeeeeeeeeeeeeeeeeeeeezzzz_game_will_be_over}

electronic_game

题目描述：

1	After finishing traditional cigarettes, let's try vaping some electronic cigarettes.

题目：

from sage.all import *
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import * 
from base64 import b64encode
from random import * 
from secret import flag
import signal

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 66
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

def qary_trans_to_int(x, q):
    return sum([int(x[i]) * q**i for i in range(len(x))])

def encode(f, q):
    try:
        return b64encode(long_to_bytes(qary_trans_to_int(f.polynomial().coefficients(sparse = False), q)))
    except:
        return b64encode(long_to_bytes(qary_trans_to_int(f.coefficients(sparse = False), q)))

def generate_irreducible_polynomial(R, n):
    while True: 
        f = R.random_element(degree=n) 
        while f.degree() != n:
            f = R.random_element(degree=n) 
        if f.is_irreducible():
            return f

def generate_sparse_irreducible_polynomial(R, n): 
    x = R.gen()
    while True:
        g = sum(choice([-1, 0, 1]) * x**i for i in range(randint(1, n//2 + 1)))
        if (x**n + g + 1).is_irreducible():
            return x**n + g + 1

def random_polynomial(R, n, beta):  
    return sum(randrange(-beta, beta) * R.gen()**i for i in range(randint(0, n))) + R.gen()**n  

q = 333337
n = 128
beta = 333 
chance = 111
polyns = beta//chance
bound  = 106
R = PolynomialRing(GF(q),'x')

F = generate_irreducible_polynomial(R,n).monic()

k1 = GF(q**n, name = 'a', modulus = generate_sparse_irreducible_polynomial(R,n).monic())
k2 = GF(q**n, name = 'b', modulus = F)

phi = FiniteFieldHomomorphism_generic(Hom(k1, k2)) 

print("F:", encode(F,q).decode())

win_count = 0
for _ in range(chance):
    opt = randint(0, 1)
    if opt:
        As = [phi(random_polynomial(k1,n,beta)) for i in range(polyns)] 
    else:
        As = [k2.random_element() for i in range(polyns)]
    
    for i in range(polyns):
        print(f"As[{i}]: {encode(As[i],q).decode()}")

    opt_guess = input("Guess the option[0/1]: ")
    if int(opt_guess) != opt:
        print("Wrong guess!")
    else:
        win_count += 1
        print("Correct guess!")

if win_count >= bound:
    print("You are so smart! Here is your flag:")
    print(flag)
else:
    print("No flag for you!")

题目是一个多项式的decision，他会先生成两个模q下度为128的不可约多项式$G,F$，然后用他们作为模多项式构造出128次的有限扩域：

$k_1 = GF(q^{128}, G)$ $k_2 = GF(q^{128}, F)$

在这里G是一个系数均为1、0、-1且除了x^128外度不超过65的多项式，而F则是完全随机的多项式。

然后生成一个有限域之间的同态：

$\phi: k_1 \rightarrow k_2$

不给出G，但给出我们F，之后进入如下decision：

如果当前opt为1，则生成三个：
$As_i = \phi(A_i)$
其中Ai是k1上的系数不超过beta，且高次项有一些0的多项式（因为是randint(0, n)）
如果当前opt为0，则生成三个k2上的随机多项式

我们需要在111次里成功106次，从而拿到flag。

偷鸡x1

第一反应当然是偷鸡！很明显能感觉到，opt为1的时候涉及同态计算，计算量会比opt为0要大不少，因此测一下本地时间会发现确实有区别：

T1 = time.time()
As = [phi(random_polynomial(k1,n,beta)) for i in range(polyns)] 
T2 = time.time()
As = [k2.random_element() for i in range(polyns)]
T3 = time.time()

print(T2-T1)
print(T3-T2)

1 2	0.005532741546630859 0.0006456375122070312

然而实际测试发现，与靶机交互的时候这种差别完全是看不出来的，只能作罢。

坐在靶机上打也许能行

同态的矩阵表示

那么就老实一点想其他办法，能显著感受到的区别在于：opt为1的时候，其模多项式G和随机多项式Ai的系数都比较小（尤其是G），而商环下的多项式乘法是可以转化成矩阵的，因此第一个想法是能不能转化成一个正交格问题来做区分。

首先需要理解同态的具体过程。对于k1中多项式A到k2的同态，其步骤为：

将k1的不可约多项式$G$放到k2中求根，得到core
在k2中计算：
$As = A(core) \quad \% \quad F$
此时就有：
$As = phi(A)$

而如果把多项式看作由系数组成的向量，那么这个过程就是：

$\textbf{as} = \textbf{a} \cdot C \quad(mod\;q)$

其中C就是在k2中代入core到多项式的矩阵。

测试过程

这一部分要用代码测试一下，首先是：

1 2	phi = FiniteFieldHomomorphism_generic(Hom(k1, k2)) print(phi)

直接打印phi的话就可以看到G的不可约多项式在F中的求根结果，如下是一个示例：

Ring morphism:
  From: Finite Field in a of size 333337^128
  To:   Finite Field in b of size 333337^128
  Defn: a |--> 73459*b^127 + 45965*b^126 + 154611*b^125 + 228072*b^124 + 222553*b^123 + 293345*b^122 + 296462*b^121 + 325636*b^120 + 110826*b^119 + 325665*b^118 + 275677*b^117 + 97527*b^116 + 274255*b^115 + 225271*b^114 + 97921*b^113 + 81246*b^112 + 328017*b^111 + 269156*b^110 + 193081*b^109 + 312527*b^108 + 189230*b^107 + 150907*b^106 + 30731*b^105 + 125825*b^104 + 31844*b^103 + 327717*b^102 + 1433*b^101 + 190323*b^100 + 897*b^99 + 63791*b^98 + 280126*b^97 + 297186*b^96 + 135758*b^95 + 56307*b^94 + 171871*b^93 + 148171*b^92 + 153362*b^91 + 232503*b^90 + 95473*b^89 + 250132*b^88 + 232460*b^87 + 109887*b^86 + 32836*b^85 + 130012*b^84 + 322154*b^83 + 215014*b^82 + 77906*b^81 + 272936*b^80 + 200528*b^79 + 190313*b^78 + 282062*b^77 + 177772*b^76 + 68233*b^75 + 110862*b^74 + 301957*b^73 + 240838*b^72 + 273201*b^71 + 130583*b^70 + 30294*b^69 + 125390*b^68 + 131116*b^67 + 296750*b^66 + 66239*b^65 + 122663*b^64 + 66040*b^63 + 327828*b^62 + 72383*b^61 + 278100*b^60 + 51545*b^59 + 110734*b^58 + 306201*b^57 + 209521*b^56 + 292167*b^55 + 211179*b^54 + 49583*b^53 + 66788*b^52 + 177292*b^51 + 290824*b^50 + 242571*b^49 + 201457*b^48 + 234932*b^47 + 127565*b^46 + 60668*b^45 + 252324*b^44 + 124866*b^43 + 211782*b^42 + 306845*b^41 + 60190*b^40 + 34820*b^39 + 200959*b^38 + 139847*b^37 + 295175*b^36 + 41736*b^35 + 187566*b^34 + 185605*b^33 + 275307*b^32 + 200245*b^31 + 227416*b^30 + 100274*b^29 + 281802*b^28 + 89121*b^27 + 223111*b^26 + 50072*b^25 + 112360*b^24 + 126574*b^23 + 47014*b^22 + 15719*b^21 + 206201*b^20 + 79590*b^19 + 224184*b^18 + 152022*b^17 + 260161*b^16 + 273909*b^15 + 241370*b^14 + 108763*b^13 + 250304*b^12 + 102586*b^11 + 65473*b^10 + 224710*b^9 + 165509*b^8 + 143187*b^7 + 328267*b^6 + 238494*b^5 + 322023*b^4 + 95192*b^3 + 305212*b^2 + 78695*b + 320671

改一改变量名，固定一组F、G进行观察：

F = x^128 + 148280*x^127 + 125296*x^126 + 303967*x^125 + 82692*x^124 + 148324*x^123 + 297200*x^122 + 19852*x^121 + 61039*x^120 + 257505*x^119 + 249895*x^118 + 308497*x^117 + 279156*x^116 + 14767*x^115 + 247088*x^114 + 295630*x^113 + 282010*x^112 + 216734*x^111 + 106241*x^110 + 221465*x^109 + 257885*x^108 + 209863*x^107 + 169559*x^106 + 46083*x^105 + 313025*x^104 + 279179*x^103 + 282980*x^102 + 301293*x^101 + 303914*x^100 + 279971*x^99 + 48418*x^98 + 132348*x^97 + 34804*x^96 + 175616*x^95 + 99277*x^94 + 251209*x^93 + 271846*x^92 + 246439*x^91 + 119459*x^90 + 247587*x^89 + 161063*x^88 + 199742*x^87 + 84803*x^86 + 203535*x^85 + 72656*x^84 + 131490*x^83 + 133892*x^82 + 100587*x^81 + 228110*x^80 + 122509*x^79 + 35010*x^78 + 206327*x^77 + 44620*x^76 + 296935*x^75 + 181274*x^74 + 176313*x^73 + 57085*x^72 + 108158*x^71 + 107810*x^70 + 206948*x^69 + 178184*x^68 + 210102*x^67 + 204244*x^66 + 176239*x^65 + 273323*x^64 + 93382*x^63 + 293018*x^62 + 116418*x^61 + 121990*x^60 + 7698*x^59 + 17397*x^58 + 269648*x^57 + 109790*x^56 + 44374*x^55 + 302391*x^54 + 266167*x^53 + 244403*x^52 + 185576*x^51 + 289374*x^50 + 300327*x^49 + 331430*x^48 + 180450*x^47 + 71904*x^46 + 196869*x^45 + 277619*x^44 + 176135*x^43 + 161273*x^42 + 214612*x^41 + 214480*x^40 + 160252*x^39 + 188335*x^38 + 94120*x^37 + 212575*x^36 + 116820*x^35 + 239270*x^34 + 122340*x^33 + 294503*x^32 + 292932*x^31 + 332717*x^30 + 106872*x^29 + 126922*x^28 + 179567*x^27 + 235901*x^26 + 83800*x^25 + 24144*x^24 + 187639*x^23 + 308050*x^22 + 223365*x^21 + 29187*x^20 + 278083*x^19 + 6529*x^18 + 55605*x^17 + 33840*x^16 + 61834*x^15 + 164019*x^14 + 42485*x^13 + 57332*x^12 + 190124*x^11 + 195118*x^10 + 94061*x^9 + 263431*x^8 + 115313*x^7 + 136480*x^6 + 315639*x^5 + 120028*x^4 + 143444*x^3 + 140329*x^2 + 75249*x + 73094
G = x^128 + x^39 + 333336*x^37 + 333336*x^36 + 333336*x^35 + 333336*x^34 + x^33 + x^30 + x^27 + 333336*x^26 + x^25 + 333336*x^24 + x^22 + x^21 + x^20 + x^19 + x^17 + 333336*x^16 + 333336*x^15 + 333336*x^14 + x^13 + x^12 + 333336*x^10 + 333336*x^9 + x^8 + x^7 + 333336*x^5 + 333336*x^4 + 333336*x^3 + 333336*x + 1

k1 = GF(q^n, name = 'a', modulus = G)
k2 = GF(q^n, name = 'b', modulus = F)
a, b = k1.gen(), k2.gen()

phi = FiniteFieldHomomorphism_generic(Hom(k1, k2)) 
#print(phi)

core = 73459*b^127 + 45965*b^126 + 154611*b^125 + 228072*b^124 + 222553*b^123 + 293345*b^122 + 296462*b^121 + 325636*b^120 + 110826*b^119 + 325665*b^118 + 275677*b^117 + 97527*b^116 + 274255*b^115 + 225271*b^114 + 97921*b^113 + 81246*b^112 + 328017*b^111 + 269156*b^110 + 193081*b^109 + 312527*b^108 + 189230*b^107 + 150907*b^106 + 30731*b^105 + 125825*b^104 + 31844*b^103 + 327717*b^102 + 1433*b^101 + 190323*b^100 + 897*b^99 + 63791*b^98 + 280126*b^97 + 297186*b^96 + 135758*b^95 + 56307*b^94 + 171871*b^93 + 148171*b^92 + 153362*b^91 + 232503*b^90 + 95473*b^89 + 250132*b^88 + 232460*b^87 + 109887*b^86 + 32836*b^85 + 130012*b^84 + 322154*b^83 + 215014*b^82 + 77906*b^81 + 272936*b^80 + 200528*b^79 + 190313*b^78 + 282062*b^77 + 177772*b^76 + 68233*b^75 + 110862*b^74 + 301957*b^73 + 240838*b^72 + 273201*b^71 + 130583*b^70 + 30294*b^69 + 125390*b^68 + 131116*b^67 + 296750*b^66 + 66239*b^65 + 122663*b^64 + 66040*b^63 + 327828*b^62 + 72383*b^61 + 278100*b^60 + 51545*b^59 + 110734*b^58 + 306201*b^57 + 209521*b^56 + 292167*b^55 + 211179*b^54 + 49583*b^53 + 66788*b^52 + 177292*b^51 + 290824*b^50 + 242571*b^49 + 201457*b^48 + 234932*b^47 + 127565*b^46 + 60668*b^45 + 252324*b^44 + 124866*b^43 + 211782*b^42 + 306845*b^41 + 60190*b^40 + 34820*b^39 + 200959*b^38 + 139847*b^37 + 295175*b^36 + 41736*b^35 + 187566*b^34 + 185605*b^33 + 275307*b^32 + 200245*b^31 + 227416*b^30 + 100274*b^29 + 281802*b^28 + 89121*b^27 + 223111*b^26 + 50072*b^25 + 112360*b^24 + 126574*b^23 + 47014*b^22 + 15719*b^21 + 206201*b^20 + 79590*b^19 + 224184*b^18 + 152022*b^17 + 260161*b^16 + 273909*b^15 + 241370*b^14 + 108763*b^13 + 250304*b^12 + 102586*b^11 + 65473*b^10 + 224710*b^9 + 165509*b^8 + 143187*b^7 + 328267*b^6 + 238494*b^5 + 322023*b^4 + 95192*b^3 + 305212*b^2 + 78695*b + 320671

f = random_polynomial(R, n, beta)
print(phi(f))
print(sum(list(f)[i]*core^i for i in range(n+1)))

结果为：

1
2

90651*b^127 + 48921*b^126 + 317095*b^125 + 7873*b^124 + 274789*b^123 + 160062*b^122 + 207308*b^121 + 237019*b^120 + 204263*b^119 + 267380*b^118 + 114003*b^117 + 149239*b^116 + 58126*b^115 + 55786*b^114 + 286352*b^113 + 305047*b^112 + 117630*b^111 + 266050*b^110 + 180452*b^109 + 272098*b^108 + 28949*b^107 + 197679*b^106 + 203360*b^105 + 226493*b^104 + 75252*b^103 + 265873*b^102 + 225485*b^101 + 59931*b^100 + 60212*b^99 + 289428*b^98 + 83485*b^97 + 295707*b^96 + 176312*b^95 + 4467*b^94 + 206451*b^93 + 258643*b^92 + 201874*b^91 + 281183*b^90 + 11864*b^89 + 104831*b^88 + 279072*b^87 + 6542*b^86 + 289955*b^85 + 95606*b^84 + 283515*b^83 + 37343*b^82 + 137199*b^81 + 157867*b^80 + 68322*b^79 + 264266*b^78 + 78000*b^77 + 39760*b^76 + 111509*b^75 + 2120*b^74 + 293613*b^73 + 45674*b^72 + 220453*b^71 + 119761*b^70 + 207557*b^69 + 67778*b^68 + 18979*b^67 + 204342*b^66 + 126067*b^65 + 320210*b^64 + 295529*b^63 + 330547*b^62 + 30523*b^61 + 49342*b^60 + 210441*b^59 + 293588*b^58 + 13751*b^57 + 162848*b^56 + 26422*b^55 + 216110*b^54 + 20437*b^53 + 329478*b^52 + 191422*b^51 + 127252*b^50 + 330040*b^49 + 222976*b^48 + 42022*b^47 + 27741*b^46 + 211697*b^45 + 180466*b^44 + 110159*b^43 + 150589*b^42 + 201801*b^41 + 298657*b^40 + 166987*b^39 + 261619*b^38 + 324182*b^37 + 330271*b^36 + 316021*b^35 + 32823*b^34 + 202060*b^33 + 101009*b^32 + 4313*b^31 + 312481*b^30 + 84293*b^29 + 111074*b^28 + 199076*b^27 + 186666*b^26 + 182304*b^25 + 13949*b^24 + 93027*b^23 + 224149*b^22 + 264084*b^21 + 300936*b^20 + 126654*b^19 + 20076*b^18 + 217563*b^17 + 293567*b^16 + 107585*b^15 + 142407*b^14 + 245*b^13 + 141130*b^12 + 161996*b^11 + 99645*b^10 + 235644*b^9 + 30653*b^8 + 142590*b^7 + 186706*b^6 + 72897*b^5 + 33019*b^4 + 284283*b^3 + 251073*b^2 + 283266*b + 291242
90651*b^127 + 48921*b^126 + 317095*b^125 + 7873*b^124 + 274789*b^123 + 160062*b^122 + 207308*b^121 + 237019*b^120 + 204263*b^119 + 267380*b^118 + 114003*b^117 + 149239*b^116 + 58126*b^115 + 55786*b^114 + 286352*b^113 + 305047*b^112 + 117630*b^111 + 266050*b^110 + 180452*b^109 + 272098*b^108 + 28949*b^107 + 197679*b^106 + 203360*b^105 + 226493*b^104 + 75252*b^103 + 265873*b^102 + 225485*b^101 + 59931*b^100 + 60212*b^99 + 289428*b^98 + 83485*b^97 + 295707*b^96 + 176312*b^95 + 4467*b^94 + 206451*b^93 + 258643*b^92 + 201874*b^91 + 281183*b^90 + 11864*b^89 + 104831*b^88 + 279072*b^87 + 6542*b^86 + 289955*b^85 + 95606*b^84 + 283515*b^83 + 37343*b^82 + 137199*b^81 + 157867*b^80 + 68322*b^79 + 264266*b^78 + 78000*b^77 + 39760*b^76 + 111509*b^75 + 2120*b^74 + 293613*b^73 + 45674*b^72 + 220453*b^71 + 119761*b^70 + 207557*b^69 + 67778*b^68 + 18979*b^67 + 204342*b^66 + 126067*b^65 + 320210*b^64 + 295529*b^63 + 330547*b^62 + 30523*b^61 + 49342*b^60 + 210441*b^59 + 293588*b^58 + 13751*b^57 + 162848*b^56 + 26422*b^55 + 216110*b^54 + 20437*b^53 + 329478*b^52 + 191422*b^51 + 127252*b^50 + 330040*b^49 + 222976*b^48 + 42022*b^47 + 27741*b^46 + 211697*b^45 + 180466*b^44 + 110159*b^43 + 150589*b^42 + 201801*b^41 + 298657*b^40 + 166987*b^39 + 261619*b^38 + 324182*b^37 + 330271*b^36 + 316021*b^35 + 32823*b^34 + 202060*b^33 + 101009*b^32 + 4313*b^31 + 312481*b^30 + 84293*b^29 + 111074*b^28 + 199076*b^27 + 186666*b^26 + 182304*b^25 + 13949*b^24 + 93027*b^23 + 224149*b^22 + 264084*b^21 + 300936*b^20 + 126654*b^19 + 20076*b^18 + 217563*b^17 + 293567*b^16 + 107585*b^15 + 142407*b^14 + 245*b^13 + 141130*b^12 + 161996*b^11 + 99645*b^10 + 235644*b^9 + 30653*b^8 + 142590*b^7 + 186706*b^6 + 72897*b^5 + 33019*b^4 + 284283*b^3 + 251073*b^2 + 283266*b + 291242

输出值相等，符合我们的预期，接下来就是转成矩阵形式：

C = matrix([(core**i).list() for i in range(n+1)])
print(phi(f).list())
f = vector(GF(q), f.list())
print(f*C)

输出值依然相等，因此我们已经找到了同态正确的矩阵表示方法，此外，由于core是G在k2中的根，因此我们还有：

$\textbf{g} \cdot C = \textbf{0}$

验证一下：

1
2
3

C = matrix([(core**i).list() for i in range(n+1)])
g = vector(GF(q), G.list())
print(g*C)

输出为：

(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

也符合我们的预期。

正交格

此时问题转化为，已知以下关系式：

$\textbf{a} \cdot C = \textbf{as}$ $\textbf{g} \cdot C = \textbf{0}$

我们知道的信息有：

$\textbf{as}$的值
$\textbf{a}$和$\textbf{g}$都比较小，尤其是$\textbf{g}$仅由1、0、-1组成，小中小

因此似乎是个HSSP类型的正交格问题。

然而试了好一会儿，发现核的方向似乎不太对，而且格的维数略大，所以最后也没有搞定这个思路。

偷鸡x2

然而，在上面的分析中可以知道，由于我们有k2的不可约多项式$F$，那么一旦我们有了k1的不可约多项式$G$，我们自然就有了矩阵$C$，那么通过解下面的矩阵方程，我们就可以得到$\textbf{a}$来：

$x \cdot C = \textbf{as}$

而$\textbf{a}$的系数是不超过beta的，因此就可以做出判断了。

为什么可以得到$G$呢？注意到他的生成过程为：

def generate_sparse_irreducible_polynomial(R, n): 
    x = R.gen()
    while True:
        g = sum(choice([-1, 0, 1]) * x**i for i in range(randint(1, n//2 + 1)))
        if (x**n + g + 1).is_irreducible():
            return x**n + g + 1

可以发现，除了最后必须会有的x^128以外，剩下的最高次数是由randint(1, n//2 + 1)决定的！而这显然有一定机会赌到较小的度，比如10以内。

而且在一次完整的交互过程中，$G$是不会变的，那么我们可以将所有度在10以内的不可约多项式$G$提前算好，然后在连接上靶机得到$F$之后，计算出所有对应的$C$。那么如果当前的$G$正好度在10以内，我们就可以成功解矩阵方程做出decision。由于有66s的timeout，所以$G$少取一些，减少$C$的计算量。

接下来就是拼脸而已，实际上我跑了几次就跑出来了。

exp：

from sage.all import *
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import * 
from base64 import *
from pwn import *
import itertools, tqdm


def qary_trans_to_int(x, q):
    return sum([int(x[i]) * q**i for i in range(len(x))])

def int_trans_to_qary_trans(x, q):
    arr = []
    while(x):
        arr.append(x % q)
        x //= q
    return arr

def encode(f, q):
    try:
        return b64encode(long_to_bytes(qary_trans_to_int(f.polynomial().coefficients(sparse = False), q)))
    except:
        return b64encode(long_to_bytes(qary_trans_to_int(f.coefficients(sparse = False), q)))

def generate_irreducible_polynomial(R, n):
    while True: 
        f = R.random_element(degree=n) 
        while f.degree() != n:
            f = R.random_element(degree=n) 
        if f.is_irreducible():
            return f

def generate_sparse_irreducible_polynomial(R, n): 
    x = R.gen()
    while True:
        g = sum(choice([-1, 0, 1]) * x**i for i in range(randint(1, n//2 + 1)))
        if (x**n + g + 1).is_irreducible():
            return x**n + g + 1


q = 333337
n = 128
beta = 333 
chance = 111
polyns = beta//chance
bound  = 106
R, (x, ) = PolynomialRing(GF(q), 'x').objgens()

try:
    Gs = #预计算过的列表
    Gs = Gs[:100]
except:
    Gs = list()
    for l in range(10):
        for g in tqdm.tqdm(itertools.product([-1, 0, 1], repeat=l+1)):
            g = sum(g[i]*x**i for i in range(l+1))
            g = x**n + g + 1
            if g.is_irreducible():
                Gs.append(g)
    print(f"{Gs = }")

while True:
    sh = remote("47.94.151.65", 32787)
    sh.recvuntil(b"F:")
    res = sh.recvline().strip().decode()
    F = int_trans_to_qary_trans(bytes_to_long(b64decode(res)), q)
    assert encode(R(F), q) == res.encode()
    F = R(F)
    k2, (b, ) = GF(q**n, name = 'b', modulus = F).objgens()

    Cs = list()
    for G in tqdm.tqdm(Gs):
        k1, (a, ) = GF(q**n, name = 'a', modulus = G).objgens()
        phi = FiniteFieldHomomorphism_generic(Hom(k1, k2))
        core = phi(a)
        C = matrix(GF(q), [(core**i).list() for i in range(n)])
        Cs.append(C)

    def decision(As, C):
        As = matrix(GF(q), [A.list() for A in As])
        try:
            fs = C.solve_left(As)
            cnt = sum([f.list().count(0) for f in fs])
            return int(cnt > 20)
        except:
            return 0

    nowC = None
    cnt = 0
    for i in tqdm.trange(111):
        As = []
        sh.recvuntil(b"As[0]: ")
        As.append(R(int_trans_to_qary_trans(bytes_to_long(b64decode(sh.recvline().strip().decode())), q)))
        sh.recvuntil(b"As[1]: ")
        As.append(R(int_trans_to_qary_trans(bytes_to_long(b64decode(sh.recvline().strip().decode())), q)))
        sh.recvuntil(b"As[2]: ")
        As.append(R(int_trans_to_qary_trans(bytes_to_long(b64decode(sh.recvline().strip().decode())), q)))
        
        ###################################################################### Decision here
        opt = 0
        if nowC:
            opt = decision(As, nowC)
        else:
            for C in Cs:
                opt = decision(As, C)
                if opt:
                    nowC = C
                    break

        ###################################################################### Decision here
        sh.recvuntil(b"Guess the option[0/1]: ")
        sh.sendline(str(opt).encode())
        res = sh.recvline()
        # print(opt, res)
        if b'Wrong' in res:
            cnt += 1
        if cnt > 5:
            sh.close()
            print("not this time")
            break
    else:
        print(sh.recvline())
        print(sh.recvline())
        sh.interactive()
    

#flag{ju5t_4_d3c1si0n4l_ff1_g4m3}

偷鸡x3

刚刚那个方法至少需要理解同态的矩阵表示，然而，仔细想想，既然已经有了$G$，真的需要这样绕一圈解矩阵方程吗？实际上这样就可以了XD：

k1 = GF(q**n, name = 'a', modulus = G)
k2 = GF(q**n, name = 'b', modulus = F)
phi = FiniteFieldHomomorphism_generic(Hom(k1, k2))
phi1 = phi^(-1)

A = random_polynomial(k1,n,beta)
phiA = phi(A)
A_ = phi1(phiA)
assert A == A_

域中元素的迹

看了下春哥他们的wp，发现说用元素的迹可以做出区分，就像下面这样：

As = [phi(random_polynomial(k1,n,beta)) for i in range(polyns)] 
print([min(i.trace(), q-i.trace()) for i in As])
As = [k2.random_element() for i in range(polyns)]
print([min(i.trace(), q-i.trace()) for i in As])

1 2	[2688, 1280, 7424] [119765, 87415, 89479]

可以看出opt为1的时候，元素的迹与q会很接近（因为元素的迹有正有负，这相当于说元素的迹比较小），因此可以区分出来。

并不是每组都这么明显，比如下面这组：
1
2
[24320, 40832, 10624]
[11763, 5615, 6528]
所以每次给出三组数据是降低错误率，并且有五次容错

那么这就引出两个问题：

什么是域中元素的迹？
为什么opt为1的时候，元素的迹会比较小？

概念

因为我完全不知道域中元素的迹是什么，因此还是得先搜索一下，发现可以参考下面这篇：

有限域的结构(3): 迹, 范数与基 - 知乎 (zhihu.com)

直截了当的，文中给出了这样的定义：

测试一下发现的确是这样，而且最终trace的值会落在基域$F_q$内：

1
2
3

a = random_polynomial(k1,n,beta)
print(sum([a^(q^i) for i in range(128)]))
print(a.trace())

1
2

1690
1690

接着往下看，可以看见一个等价定义：

也就是说一个元素的迹实际上是他的极小多项式的所有根的和，而把极小多项式按照全部根做因式分解后对比系数可以发现，迹其实就是极小多项式的次高项系数的负数值。

依然测试一下：

1
2
3

a = random_polynomial(k1,n,beta)
g = a.minimal_polynomial()
print(-g.coefficients()[-2] % q == a.trace())

True

结果是正确的。

推论1

有了上面的基础理论，现在回顾题目。

显然，对于opt=0的情况，三个元素都是k2中随机的，迹自然也不会有什么特殊性质，因此我们主要关注opt=1。由于迹仅跟元素的极小多项式有关，因此我们要关注元素的极小多项式。

我们记没有经过同态的当前元素为$\alpha$，极小多项式的意义在于，由他生成的主理想可以得到所有系数来自基域$F_p$的以$\alpha$为根的多项式，自然有：

$g(\alpha) = 0$

那么同态之后就有：

$g(\phi(\alpha)) = \phi(g(\alpha)) = 0$

可以推得，对于$\forall f \in J,J = (g(x))$，有：

$f(\phi(\alpha)) = \phi(f(\alpha)) = 0$

这说明$g(x)$生成的主理想也能得到所有以$\phi(\alpha)$为根的多项式，因此同态前后极小多项式是相等的，测试一下：

1 2	a = random_polynomial(k1,n,beta) print(phi(a).minimal_polynomial() == a.minimal_polynomial())

True

的确符合预期。

抽代说实话有点忘了，不严谨甚至错误的地方欢迎指出

这说明什么呢？由于极小多项式一样，而迹只和极小多项式有关，那么对于这个题目来说就得到了一个重要结论：同态前后元素的迹是相等的。

推论2

因此现在我们只需要关注同态前元素的迹有什么性质，我们知道同态前的元素$\alpha$满足：

本身系数比较小
所在扩域的模多项式系数也比较小

然而我的确想明白为什么满足这两个条件，$\alpha$的迹就会也显得比较小，不过不管是脑子里冥冥之中的直觉还是实际测试出来都的确是这样。因此我们不妨脸皮厚一点，认为我们得到了第二个结论：random_polynomial(k1,n,beta)生成的元素$\alpha$的迹比较小。

所以结合上述两个推论就可以用迹的大小来对元素究竟是opt为1还是opt为0做出判断。

ECRandom_game

题目描述：

easy密码游戏

题目：

from flag import M, q, a, b, select
import hashlib
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES
import sys
import ecdsa
from Crypto.Util.Padding import pad, unpad
from ecdsa.ellipticcurve import CurveFp,Point
from math import ceil
import os
import random
import string

flag = b'qwb{kLeMjJw_HBPtoHsVhnnxZdvtGjomivNDUI_vMRhZHrfKlCZ6HlGAeXRV_gQ8i117nGhzEMr0Zk_YTl1wftSskpX4JLnryE9Mhl96cPTWorGCl_R6nD33bcx1AYflag_leak}'
assert len(flag) == 136

BANNER = '''
 GGGGG   OOOOO   DDDDD   DDDDD    GGGGG    AAA    MM    MM EEEEEEE 
GG      OO   OO  DD   D  DD   D  GG       AAAAA   MMM  MMM EE      
GG  GGG OO   OO  DD   D  DD   D  GG  GGG  A   A   MM MM MM EEEEE   
GG   GG OO   OO  DD   D  DD   D  GG   GG  AAAAA   MM    MM EE      
GGGGGGG  OOOOO   DDDDD   DDDDD   GGGGGGG  A   A   MM    MM EEEEEEE 
 '''

NNN = []
def die(*args):
    pr(*args)
    quit()

def pr(*args):
    s = " ".join(map(str, args))
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

def sc():
    return sys.stdin.buffer.readline()

def Rng(k):
    ran = random.getrandbits(k)
    NNN.append(ran)
    return ran


def ADD(num):
    NUM = 0
    for i in range(num):
        NUM += Rng(32)
    return NUM

def secure_choice(sequence):
    if not sequence:
        return None
    randbelow = 0
    for i, x in enumerate(sequence):
        randbelow += 1
        if os.urandom(1)[0] < (1 << 8) * randbelow // len(sequence):
            return x

def xDBLADD(P, Q, PQ, q, a, b):
    (X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
    X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
    Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
    X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))
    Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
    X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
    return (X4, Z4), (X5, Z5)

def xMUL(P, k, q, a, b):
    Q, R = (1, 0), P
    for i in reversed(range(k.bit_length() + 1)):
        if k >> i & 1:
            R, Q = Q, R
        Q, R = xDBLADD(Q, R, P, q, a, b)
        if k >> i & 1:
            R, Q = Q, R
    return Q

def shout(x, d, q, a, b):
    P = (x,1)
    Q = xMUL(P, d, q, a, b)
    return Q[0] * pow(Q[1], -1, q) % q

def generate_random_string(length):
    characters = string.ascii_letters + string.digits
    random_string = ''.join(secure_choice(characters) for i in range(length))
    return random_string

class ECCDu():
    def __init__(self,curve,G):
        self.state = getRandomNBitInteger(512)
        self.Curve = curve
        self.g = G

        self.num = Rng(32)
        d = 65537
        self.Q = self.num*self.g
        self.P = d * self.Q

    def ingetkey(self):
        t = int((self.state * self.Q).x())
        self.updade()
        return t%(2**250)

    def updade(self):
        self.state = int((self.state * self.P).x())

    def Random_key(self, n:int):
        out = 0
        number = ceil(n/250)
        for i in range(number):
            out = (out<<250) + self.ingetkey()
        return out % (2**n)

def proof_of_work():
    random.seed(os.urandom(8))
    proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
    _hexdigest = sha256(proof.encode()).hexdigest()
    pr(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
    pr('Give me XXXX: ')
    x = sc().rstrip(b'\n')
    if len(x) != 4 or sha256(x + proof[4:].encode()).hexdigest() != _hexdigest:
        return False
    return True

def main():
    pr(BANNER)
    pr('WELCOME TO THIS SIMPLE GAME!!!')
    ASSERT = proof_of_work()
    if not ASSERT:
        die("Not right proof of work")

    pr('Now we will start our formal GAME!!!')
    pr('===== First 1💪: =====')
    pr('Enter an integer as the parameter p for Curve: y^2 = x^3+12x+17 (mod p) and 250<p.bit_length()')
    p1 = int(sc())
    if not 250<=p1.bit_length():
        die('Wrong length!')
    curve = CurveFp(p1, 12, 17,1)
    pr(curve)
    pr('Please Enter a random_point G:')
    G_t = sc().split(b' ')
    Gx,Gy = int(G_t[0]),int(G_t[1])
    if not curve.contains_point(Gx,Gy):
        die('This point is outside the curve')
    G = Point(curve,Gx,Gy)

    for i in range(500):
        ECDU = ECCDu(curve,G)
        m  = 'My secret is a random saying of phrase,As below :' + generate_random_string(119)
        Number = ECDU.Random_key(1344)
        c = Number^bytes_to_long(m.encode())
        pr(f'c = {c}')
        pr(f'P = {int(ECDU.P.x()), int(ECDU.P.y())}')
        pr(f'Q = {int(ECDU.Q.x()), int(ECDU.Q.y())}')

        pr('Enter m:')
        m_en = sc().rstrip(b'\n')
        if m_en != m.encode():
            die('This is not the right m,Please try again')
        else:
            pr('Right m!!!')
    pr('Bingo!')
    new_state,new_state1 = ADD(136),ADD(50)
    
    random.seed(new_state)

    pr('===== Second 2💪: =====')
    curve1 = CurveFp(q,a,b,1)
    pr(f'{int(curve1.p()),int(curve1.a()),int(curve1.b())}')

    pr("Enter a number that does not exceed 1500")
    number = int(sc())

    pr(f'You only have {number} chances to try')
    success = 0
    for i in range(number):
        Gx = secure_choice(select)
        R = Rng(25)
        pr('Gx = ',Gx)
        pr('Px = ',shout(Gx, R, q, a, b))
        R_n = int(sc().rstrip(b'\n'))
        if R_n != R:
            pr(f'Wrong number!!!,Here is your right number {R}')
        else:
            pr('GGood!')
            success += 1

    if int(success)/int(number) <= 0.262:
        die('Please Try more...')

    random.seed(new_state)
    iv_num = ADD(2000)

    iv = hashlib.sha256(str(iv_num).encode()).digest()[:16]
    key = hashlib.sha256(str(new_state1).encode()).digest()[:16]
    Aes = AES.new(key,AES.MODE_CBC, iv)
    C = Aes.encrypt(pad(flag,16))

    key_n, iv_n = int(sc()), int(sc())
    iv1 = hashlib.sha256(str(iv_n).encode()).digest()[:16]
    key1 = hashlib.sha256(str(key_n).encode()).digest()[:16]
    Aes_verify = AES.new(key1,AES.MODE_CBC, iv1)
    C_verify = unpad(Aes_verify.decrypt(C),16)

    if C_verify == flag:
        pr('Congratulations🎇🎇🎇!!!!')
        pr('Here is your flag😊：', M)
    else:
        pr('Maybe you could get the right flag!')

if __name__ == '__main__':
    main()

这个题表面上是ECC，实际上是MT19937的大满套。

part1

第一部分基于一个Dual EC的伪随机数生成器，其原理可以参考：

密码学后门系列Ⅰ: Dual EC | tl2cents blog (tanglee.top)

总之，我们既然有他的后门d，而且每次msg固定了高位，因此可以获得stage从而往后预测随机数，所以通过500次不是问题。

而这五百次中，每一次都会涉及一个MT19937的随机数ki，他是getrandbits(32)生成的，我们需要求出他来进行后续的随机数预测，具体来说它满足：

$Q = k_iG$

而他们所在的曲线的素数p是我们提供的，因此爆破一下p，找一个光滑小因子乘积超过32bit的曲线就可以快速求解dlp得到ki了。

在通过这五百轮之后他会生成：

1	new_state,new_state1 = ADD(136),ADD(50)

这里ADD的意思就是接下来136个getrandbits(32)和50个getrandbits(32)的求和结果。

我们只有500个随机数，做不到准确预测后续所有的随机数，然而由于MT的twist只和三个状态有关，也就是：

$s_{i+624} = f(s_{i}, s_{i+1}, s_{i+397})$

因此我们虽然预测不了newstate，但是预测newstate1是完全没有问题的，因为所有与他有关的位置都在前500个已知的随机数中。而且做法更加简单，只需要往predictor里塞了前500个正确数据之后，再塞124个垃圾数据凑够624个，之后进行预测就行了。

exp：

from Crypto.Util.number import *
from pwn import *

####################################################################################################### part1 Dual EC
def proof(sh):
    import string, tqdm, hashlib, itertools

    sh.recvuntil(b'sha256(XXXX+')
    suffix = sh.recv(16)
    sh.recvuntil(b') == ')
    pre = sh.recvline().strip().decode()[:-1]
    for prefix in tqdm.tqdm(itertools.product(string.ascii_letters + string.digits, repeat=4)):
        prefix = ''.join(prefix).encode()
        if hashlib.sha256(prefix+suffix).hexdigest() == pre:
            sh.sendlineafter(b'Give me XXXX: ', prefix)
            break
    return

def func1():
    global out1
    def part1(P, Q, c):
        d = 65537
        known = b'My secret is a random saying of phrase,As below :' + b'\x00'*119
        m = bytes_to_long(known) ^^ c
        prefix = bytes_to_long(long_to_bytes(m, len(known))[:len(known)-119])<<(119*8)
        number = ceil(1344/250)
        outs = [(prefix>>(i*250)) % 2**250 for i in range(number)][::-1]
        # ls0, s1, hs2, ...
        t1 = outs[1]
        ht2 = outs[2]
        for k in range(2**10):
            s1 = ZZ(t1 + k*2**250)
            try:
                sQ = E.lift_x(s1)
                s2 = int((d*sQ).xy()[0])
                t2 = int((s2*Q).xy()[0]) % 2**250
                if ((t2|ht2) == t2) and ((t2&ht2) == ht2):
                    break
            except Exception as e:
                continue
        else:
            raise Exception("not this time")
        state = s2
        outs = outs[:2]
        for i in range(number-2):
            t = int((state*Q).xy()[0])
            state = int((state*P).xy()[0])
            outs.append(t % 2**250)
        out = 0
        for t in outs:
            out = (out<<250) + (t)
        m = long_to_bytes(out ^^ c)
        return m
    
    p = 76837912973221323002483668912067151296065917149894557283725838853584131795679
    E = EllipticCurve(GF(p), [12, 17])
    n = 76837912973221323002483668912067151296162675561982794479768589266782793320165
    Gx, Gy = (50815842720719088866452690975886010078415234799217383820996108469852859980668, 21844377630643101592426006459110255155148432904632255524120741447151662349886)
    rrr = 3689513 * 6432902579 * 999652676767686311 * 815669308181510359025276279
    G = E(Gx, Gy)
    
    from tqdm import trange
    sh.sendlineafter(b'Enter an integer as the parameter p for Curve: y^2 = x^3+12x+17 (mod p) and 250<p.bit_length()', str(p).encode())
    sh.sendlineafter(b'Please Enter a random_point G:', f"{Gx} {Gy}".encode())
    for _ in trange(500):
        sh.recvuntil(b'c = ')
        c = int(sh.recvline())
        sh.recvuntil(b'P = ')
        P = E(eval(sh.recvline()))
        sh.recvuntil(b'Q = ')
        Q = E(eval(sh.recvline()))
        m = part1(P, Q, c)
        out1.append(int((rrr*Q).log(rrr*G)))
        sh.sendlineafter(b'Enter m:\n', m)
    return

sh = remote(*"47.93.99.173 26698".split())
proof(sh)
out1 = []
func1()

part2

第二部分开始时，会先用new_state设置随机数种子，而第三部分会同样设置这个随机数种子去生成所需数据，因此我们接下来的任务就是求出这个设置了种子后的state。

而这一部分基于一个看上去很奇怪的曲线，每一次我们需要在这个曲线上解决25bit的ECDLP问题，从而拿到足够的随机数去恢复输出state。而这个曲线点加和倍乘操作是：

def xDBLADD(P, Q, PQ, q, a, b):
    (X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
    X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
    Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
    X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))
    Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
    X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
    return (X4, Z4), (X5, Z5)

def xMUL(P, k, q, a, b):
    Q, R = (1, 0), P
    for i in reversed(range(k.bit_length() + 1)):
        if k >> i & 1:
            R, Q = Q, R
        Q, R = xDBLADD(Q, R, P, q, a, b)
        if k >> i & 1:
            R, Q = Q, R
    return Q

def shout(x, d, q, a, b):
    P = (x,1)
    Q = xMUL(P, d, q, a, b)
    return Q[0] * pow(Q[1], -1, q) % q

这个部分看了让人害怕，但实际上测试下会发下，这实际上就是很普通的椭圆曲线而已：

$E :\quad y^2 = x^3 + ax + b \quad(mod\;q)$

而shout的操作实际上就是对横坐标为x的点乘d倍，并返回这个倍点横坐标而已，所以这个ECDLP部分实际是很简单的。

再细看一下会发现他似乎根本没检查请求次数是不是真的小于1500，所以不用ECDLP会显著加快速度，直接要足够的数据之后（比如1300组），再往后预测直到超过0.262的成功率就可以了。

所以这一部分实际上是一个已知多个连续的getrandbits(25)，怎么向后预测随机数，并推理初始state的问题。这个实际上可以用建矩阵的方法来解，但是正好试用一下maple的新板子，发现速度会快上很多：

maple3142/gf2bv: Solving linear systems over GF(2) by manipulating bitvectors (github.com)

exp：

#sh.recvuntil(b': =====')
#print(sh.recvline())
#print(sh.recvline())
#print(sh.recvline())

####################################################################################################### part2 MT 25
import random
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
from tqdm import *

def mt19937(bs, out):
    lin = LinearSystem([32] * 624)
    mt = lin.gens()

    rng = MT19937(mt)
    zeros = [rng.getrandbits(bs) ^^ int(o) for o in out] + [mt[0] ^^ int(0x80000000)]
    sol = lin.solve_one(zeros)

    rng = MT19937(sol)
    pyrand = rng.to_python_random()
    return pyrand

################################################################################## test
if(0):
    nums = 1300
    random.seed(int(3142))
    out = [random.getrandbits(25) for i in range(nums)]
    RNG = mt19937(25, out)
    STATE = RNG.getstate()[1][:-1]
    temp = [RNG.getrandbits(25) for i in range(nums)] #iter
    
    for i in range(1000):
        assert RNG.getrandbits(25) == random.getrandbits(25)

################################################################################## use
if(1):
    sh.recvuntil(b"Enter a number that does not exceed 1500")
    nums = 1300
    sh.sendline(b"2000")
    print(sh.recvline())

    out2 = []
    for i in trange(nums):
        sh.sendline(b"1")
        sh.recvuntil(b"Wrong number!!!,Here is your right number ")
        out2.append(int(sh.recvline().strip().decode()))
    RNG = mt19937(25, out2)
    temp = [RNG.getrandbits(25) for i in range(nums)] #iter
    for i in trange(2000-nums):
        sh.sendline(str(RNG.getrandbits(25)).encode())
        sh.recvuntil(b'GGood!')

    RNG1 = mt19937(25, out2)

part3

有了state和state1之后，这一部分就是纯粹把预测的随机数回传给靶机。

exp：

from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from mt19937predictor import MT19937Predictor

flag = b'qwb{kLeMjJw_HBPtoHsVhnnxZdvtGjomivNDUI_vMRhZHrfKlCZ6HlGAeXRV_gQ8i117nGhzEMr0Zk_YTl1wftSskpX4JLnryE9Mhl96cPTWorGCl_R6nD33bcx1AYflag_leak}'

iv_num = 0
for i in range(2000):
    iv_num += RNG1.getrandbits(32)


predictor1 = MT19937Predictor()
for i in range(500):
    predictor1.setrandbits(out1[i], 32)
for i in range(124):
    predictor1.setrandbits(0, 32)
for i in range(136-124):
    predictor1.getrandbits(32)

key = 0
for i in range(50):
    key += predictor1.getrandbits(32)

print(key)
print(iv_num)
sh.sendline(str(key).encode())
sh.sendline(str(iv_num).encode())

print(sh.recvline())
print(sh.recvline())
print(sh.recvline())


#qwb{hdasdh_sdah_sdadhd_vnvm_2323rerwegfds}