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): 
        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()
9532661852319730905237618111119755138721742033816477427264102992961790347658250107581497027936585530959163246331764668598827773591551
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()

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

1894289652774975650974900671306291756315094080778311977262575738262915229307706723216150481748412483111797098870195259179007
%%time
###################################SIKE##########################################
#----------------------------PRIME GENERATION------------------------------------
a, b = [8, 13] #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 21.3 ms, sys: 200 µs, total: 21.5 ms Wall time: 21.7 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^148 * 3^165 + (-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^7 where the biggest multiplicity of 3-subgroup is 8 Bob's secret Key is of order 2^12 where the biggest multiplicity of 2-subgroup is 13 CPU times: user 605 ms, sys: 7.88 ms, total: 613 ms Wall time: 646 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 1.2 s, sys: 14.1 ms, total: 1.22 s Wall time: 1.29 s
#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 121 ms, sys: 3.13 ms, total: 124 ms Wall time: 144 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 14.2 s, sys: 120 ms, total: 14.3 s Wall time: 16.5 s
%%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 12.9 s, sys: 65.3 ms, total: 12.9 s Wall time: 13.9 s
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 1592620442213299729227777122680709430802506463118738236119453726117214899705361598072508644927879699464240108363370819930240
q
1894289652774975650974900671306291756315094080778311977262575738262915229307706723216150481748412483111797098870195259179007
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)"""