2024-网鼎杯半决赛-crypto

赛后复现

RSA

题目：

# sagemath
import random
from Crypto.Util.number import *

flag = b''

k = 3
d = k/(2*(k+1))
ns = []
pqs = []
es = []

for i in range(3):
    p = getPrime(512)
    q = getPrime(512)
    if p < q:
        tmp = p
        p = q
        q = tmp
    n = p*q
    ns.append(n)
    pqs.append((p,q))

n = min(ns)
x = random.randint(0,int(n^(d/2)))
x = next_prime(x)

for i in range(3):
    p,q = pqs[i][0],pqs[i][1]
    bound1 = int((p-q)/(3*(p+q)) * x * n ^ 0.25)
    bound2 = int((p-q)/(3*(p+q)) * x^2 * n ^ 0.25)
    z = random.randint(bound1,bound2)
    f = (p-1)*(q-1)
    e = inverse(x^2,f) * z % f
    es.append(e)

e = 8462913
c = pow(bytes_to_long(flag),e,ns[0])

print(f'ns={ns}')
print(f'es={es}')
print(f'c={c}')

'''
ns=[58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]
es=[46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]
c=45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729
'''

首先我们通过

  e = inverse(x^2,f) * z % f

得到以下式子

$e_1x^2 = z_1 + k_1(phi1)$

$e_2x^2 = z_2 + k_2(ph2)$

$e_3x^2 = z_3 + k_3(phi3)$

这道题有两种方法造格
第一种：可以参考一下DexterJie's Blog
第二种：我参考的论文
根据论文造格

N = max(Ns)
k = 3
delta = 0.375
epsilon = sqrt(5) * N^(delta-1/2)
n = k
C = int(3^(n+1) * 2 ^ ((n+1)*(n-4)/4) * epsilon^(-n-1))

M = Matrix(ZZ, [[1, -int(C * es[0] / (ns[0] + 1)), -int(C * es[1] / (ns[1] + 1)), -int(C * es[2] / (ns[2] + 1))],
                [0, C, 0, 0],
                [0, 0, C, 0],
                [0, 0, 0, C]])

K = M.LLL()
need_x = K * M.inverse()
x, y1, y2, y3 = -need_x[0]
# print(x, y1, y2, y3)
ys = [y1, y2, y3]

这么写出来之后得到的x其实是$ex^2 = z + k(phi)$中的$x^2$,y是其中的k
然后再通过

算出了p的高位,测试数据后发现大概是p的低254位是未知的，直接爆破8位使用copper，最后由于e和phi不互素，选择直接开e次方
代码如下：

from Crypto.Util.number import *
import itertools
import gmpy2
from tqdm import *
x2 = 2877220048349607321239927445084818279140784565868620282931508422526367853504956884205255802759310840082258719223169
y = 2301676272809692596927119509132698644931773271928055900098255469704331118044221153572405926526946327057790408660435
Ns = [58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]

es = [46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]

cs = 45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729

S = abs(int(Ns[0] + 1 - es[0] * x2 // y))
D = isqrt(abs(S**2-4*Ns[0]))
phigh = (S+D)//2
print(len(bin(phigh)))
p_high = int(phigh) >> 256
for i in trange(2**8):
     p4 = p_high << 8
     p4 = p4 + i
     kbits = 512 - p4.bit_length()
     p4 = p4 << kbits
     R.<x> = PolynomialRing(Zmod(Ns[0]))
     f = x + p4
     x = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)
     if x:
         p = p4 + int(x[0])
         q = Ns[0] // p
         print(f"p = {p}")
         print(f"q = {q}")
         break
p = 7696200979887856341831037613988614280823562431557099321251289719686349578851157595313091133333376255237947592610103860940743200558583228583143108125315529
q = 7595466686419558151205913432118661460574378336265188601308332178368424478703273480167149453312906478797521330243646557948961908036589158891684701262055023
n = p * q
assert  n == Ns[0]
e = 8462913
k = gmpy2.gcd(e,(p-1)*(q-1))
res = Zmod(p)(c).nth_root(e, all=True)
for i in res:
    temp = long_to_bytes(int(i))
    if (b"flag" in temp):
      print(temp)
#b'flag{N3w_Attacks_4_key_equat1ons}'