#!/usr/bin/env python
# coding: utf-8

# # SIDH toy example
# 
# ## Public parameters

# In[1]:


p = 2^8*3^5 - 1
p.is_prime()


# In[2]:


_.<I> = GF(p)[]
K.<i> = GF(p^2, modulus=I^2+1)
K


# In[3]:


E = EllipticCurve(K, [1, 0])
E


# ## $2^8$-torsion generators

# In[4]:


Pa = E(0)
while (2^7)*Pa == 0:
    Pa = 3^5 * E.random_point()
Pa


# In[5]:


Qa = Pa
while Pa.weil_pairing(Qa, 2^8)^(2^7) == 1:
    Qa = 3^5 * E.random_point()
Qa


# Just for checking (Sage would be too slow on real world parameters)

# In[6]:


Pa.order(), Qa.order(), Pa.weil_pairing(Qa, 2^8).multiplicative_order()


# ## $3^5$-torsion generators

# In[7]:


Pb = E(0)
while (3^4)*Pb == 0:
    Pb = 2^8 * E.random_point()
Pb


# In[8]:


Qb = Pb
while Pb.weil_pairing(Qb, 3^5)^(3^4) == 1:
    Qb = 2^8 * E.random_point()
Qb


# Just for checking (Sage would be too slow on real world parameters)

# In[9]:


Pb.order(), Qb.order(), Pb.weil_pairing(Qb, 3^5).multiplicative_order()


# ## Alice

# In[10]:


Sa = randint(0, 2^8-1)
R = Pa + Sa * Qa
R


# **Warning:** This computation does not use the isogeny walk algorithm, will not scale to real size parameters

# In[11]:


phi = E.isogeny(R)
phi


# Public data sent to Bob

# In[12]:


Ea, phiPb, phiQb = phi.codomain(), phi(Pb), phi(Qb)
Ea, phiPb, phiQb


# ## Bob

# In[13]:


Sb = randint(0, 3^5-1)
R = Pb + Sb * Qb
R


# **Warning:** This computation does not use the isogeny walk algorithm, will not scale to real size parameters

# In[14]:


psi = E.isogeny(R)
psi


# Public data sent to Alice

# In[15]:


Eb, psiPa, psiQa = psi.codomain(), psi(Pa), psi(Qa)
Eb, psiPa, psiQa


# ## Key establishment

# In[16]:


Eb.isogeny(psiPa + Sa*psiQa).codomain().j_invariant()


# In[17]:


Ea.isogeny(phiPb + Sb*phiQb).codomain().j_invariant()


# ## Your turn, now: implement a real world example using

# In[18]:


p = 2^250 * 3^159 - 1
p.is_prime()


# ### 1. Write functions to generate torsion bases
# 
# Alternatively, you can take the official basis points [from the spec](https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/SIKE.zip).

# In[ ]:





# ### 2. Write an isogeny walk algorithm
# 
# You can either use a simple quadratic strategy using a for loop, or an advanced optimized strategy. See [the spec](https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/SIKE.zip) for both.

# In[ ]:





# ### 3. Write the key exchange functions for Alice and Bob
# 
# Do not forget to check that $j$-invariants match in the end.

# In[ ]:





# ### 4. Optional: optimize things
# 
# - Replace Sage's elliptic curve class with your own implementation of Montgomery curves.
# - Replace Sage's implementation of GF(p²) with your own implementation on top of `Zmod(p)`.
# 
# Do not forget to benchmarks things to see how much you gain!

# In[ ]: