第五届美团CTF初赛&决赛Crypto wp

被师傅们带进决赛了，tql呜呜呜。

[初赛]strange_rsa1

题目源码：

from Crypto.Util.number import *
from sage.all import RealField
from secret import flag1

Bits = 512
p = getPrime(Bits)
q = getPrime(Bits)
n = p * q

gift = RealField(prec=Bits*2)(p) / RealField(prec=Bits*2)(q)
e = 0x10001
m = bytes_to_long(flag1)
c = pow(m, e, n)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')

直接在给定的实数域上求根，然后转整数得到 q，解 RSA 即可。

解题脚本：

from Crypto.Util.number import *

e = 0x10001
n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
c = 23970397560482326418544500895982564794681055333385186829686707802322923345863102521635786012870368948010933275558746273559080917607938457905967618777124428711098087525967347923209347190956512520350806766416108324895660243364661936801627882577951784569589707943966009295758316967368650512558923594173887431924
gift = 0.9878713210057139023298389025767652308503013961919282440169053652488565206963320721234736480911437918373201299590078678742136736290349578719187645145615363088975706222696090029443619975380433122746296316430693294386663490221891787292112964989501856435389725149610724585156154688515007983846599924478524442938

F=RealField(prec=512*2)
R.<x>=PolynomialRing(F)
f=x*x*gift-n
r=f.roots()[0][0]
q=int(abs(r))
p=n//q
d=inverse(e,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))
#b'flag{a5537b232c1ab750e0db61ec352504a301b7b212}'

[初赛]strange_rsa2

题目源码：

from Crypto.Util.number import *
from secret import flag1, flag2


def generate_poly(modulus, num, root):
    poly = []
    res = 0
    for i in range(1, num+1):
        poly.append(getRandomRange(1, modulus-1))
        res = (res + poly[-1] * pow(root, i, modulus)) % modulus
    return [modulus-res] + poly


Bits = 512
p = getPrime(Bits)
q = getPrime(Bits)
n = p * q

a = getRandomRange(1, p-1)
k = bytes_to_long(flag1)
gift = [generate_poly(p, Bits, a), generate_poly(p, Bits, k * a)]

e = 0x10001
m = bytes_to_long(flag2)
c = pow(m, e, n)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')

注意这题用到了上题的 flag（本题的坑点）。

给出了两个随机多项式，我的想法是构造二元多项式，用 grobner 基求出 a。由于模数 p 未知，先用 n 替代。然而解完惊奇地发现顺带把 p 直接规约出来了，属于是意外收获了。后面解RSA 就 OK 了。

解题脚本：

from Crypto.Util.number import *

def my_poly(coe,x):
	res=0
	for i in range(1,513):
		res+=coe[i-1]*(x^i)
	return res

e = 0x10001
flag1 = b'flag{a5537b232c1ab750e0db61ec352504a301b7b212}'
k = bytes_to_long(flag1)
exec(open('output.txt','r').read())
R.<a,t>=PolynomialRing(Zmod(n))
s1=gift[0][0]
coe1=gift[0][1:]
s2=gift[1][0]
coe2=gift[1][1:]
f1=my_poly(coe1,a)+s1
f2=my_poly(coe2,t)+s2

res=Ideal([f1,f2,t-k*a]).groebner_basis()
print(res)
res=[ x.constant_coefficient() for x in res]
a,t,p=list(map(int,res))
print(a,t,p)
q=n//p
d=inverse(e,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(int(m)))
#b'flag{e6d7511d75bd537e1bd0cd08abea415f5f27d6cf}'

[决赛]strange_lwe

题目源码：

from Crypto.Util.number import *
from hashlib import sha1
from secret import my_secret_bits, flag
from sage.all import *
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler


def matrix_to_list(M):
    count = M.nrows()
    dimension = M.ncols()
    Matrix_list = M.list()
    M = []
    for i in range(count):
        M.append(Matrix_list[i * dimension:(i+1) * dimension])
    if len(M) == 1:
        return M[0]
    return M


q = 401
m = 64
n = 16
a = 0.025
A = random_matrix(GF(q), m, n)
t = DiscreteGaussianDistributionIntegerSampler(a*q)
s = random_matrix(GF(q), n, 1)

num = 48
assert flag == 'flag{' + sha1(str(my_secret_bits).encode()).hexdigest() + '}'
cipher = []
for j in range(num):
    if my_secret_bits[j] == 0:
        cipher.append([random_vector(GF(q), m).list() for _ in range(num*8)])
    else:
        cipher.append([(A * s + Matrix([t() for _ in range(m)]).transpose()).list() for _ in range(num*8)])

A = matrix_to_list(A)
data = str([[int(A[i][j]//8) for j in range(len(A[0]))] for i in range(len(A))]) + '\n'
data += str(cipher)
open('data.txt', 'w').write(data)

LWE问题，形如，其中给定矩阵A和向量b，e是一个很小的误差向量，目标是求出s向量。该问题可以转化为格密码中的CVP求解问题，即求出格中的一个向量，使其距离目标向量b最近。通常可以使用babai's nearest plane algorithm算法求解。

直接输出误差向量来判断会发现很多bits对不上，搞了半天不太懂什么原因。但还好能算出s向量，因此绕了个弯通过s再来反求误差。

from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.modules.free_module_integer import IntegerLattice
import numpy as np
from Crypto.Util.number import *
from hashlib import sha1

# Babai's Nearest Plane algorithm
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(5):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -=  M[i] * c
    return target - small

q = 401
m = 64
n = 16
a = 0.025
num = 48
data=open('data.txt','r').readlines()
A=Matrix(ZZ,eval(data[0].strip()))
cipher=eval(data[1].strip())
print(len(cipher))

'''
#find the same s vector that output bit '1'
res=''
for k in range(num):
	rt=cipher[k][0]
	Lattice = matrix(ZZ, m + n, m)
	for i in range(m):
		for j in range(n):
			Lattice[m + j, i] = A[i][j]
		Lattice[i, i] = q

	lattice = IntegerLattice(Lattice, lll_reduce=True)
	print("LLL done")
	gram = lattice.reduced_basis.gram_schmidt()[0]
	target = vector(ZZ,rt)
	cv = Babai_closest_vector(lattice.reduced_basis, gram, target)
	#print("Closest Vector: {}".format(cv))
	error=cv-target
	print("Error: {}".format(error))
	if any([abs(e)>40 for e in error]):
		res+='0'
	else:
		res+='1'
	print(res)
	A = matrix(Zmod(q), A)
	try:
		s = A.solve_right(cv)
		print('s: {}'.format(s))
	except:
		print("no solution")
		continue
print(res)
'''
s=(195, 202, 322, 287, 230, 311, 396, 58, 242, 191, 117, 41, 248, 264, 139, 291)
s=vector(GF(q),s)
A=Matrix(GF(q),A)
print(A*s)
res=''
for k in range(num):
	tmp=[]
	for l in range(num*8):
		c=vector(ZZ,cipher[k][l])
		As=vector(GF(q),A*s)
		t=c-As
		t=[tt if tt<(q//2) else q-tt for tt in t]
		tmp.extend(t)
	if all([ tt<40 for tt in t]):
		res+='1'
	else:
		res+='0'
print(res)
#res='000000110110001010100111101100001101011110011110'
my_secret_bits=list(map(int,res))
flag = 'flag{' + sha1(str(my_secret_bits).encode()).hexdigest() + '}'
print(flag)
#flag{7e0fefd15c630d4b41db2ac9e18d48d691b3d419}