比赛的时候只做出来了一道题，剩下那道题还因为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 x**3 + y**3 + 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-5*x^2*(y+z)-5*y^2*(x+z)-5*z^2*(x+y)-9*x*y*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

分析题目中 都大概为381位， 为大概1024位，为大概512位对于题目分析我们可以得到

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

根据 , 我们可以分析得到 k 应该是512左右 那就带入格基规约得到的目标向量为 于是就得到了 x 的值那么就可以得到 减出来的数 接下来分析这个余数， 我们发现第二项的如果整除值和实际值没啥差距，第三项是个非负数。所以得到了 的绝对值不会超过 x ，于是可以 都整除y 之后发现直接就是0了

令 ，于是我们可以认为 而我们已知 ，未知量仅仅是 和 ，那么我们可以变换后去得到 , 我们假设 , 那么我们可以得知 ,于是我们划出来 于是我们就变成了求解

我们观察这条式子，发现一件事情，这条式子中左边他是单调递增的，那就我们可以使用二分法去求解他的近似整数解，根据奇偶性可以得到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 = s*s - (9*s*s*(K-1-s)*(K-1-s)//(round(N**0.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))