比赛的时候只做出来了一道题,剩下那道题还因为Coppersmith没有弄懂就一直没看,而且还理解错了
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
# 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)) |