<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>

比赛的时候只做出来了一道题,剩下那道题还因为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

分析题目中 x,y1,y2,y3x,y_1,y_2,y_3 都大概为 381 位,n1,n2,n3,e1,e2,e3n_1,n_2,n_3,e_1,e_2,e_3 为大概 1024 位,p,qp,q 为大概 512 位对于题目分析我们可以得到eixn1y=z_+y(p+q)e_ix-n_1y=-z\_+y(p+q)

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

L=[2ke1e2e20n10000n20000n3]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]

根据 SVPndet(L)1n||SVP||≤\sqrt{n}\det(L)^{\frac{1}{n}} , 我们可以分析得到 k 应该是 512 左右 那就带入格基规约得到的目标向量为 V=(2512x,z_+y(p1+q1),z_+y(p2+q2),z_+y(p3+q3))V=(2^{512}x,-z\_+y(p_1+q_1),-z\_+y(p_2+q_2),-z\_+y(p_3+q_3)) 于是就得到了 x 的值那么就可以得到 减出来的数 ki=eixniyik_i=e_ix-n_iy_i 接下来分析这个余数, ki=(p+q+1)y+(pq)n14y3(p+q)+((p+1)(q+1)y(pq)n14y3(p+q))%xk_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+(pq)n143(p+q))yk-(p+q+1+\frac{(p-q)n^\frac{1}{4}}{3(p+q)})y 的绝对值不会超过 x ,于是可以 都整除 y 之后发现直接就是 0 了

K=k//yK=k//y ,于是我们可以认为 K=p+q+1+(pq)n143(p+q)K=p+q+1+\frac{(p-q)n^{\frac{1}{4}}}{3(p+q)} 而我们已知 round(n14)round(n^\frac{1}{4}) ,未知量仅仅是 pqp-qp+qp+q ,那么我们可以变换后去得到 pq=3(K1(p+q))(p+q)//(n14)p-q=3(K-1-(p+q))(p+q)//(n^\frac{1}{4}) , 我们假设 p+q=sp+q=s , 那么我们可以得知 (p+q)2(pq)2=4n(p+q)^2-(p-q)^2=4n , 于是我们划出来 s29(K1s)2s2//round(n0.25)2=4ns^2-9(K-1-s)^2s^2//round(n^{0.25})^2=4n 于是我们就变成了求解 s2s^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 = 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))

请我喝[茶]~( ̄▽ ̄)~*

De3B4to 微信支付

微信支付

De3B4to 支付宝

支付宝