cooper+隐含数+2元cooper
发现群里一个题，应该是几天前一个比赛的。作了一下午。
from Crypto.Util.number import *
import os
from hashlib import *
from random import *
p = getPrime(512)
q = getPrime(512)
n = p*q
m = bytes_to_long(os.urandom(20))
x = pow(m,p,n)
y = pow(m,q,n)
with open('output.txt', 'w') as file:
file.write('n = ' + str(n) + '\n')
file.write('x = ' + str(x) + '\n') # x = m+kp y = m+kq
file.write('y = ' + str(y) + '\n')
iv = sha256(str(p).encode()).digest()[:16]
n = 17
q = getPrime(1024)
x = randint(q//2,q-1)
S = 2**544
K = 2**480
s = [randint(S//2,S-1) for i in range(n+1)]
t = [randint(S//2,S-1) for i in range(n+1)]
k = [randint(K//2,K-1) for i in range(n+1)]
b = [randint(K//2,K-1) for i in range(n+1)]
r = [(s[i]*k[i] - b[i]*t[i]) * inverse(x,q) % q for i in range(n+1)]
with open('output.txt', 'a') as file:
file.write(f"s = {s}\n")
file.write(f"t = {t}\n")
file.write(f"r = {r}\n")
file.write('q = ' + str(q) + '\n')
key = sha256(str(2024*b[0]+2023*k[0] + x).encode()).digest()[:16]
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from uuid import *
from flag import flag
aes = AES.new(key,AES.MODE_CBC,iv)
cipher = aes.encrypt(pad(flag.encode(),16))
with open('output.txt', 'a') as file:
file.write(f"cipher = {cipher}")
题目分3部分，第1部分给了x, x=m^p mod n 求p
这个式子转化成模p则有 x= m mod p => x = m+kp 所以第1步就是用 cooper求m得到iv
P.<v> = PolynomialRing(Zmod(n))
f = x-v
res = f.monic().small_roots(X=2^160, beta=0.499, epsilon=0.02)
m = res[0]
p = gcd(x-m,n)
#11675696190896351906539196500765316141680444580734032619300603052044661463297533718415320957466064560635233414047482845327443000187098988487753476160734723
iv = sha256(str(p).encode()).digest()[:16]
#b'\x80v\xdd\x87F{\x15\x921\x129!\xf9-\xd3\x9b'第2步给了r[i] = (s[i]*k[i]-t[i]*b[i])*x^-1 mod q 其中s,t,r,q是已知数x,k,b未知，这个式子与标准的hnp_2hole很相似转化一下得到 0 = r[i]*x + s[i]*k[i] - t[i]*b[i] mod q
对应的Beta=[0]*18, Alpha=r,Rho=[s,t] 对应的k,b的规模是[[480,480]]*18 结果试了半天出来的不大对，然后生成测试数据作，发现只有前几个数正确。说明可能规模可能小了，仔细看ehnp函数，发现delta参数默认是1/10^8是啥意思不清楚，指向一篇论文就看不懂了。不过猜就是个粒度之类的，把它调到1/10^12试了一下测试数成功。然后解出x（数不能也能解了不正确的数来，而且这题x只是个随机数也没法判断，只能用后边的s0,t0解key才知道，这里比较坑，如果x是个素数就好了解出来可以看看对不对）
#2,双值隐含数
#r*x + si*ki + ti*bi = 0 mod q
Rho = [[s[i],-t[i]] for i in range(18)]
xbar = 0
Pi = [0]
Nu = [1024] #x
Mu = [[480,480] for i in range(18)] #k,b的规模
Beta = [0]*18
Alpha = [-i for i in r]
sol = ehnp(xbar, q, Pi, Nu, Alpha, Rho, Mu, Beta, delta=1/10^12,verbose=True)
x = sol
#62630910220966472045159148570603595043775972841964521368726922111769596530618108951116184620060671080472122175609477748445264320873556413198173335784639672637398271928839444735059985662973808598735155594200861656906081025647421950580468995090600624842415232284779649351298179580388119427972698247798862505412第3步还是上边那个式子。 f = r0*x+s0*k0-t0*b0 mod q 两个未知数k0,b0用二元cooper
s0,t0,r0 = s[0],t[0],ZZ(r[0]*x%q)
P.<k,b> = PolynomialRing(Zmod(q))
f = k*s0 - b*t0 - r0
k,b=small_roots(f,bounds=(2^480,2^480))[0]
#(2388717748081872654267007777796026827223725574875279634585519193723629483406071381412054772532848739496578082558657978304684124455356276915197267, 2268138536252103308931576938654214291075320009135327629529040117599409415980617650634082218105186688883459074797741629941873869662268650606639168)这一步的结果也没法验证毕竟这东西都是随机数。只能到最后解看结果了。
key = sha256(str(2024*b+2023*k + x).encode()).digest()[:16]
aes = AES.new(key,AES.MODE_CBC,iv)
aes.decrypt(cipher)