SharedSIKE Sage implementation non-optimized.ipynbOpen in CoCalc
Implementation of SuperSingular isogeny keyexchange

#Generating a prime p, following different methods
l1 = 2
l2 = 3
e1 = randint(100,200) #These exponents are huge for SIKE on an ordinary computer
e2 = randint(100,200)
(l1, e1, l2, e2)

def genPrime(l1, e1, l2, e2):
"""Return a prime  (l1^e2)(l2^e2)f + *{-}1, where f is a random number
This method has been mentioned in TOWARDS QUANTUM-RESISTANT CRYPTOSYSTEMS FROM SUPERSINGULAR"""
pm1 = (l1^e1)*l2^e2

p = pm1*1 -1
for i in range(2, 2^20):
p = (p+1) + pm1 -1 #upadte
if is_prime(p): return p
if is_prime(p+2): return p+2

def genPrimeR(l1, e1, l2, e2):
"""Return a prime  (l1^e2)(l2^e2)f + *{-}1, we increment f by 1 each time till a prime is found"""
pm1 = (l1^e1)*l2^e2

r = randint(1, 2^10)

for i in range(2, 2^20):
if is_prime(p): return p
if is_prime(p+2):return p+2
r = randint(1, 2^10) #update

def genPrime23(e1,  e2):
"""Get a prime of the form (2^n)*(3^m)±1"""
p = (2<<e1)*(3^e2)
for i in xrange(e1, 2*e1):
for j in xrange(e2, 2*e2):
p = p << 1
p = 3*p
if is_prime(p+1): return p+1 #For the future, it should return e1, e2

if is_prime(p-1): return p-1

def genSupSing(p):
"""Given a prime p, returns a supersingular curve coefficients
The standard form of entering an elliptic curve in Sage is
EllipticCurve(Field, [a1, a2, a3, a4, a5, a6]) where
y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6."""

if p == 2: return [0, 0, 1, 0, 0]
elif p%4 == 3: return [0, 0, 0, -1, 0]
elif legendre_symbol(-3, p) == -1: return [0, 0, 0, 0, -1]
else: return False #This part is more involved, I prefer to generate another prime.
#See Reinier Bröker. Constructing supersingular elliptic curves

#For the future, All above functions need to be edited to return whether p = m+1 or m-1


######################TESTING PRIME GENERATION##############################
l1 = 2
l2 = 3
e1 = randint(100,200)
e2 = randint(100,200)
q = genPrime(l1, e1, l2, e2 )
t = q
while  genSupSing(q) == False:
e1 = randint(100,200)
e2 = randint(100,200)
q = genPrime(l1, e1, l2, e2 )
if genSupSing(q):
t=q #for some reason, it updates the value before leaving the loop

q = t; print(q)
EllipticCurve(GF(q),genSupSing(q)).is_supersingular()

5194994355689918998948375534214446732680520861354545436708195599748240133397592369029790575386462392596047460303979357256019325902210604204031
True
l1 = 2
l2 = 3
e1 = randint(100,200)
e2 = randint(100,200)
qr = genPrimeR(l1, e1, l2, e2 )

while  genSupSing(q) != False:
#e1 = randint(100,200)
#e2 = randint(100,200) #First algorithm returns a differnt output for a fixed input
q = genPrimeR(l1, e1, l2, e2 )
if genSupSing(q) != False: t=q #for some reason, it updates the value before leaving the loop

qr = t; print(qr)
EllipticCurve(GF(qr),genSupSing(qr)).is_supersingular()


5194994355689918998948375534214446732680520861354545436708195599748240133397592369029790575386462392596047460303979357256019325902210604204031
True
e1 = randint(100,170)
e2 = randint(100,170)
q23 = genPrime23(e1, e2 )
t = q23
while  genSupSing(q) == False:
e1 = randint(100,200)
e2 = randint(100,200) #First algorithm returns a differnt output for a fixed input
q = genPrime23(e1, e2)
if genSupSing(q23) != False: t=q23 #for some reason, it updates the value before leaving the loop

q23 = t; print(q23)
#EllipticCurve(GF(q23),genSupSing(q23)).is_supersingular()

#######################################END TESTING###################################################


229036002299580430864382545454534508354326861103924243886156739364802216156884115227899761308451782617967270366579042488442498132519929653698943465033139313565151784203127224027578369
%%time
###################################SIKE##########################################
#----------------------------PRIME GENERATION------------------------------------
a, b = [4, 6] #pick e1, e2 from this interval. CoCalc would not allow larger exponents.
l1 = 2
l2 = 3
e1 = randint(a, b)
e2 = randint(a, b)
q = genPrime(l1, e1, l2, e2 )

while  genSupSing(q) == False:
e1 = randint(a, b)
e2 = randint(a,b)
q = genPrime(l1, e1, l2, e2 )
if genSupSing(q) != False: t=q #for some reason, it updates the value before leaving the loop
q = t
#EllipticCurve(GF(q),genSupSing(q)).is_supersingular()

#This part can be removed by editing the functions that generate the primes
l = l2^e2
if gcd(q-1, l) == l:
one = 1
else:
one = -1


CPU times: user 39.9 ms, sys: 0 ns, total: 39.9 ms Wall time: 66.8 ms
print("We are going to use p where p = {} + ({})".format(factor(q-one), one ))

#Sanity's check
assert gcd(q-one, l) == l
#assert gcd(q-one, 2<<e1) == 2<<e1


We are going to use p where p = 2^5 * 3^6 * 5 + (-1)
%%time
#------------------------Initializing
E = EllipticCurve(GF(q), genSupSing(q)) #Create an elliptic cuve. This information is public.
assert E.is_supersingular()

#Alice prepares her public and secret key
orderA = Integer((q-one)/l)
AliceP = orderA*(E.random_element())  #Public point of order 3^e2 (probably)
AliceQ = orderA*(E.random_element()) #Public point of order 3^e2 (probably)

(u1, u2) = (randint(1, q), randint(1, q)) #Alice's secret key, she is going to compute u1*AliceP + u2*AliceQ
AliceS = u1*AliceP+u2*AliceQ # Alice is going to compute E/<AliceS>
print("Alice's secret Key is of order {} where the biggest multiplicity of 3-subgroup   is {}".format(factor(AliceS.order()), e2) )

#Bob repeats the above process with different random points and a secret key
orderB = Integer((q-one)>>e1)
BobP = orderB*E.random_element() #Public point
BobQ = orderB*E.random_element() #Public point
(v1, v2) = (randint(1, q), randint(1, q)) #Bob's secret key, he is going to compute v1*BobP + u2*BobQ
BobS = v1*BobP+v2*BobQ
print("  Bob's secret Key is of order {} where the biggest multiplicity of 2-subgroup is {}\n".format(factor(BobS.order()), e1) )

Alice's secret Key is of order 3^4 where the biggest multiplicity of 3-subgroup is 6 Bob's secret Key is of order 2 where the biggest multiplicity of 2-subgroup is 5 CPU times: user 26.7 ms, sys: 542 µs, total: 27.3 ms Wall time: 52.3 ms
%%time
#Creating secret isogenies
AliceMap = E.isogeny(AliceS) #Find a map phi and a curve E2 such that phi: E->E2 where ker(phi) = <AliceS>
AliceNewEll = AliceMap.codomain() #E/<AliceS> or E2 in the comment above. This is a public information. phi is a secret!

BobMap = E.isogeny(BobS)
BobNewEll = BobMap.codomain() #E/<BobS>,this is a public information


CPU times: user 21.2 ms, sys: 8.16 ms, total: 29.4 ms Wall time: 33.2 ms
%%time
#Naive method
AliceS1 = 3* AliceS
print(AliceS1.order())

27 CPU times: user 4.03 ms, sys: 7 µs, total: 4.04 ms Wall time: 3.89 ms
E.isogeny(AliceS1)

Isogeny of degree 27 from Elliptic Curve defined by y^2 = x^3 + 116638*x over Finite Field of size 116639 to Elliptic Curve defined by y^2 = x^3 + 82968*x + 70354 over Finite Field of size 116639
#It takes time to evaluate this, try with smaller parameters
#print("Alice's secret map is: ", AliceMap.rational_maps())
#print("There is no obvious way of getting from ", E, "to ", AliceNewEll)

%%time
#---------------------EXCHANGING------------------------
send2Bob = (AliceMap(BobP), AliceMap(BobQ)) #Bob would receive phi(BobP), phi(BobQ), AliceNewEll
send2Alice = (BobMap(AliceP), AliceMap(AliceQ)) #Same as above but roles are reversed


CPU times: user 4.91 ms, sys: 144 µs, total: 5.05 ms Wall time: 4.22 ms
%%time
#-------Bob creates the common cvrve
#Alice is going to computer AliceNewEll/ <v1*phi(BobP)+v2*phi(BobQ)> = E/<BobS, AliceS>
BobS = v1*AliceNewEll(send2Bob[0])+v2*AliceNewEll(send2Bob[1]) #Bob's secret which lives in AliceNewEll
BobMap = AliceNewEll.isogeny(BobS)
BobSharedEll = BobMap.codomain() #E/<AliceS, BobS>, this is a pvblic informatio

CPU times: user 5.59 ms, sys: 3.61 ms, total: 9.2 ms Wall time: 9.46 ms
%%time
#------Alice creates the common curve
AliceS = u1*BobNewEll(send2Alice[0])+u2*BobNewEll(send2Alice[0]) #Alice's secret which lives in BobNewEll
AliceMap = BobNewEll.isogeny(AliceS)
AliceSharedEll = AliceMap.codomain() #E/<BobS, AliceS>, this is a public informatio


CPU times: user 20.9 ms, sys: 142 µs, total: 21 ms Wall time: 19.2 ms
print("Have Alice and Bob arrived at the same curve?\n"+ str(BobSharedEll == AliceSharedEll))

Have Alice and Bob arrived at the same curve? True
print("Their shared secret key is  {}".format(BobSharedEll.j_invariant()))

Their shared secret key is 111162
q

116639
class SIKE:
#enscapulate all functions above in a single class
def __init__(self, security, baseEll = None):
self.security = security
self.baseEll = baseEll

#def  E(sec)
#def __genSec():
#def send2friend(P, Q):
"""Return phi(P), phi(Q)"""

(E.j_invariant(), AliceNewEll.j_invariant(), BobSharedEll.j_invariant())

(1728, 90546, 111162)
AliceNewEll

BobSharedEll

E