SharedSIKE Sage implementation non-optimized.ipynbOpen in CoCalc
Authors: Ahmed Alharbi, Boukha Saleh
Views : 69
Description: Implementation of SuperSingular isogeny keyexchange

In [20]:
#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): p = pm1*r-1 #upadte 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
In [2]:
######################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
In [3]:
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
In [4]:
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
In [5]:
%%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
In [6]:
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)
In [7]:
%%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
In [8]:
%%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
In [9]:
%%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
In [10]:
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
In [11]:
#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)
In [12]:
%%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
In [13]:
%%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
In [14]:
%%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
In [15]:
print("Have Alice and Bob arrived at the same curve?\n"+ str(BobSharedEll == AliceSharedEll))
Have Alice and Bob arrived at the same curve? True
In [16]:
print("Their shared secret key is {}".format(BobSharedEll.j_invariant()))
Their shared secret key is 111162
In [17]:
q
116639
In [18]:
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)"""
In [19]:
(E.j_invariant(), AliceNewEll.j_invariant(), BobSharedEll.j_invariant())
(1728, 90546, 111162)
In [ ]:
AliceNewEll
In [ ]:
BobSharedEll
In [ ]:
E
In [ ]: