breakMe and magic_ecc

2022-11-15

研究生国赛，听说两个题都是N1的密码师傅出的，就做了做，感谢等风师傅和coin哥哥的帮助。

breakMe

题目：

import os
from random import randint
from Crypto.Util.number import *
from secret import flag

flag = flag + os.urandom(63-len(flag))
assert len(flag) == 63
m = bytes_to_long(flag) 

def leak():
    p = getPrime(256)
    q = getPrime(256)
    n = p * q
    Zn = Zmod(n)
    r = randint(2, n-1)
    enc = Zn(m)^4 + 3*Zn(m)^2 + r*Zn(m)
    return (n, r, enc)

out = []
for i in range(4):
    out.append(leak())

print(out)

"""
out = [(10104838556837572425858698219763292763650577822827673166610165534445905790599515983298170585537299796651687586519310335005278459900442296258190069157011689, 7564828531806668305145314143078783846371361009728098013923139274278986668460078185780789906860320972246757193033127803017086784149355945294908935420078516, 4485282300120902750491340174759104149475684698869265622396467866957919693682690175170986883471126578030682174788280328493147605703476577928850956031397969), (9565548877530896106016727232483590558935243658719980153279803247495028412133813638614011877483865630231054031084370990573419237535803428480492680139453999, 6038408119341558448569646184012774768725225345959109849115178440273061081156678389998969575922258723126076562743356339971035685064411166619777569139016508, 8750745342976938305411200510628417969404035221738007736422965823102502205577159397824830272988223657169242542971101468532748569435454625452166610190128781), (7032132827543709857775159929155596851822367214393091928329402747976746664890617830698759196796244901655353689522245761374585849734855765538189679713755499, 537414417641982152632158507627084083552317654751808484984901390258392606135955264531766980767789787016920198980507584546004466948509548457976277102756022, 6922262573315623933995838201220725774224132378664014973566219095767042719198956812716498145319448424126056354168025846702083830628832406132772890238012895), (10867950060245850877527719152309028431430000864654153258281294463898174216443333061889067616907305797497470525064325706490087786413068565388484751510567929, 2817477928396391253997165521234258370798748353920680581012362899514855249356663733557730846938679462940826446464369055820695102402810943359431061366297287, 6437402158704542412615350656111816825238327397134975867813883010385929819022183388539677074062781989152267579279340992202100004308737301019250714974969949)]
"""

4个n乘起来是2046比特，而维数是4，flag比特位数为$63\cdot8=504$，那么$2046\cdot(1/4-0.02)=471$，可以看出这个卡界很恶心，crt增大n也不够。于是想到flag头flag{有5个字节是已知的，那么这里可以把它拿掉，那么X大小变为$504-40=464$。这样就能出了，要把epsilon控为0.02。但是如果把X直接设为464，epsilon设为0.03也可以，dbt说是sage的epsilon和copper界的epsilon有点差异，咱也不太明白，就大概划个约等于符号吧。

exp：

out = [(10104838556837572425858698219763292763650577822827673166610165534445905790599515983298170585537299796651687586519310335005278459900442296258190069157011689, 7564828531806668305145314143078783846371361009728098013923139274278986668460078185780789906860320972246757193033127803017086784149355945294908935420078516, 4485282300120902750491340174759104149475684698869265622396467866957919693682690175170986883471126578030682174788280328493147605703476577928850956031397969), (9565548877530896106016727232483590558935243658719980153279803247495028412133813638614011877483865630231054031084370990573419237535803428480492680139453999, 6038408119341558448569646184012774768725225345959109849115178440273061081156678389998969575922258723126076562743356339971035685064411166619777569139016508, 8750745342976938305411200510628417969404035221738007736422965823102502205577159397824830272988223657169242542971101468532748569435454625452166610190128781), (7032132827543709857775159929155596851822367214393091928329402747976746664890617830698759196796244901655353689522245761374585849734855765538189679713755499, 537414417641982152632158507627084083552317654751808484984901390258392606135955264531766980767789787016920198980507584546004466948509548457976277102756022, 6922262573315623933995838201220725774224132378664014973566219095767042719198956812716498145319448424126056354168025846702083830628832406132772890238012895), (10867950060245850877527719152309028431430000864654153258281294463898174216443333061889067616907305797497470525064325706490087786413068565388484751510567929, 2817477928396391253997165521234258370798748353920680581012362899514855249356663733557730846938679462940826446464369055820695102402810943359431061366297287, 6437402158704542412615350656111816825238327397134975867813883010385929819022183388539677074062781989152267579279340992202100004308737301019250714974969949)]
from Crypto.Util.number import *

print(long_to_bytes(9188843383765595152732717869563960735854186901243181659845493688642386675610699689062518689951817902641510893611339868537231465535961032531))
def Function(n,r,c):
    P.<m> = PolynomialRing(Zmod(n))
    k = bytes_to_long(b'flag{') * 2^(58 * 8) + m
    f = k^4 + 3*k^2 + r*k - c
    return f
fs = []
ns = []
for i in out:
    ns.append(i[0])
    print(i[0].nbits())
    ff = Function(i[0],i[1],i[2]).monic().change_ring(ZZ)
    fs.append(ff)
F = crt(fs,ns)
#print(F)
N = prod(ns)
print(N.nbits())
FF = F.change_ring(Zmod(N))
roots = FF.small_roots(X=2^464,epsilon = 0.03)
print(roots)
#print(long_to_bytes(int(roots[0])))

magic_ecc

也是在基本的crt上改了一下，就是需要去爆破一下x的偏移量，这个调参也不太好高，等风师傅说是这种一般先本地出一个调通了再去做题；然后一般在界里面的调beta就行，卡的很紧的再去调epsilon。关于copper的调参问题等我再细读论文出一个专栏学习吧。

题目：

from Crypto.Util.number import *
import random, os
from secret import flag

x = bytes_to_long(flag + os.urandom(128 - len(flag)))

for i in range(4):
    p = getPrime(512)
    q = getPrime(512)
    n = p*q
    a = random.randint(0,n-1)
    b = random.randint(0,n-1)
    Ep = EllipticCurve(GF(p),[a,b])
    Eq = EllipticCurve(GF(q),[a,b])
    while True:
        try:
            Gp = Ep.lift_x(x)
            Gq = Eq.lift_x(x)
            y = crt([int(Gp[1]),int(Gq[1])],[p,q])
            break
        except:
            x += 1
    print(n,a,b,y)

exp：

from Crypto.Util.number import *

lines = open("magic.txt","r").readlines()
fs = []
ns = []

def Function(para,i):
    P.<x> = PolynomialRing(Zmod(para[0]))
    f = para[3]^2 - (x+i)^3 -para[1]*(x+i) - para[2]
    return f

paras = []
for line in lines:
    n,a,b,y = [ZZ(i) for i in line.strip().split(" ")]
    paras.append((n,a,b,y))
    ns.append(n)
    
N = prod(ns)
print('brute force')
for i1 in range(2^6):
    for i2 in range(2^6):
        for i3 in range(2^6):
            for i4 in range(2^6):
                try:
                    f1 = Function(paras[0],i1).monic().change_ring(ZZ)
                    f2 = Function(paras[1],i2).monic().change_ring(ZZ)
                    f3 = Function(paras[2],i3).monic().change_ring(ZZ)
                    f4 = Function(paras[3],i4).monic().change_ring(ZZ)
                    fs = [f1,f2,f3,f4]
                    F = crt(fs,ns)                
                    print('start')
                    FF = F.change_ring(Zmod(N))
                    roots = FF.small_roots(beta=0.5,epsilon=0.02)
                    #print('done')
                    #print(roots)
                    if b'flag' in long_to_bytes(roots[0]):
                        print(long_to_bytes(int(roots[0])))
                except:
                    continue