forked from GiacomoPope/Castryck-Decru-SageMath
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSIKE_challenge.sage
114 lines (86 loc) · 4.26 KB
/
SIKE_challenge.sage
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
import public_values_aux
from public_values_aux import *
set_verbose(-1)
load('castryck_decru_shortcut.sage')
load('sandwich_attack.sage')
# $IKEp217 parameters
a = 110
b = 67
p = 2^a*3^b - 1
public_values_aux.p = p
Fp2.<i> = GF(p^2, modulus=x^2+1)
assert i^2 == -1
R.<x> = PolynomialRing(Fp2)
E_start = EllipticCurve(Fp2, [0,6,0,1,0])
# Speeds things up in Sage
E_start.set_order((p+1)^2)
# Generation of the endomorphism 2i
two_i = generate_distortion_map(E_start)
# $IKEp217 public parameters
xQ2 = 86445170414599058485968715662346922796016566052081315743781191908 + i*40452781127453632342062231901634407992350274206219311799642330230
yQ2 = 65598021239445364766945421641383356785387864046503211101901536990 + i*4185188043442820950612067662642469583838730096408235972690714750
Q2 = E_start(xQ2, yQ2)
xP2 = 37927755131506746411537091732732279589710442710570639382902295344 + i*37017495259074475516858568039563512752905548684528955375066616976
yP2 = 47930070613074499206421889519713097155043539387599009924307417901 + i*7176302698603683442486948733484190513242470057553561741081582098
P2 = E_start(xP2, yP2)
# # CONSISTENCY WITH R (NOT NEEDED BUT OK)
# xR2 = 46724562430016373759602265681716628459894400021233033976074511127 + i*62869247191516167619032311426583862201277153531817575978673280654
# assert (P2 - Q2)[0] == xR2
xQ3 = 47793138785202808493310870472269548499693686682045542672866243781
yQ3 = i*59233392251697228025115695338640088714243311845504632846426147327
Q3 = E_start(xQ3, yQ3)
xP3 = 92537981321677359984282752681526321709848257167914581295182029482
yP3 = 64890706732687703644418730466418873818100958793359354306462487533
P3 = E_start(xP3, yP3)
# # CONSISTENCY WITH R (NOT NEEDED BUT OK)
# # Typo in magma, should be P3 and Q3
# xR3 = 100985822528123790926639173045977043567721100360555352880158477546 + i*53651151307208479216007649001480928514654306829312202244997088803
# assert (P3 - Q3)[0] == xR3
# ALICE'S PUBLIC KEY:
xPA = 78851325149093883127710876413676714831509071567295995722742563459 + i*21481241277029422048465721240261620296276964367410557936597294375
xQA = 109443172641179151776707590487317622581952970379528972130069645642 + i*3867221956981918915643365445875236474767408154492041549977730573
xRA = 24146826348939386714009375843953121070061474437444339669850030464 + i*9794094030587590044286487045494277248551007280921263840310791516
A = (1 - xPA*xQA - xPA*xRA - xQA*xRA)^2/(4*xPA*xQA*xRA) - xPA - xQA - xRA
yPA = sqrt(xPA^3 + A*xPA^2 + xPA)
yQA = sqrt(xQA^3 + A*xQA^2 + xQA)
# SMALL ERROR IN SIDH-spec.pdf, CORRECTED HERE
if xRA + xQA + xPA + A != (yQA + yPA)^2 / (xQA - xPA)^2:
yQA = -yQA
# let's check:
EA = EllipticCurve(Fp2, [0,A,0,1,0])
EA.set_order((p+1)^2)
PA = EA(xPA, yPA)
QA = EA(xQA, yQA)
# BOB'S PUBLIC KEY:
xPB = 52037618715847826453371077000320105687598036562145407135988121710 + i*62945436285055860346151337655131657491042243534644871894809196747
xQB = 94057161062674597281795314311864564004565620907834550169224722966 + i*91420731496759657779126063859508682663377955903334296321639551249
xRB = 43790287819500432145214110821932450371863522319238208485657321972 + i*98694640376206066779482191725776091085259044935342665789389325446
B = (1 - xPB*xQB - xPB*xRB - xQB*xRB)^2/(4*xPB*xQB*xRB) - xPB - xQB - xRB
yPB = sqrt(xPB^3 + B*xPB^2 + xPB)
yQB = sqrt(xQB^3 + B*xQB^2 + xQB)
# SMALL ERROR IN SIDH-spec.pdf, CORRECTED HERE
if xRB + xQB + xPB + B != (yQB + yPB)^2 / (xQB - xPB)^2:
yQB = -yQB
# let's check:
EB = EllipticCurve(Fp2, [0,B,0,1,0])
EB.set_order((p+1)^2)
PB = EB(xPB, yPB)
QB = EB(xQB, yQB)
# ===================================
# ===== ATTACK ====================
# ===================================
def RunAttack(num_cores):
return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)
if __name__ == '__main__' and '__file__' in globals():
if '--parallel' in sys.argv:
# Set number of cores for parallel computation
num_cores = os.cpu_count()
print(f"Performing the attack in parallel using {num_cores} cores")
else:
num_cores = 1
if '--sandwich' in sys.argv:
# Use the fact that 2^(a-1) - 5*3^b is a sum of squares
assert two_squares(2^(a-1) - 5*3^b)
recovered_key = SandwichAttack(E_start, P2, Q2, EB, PB, QB, two_i, k=5, alp=1)
else:
RunAttack(num_cores)