CoCalc -- SIKE_challenge.sage

GitHub Repository: jack4818/Castryck-Decru-SageMath
Path: blob/main/direct-reimplementation/SIKE_challenge.sage
³²³ views
1
import time
2
from itertools import product
3

4
load('richelot_aux.sage')
5
load('uvtable.sage')
6
load('speedup.sage')
7

8
# Remove annoying messages about slow Gröbner
9
set_verbose(-1)
10

11
# Stop slow primality checks GF(p^k) construction
12
proof.arithmetic(False)
13

14
# $IKEp217 parameters
15
a = 110
16
b = 67
17
p = 2^a*3^b - 1
18
Fp2.<i> = GF(p^2, modulus=x^2+1)
19
assert i^2 == -1
20

21
R.<x> = PolynomialRing(Fp2)
22

23
E_start = EllipticCurve(Fp2, [0,6,0,1,0])
24
# Speeds things up in Sage
25
E_start.set_order((p+1)^2)
26

27
phi = EllipticCurveIsogeny(E_start, x)
28
E1728 = phi.codomain()
29
# Speeds things up in Sage
30
E1728.set_order((p+1)^2)
31

32
for iota in E1728.automorphisms():
33
    P = E1728.random_point()
34
    if iota(iota(P)) == -P:
35
        two_i = phi.post_compose(iota).post_compose(phi.dual())
36
        break
37

38
# $IKEp217 public parameters
39

40
xQ2 = 86445170414599058485968715662346922796016566052081315743781191908 + i*40452781127453632342062231901634407992350274206219311799642330230
41
yQ2 = 65598021239445364766945421641383356785387864046503211101901536990 + i*4185188043442820950612067662642469583838730096408235972690714750
42
Q2 = E_start(xQ2, yQ2)
43

44
xP2 = 37927755131506746411537091732732279589710442710570639382902295344 + i*37017495259074475516858568039563512752905548684528955375066616976
45
yP2 = 47930070613074499206421889519713097155043539387599009924307417901 + i*7176302698603683442486948733484190513242470057553561741081582098
46
P2 = E_start(xP2, yP2)
47

48
# CONSISTENCY WITH R (NOT NEEDED BUT OK)
49
xR2 = 46724562430016373759602265681716628459894400021233033976074511127 + i*62869247191516167619032311426583862201277153531817575978673280654
50
assert (P2 - Q2)[0] == xR2
51

52
xQ3 = 47793138785202808493310870472269548499693686682045542672866243781
53
yQ3 = i*59233392251697228025115695338640088714243311845504632846426147327
54
Q3 = E_start(xQ3, yQ3)
55

56
xP3 = 92537981321677359984282752681526321709848257167914581295182029482
57
yP3 = 64890706732687703644418730466418873818100958793359354306462487533
58
P3 = E_start(xP3, yP3)
59

60
# CONSISTENCY WITH R (NOT NEEDED BUT OK)
61
# Typo in magma, should be P3 and Q3
62
xR3 = 100985822528123790926639173045977043567721100360555352880158477546 + i*53651151307208479216007649001480928514654306829312202244997088803
63
assert (P3 - Q3)[0] == xR3
64

65
# ALICE'S PUBLIC KEY:
66
xPA = 78851325149093883127710876413676714831509071567295995722742563459 + i*21481241277029422048465721240261620296276964367410557936597294375
67
xQA = 109443172641179151776707590487317622581952970379528972130069645642 + i*3867221956981918915643365445875236474767408154492041549977730573
68
xRA = 24146826348939386714009375843953121070061474437444339669850030464 + i*9794094030587590044286487045494277248551007280921263840310791516
69

70
A = (1 - xPA*xQA - xPA*xRA - xQA*xRA)^2/(4*xPA*xQA*xRA) - xPA - xQA - xRA
71

72
yPA = sqrt(xPA^3 + A*xPA^2 + xPA)
73
yQA = sqrt(xQA^3 + A*xQA^2 + xQA)
74

75
# SMALL ERROR IN SIDH-spec.pdf, CORRECTED HERE
76
if xRA + xQA + xPA + A != (yQA + yPA)^2 / (xQA - xPA)^2:
77
    yQA = -yQA
78

79
# let's check:
80
EA = EllipticCurve(Fp2, [0,A,0,1,0])
81
EA.set_order((p+1)^2)
82
PA = EA(xPA, yPA)
83
QA = EA(xQA, yQA)
84

85
# BOB'S PUBLIC KEY:
86
xPB = 52037618715847826453371077000320105687598036562145407135988121710 + i*62945436285055860346151337655131657491042243534644871894809196747
87
xQB = 94057161062674597281795314311864564004565620907834550169224722966 + i*91420731496759657779126063859508682663377955903334296321639551249
88
xRB = 43790287819500432145214110821932450371863522319238208485657321972 + i*98694640376206066779482191725776091085259044935342665789389325446
89

90
B = (1 - xPB*xQB - xPB*xRB - xQB*xRB)^2/(4*xPB*xQB*xRB) - xPB - xQB - xRB
91

92
yPB = sqrt(xPB^3 + B*xPB^2 + xPB)
93
yQB = sqrt(xQB^3 + B*xQB^2 + xQB)
94

95
# SMALL ERROR IN SIDH-spec.pdf, CORRECTED HERE
96
if xRB + xQB + xPB + B != (yQB + yPB)^2 / (xQB - xPB)^2:
97
    yQB = -yQB
98

99
# let's check:
100
EB = EllipticCurve(Fp2, [0,B,0,1,0])
101
EB.set_order((p+1)^2)
102
PB = EB(xPB, yPB)
103
QB = EB(xQB, yQB)
104

105
# ===================================
106
# =====  ATTACK  ====================
107
# ===================================
108
tim = time.time()
109

110
skB = [] # TERNARY DIGITS IN EXPANSION OF BOB'S SECRET KEY
111

112
# gathering the alpha_i, u, v from table
113

114
expdata = [[0, 0, 0] for _ in range(b-3)]
115
# for i in [1..b-3] do
116
for i in range(1,b-2):
117
    # if IsOdd(b-i) then
118
    if (b-i)%2 == 1:
119
        index = (b - i + 1) // 2
120
        exp = uvtable[index-1][1]
121
        if exp <= a:
122
            u = uvtable[index-1][2]
123
            v = uvtable[index-1][3]
124
            expdata[i-1] = [exp, u, v]
125

126
# gather digits until beta_1
127
bet1 = 0
128
while expdata[bet1][0] == 0:
129
    bet1 += 1
130
bet1 += 1
131

132
ai = expdata[bet1-1][0]
133
u  = expdata[bet1-1][1]
134
v  = expdata[bet1-1][2]
135

136
print(f"Determination of first {bet1} ternary digits. We are working with 2^{ai}-torsion.")
137

138
bi = b - bet1
139
alp = a - ai
140

141
# for j in CartesianPower([0,1,2], bet1) do
142
for j in product([0,1,2], repeat=int(bet1)):
143
    print(f"Testing digits: {[j[k] for k in range(bet1)]}")
144

145
    # tauhatkernel = 3^bi*P3 + sum([3^(k-1)*j[k-1] for k in range(1,beta+1)])*3^bi*Q3
146
    tauhatkernel = 3^bi*P3 
147
    for k in range(1, bet1+1):
148
        tauhatkernel += (3^(k-1)*j[k-1])*3^bi*Q3
149

150
    tauhatkernel_distort = u*tauhatkernel + v*two_i(tauhatkernel)
151

152
    C, tau_tilde = Pushing3Chain(E_start, tauhatkernel_distort, bet1)
153

154
    P_c = u*P2 + v*two_i(P2) 
155
    for taut in tau_tilde:
156
        P_c = taut(P_c)
157
    Q_c = u*Q2 + v*two_i(Q2)
158
    for taut in tau_tilde:
159
        Q_c = taut(Q_c)
160

161
    # if j eq <2 : k in [1..bet1]> or Does22ChainSplit(C, EB, 2^alp*P_c, 2^alp*Q_c, 2^alp*PB, 2^alp*QB, ai) then
162
    if j == (2,)*bet1 or Does22ChainSplit(C, EB, 2^alp*P_c, 2^alp*Q_c, 2^alp*PB, 2^alp*QB, ai):
163
        print("Glue-and-split! These are most likely the secret digits.")
164
        for k in j:
165
            skB.append(k)
166
        break
167

168
print(skB)
169

170

171
# now compute longest prolongation of Bob's isogeny that may be needed
172
length = 1
173
max_length = 0
174
# for i in [bet1+1..b-3] do
175
for i in range(bet1 + 1, b - 2):
176
  if expdata[i-1][0] != 0:
177
    max_length = max(length, max_length)
178
    length = 0
179
  else:
180
    length += 1
181

182
while True:
183
    K = 2^a*3^(b - max_length)*EB.random_point()
184
    if K.order() == 3^max_length:
185
        break
186

187
while True:
188
    alternativeK = 2^a*3^(b - max_length)*EB.random_point()
189
    if K.weil_pairing(alternativeK, 3^max_length)^(3^(max_length - 1)) != 1:
190
        break
191

192
_, EBprolong = Pushing3Chain(EB, K, max_length)
193

194
# gather next digit and change prolongation if needed
195
i = bet1 + 1
196
bi = b - i
197

198
print(f"Determination of the {i}th ternary digit. We are working with 2^{ai}-torsion.")
199
prolong = 1
200
print("Prolonging with 1 steps.")
201
endPB = EBprolong[0](PB)
202
endQB = EBprolong[0](QB)
203
endEB = EBprolong[0].codomain()
204
# Speeds things up in Sage
205
endEB.set_order((p+1)^2)
206

207
positives = []
208

209
for j in range(0,2+1):
210
    print(f"Testing digit: {j}")
211
    # tauhatkernel := 3^bi*P3 + (&+[3^(k-1)*skB[k] : k in [1..i-1]] + 3^(i-1)*j)*3^bi*Q3;
212
    tauhatkernel = 3^bi*P3 
213
    for k in range(1, i):
214
        tauhatkernel += (3^(k-1)*skB[k-1])*3^bi*Q3
215
    tauhatkernel += 3^(i-1)*j*3^bi*Q3
216

217
    tauhatkernel_distort = u*tauhatkernel + v*two_i(tauhatkernel)
218

219
    C, tau_tilde = Pushing3Chain(E_start, tauhatkernel_distort, i)
220
    P_c = u*P2 + v*two_i(P2)
221
    for taut in tau_tilde:
222
        P_c = taut(P_c)
223
    Q_c = u*Q2 + v*two_i(Q2)
224
    for taut in tau_tilde:
225
        Q_c = taut(Q_c)
226

227
    if Does22ChainSplit(C, endEB, 2^alp*P_c, 2^alp*Q_c, 2^alp*endPB, 2^alp*endQB, ai):
228
        print("Glue-and-split!")
229
        positives.append(j)
230
        break
231

232
if len(positives) == 1:
233
    print(f"Most likely good prolongation and the secret digit is: {positives[0]}")
234
    skB.append(positives[0])
235
    next_i = i + 1
236
else:
237
    print("All glue-and-splits, must be bad prolongation: changing it and redoing this digit.")
238
    _, EBprolong = Pushing3Chain(EB, alternativeK, max_length)
239
    next_i = i
240
    prolong = 0
241

242

243
# now gather all remaining digits, except for last three (we close that gap by trial and error)
244

245
# for i in [next_i..b-3] do
246
for i in range(next_i, b-2):
247
    bi = b - i
248
    if expdata[i-1][0] != 0:
249
        ai = expdata[i-1][0]
250
        alp = a - ai
251
        u = expdata[i-1][1]
252
        v = expdata[i-1][2]
253
        prolong = 0
254
    else:
255
        prolong += 1
256

257
    print(f"Determination of the {i}th ternary digit. We are working with 2^{ai}-torsion.")
258
    print(f"Prolonging with {prolong} steps. Current: {skB}")
259
    endPB = PB
260
    endQB = QB
261
    endEB = EB
262
    # for j in [1..prolong] do
263
    for j in range(1,prolong+1):
264
        endPB = EBprolong[j-1](endPB)
265
        endQB = EBprolong[j-1](endQB)
266
    if j == prolong:
267
        endEB = EBprolong[j-1].codomain()
268
        # Speeds things up in Sage
269
        endEB.set_order((p+1)^2)
270

271

272
    for j in range(0,3):
273
        print(f"Testing digit: {j}")
274
        # tauhatkernel := 3^bi*P3 + (&+[3^(k-1)*skB[k] : k in [1..i-1]] + 3^(i-1)*j)*3^bi*Q3;
275
        tauhatkernel = 3^bi*P3 
276
        for k in range(1, i):
277
            tauhatkernel += (3^(k-1)*skB[k-1])*3^bi*Q3
278
        tauhatkernel += 3^(i-1)*j*3^bi*Q3
279

280
        tauhatkernel_distort =u*tauhatkernel + v*two_i(tauhatkernel)
281
        
282
        C, tau_tilde = Pushing3Chain(E_start, tauhatkernel_distort, i)
283
        P_c = u*P2 + v*two_i(P2)
284
        for taut in tau_tilde:
285
            P_c = taut(P_c)
286
        Q_c = u*Q2 + v*two_i(Q2)
287
        for taut in tau_tilde:
288
            Q_c = taut(Q_c)
289
        if j == 2 or Does22ChainSplit(C, endEB, 2^alp*P_c, 2^alp*Q_c, 2^alp*endPB, 2^alp*endQB, ai):
290
            print("Glue-and-split! This is most likely the secret digit.")
291
            skB.append(j)
292
            break
293

294
key = sum([skB[i-1]*3^(i-1) for i in range(1,b-2)])
295

296
# bridge last safety gap
297
tim2 = time.time()
298

299
found = false
300
for i in range(3^5+1):
301
    bobskey = key + i*3^(b-3)
302
    bobscurve, _ = Pushing3Chain(E_start, P3 + bobskey*Q3, b)
303
    if bobscurve.j_invariant() == EB.j_invariant():
304
        found = true
305
        break
306

307
print(f"Bridging last gap took: {time.time() - tim2}")
308

309
if found:
310
    print(f"Bob's secret key revealed as: {bobskey}")
311
    print(f"In ternary, this is: {Integer(bobskey).digits(base=3)}")
312
else:
313
    print("Something went wrong.")
314

315
print(f"Altogether this took {time.time() - tim} seconds.")
316

317

318

319

320

321

322

323

324

325

326
Product

Resources

Company
