CoCalc -- SIKE_challenge.m

GitHub Repository: jack4818/Castryck-Decru-SageMath
Path: blob/main/Magma-Reference/SIKE_challenge.m
³²³ views
1
/*
2
This code was downloaded from https://homes.esat.kuleuven.be/~wcastryc/ on 3 August 2022
3
*/
4

5
load "richelot_aux.m";
6
load "uvtable.m";
7

8
a := 110;
9
b := 67;
10

11
p := 2^a*3^b - 1;
12
Fp2<I> := GF(p, 2);
13
assert I^2 eq -1;
14
R<x> := PolynomialRing(Fp2);
15

16
E_start := EllipticCurve(x^3 + 6*x^2 + x);
17

18
// NAIVE GENERATION OF AUTOMORPHISM 2i
19
E1728, phi := IsogenyFromKernel(E_start, x);
20
for iota in Automorphisms(E1728) do
21
  P := Random(E1728);
22
  if iota(iota(P)) eq -P then
23
    two_i := phi*iota*DualIsogeny(phi);
24
    break;
25
  end if;
26
end for;
27

28
xQ2 := 86445170414599058485968715662346922796016566052081315743781191908 + I*40452781127453632342062231901634407992350274206219311799642330230;
29
yQ2 := 65598021239445364766945421641383356785387864046503211101901536990 + I*4185188043442820950612067662642469583838730096408235972690714750;
30
Q2 := E_start ! [xQ2, yQ2];
31

32
xP2 := 37927755131506746411537091732732279589710442710570639382902295344 + I*37017495259074475516858568039563512752905548684528955375066616976;
33
yP2 := 47930070613074499206421889519713097155043539387599009924307417901 + I*7176302698603683442486948733484190513242470057553561741081582098;
34
P2 := E_start ! [xP2, yP2];
35

36
// CONSISTENCY WITH R (NOT NEEDED BUT OK)
37
// xR2 := 46724562430016373759602265681716628459894400021233033976074511127 + I*62869247191516167619032311426583862201277153531817575978673280654;
38
// (P2 - Q2)[1] eq xR2;
39

40
xQ3 := 47793138785202808493310870472269548499693686682045542672866243781;
41
yQ3 := I*59233392251697228025115695338640088714243311845504632846426147327;
42
Q3 := E_start ! [xQ3, yQ3];
43

44
xP3 := 92537981321677359984282752681526321709848257167914581295182029482;
45
yP3 := 64890706732687703644418730466418873818100958793359354306462487533;
46
P3 := E_start ! [xP3, yP3];
47

48
// CONSISTENCY WITH R (NOT NEEDED BUT OK)
49
// xRB := 100985822528123790926639173045977043567721100360555352880158477546 + I*53651151307208479216007649001480928514654306829312202244997088803;
50
// (PB - QB)[1] eq xRB;
51

52
// ALICE'S PUBLIC KEY:
53

54
xPA := 78851325149093883127710876413676714831509071567295995722742563459 + I*21481241277029422048465721240261620296276964367410557936597294375;
55
xQA := 109443172641179151776707590487317622581952970379528972130069645642 + I*3867221956981918915643365445875236474767408154492041549977730573;
56
xRA := 24146826348939386714009375843953121070061474437444339669850030464 + I*9794094030587590044286487045494277248551007280921263840310791516;
57

58
A := (1 - xPA*xQA - xPA*xRA - xQA*xRA)^2/(4*xPA*xQA*xRA) - xPA - xQA - xRA;
59

60
yPA := Sqrt(xPA^3 + A*xPA^2 + xPA);
61
yQA := Sqrt(xQA^3 + A*xQA^2 + xQA);
62

63
if xRA + xQA + xPA + A ne (yQA + yPA)^2 / (xQA - xPA)^2 then yQA := -yQA; end if; // SMALL ERROR IN SIDH-spec.pdf, CORRECTED HERE
64

65
// let's check:
66

67
EA := EllipticCurve(x^3 + A*x^2 + x);
68
PA := EA ! [xPA, yPA];
69
QA := EA ! [xQA, yQA];
70

71
// BOB'S PUBLIC KEY:
72

73
xPB := 52037618715847826453371077000320105687598036562145407135988121710 + I*62945436285055860346151337655131657491042243534644871894809196747;
74
xQB := 94057161062674597281795314311864564004565620907834550169224722966 + I*91420731496759657779126063859508682663377955903334296321639551249;
75
xRB := 43790287819500432145214110821932450371863522319238208485657321972 + I*98694640376206066779482191725776091085259044935342665789389325446;
76

77
B := (1 - xPB*xQB - xPB*xRB - xQB*xRB)^2/(4*xPB*xQB*xRB) - xPB - xQB - xRB;
78

79
yPB := Sqrt(xPB^3 + B*xPB^2 + xPB);
80
yQB := Sqrt(xQB^3 + B*xQB^2 + xQB);
81

82
if xRB + xQB + xPB + B ne (yQB + yPB)^2 / (xQB - xPB)^2 then yQB := -yQB; end if; // SMALL ERROR IN SIDH-spec.pdf, CORRECTED HERE
83

84
// let's check:
85

86
EB := EllipticCurve(x^3 + B*x^2 + x);
87
PB := EB ! [xPB, yPB];
88
QB := EB ! [xQB, yQB];
89

90
// ===================================
91
// =====  ATTACK  ====================
92
// ===================================
93

94
tim := Cputime();
95

96
skB := []; // TERNARY DIGITS IN EXPANSION OF BOB'S SECRET KEY
97

98
// gathering the alpha_i, u, v from table
99

100
expdata := [[0, 0, 0] : i in [1..b-3]];
101
for i in [1..b-3] do
102
  if IsOdd(b-i) then
103
    index := (b - i + 1) div 2;
104
    exp := uvtable[index][2];
105
    if exp le a then
106
      u := uvtable[index][3];
107
      v := uvtable[index][4];
108
      expdata[i] := [exp, u, v];
109
    end if;
110
  end if;
111
end for;
112

113
// gather digits until beta_1
114

115
bet1 := 0;
116
repeat
117
  bet1 +:= 1;
118
until expdata[bet1][1] ne 0;
119

120
ai := expdata[bet1][1];
121
u := expdata[bet1][2];
122
v := expdata[bet1][3];
123

124
print "Determination of first", bet1, "ternary digits. We are working with 2^"*IntegerToString(ai)*"-torsion.";
125

126
bi := b - bet1;
127
alp := a - ai;
128

129
for j in CartesianPower([0,1,2], bet1) do
130
  print "Testing digits", &*[IntegerToString(j[k])*" " : k in [1..bet1]];
131
  tauhatkernel := 3^bi*P3 + (j[1] + 3*j[2])*3^bi*Q3;
132
  tauhatkernel_distort := u*tauhatkernel + v*two_i(tauhatkernel);
133
  C, tau_tilde := Pushing3Chain(E_start, tauhatkernel_distort, bet1);
134
  P_c := u*P2 + v*two_i(P2); for taut in tau_tilde do P_c := taut(P_c); end for;
135
  Q_c := u*Q2 + v*two_i(Q2); for taut in tau_tilde do Q_c := taut(Q_c); end for;
136
  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
137
    print "Glue-and-split! These are most likely the secret digits.";
138
    skB cat:= [j[k] : k in [1..bet1]];
139
    break;
140
  end if;
141
end for;
142

143
// now compute longest prolongation of Bob's isogeny that may be needed
144

145
length := 1;
146
max_length := 0;
147
for i in [bet1+1..b-3] do
148
  if expdata[i][1] ne 0 then
149
    max_length := Max(length, max_length);
150
    length := 0;
151
  else
152
    length +:= 1;
153
  end if;
154
end for;
155

156
repeat
157
  K := 2^a*3^(b - max_length)*Random(EB);
158
until Order(K) eq 3^max_length;
159

160
repeat
161
  alternativeK := 2^a*3^(b - max_length)*Random(EB);
162
until WeilPairing(K, alternativeK, 3^max_length)^(3^(max_length - 1)) ne 1;
163

164
_, EBprolong := Pushing3Chain(EB, K, max_length);
165

166
// gather next digit and change prolongation if needed
167

168
i := bet1 + 1;
169
bi := b - i;
170

171
print "Determination of the "*IntegerToString(i)*"th ternary digit. We are working with 2^"*IntegerToString(ai)*"-torsion.";
172
prolong := 1;
173
print "Prolonging with 1 steps.";
174
endPB := EBprolong[1](PB);
175
endQB := EBprolong[1](QB);
176
endEB := Codomain(EBprolong[1]);
177

178
positives := [];
179

180
for j in [0..2] do
181
  print "Testing digit", j;
182
  tauhatkernel := 3^bi*P3 + (&+[3^(k-1)*skB[k] : k in [1..i-1]] + 3^(i-1)*j)*3^bi*Q3;
183
  tauhatkernel_distort := u*tauhatkernel + v*two_i(tauhatkernel);
184
  C, tau_tilde := Pushing3Chain(E_start, tauhatkernel_distort, i);
185
  P_c := u*P2 + v*two_i(P2); for taut in tau_tilde do P_c := taut(P_c); end for;
186
  Q_c := u*Q2 + v*two_i(Q2); for taut in tau_tilde do Q_c := taut(Q_c); end for;
187
  if Does22ChainSplit(C, endEB, 2^alp*P_c, 2^alp*Q_c, 2^alp*endPB, 2^alp*endQB, ai) then
188
    print "Glue-and-split!";
189
    positives cat:=[j];
190
    if #positives gt 1 then
191
      break;
192
    end if;
193
  end if;
194
end for;
195

196
if #positives eq 1 then
197
  print "Most likely good prolongation and the secret digit is", positives[1];
198
  skB cat:= [positives[1]];
199
  next_i := i + 1;
200
else
201
  print "All glue-and-splits, must be bad prolongation: changing it and redoing this digit.";
202
  _, EBprolong := Pushing3Chain(EB, alternativeK, max_length);
203
  next_i := i;
204
  prolong := 0;
205
end if;
206

207
// now gather all remaining digits, except for last three (we close that gap by trial and error)
208

209
for i in [next_i..b-3] do
210
  bi := b - i;
211
  if expdata[i][1] ne 0 then
212
    ai := expdata[i][1];
213
    alp := a - ai;
214
    u := expdata[i][2];
215
    v := expdata[i][3];
216
    prolong := 0;
217
  else
218
    prolong +:= 1;
219
  end if;
220
  print "Determination of the "*IntegerToString(i)*"th ternary digit. We are working with 2^"*IntegerToString(ai)*"-torsion.";
221
  print "Prolonging with", prolong, "steps.";
222
  endPB := PB;
223
  endQB := QB;
224
  endEB := EB;
225
  for j in [1..prolong] do
226
    endPB := EBprolong[j](endPB);
227
    endQB := EBprolong[j](endQB);
228
    if j eq prolong then
229
      endEB := Codomain(EBprolong[j]);
230
    end if;
231
  end for;
232

233
  for j in [0..2] do
234
    print "Testing digit", j;
235
    tauhatkernel := 3^bi*P3 + (&+[3^(k-1)*skB[k] : k in [1..i-1]] + 3^(i-1)*j)*3^bi*Q3;
236
    tauhatkernel_distort := u*tauhatkernel + v*two_i(tauhatkernel);
237
    C, tau_tilde := Pushing3Chain(E_start, tauhatkernel_distort, i);
238
    P_c := u*P2 + v*two_i(P2); for taut in tau_tilde do P_c := taut(P_c); end for;
239
    Q_c := u*Q2 + v*two_i(Q2); for taut in tau_tilde do Q_c := taut(Q_c); end for;
240
    if j eq 2 or Does22ChainSplit(C, endEB, 2^alp*P_c, 2^alp*Q_c, 2^alp*endPB, 2^alp*endQB, ai) then
241
      print "Glue-and-split! This is most likely the secret digit.";
242
      skB cat:= [j];
243
      break;
244
    end if;
245
  end for;
246

247
end for;
248

249

250
key := &+[skB[i]*3^(i-1) : i in [1..b-3]];
251

252
// bridge last safety gap
253

254
tim2 := Cputime();
255

256
found := false;
257
for i in [0..3^5] do
258
  bobskey := key + i*3^(b-3);
259
  bobscurve := Pushing3Chain(E_start, P3 + bobskey*Q3, b);
260
  if jInvariant(bobscurve) eq jInvariant(EB) then
261
    found := true;
262
    break;
263
  end if;
264
end for;
265

266
print "Bridging last gap took", Cputime(tim2);
267

268
if found then
269
  print "Bob's secret key revealed as", bobskey;
270
else
271
  print "Something went wrong.";
272
end if;
273

274
print "Altogether this took", Cputime(tim), "seconds.";
275

276
Product

Resources

Company
