我的copper之路~持续更新中~

发表于 更新于 分类于 阅读次数： Disqus： 本文字数： 14k 阅读时长 ≈ 25 分钟
我的copper之路~持续更新中~

[CISCN 2021华南]small

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import random, hashlib
from Crypto.Util.number import getPrime
from secret import x, y, flag

BITS = 70

assert(2**BITS < x < 2**(BITS+1))
assert(2**BITS < y < 2**(BITS+1))

m = str(x) + str(y)
h = hashlib.sha256()
h.update(m.encode())
assert(flag == "flag{" + h.hexdigest() + "}")


p = getPrime(512)
a = getPrime(510)
b = getPrime(510)
c = (1 + a * x * y ** 2 + b * x ** 2 * y) % p
print("p = " + str(p))
print("a = " + str(a))
print("b = " + str(b))
print("c = " + str(c))

'''
p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881
'''

格解：

有式子

令 然后就有

两边同时乘以a在模p下的逆元就有

整理得到 可以构造格

img

至于这里为什么是而不是1，我觉得是因为,的bit数都是70所以而且测试发现我构造的格是1，但是最后求规约出来的向量第一个元素是一个211位的数，也是涉及到了格的配平

可以参考格攻击之小未知数方程求解入门——原理与例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#!/usr/bin/env python
import hashlib
import gmpy2
from Crypto.Util.number import *

p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881
c = c-1
inv=inverse(a,p)
c=(inv*c)%p
b=((-b)*inv)%p


M = Matrix(ZZ,3,3)
M[0] = [2**210,0,c]
M[1] = [0,1,b]
M[2] = [0,0,-p]
ML=M.LLL()
print(ML[0])
a=int(ML[0][0])
print(a)
xy2=-int(ML[0][2])
x2y=-int(ML[0][1])
xy=gmpy2.gcd(x2y,xy2)
print(xy)
y=xy2//xy
x=x2y//xy

m = str(x) + str(y)
h = hashlib.sha256()
h.update(m.encode())
flag = "flag{" + h.hexdigest() + "}"
print(flag)
#flag{e94e1ea0b945c6573b64ae79f0ebf33d5a585398c183a6752c74c3826bceb74c}

二元copper解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#sage
import hashlib
import itertools
p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []
R.<x,y>=Zmod(p)[]
f=(1 + a * x * y ** 2 + b * x ** 2 * y)-c
x,y=small_roots(f,bounds=(2^70,2^71))[0]
m = str(x) + str(y)
h = hashlib.sha256()
h.update(m.encode())
flag = "NSSCTF{" + h.hexdigest() + "}"
print(flag)
#NSSCTF{e94e1ea0b945c6573b64ae79f0ebf33d5a585398c183a6752c74c3826bceb74c}

[tangcuxiaojkuai]easy_copper1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import *
from random import *
from secret import flag

assert flag.startswith(b"NSSCTF{") and flag.endswith(b"}")
assert len(flag) == 37

def gen_data(p,length):
    coeff = [randint(-2**32,2**32) for i in range(length-1)] + [randint(1,2**32)]
    return sum([coeff[i]*p**i for i in range(length)])

b = getPrime(1400)
a = gen_data(b,6)
p = getPrime(256*5)
q = getPrime(256)
n = p*q
m = bytes_to_long(flag[7:-1])

print("a =",a)
print("b =",b)
print("n =",n)
print("c =",a % (b-m) % p)

'''
a = 5549997533567190765451060003378594328208085965171057613046272782399320385801262427125465925310587069826816190505343998268891453664853919954972318043604177749860432778530185933735996050024160286370510179686746394158379258246587487978911503057556662561587215910791569507689015766531668277131113986057590781396398336299292315557904756600303993655014781202374308079885517355500419820878630803963625154724593589268277135757575099029314373537333985928427361897778453968429622806601778705482232467565493789524705788745221275426482603133790789320192127238641529684801868328091692081269798378555677980295282241736002111769899269365161305274768242912746034221266737507823710607682307448305506469386320122162063129111963956813928790055972563594890074229166442357508298255754150913934863439503751818506701092029312330070104636530223422238884679342877228773018649571938389437053258838947075103547766682006907290041060099030401078504154580918834901230411520541473984503892569919351799880236285333890681120340758177935223362561618860440679402085624994947954310720781671847323988290985994849577007330168617301104973145130975458942852068773890456852008660678772797081769299221752824132395057925957966236190693386264986627705062247274388532481890731361579962994281795847973719352965725024336536011747744286094626784548450945808977185031072003163884715639335582500821735372264778337277968982744615544014751382104123657815885683865159874330848264901320900587726777026680111663529893241507534145907710815328515080873983547987954554660585289621642017226020909406358582195295944513518489513783744170261194300084082634297086645338918551616443632828664857206551814971287007726341429714596407033649324399745531577851802389713905682407743356548494218886990858323750912334486066574949941863337284447418868362349705104596997062541665923824132293441261853623963153677146052741893849156220411360012198280306111549261407941431691085949136294791896025980996617245031309439043593114299292206028201810212469726512376109348231607843056259556121448353511032010729667364764526544162088652166231118576736952880650975321889920727908566750809108688218503956
b = 19088700216864219992000481909154962955010217153589993304722719340884054355376558326105036947257582728860147557431276912919643940358478125733042829478349114754313750607492935206321298801011776939307313478546331523512938761672813983870399597182080005906066953602228332948790458576153448761425614070248334986663583719133564252378947422392557755444674008030141846366476287826338519233008704965899055639264609925259823048079319
n = 1698281899194715114165111012319277103359733674717346894156321734086384210027912893592223341535254583183189375047805019470712423207121454213625786296403115965465797639874678119529865412063714723513964182015925137173277042639307327631371055326412204990172328114832185024332076266014268385262996787504249248741895102659976146333218908476195041388126877183421158327681480273218635257896126985050902620483850502219753728842322424353423665711001628722961510508066740039
c = 53146904354859601599585110457067111012858829248246133531123405294986679458995718625053726629192021849150034273282207940006128865030953003797480171720673649060942787124637476440400908506795533118278613492356804275358218541297790334587524059713360959881377651255593428483947657195937373058321156413003347566693680573881827047037751088091600420762361729539354
'''

观察有关密文的加密方式

1
print("c =",a % (b-m) % p)

分析gen_data函数

1
2
3
4
def gen_data(p,length):
    coeff = [randint(-2**32,2**32) for i in range(length-1)] + [randint(1,2**32)]
    return sum([coeff[i]*p**i for i in range(length)])
a = gen_data(b,6)

我们可以知道a是关于b的多项式

可以表示成

我们可以知道a的多项式系数是非常小的，怎么利用这个特点

我们对a进行多次这样的操作，

1
2
t=a%b
a=a//b

尝试找到这些系数，并保存它，我们将这个过程用式子表示出来， 并将m转换到其中

我们可以知道s0和t0是可以求的，它们实际上是关于a的多项式的一个带余除法得到的商和余数，我们也可以知道t0是一个(-232,232)bit内的数，继续模，我们又可以得到式子

反复操作，得到的就是a对应b的多项式，只不过它是由m组成的：

由于k5为1-2^32位之间的数，flag去掉前后缀，还剩下29字节，所以f(m)的最大值一定小于b-m(约为1400bit),所以模b-m就可以去掉了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from Crypto.Util.number import*
a = 5549997533567190765451060003378594328208085965171057613046272782399320385801262427125465925310587069826816190505343998268891453664853919954972318043604177749860432778530185933735996050024160286370510179686746394158379258246587487978911503057556662561587215910791569507689015766531668277131113986057590781396398336299292315557904756600303993655014781202374308079885517355500419820878630803963625154724593589268277135757575099029314373537333985928427361897778453968429622806601778705482232467565493789524705788745221275426482603133790789320192127238641529684801868328091692081269798378555677980295282241736002111769899269365161305274768242912746034221266737507823710607682307448305506469386320122162063129111963956813928790055972563594890074229166442357508298255754150913934863439503751818506701092029312330070104636530223422238884679342877228773018649571938389437053258838947075103547766682006907290041060099030401078504154580918834901230411520541473984503892569919351799880236285333890681120340758177935223362561618860440679402085624994947954310720781671847323988290985994849577007330168617301104973145130975458942852068773890456852008660678772797081769299221752824132395057925957966236190693386264986627705062247274388532481890731361579962994281795847973719352965725024336536011747744286094626784548450945808977185031072003163884715639335582500821735372264778337277968982744615544014751382104123657815885683865159874330848264901320900587726777026680111663529893241507534145907710815328515080873983547987954554660585289621642017226020909406358582195295944513518489513783744170261194300084082634297086645338918551616443632828664857206551814971287007726341429714596407033649324399745531577851802389713905682407743356548494218886990858323750912334486066574949941863337284447418868362349705104596997062541665923824132293441261853623963153677146052741893849156220411360012198280306111549261407941431691085949136294791896025980996617245031309439043593114299292206028201810212469726512376109348231607843056259556121448353511032010729667364764526544162088652166231118576736952880650975321889920727908566750809108688218503956
b = 19088700216864219992000481909154962955010217153589993304722719340884054355376558326105036947257582728860147557431276912919643940358478125733042829478349114754313750607492935206321298801011776939307313478546331523512938761672813983870399597182080005906066953602228332948790458576153448761425614070248334986663583719133564252378947422392557755444674008030141846366476287826338519233008704965899055639264609925259823048079319
n = 1698281899194715114165111012319277103359733674717346894156321734086384210027912893592223341535254583183189375047805019470712423207121454213625786296403115965465797639874678119529865412063714723513964182015925137173277042639307327631371055326412204990172328114832185024332076266014268385262996787504249248741895102659976146333218908476195041388126877183421158327681480273218635257896126985050902620483850502219753728842322424353423665711001628722961510508066740039
c = 53146904354859601599585110457067111012858829248246133531123405294986679458995718625053726629192021849150034273282207940006128865030953003797480171720673649060942787124637476440400908506795533118278613492356804275358218541297790334587524059713360959881377651255593428483947657195937373058321156413003347566693680573881827047037751088091600420762361729539354
t=a
coeff=[]
for i in range(5,-1,-1):
    t_=t+2**32*b**i
    if (i>0):
        t_+=2**33*b**(i-1)
    k=t_//b**i-2**32
    coeff.append(k)
    t-=k*b**i
coeff=coeff[::-1]
print(coeff)
PR.<x>=PolynomialRing(Zmod(n))
f=sum([coeff[i]*x**i for i in range(len(coeff))])-c
f=f.monic()
sol=f.small_roots(X=2^252,beta=0.4)
print(sol)
m=int(sol[0])
print(long_to_bytes(m))
#[-2199405606, -2479878525, 2139313240, 815370412, -1991983599, 2189833032]
b'F1nd_4_M3th0d_70_COPPER5m1th!'
#NSSCTF{F1nd_4_M3th0d_70_COPPER5m1th!}
'''
从5到0逆序迭代，
最后列表反转，将系数正确放置
'''
for i in range(5,-1,-1): 
    t_=t+2**32*b**i
    if (i>0):
        t_+=2**33*b**(i-1)
    k=t_//b**i-2**32
    coeff.append(k)
    t-=k*b**i
coeff=coeff[::-1]