糖醋小鸡块的blog
0%

2024-H&NCTF-Iso-wp-crypto

发表于 分类于 Valine：

包含Is this Iso? 1/2题目的题解

Is this Iso ?

题目描述：

1
Seems a lot of values were leaked

题目：

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
63
from Crypto.Util.number import *
from random import *
from secret import flag

def nextPrime(p):
    while(not isPrime(p)):
        p += 1
    return p


#part1 gen Fp and init supersingular curve
while(1):
    p = 2^randint(150,200)*3^randint(100,150)*5^randint(50,100)-1
    if(isPrime(p)):
        break

F.<i> = GF(p^2, modulus = x^2 + 1)
E = EllipticCurve(j=F(1728))
assert E.is_supersingular()


#part2 find a random supersingular E
ways = [2,3,5]
for i in range(20):
    P = E(0).division_points(choice(ways))[1:]
    shuffle(P)
    phi = E.isogeny(P[0])
    E = phi.codomain()


#part3 gen E1 E2 E3
E1 = E

deg1 = 2
P = E1(0).division_points(deg1)[1:]
shuffle(P)
phi1 = E1.isogeny(P[0])
E2 = phi1.codomain()

deg2 = choice(ways)
P = E2(0).division_points(deg2)[1:]
shuffle(P)
phi2 = E2.isogeny(P[0])
E3 = phi2.codomain()


#part4 leak
j1 = E1.j_invariant()
j2 = E2.j_invariant()
j3 = E3.j_invariant()

m = bytes_to_long(flag)
n = getPrime(int(j3[0]).bit_length())*nextPrime(int(j3[0]))

print("p =",p)
print("deg1 =",deg1)
print("deg2 =",deg2)
print("leak1 =",j1[0] >> 400 << 400)
print("leak2 =",j1[1] >> 5 << 5)
print("leak3 =",j2[0] >> 5 << 5)
print("leak4 =",j2[1] >> 400 << 400)
print("n =",n)
print("cipher =",pow(m,65537,n))

output：

1
2
3
4
5
6
7
8
9
p = 680201537161531317827869565786140240595567913096417274637134403255116055511280864892266374758399999999999999999999999999999999999999999999999999999999999999999999999
deg1 = 2
deg2 = 5
leak1 = 84624382514957324426794167416980084161297449460045164807842311763375830274875400809588635343195174135691613055453493035516696630357254763624394674275492513550696448
leak2 = 569334021319485756763137861791243638993859221789562816154577308542976649646202822945301844698450579193326962681107954744030417590603938838204734858601313640848501344
leak3 = 325720000771917646719671745106544502680895911477018701616420509369836768451047103170212051953041518446572892754419417720965474892312189833039602545011787135282170400
leak4 = 607188653779811312711900086497209011406043384341389739547214249680956969386970129072753246609362372591781044704784040165947962309186896993435085198595013761765998592
n = 336631348442872227475735277623305104458216242371136122513108670525622121689052346348620824105820633714562546800934735845952338946486424402720093748392510487705996344393513464710255615634248631016778273746776059762111364616763243266453211367983670687473800622632626192654424964609849049774336197739675356042226277067017714668077407
cipher = 98106149415612242984147419198102021164901863054603625014502538888604192644391041028562541950192883864954991703087157292974235031070431515337932833347213492206351147110891983722997746801220179144171968380355798405953558533823282395282563952623698461579297014597381904081095895011393305504119244812232164909852287688815879984263470

题目的前两part是生成一条随机的$F_{q^2}$下的超奇异椭圆曲线E1，然后寻找其一个2-isogeny的邻居E2，再寻找E2的一个5-isogeny的邻居E3，用E3的j不变量生成了RSA的加密参数。

不妨将E1、E2的j不变量j1、j2记为：

然后题目隐藏了以下数据：

  • a的低400位
  • b的低5位
  • c的低5位
  • d的低400位

要求还原明文。

可以看出b、c未知的位数实在太少了，总共只需要爆破10位就一定有正确的b、c。而由于E1、E2互为2-isogeny的邻居，所以他们的j不变量可以由2-modular polynomial联系，该等式共有虚部和实部两个等式可以用，所以用resulatnt消元+求根就可以求解出a、d了。

有了完整的j2后，由于E2和E3又互为5-isogeny的邻居，所以遍历E2的所有5-isogeny的邻居，其中就有一个是j3，然后就可以生成：

1
nextPrime(int(j3[0]))

从而与n求gcd得到n的分解，进而解密RSA密文。

exp：

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
from Crypto.Util.number import *
from tqdm import *
import itertools

def nextPrime(p):
    while(not isPrime(p)):
        p += 1
    return p

p = 680201537161531317827869565786140240595567913096417274637134403255116055511280864892266374758399999999999999999999999999999999999999999999999999999999999999999999999
deg1 = 2
deg2 = 5
leak1 = 84624382514957324426794167416980084161297449460045164807842311763375830274875400809588635343195174135691613055453493035516696630357254763624394674275492513550696448
leak2 = 569334021319485756763137861791243638993859221789562816154577308542976649646202822945301844698450579193326962681107954744030417590603938838204734858601313640848501344
leak3 = 325720000771917646719671745106544502680895911477018701616420509369836768451047103170212051953041518446572892754419417720965474892312189833039602545011787135282170400
leak4 = 607188653779811312711900086497209011406043384341389739547214249680956969386970129072753246609362372591781044704784040165947962309186896993435085198595013761765998592
n = 336631348442872227475735277623305104458216242371136122513108670525622121689052346348620824105820633714562546800934735845952338946486424402720093748392510487705996344393513464710255615634248631016778273746776059762111364616763243266453211367983670687473800622632626192654424964609849049774336197739675356042226277067017714668077407
cipher = 98106149415612242984147419198102021164901863054603625014502538888604192644391041028562541950192883864954991703087157292974235031070431515337932833347213492206351147110891983722997746801220179144171968380355798405953558533823282395282563952623698461579297014597381904081095895011393305504119244812232164909852287688815879984263470


##################################################### part1
F.<i> = GF(p^2, modulus = x^2 + 1)
PR.<a,d> = PolynomialRing(Zmod(p))

Find = 0
for b in trange(2^5):
    for c in range(2^5):
        a,d = PR.gens()
        X = (leak1 + a) + (leak2 + b) * i
        Y = (leak3 + c) + (leak4 + d) * i
        f = (
            X^3
            + Y^3
            - X^2 * Y^2
            + 1488 * X^2 * Y
            + 1488 * X * Y^2
            - 162000 * X^2
            - 162000 * Y^2
            + 40773375 * X * Y
            + 8748000000 * X
            + 8748000000 * Y
            - 157464000000000
        )

        f_re = 0
        f_im = 0
        for jj in f:
            temp = str(jj[0]).split("*i")
            if(len(temp) == 1):
                if(temp[0] == "i"):
                    f_im += jj[1]
                else:
                    f_re += int(temp[0])*jj[1]
            else:
                f_im += int(temp[0])*jj[1]
                if(temp[1] != ""):
                    f_re += int(temp[1][2:])*jj[1]


        h = f_im.sylvester_matrix(f_re, a).det().univariate_polynomial().monic()
        res = h.change_ring(Zmod(p)).roots()
        if(res != []):
            for jj in res:
                if(int(jj[0]) < 2^400):
                    Find = 1
                    j2il = int(jj[0])
                    j2 = (leak3 + c) + (leak4 + j2il) * i
                    break

                elif(p - int(jj[0]) < 2^400):
                    Find = 1
                    j2il = p - int(jj[0])
                    j2 = (leak3 + c) + (leak4 + j2il) * i
                    break
        if(Find):
            break
    if(Find):
        break


##################################################### part2
#Φ5
def find_neighbors_phi5(X,j_prev=None):
    R.<Y> = PolynomialRing(X.parent())
    Φ5 = (
        X^6
        + Y^6
        - X^5*Y^5 
        + 3720*X^5*Y^4 
        + 3720*X^4*Y^5 
        - 4550940*X^5*Y^3 
        - 4550940*X^3*Y^5
        + 2028551200*X^5*Y^2 
        + 2028551200*X^2*Y^5
        - 246683410950*X^5*Y
        - 246683410950*X*Y^5 
        + 1963211489280*X^5 
        + 1963211489280*Y^5 
        + 1665999364600*X^4*Y^4 
        + 107878928185336800*X^4*Y^3 
        + 107878928185336800*X^3*Y^4 
        + 383083609779811215375*X^4*Y^2 
        + 383083609779811215375*X^2*Y^4
        + 128541798906828816384000*X^4*Y 
        + 128541798906828816384000*X*Y^4  
        + 1284733132841424456253440*X^4
        + 1284733132841424456253440*Y^4
        - 441206965512914835246100*X^3*Y^3  
        + 26898488858380731577417728000*X^3*Y^2 
        + 26898488858380731577417728000*X^2*Y^3 
        - 192457934618928299655108231168000*X^3*Y
        - 192457934618928299655108231168000*X*Y^3 
        + 280244777828439527804321565297868800*X^3
        + 280244777828439527804321565297868800*Y^3
        + 5110941777552418083110765199360000*X^2*Y^2 
        + 36554736583949629295706472332656640000*X^2*Y 
        + 36554736583949629295706472332656640000*X*Y^2        
        + 6692500042627997708487149415015068467200*X^2 
        - 264073457076620596259715790247978782949376*X*Y 
        + 6692500042627997708487149415015068467200*Y^2 
        + 53274330803424425450420160273356509151232000*X 
        + 53274330803424425450420160273356509151232000*Y 
        + 141359947154721358697753474691071362751004672000
    )

    res = Φ5.roots(multiplicities=False)
    if(j_prev == None):
        return res
    else:
        return list(set(res) - set([j_prev]))
    

for j3 in find_neighbors_phi5(j2):
    p = GCD(nextPrime(int(j3[0])),n)
    if(p != 1):
        q = n // p
        d = inverse(65537,(p-1)*(q-1))
        print(long_to_bytes(int(pow(cipher,d,n))))
        break


#H&NCTF{S33m5_L1ke_C0pp3RsM1th_But_N0t:)}



Is this Iso ?2

题目描述：

1
Seems still a lot of values were leaked

题目：

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
from Crypto.Util.number import *
from random import *
from secret import flag

def nextPrime(p):
    while(not isPrime(p)):
        p += 1
    return p


#part1 gen Fp and init supersingular curve
while(1):
    p = 2^randint(250,300)*3^randint(200,250)*5^randint(150,200)-1
    if(isPrime(p)):
        break

F.<i> = GF(p^2, modulus = x^2 + 1)
E = EllipticCurve(j=F(1728))
assert E.is_supersingular()


#part2 find a random supersingular E
ways = [2,3,5]
for i in range(20):
    P = E(0).division_points(choice(ways))[1:]
    shuffle(P)
    phi = E.isogeny(P[0])
    E = phi.codomain()


#part3 gen E1 E2 E3
E1 = E

deg1 = 2
P = E1(0).division_points(deg1)[1:]
shuffle(P)
phi1 = E1.isogeny(P[0])
E2 = phi1.codomain()

deg2 = 5
P = E2(0).division_points(deg2)[1:]
shuffle(P)
phi2 = E2.isogeny(P[0])
E3 = phi2.codomain()


#part4 leak
unknown = 48
j1 = E1.j_invariant()
j2 = E2.j_invariant()
j3 = E3.j_invariant()

m = bytes_to_long(flag)
n = getPrime(int(j3[0]).bit_length())*nextPrime(int(j3[0]))

print("p =",p)
print("leak1 =",j1[0] >> unknown << unknown)
print("leak2 =",j1[1] >> unknown << unknown)
print("leak3 =",j2[0] >> unknown << unknown)
print("leak4 =",j2[1] >> unknown << unknown)
print("n =",n)
print("cipher =",pow(m,65537,n))

与上一个题目唯一的区别在于，隐藏的信息变成了：

  • a的低48位
  • b的低48位
  • c的低48位
  • d的低48位

所以没有可以爆破的量了，然而显然48位相对于p实在是很小，所以很自然的会想到copper去解决它。

然而用copper的话会遇到一些问题。首先就是四个变量对应的shift实在太多了；其次，modular polynomial本身并不算一个很简单的多项式，所以综合起来用多元copper格的维数很容易就是几大百；最后还有等式数量的问题，实部和虚部分别对应两个等式，当然要一起利用上才行，但如果联立起来resultant消掉一元的话，虽然从变量数来说减少了，会变成三元copper，但是resultant之后的三元多项式度会相当高，更不利于copper，所以不容易解决。

然而，注意到2-isogeny对应的多项式中最高次项也仅有4次，所以其实最大的未知量也就只有192bit，直接把两个等式一起当作约束放入格中去LLL，就可以在规约后的短向量中直接找到我们需要的目标向量了。造格的细节可以参考solver。

exp：

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
from Crypto.Util.number import *

def nextPrime(p):
    while(not isPrime(p)):
        p += 1
    return p

p = 33002887544016314031879710107963270568979015443349496461580994217348108581943462671401891805445187804473789436219797804155565167447548582923397954849996799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
leak1 = 23970024189101676739284999949112801596159475131875488713138494179350672457539898031864018813881524127059547346056890355337626004377168849677299388452735608521932571216168945616402953073274716141377186272923187362572945186088197355146879606612986821843373706666768942322893903428906105943365666240678544198804428017369088
leak2 = 18968478281644090200080507268714677611062523716159449265101819113233914046740738809721658379928130465004476176599403035347489355703796382914550216763662625998487554273370838080897607173662469212264589929308724920155969968302754999378875497515768504097606413596494718061943021600129084717056109413521498214039208905932800
leak3 = 24846971521346659533622446473264138521227563244935912977395904811225387611724566290176121582061549516865041576960467180732303630070352480104283169087055565855330769507536550703237906927824653705302857676851252497170817996780480787545788757588029762501569142537824866794895641164190331637129027655971847921430387098648576
leak4 = 14506384300219774277241069081690189345236549123813938708663001975576355357273770188385102465249828661430885152936340057890533616107247269132829273586451886946676551549255821786705150859518035298037172807466360938386435146531493168660580846121143769776024893444008660445579419515274295620015909587687581741666493110681600
n = 17493161302233539865959778115545849614338747587320539830958673046207703917485289344059005689614899617727057491562059564216328452528431891394964839425545058028178376719697816107862705922877310886122597831458084446977069139926783492027694957365054350790083539389958649142920896888580550434273011064581701139955036959685836337063232723340151170432920208045324320904257623616896017119310224381452189172970937417436861279136518242101847150438391226935084568440274930855362251299289608983772866874344756978071504480416710819717504154104303015133892355188631899268990010375768150730500938937147573182759644411399269734039357767059492842474140949
cipher = 16921253539344108497068632546240027709825757991466136956611001346572164679990250077204370295206837487391144086361806843608963030262072269950948128913794922674041531052955655884066609971456009776555957969815343040743446935276861391783043533446286228409288466221337064700577406994578750474068930699978389468927444219610938550365285817940713903147886965909078470774683916754388441563810469530491686011112673883268153010239483497777390409547764296300047653921679373300693423282406815477193889860589206837874689550943581455570596354670272027903696833667599311930587303088445675268598000581375688180056683387083737664908840976358250628881034642

##################################################### part1
F.<i> = GF(p^2, modulus = x^2 + 1)
PR.<a,b,c,d> = PolynomialRing(Zmod(p))
a,b,c,d = PR.gens()
X = (leak1 + a) + (leak2 + b) * i
Y = (leak3 + c) + (leak4 + d) * i
f = (
    X^3
    + Y^3
    - X^2 * Y^2
    + 1488 * X^2 * Y
    + 1488 * X * Y^2
    - 162000 * X^2
    - 162000 * Y^2
    + 40773375 * X * Y
    + 8748000000 * X
    + 8748000000 * Y
    - 157464000000000
)

f_re = 0
f_im = 0
for jj in f:
    temp = str(jj[0]).split("*i")
    if(len(temp) == 1):
        if(temp[0] == "i"):
            f_im += jj[1]
        else:
            f_re += int(temp[0])*jj[1]
    else:
        f_im += int(temp[0])*jj[1]
        if(temp[1] != ""):
            f_re += int(temp[1][2:])*jj[1]

polys = []


deg_h = (f_re+f_im).degree()
polys.append(f_re)
polys.append(f_im)
T = 2^48
M, v = Sequence(polys).coefficient_matrix()
M = M.T.dense_matrix()
R, C = M.dimensions()
B = block_matrix(
    ZZ, [[matrix.identity(C)*p, matrix.zero(C, R)], [M, matrix.identity(R)]]
)
vT = (v.T).list()

B[:,:C] *= p
for jj in range(len(vT)):
    B[:,C+jj:C+jj+1] *= T^(deg_h-vT[jj].degree())
print(B.dimensions())

res = B.LLL()
for tt in res:
    if(abs(tt[-1]) == T^deg_h):
        a,b,c,d = abs(tt[-5])//T^(deg_h-1) ,  abs(tt[-4])//T^(deg_h-1) ,  abs(tt[-3])//T^(deg_h-1) , abs(tt[-2])//T^(deg_h-1)
        if(a > 0):
            break


j2 = (leak3 + c) + (leak4 + d) * i
##################################################### part2
#Φ5
def find_neighbors_phi5(X,j_prev=None):
    R.<Y> = PolynomialRing(X.parent())
    Φ5 = (
        X^6
        + Y^6
        - X^5*Y^5 
        + 3720*X^5*Y^4 
        + 3720*X^4*Y^5 
        - 4550940*X^5*Y^3 
        - 4550940*X^3*Y^5
        + 2028551200*X^5*Y^2 
        + 2028551200*X^2*Y^5
        - 246683410950*X^5*Y
        - 246683410950*X*Y^5 
        + 1963211489280*X^5 
        + 1963211489280*Y^5 
        + 1665999364600*X^4*Y^4 
        + 107878928185336800*X^4*Y^3 
        + 107878928185336800*X^3*Y^4 
        + 383083609779811215375*X^4*Y^2 
        + 383083609779811215375*X^2*Y^4
        + 128541798906828816384000*X^4*Y 
        + 128541798906828816384000*X*Y^4  
        + 1284733132841424456253440*X^4
        + 1284733132841424456253440*Y^4
        - 441206965512914835246100*X^3*Y^3  
        + 26898488858380731577417728000*X^3*Y^2 
        + 26898488858380731577417728000*X^2*Y^3 
        - 192457934618928299655108231168000*X^3*Y
        - 192457934618928299655108231168000*X*Y^3 
        + 280244777828439527804321565297868800*X^3
        + 280244777828439527804321565297868800*Y^3
        + 5110941777552418083110765199360000*X^2*Y^2 
        + 36554736583949629295706472332656640000*X^2*Y 
        + 36554736583949629295706472332656640000*X*Y^2        
        + 6692500042627997708487149415015068467200*X^2 
        - 264073457076620596259715790247978782949376*X*Y 
        + 6692500042627997708487149415015068467200*Y^2 
        + 53274330803424425450420160273356509151232000*X 
        + 53274330803424425450420160273356509151232000*Y 
        + 141359947154721358697753474691071362751004672000
    )

    res = Φ5.roots(multiplicities=False)
    if(j_prev == None):
        return res
    else:
        return list(set(res) - set([j_prev]))
    

for j3 in find_neighbors_phi5(j2):
    p = GCD(nextPrime(int(j3[0])),n)
    if(p != 1):
        q = n // p
        d = inverse(65537,(p-1)*(q-1))
        print(long_to_bytes(int(pow(cipher,d,n))))
        break


#H&NCTF{5till_n0_n33d_to_u5e_co0p3R!XD}