HFCTF2021Crypto Wp - writeup | De3B4t0 = Great-Station = Come on!Let us do it!

比赛的时候只做出来了一道题，剩下那道题还因为Coppersmith没有弄懂就一直没看，而且还理解错了

# Crypto 1

借鉴了 https://mlzeng.com/an-interesting-equation.html#sec-5 里的基底生成脚本和 https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4 的 Eduardo Ruiz 的脚本

先是去生成基底发现很多组数据相同但位置不同而且加了负号的东西...，然后你接着去看这个脚本，原来的脚本是有问题的，他成功一次后就 break 那就去修改，删掉错误还 print 的同时删掉 break 然后出来一次只能回显三组把最多，那就去多弄两个，使得都不会太长，然后去解题....（这 nima 不是利用工具吗... 就是我太菜了没时间弄懂原理 555

	from fractions import Fraction as Frac
	from math import gcd
	n = 100
	for x in range(-n, n + 1):
	for y in range(-n, n + 1):
	for z in range(0, n + 1):
	if gcd(x, gcd(y, z)) == 1:
	if x3 + y3 + z*3 - 5 x*2 (y + z) - 5 * y*2 (
	z + x) - 5 * z*2 (x + y) - 9 * x * y * z == 0:
	print((x, y, z))

	R<x,y,z> := RationalFunctionField(Rationals(),3);

	problem := ((x/(y+z) + y/(x+z) + z/(x+y)) - 6) ;
	Evaluate(problem,[-7,-8,5]);
	problem*Denominator(problem);
	P2<x,y,z> := ProjectiveSpace(Rationals(),2);
	C := Curve(P2,x^3+y^3+z^3-5x^2(y+z)-5y^2(x+z)-5z^2(x+y)-9xy*z);
	Pt := C![-7,-8,5];

	E,f := EllipticCurve(C);
	g := f^-1;
	for n:= 1 to 100 do
	nPt_inE:=n*f(Pt);
	nPt_inC:=g(nPt_inE);
	X := Numerator(nPt_inC[1]);
	Y := Numerator(nPt_inC[2]);
	Z := Denominator(nPt_inC[1]);
	if ((X gt 0) and (Y gt 0)) then
	printf("GOT IT!!! x=apple, y=banana, z=pineapple, check the above solution\n");
	printf "X=%o\nY=%o\nZ=%o\n",Y,Z;
	else
	end if;
	end for;
	// We check the solution fits in the original problem
	if Evaluate(problem, [X,Y,Z]) eq 0 then
	printf "I evaluated the point to the original problem and yes, it worked!\n";
	else
	printf "Mmm this cannot happen!\n";
	end if;

# Crypto 2 simultaneous

分析题目中 $x,y_1,y_2,y_3$ 都大概为 381 位， $n_1,n_2,n_3,e_1,e_2,e_3$ 为大概 1024 位， $p,q$ 为大概 512 位对于题目分析我们可以得到 $e_ix-n_1y=-z\_+y(p+q)$

一共三条式子，我们可以去构造格子，假设 x 的系数是 $2^k$ 先构造格子 L

$L=\left[\begin{matrix}2^k&e_1&e_2&e_2\\\\ 0&-n_1&0&0\\\\ 0&0&-n_2&0\\\\ 0&0&0&-n_3 \end{matrix}\right]$

根据 $||SVP||≤\sqrt{n}\det(L)^{\frac{1}{n}}$ , 我们可以分析得到 k 应该是 512 左右那就带入格基规约得到的目标向量为 $V=(2^{512}x,-z\_+y(p_1+q_1),-z\_+y(p_2+q_2),-z\_+y(p_3+q_3))$ 于是就得到了 x 的值那么就可以得到减出来的数 $k_i=e_ix-n_iy_i$ 接下来分析这个余数， $k_i=(p+q+1)·y+\frac{(p-q)n^{\frac{1}{4}}y}{3(p+q)}+((p+1)(q+1)y-\frac{(p-q)n^{\frac{1}{4}}y}{3(p+q)})\%x$ 我们发现第二项的如果整除值和实际值没啥差距，第三项是个非负数。所以得到了 $k-(p+q+1+\frac{(p-q)n^\frac{1}{4}}{3(p+q)})y$ 的绝对值不会超过 x ，于是可以都整除 y 之后发现直接就是 0 了

令 $K=k//y$ ，于是我们可以认为 $K=p+q+1+\frac{(p-q)n^{\frac{1}{4}}}{3(p+q)}$ 而我们已知 $round(n^\frac{1}{4})$ ，未知量仅仅是 $p-q$ 和 $p+q$ ，那么我们可以变换后去得到 $p-q=3(K-1-(p+q))(p+q)//(n^\frac{1}{4})$ , 我们假设 $p+q=s$ , 那么我们可以得知 $(p+q)^2-(p-q)^2=4n$ , 于是我们划出来 $s^2-9(K-1-s)^2s^2//round(n^{0.25})^2=4n$ 于是我们就变成了求解 $s^2$

我们观察这条式子，发现一件事情，这条式子中左边他是单调递增的，那就我们可以使用二分法去求解他的近似整数解，根据奇偶性可以得到 s 的值（s 必然是偶数），因此就能够得到了 d。

	from Crypto.Util.number import*
	from gmpy2 import*
	'''
	M = Matrix(ZZ,[[2**512,e[0],e[1],e[2]],[0,-n[0],0,0],[0,0,-n[1],0],[0,0,0,-n[2]]])
	GV = M.LLL()[0]
	x = GV[0]>>512
	y.append((e[0]*x-GV[1])//n[0])
	y.append((e[1]*x-GV[2])//n[1])
	y.append((e[2]*x-GV[3])//n[2])
	'''
	#我们可以发现这里他的长度大概是 x 的长度，因此去求他的余数

	n = []
	e = []
	c = []
	y = []
	n.append(90491363059261404858550634231628058963249510634056675949243050070342967726901705474014306927602327030350384724177110635460575819174999690119596483244243479600712538918767265671875210900320134535674577409813015049083534046496520463201426519076941111176300156840093523729587718662300148396809204630544859119149)
	e.append(168885479631267618895786982845222604163453078896291533672682347591744598107689212526033974774513653433252346257997820414442658988591213688157626171903932299809982342730274878146639873845642550557892032102862465267830686337683681811035549767605127670639313526152274657121913611059493817170297018143021110779877)
	n.append(95095659207029012582441281486144446868010823436167102942651286702532916783769809925573460637458450988006229579100306132641666284428903268946094064959939187731480872200371279589619799501099719647308276024427981251602812835714397316315251516049360167072367461142715945513735666944539297649274039644651643860709)
	e.append(803083831363140689387491043859995397264097623843277450416122235772461812328647926123252685647971839611777215549762999753046866799101827482369517811418620191075968232200493026341022069951100818193450315629944185492666858982140493791542156525823304188919134830223972206436313384674434426205057120372785617239573)
	n.append(79783914666941430193016422767234758486269300813425360037124961732818657481292239838325070399038041076030925132009832656732232485316489140378503241203611852385887657171830207427052240486122880429096750734201402521125250313116205524437146696335787282704143922449422332849550092832299254353363532151938268614467)
	e.append(684492483256695788393129421198297524550481983825005067209597057774764109623746650728270481031194051696472334243263072636994984124025741021144411447925322543452713770032130935145684958475930669835466496158115635503193348699515511486332577820479935984969535141042375968326457182345240372145420230964104483785721)
	c.append((0, 90491363059261404858550634231628058963249510634056675949243050070342967726901705474014306927602327030350384724177110635460575819174999690119596483244243469196198986120292668239952402666838171832151959642809949669793954518190032439693973116745657766490465383207136884797416616202864323502381586901806453928514))
	c.append((0, 95095659207029012582441281486144446868010823436167102942651286702532916783769809925573460637458450988006229579100306132641666284428903268946094064959939176080644834649736585931140833237424823927852722577715067469685760622261935834373569238657224079294882287377105449565799679890984772111495083088228691564783))
	c.append((73041862154157371674229064670550888409216140053451529283374004436651536110734376938918521442316738516203639268463111472485680083502732108867931825491194808519825096059573881206695909907258008432595237281363578731293669489033897367074393143363419088244861083645807156213390581687771017186306856077620367500647, 77837817707573379707151623790394892748771598114914937592003582442426802996364758601494359727747880510291001949424184772858956540706002999451105625873493875954677023151702166989487010859391554750093501077015364319622792488092868684171640035107565651570183298377905027193006475189322440398876152882180702841119))
	y=[1234160442019081205971633839080171591517296670682179517951651316669120445932747593240541724314677115317356928552223,5584530014107972751790443286838215319435330117138078723753388886031684850098305720586321389113525873796692845334453,5673352682784161640574325568051734030879350274946435727408336124736359465461431142246637344016863104357076555679503]
	x = 661281602633708663826486920028427898009447098405701242291443669957936453059596989424786500921975783032016279781143
	k = []
	for i in range(3):
	k.append(e[i]x-n[i]y[i])
	K = []
	for i in range(3):
	K.append(k[i]//y[i])
	'''
	def factor(K,N):
	l = 0
	r = K
	for i in range(518):
	s = (l+r)//2
	v = ss - (9ss(K-1-s)(K-1-s)//(round(N0.25)round(N**0.25)))
	if v < 4*N:
	l = s
	else :
	r = s
	return r
	S = []
	for i in range(3):
	S.append(factor(K[i],n[i]))'''
	S=[19094603811148743548404150847713419121365563250591127608146415278074868880338697379102160497997619208075125156916806494003926028149361835606603268896884014,19511198066679441661645179970610060853694402093688175864187492448475141832783517018527146512367573855149291232173039125664151037907250865382648639649226905,18459018640955512832829048105711364903415072505002892754520813962752576865824290315357137127800833228562342513337961044655924159981814783588968959511015508]
	d = []
	for i in range(3):
	d.append(inverse(e[i],n[i]+1+S[i]))
	print(d)
	print(long_to_bytes(56006392793427934292814302486125208538927193266728400911397747017719430264839671385701729956903006333))

WriteUp

# Crypto 1

# Crypto 2 simultaneous

HMGCTF2021 babyForgery

Mini-L CTF 2021 WriteUp