SIKE Sage implementation non-optimized.ipynb

Kernel: SageMath (stable)

#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

######################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