Isogenies

Isogeny-based cryptography is a relatively new area of cryptography which began in the early 2000s with work by Couveignes (which was unpublished for more than a decade) and Rostovtsev and Stolbunov, who worked with hard homogenous spaces and isogeny-based protocols. Due to the mathematical complexity of the area, it's a fairly intimidating topic for many young researchers, but the mathematical richness is also a beautiful and alluring aspect which has driven a lot of research attention for the past twenty years.

Of particular interest to cryptographers are supersingular elliptic curves. Considering the collection of isogenies between these curves as a graph, with (isomorphism classes) of curves as nodes and isogenies as edges, supersingular isogeny graphs have particular properties which make them attractive to designing asymmetric cryptographic primitives where public values are the start and end nodes, and the secret values are the paths between them.

In 2022, isogeny-based cryptography went through its "second-wave" when it was shown that the isogeny-based key exchange mechanism known as "SIDH" could be broken in polynomial time thanks to work by the mathematician Kani from a paper published in 1996. As SIKE (built form SIDH) was a fourth-round candidate in the NIST post-quantum cryptography project, the complete break of the most well-known isogeny-based primitive has had a big impact on isogeny-based primitives.

In a post-SIDH world, isogeny-based cryptography is now experiencing rapid progress in many different primitives thanks to constructive applications of the SIDH attack. One of the first descriptions of this is the PKE FESTA, and the variant QFESTA. More recently, an updated version of SQIsign (a digital signature algorithm currently in the NIST competition) was published which used work based on the SIDH-attack to dramatically improve performance of key generation, signing and verification.


Introduction

Toggle
  • Introduction to Isogenies
    10 pts · 295 Solves
    Before beginning this section you should have attempted many of the challenges in the "Elliptic Curves" section and completed the starter challenges.

    Welcome to the isogeny section of cryptohack!

    Disclaimer: throughout the following challenges there will be (at times) slightly relaxed notation / statements. Sometimes this will be an accident and the challenges may be modified and improved over time. Other times it will be done on purpose with the hope of losing some mathematical rigour in the description with the hope to build intuition. We're aware that not everyone likes learning this way, but a more formal education of isogenies are available from textbooks and lecture notes which we link throughout.

    Isogenies between elliptic curves, at their heart, are two things. Firstly, they are rational maps between elliptic curves (a surjective morphism). They don't just map between curves though, they also preserve the group structure from the domain to the codomain of the map. This means they are also group homomorphisms (they are a non-constant rational map which fixes the point at infinity). We denote an isogeny $\phi$ with domain $E$ and codomain $E'$ as $\phi : E \to E'$.

    For most of what follows, we will be concerned with separable isogenies, for which the degree of the map is exactly equal to the size of the kernel (the kernel is the set of points on the domain mapped to the point at infinity on the codomain). The mathematics of isogenies extends far beyond cryptographic applications (and certainly beyond these sets of challenges), but generally we will want to do two things. The first is given a subgroup $H$ of points, we will want to be able to compute an isogeny with kernel $H$ (and so of degree $\#H$). The second thing we will want to do is to take any point on the domain and evaluate the isogeny at this point to find a corresponding point on the codomain. If you can do these two things, you can implement most of what you need for isogeny-based cryptography (narrator: this is dramatically over-simplified).

    Understanding why we do certain combinations of these calculations and why we consider them useful for asymmetric cryptography is much more complicated. We hope a small amount of intuition comes from solving these challenges but let us also discuss a little bit about what we think is a hard problem in isogeny based cryptography and what problems we have efficient solutions for.

    The cryptographic side of isogenies comes from considering long paths of isogenies between many different elliptic curves. If we fix some prime $\ell$, then the $\ell$-isogeny graph is a graph whose vertices are (isomorphism classes) of elliptic curves and the edges are isogenies of degree $\ell$ (the polynomials appearing in the rational map have maximum degree $\ell$). Generally, when we consider the isogeny graphs of supersingular elliptic curves, we end up with a horrible mess of a graph, where you can take relatively short walks through the graph and get totally lost (this is true for SIDH, but for CSIDH we restrict to a special set of isogenies and the graphs have more structure and look more beautiful).

    When $\ell$ is small, we can compute an $\ell$-isogeny efficiently. We can walk through the graph by computing many $\ell$-isogenies and end up on some vertex. The idea of isogeny-based cryptography is to use this path of isogenies as a secret key and the start and end nodes as a public key. Protocols are built by taking secret walks between curves, exchanging these curves (and sometimes additional data) and then repeating this walk to end up on a shared secret vertex on the graph for which no one else knows. This vertex can then be used to create symmetric keys just like secret points on elliptic curves can be used in the ECDH key exchange.

    In this series of challenges you will first learn a few background tricks before setting out to implement two key exchange protocols: SIDH and CSIDH. The last challenges in the section are more CTF-like and should give you some fun isogeny-based puzzles to get additional experience and intuition for working with these maps. There are many other isogeny-based cryptographic primatives (such as SQIsign, the CGL hash function and more exotic things like verifiable delay functions). Introductions to these topics may appear at a later date.

    There are two ways we think you can approach solving the following challenges. For those who want to get a surface level understanding, a great way to start is to try and solve the challenges using all the various functions available in SageMath. This will avoid needing to worry about the gritty details of isogenies and algebraic geometry and should get you some practical experience useful for solving CTF challenges.

    Alternatively, we have tried to include as many resources as we can through the starter challenges. For a focused student, these should set you on the right path to really appreciate the subject and give practical experience with the engineering required to compute isogenies efficiently. Of course another option is to do both! Work with SageMath to verify your understanding and then start coding things yourself.

    If you use Discord, then the channel #isogeny-school (Discord Invite) is a great place to ask for more details about isogeny based cryptography. We hope to see you there!

    Below are a few general resources which we found useful ourselves while learning about this subject. Specific resources are also attached to challenges so don't feel like you need to read all of the below before starting — dive in!

    For the flag of this wall of text, what would the size of a kernel be for a separable isogeny of degree 65537?

    Resources:
      - Mathematics of Isogeny Based Crypto, Luca De Feo, Marc Houben
      - Elliptic Curves, Lecture Notes, Andrew Sutherland
      - Cryptography on Isogeny Graphs, Lorenz Panny
      - Supersingular isogeny key exchange for beginners, Craig Costello

    You must be logged in to submit your flag.



Starter

Toggle
  • The j-invariant
    20 pts · 257 Solves · 2 Solutions
    Much like in modular arithmetic, where many computations are only equal up to an equivalence modulo N, in isogeny based-cryptography, many computations are only equal up to isomorphism. For two participants in a protocol, it's not enough to compare curve equations but instead they check whether two curves are isomorphic.

    One way of determining whether two curves are isomorphic is by comparing an invariant of the curve. For elliptic curves we use the "j-invariant", denoted $j(E)$, which is what we will be computing for this challenge.

    There is a subtle point here. If two curves are isomorphic, they have the same j-invariant, but if two curves have the same j-invariant they may not be isomorphic over the base field, but instead over some extension. An example of this is two curves related by a quadratic twist. The curves will have the same j-invariant but are only isomorphic over a quadratic extension.

    To grab the flag for this challenge, compute $j(E)$ of the supersingular curve:

    $E : y^2 = x^3 + 145 x + 49 \mod 163$

    Resources:
      - Ordinary and supersingular elliptic curves, Section 13.2, Andrew Sutherland

    You must be logged in to submit your flag.


  • Where's the Supersingular Curve
    25 pts · 214 Solves · 2 Solutions
    For the majority of this category (and all challenges at the time of writing) we are interested in computing isogenies between supersingular curves. Cryptographically, we are interested in supersingular elliptic curves because the $\ell$-isogeny graph for supersingular elliptic curves are $(\ell+1)$-regular graphs (each vertex on the graph has $\ell + 1$ neighbours) as well as Ramanujan graphs with optimal expansion properties. Essentially this means it is easy to get lost walking randomly around the graph, and hard isogeny problems are based on the fact that knowing the beginning and end of these walks is not enough to recover the path itself.

    Mathematically, the name "supersingular" came from the fact that the endomorphism ring of these elliptic curves are "super-sized". They're not singular curves (all elliptic curves are non-singular!) but the "singularity" part of this comes from "special" (or rare) rather than singular in the geometric sense. In higher dimension we talk about superspecial abelian varieties and really this makes sense for elliptic curves too! These supersingular curves are very special and for very large characteristic, happening upon a supersingular curve is extremely unlikely (probability $p^{-1}$). An open problem is how to hash to a random supersingular curve!

    For this challenge there is a list of curves to pick from — can you identify the supersingular elliptic curve? Unironically, the wikipedia resource below is a great start and we've also included some lecture notes by Andrew Sutherland which are a fantastic resource.

    The flag is the Montgomery coefficient A of the supersingular elliptic curve in the list of curves provided.

    Challenge files:
      - curves.sage

    Resources:
      - Ordinary and supersingular elliptic curves, Section 13.2, Andrew Sutherland
      - Supersingular elliptic curve, Wikipedia

    You must be logged in to submit your flag.


  • Image Point Arithmetic
    30 pts · 202 Solves · 4 Solutions
    As mentioned in the introduction, an isogeny is not only a rational map between curves, but also a map which preserves the group structure on these curves. This means that even if the isogeny $\phi : E \to E'$ is unknown, given $\phi(P)$ and $\phi(Q)$ one can determine the result of $\phi(P + Q)$.

    Something to think about: imagine you had access to an oracle which evaluated points under the action of an isogeny $\phi : E \to E'$. Could you use this to determine the kernel of the secret isogeny?

    To solve this challenge, compute the $x$-coordinate of the point $\phi(P + Q)$ given the following data, where $\phi : E \to E'$ is an isogeny between elliptic curves in the short Weierstrass model:

    $\phi(P) = (48622, 27709), \quad \phi(Q) = (9460, 13819), \quad p = 63079$

    Resources:
      - Isogenies, Lecture Notes, Andrew Sutherland

    You must be logged in to submit your flag.


  • Montgomery Curves
    30 pts · 184 Solves · 2 Solutions
    Here's an isogeny challenge which many of you may have already solved before. An isomorphism between elliptic curves is an isogeny of degree one, and a common isomorphism one might compute is mapping from one curve model to another.

    In this challenge, you are given a curve in short Weierstrass form: $E : y^2 = x^3 + ax + b$ and the goal is to find the Montgomery model of the curve: $E_M : y^2 = x^3 + Ax^2 + x$. The flag is the Montgomery coefficient A.

    $E : y^2 = x^3 + 312589632 x + 654443578 \mod 1912812599$

    Hint: a point of order two on a Montgomery curve is $(0 : 0 : 1)$, to find an isomorphism from a curve to Montgomery form, look at the transformation you need to send a point of order two to this so-called "Montgomery point".

    You must be logged in to submit your flag.


  • DLOG on the Surface
    40 pts · 140 Solves · 5 Solutions
    For the isogenies we compute together, we'll generally be computing the isogeny from a kernel generated by a single point. For an isogeny of degree n, we'll have a point of order $n$. For supersingular elliptic curves over $\Fpp$ the abelian group of points on the curve is isomorphic to $\mathbb{Z}/(p+1) \times \mathbb{Z}/(p+1)$. When we look at the torsion subgroup $E[n]$ it will have two generators $(P, Q)$, both of order $n$, and commonly a kernel generator will be of the form $[a]P + [b]Q$ for some fixed basis.

    In elliptic curve Diffie-Hellman, we work on curves where solving the discrete log for $P = [x]Q$ is hard. However for isogeny-based cryptography we usually require that the order of the curve, $p+1$ is smooth and the discrete log problem is easy. What we compute more often though is a two-dimensional discrete log to relate torsion bases.

    For this challenge we will give you two torsion bases: $(P, Q)$ and $(R, S)$. The goal of the challenge is to find integers $(a, b, c, d)$ such that $R = [a]P + [b]Q$ and $S = [c]P + [d]Q$.

    Challenge files:
      - source.sage
      - output.txt

    Resources:
      - Isogeny kernels and division polynomials, Lecture Notes, Andrew Sutherland

    You must be logged in to submit your flag.



Road to SIDH

Toggle
  • Two Isogenies
    30 pts · 148 Solves · 1 Solutions
    It's time to compute our first two-isogeny! In this set of challenges we will work our way towards implementing (and then breaking!!) the supersingular isogeny Diffie-Hellman protocol (SIDH).

    Note: for all of the following challenges we will be working with the finite field $\Fpp$. Where $p \equiv 3 \mod 4$. We will use the modulus $i^2 + 1$ so elements of the field will be of the form $x = a + ib$ for $a, b < p$. In SageMath you can create this field with F = GF(p**2, names="i", modulus=[1,0,1]).

    In this challenge, your goal is to compute the two-isogeny with domain $E$ and kernel generated by $K$:

    $E : y^2 = x^3 + x, \quad K = (i, 0), \quad p = 2^{18} \cdot 3^{13} - 1$

    The flag for this challenge is the j-invariant $j(E^\prime)$ of the codomain of this isogeny: $\phi_2 : E \to E^\prime$.

    In the resources we offer two options. Sutherland's lecture notes, in particular Theorem 5.13 will help you compute prime degree isogenies. If you want a more computational paper, then Renes' paper is a fantastic resource. Good luck!

    Resources:
      - Isogeny kernels and division polynomials, lecture notes, Andrew Sutherland
      - Computing isogenies between Montgomery curves using the action of (0,0), Joost Renes

    You must be logged in to submit your flag.


  • Three Isogenies
    35 pts · 147 Solves · 1 Solutions
    This challenge is very similar to the previous one, only now the isogeny is going to be a three isogeny, and the kernel you will be given is generated by a point of order three. For the two-isogeny, we only needed the single point (as it had order two) but to compute the three isogeny we will need to know the points $K, [2]K$.

    For this challenge, your goal is to compute the three-isogeny with domain $E$ and kernel generated by $K$:

    $E : y^2 = x^3 + x, \quad K = (483728976, 174842350631), \quad p = 2^{18} \cdot 3^{13} - 1$

    The flag for this challenge is the j-invariant $j(E')$ of the codomain of this isogeny: $\phi_3 : E \to E^\prime$.

    If you used Sutherland's notes for the previous challenge then a lot of your code should be able to be reused. If you used Renes' code for the last one then we've included a paper by Costello and Hisil which is a fantastic introduction to computing odd-degree isogenies.

    Resources:
      - Isogeny kernels and division polynomials, lecture notes, Andrew Sutherland
      - A simple and compact algorithm for SIDH with arbitrary degree isogenies, Craig Costello and Huseyin Hisil

    You must be logged in to submit your flag.


  • Composite Isogenies
    60 pts · 140 Solves · 4 Solutions
    You may have noticed two things so far. One is that the algorithms you're using are linear in the degree of the isogeny (for a degree n-isogeny generated by a point of order n, we need to compute all n multiples of the kernel. The second is that the shape of the prime tells you all rational points will have order dividing $2^{18} \cdot 3^{13}$, which have smooth order.

    It turns out that for composite degree isogenies, we can compute an isogeny of order $n = p_0^{e_0} \cdot p_1^{e_1} \cdot \ldots \cdot p_k^{e_k}$, by chaining $e_0$ isogenies of degree $p_0$, followed by $e_1$ isogenies of degree $p_1$ and so on. This is significantly faster than enumerating all $n$ multiples of the kernel generator!!

    For an isogeny $\phi : E \to E'$, we know evaluating a point in the kernel through this isogeny will give us the identity point. If we take the kernel generator $K$ and scale it to have order $p_0$, then we can compute the isogeny $\phi_0$ of degree $p_0$ and if we evaluate the kernel generator $K' = \phi_0(K)$ we will have a point of order $p_0^{e_0 - 1} \cdot p_1^{e_1} \cdot \ldots \cdot p_k^{e_k}$. We can do this for every prime one by one until we have computed the entire isogeny chain.

    For this challenge, your goal is to compute the $3^{13}$-isogeny with domain $E$ and kernel generated by $K$:

    $E : y^{2} = x^{3} + x, \quad K = (357834818388i + 53943911829, 46334220304i + 267017462655), \quad p = 2^{18} \cdot 3^{13} - 1$

    Resources:
      - Supersingular isogeny key exchange for beginners, Craig Costello
      - Mathematics of Isogeny Based Crypto, Luca De Feo, Marc Houben

    You must be logged in to submit your flag.


  • SIDH Key Exchange
    80 pts · 133 Solves · 2 Solutions
    By this point you should be able to efficiently compute an isogeny of large smooth degree and compute the image of points through this isogeny. This is everything which you need to implement the SIDH protocol.

    The public parameters of SIDH are a starting curve $E_0$ and two sets of torsion bases $E[2^{e_A}] = (P_2, Q_2)$ and $E[3^{e_B}] = (P_3, Q_3)$.

    For the public key generation, Alice computes an isogeny $\phi_A : E_0 \to E_A$ generated by the point $K_A = P_2 + [s_A]Q_2$ of order $2^{e_A}$ and computes the images $\phi_A(P_3), \phi_A(Q_3)$. Alice sends Bob $E_A, \phi_A(P_3), \phi_A(Q_3)$ and keeps $s_A$ as her secret key.

    Bob does something very similar. He computes an isogeny $\phi_B : E_0 \to E_B$ generated by the point $K_B = P_3 + [s_B]Q_3$ of order $3^{e_B}$ and computes the images $\phi_B(P_2), \phi_B(Q_2)$. Bob sends Alices $E_B, \phi_B(P_2), \phi_B(Q_2)$ and keeps $s_B$ as his secret key.

    The shared secret comes from a second isogeny they compute. Alice computes an isogeny $\phi_{SA} : E_B \to E_{SA}$ with kernel generated by $K_{SA} = \phi_B(P_2) + [s_A]\phi_B(Q_2)$. Bob does something very similar by computing an isogeny $\phi_{SB} : E_A \to E_{SB}$ with kernel generated by $K_{SB} = \phi_A(P_3) + [s_B]\phi_A(Q_3)$. The shared secret is the j-invariant of the codomain: $j(E_{SA}) = j(E_{SB})$.

    These four isogenies form a commutative diagram. Using that isogenies are group homomorphisms and that 2 and 3 are coprime, can you see why $E_0 \to E_A \to E_{SB}$ and $E_0 \to E_B \to E_{SA}$ have isomorphic codomains?

    Complete the below source file and use the j-invariant to decrypt the flag!

    Challenge files:
      - source.sage

    Resources:
      - Supersingular isogeny key exchange for beginners, Craig Costello
      - Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, Luca De Feo, David Jao, Jérôme Plût

    You must be logged in to submit your flag.


  • Breaking SIDH
    250 pts · 73 Solves · 1 Solutions
    The SIDH protocol is a great way to learn some of the machinery of isogeny-based cryptography, but in 2022 it was shown to be broken in polynomial time by a series of papers (the paper by Castryck and Decru appeared online first, only a week before the following two papers which further broke more general protocols).

    Given only the public data of an SIDH protocol can you recover the shared secret and decrypt the flag?

    You may notice the prime used here: $p = 45 \cdot 2^{117} \cdot 3^{73} - 1$ is different to the previous challenges. This has been done on purpose to simplify the attack! Read the resources and you should see why.

    Setting the score for this challenge is very hard. The whole attack implemented without help is very challenging and was first done in SageMath as a team effort in our discord chat (see the resources below). On the other hand, there's now a few different implementations of the attack on GitHub which do a lot of the work for you. Our advice here is to spend as much time as you want on this project and if you rely on tools for the flag, maybe come back another day and try implementing certain steps yourself. It's a beautiful topic and the main reason I (Jack) am so interested in the topic today. It's also the cornerstone of many new advanced isogeny primitives such as SQIsign2D, FESTA and SCALLOP-HD.

    Challenge files:
      - source.sage

    Resources:
      - An efficient key recovery attack on SIDH, Wouter Castryck, Thomas Decru
      - A Direct Key Recovery Attack on SIDH, Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, Benjamin Wesolowski
      - Breaking SIDH in polynomial time, Damien Robert
      - A Note on Reimplementing the Castryck-Decru Attack and Lessons Learned for SageMath, Rémy Oudompheng, Giacomo Pope
      - You could have broken SIDH, Lorenz Panny

    You must be logged in to submit your flag.



Road to CSIDH

Toggle
  • Special Isogenies
    30 pts · 120 Solves · 2 Solutions
    For the SIDH challenges, the torsion basis $E[n] = \langle P, Q \rangle$ had two generators and we could compute many kernel generators which were linearly independent. This meant for large n we had a huge number of isogenies to pick from when walking through the graph. The downside was that to have a commutative key exchange, it was not enough to send the codomain but also the image of a torsion bases through the secret isogeny. This additional information ultimately led to the polynomial time break of the SIDH protocol.

    CSIDH on the other hand works with supersingular elliptic curves over the field $\Fp$. This radically changes the supersingular isogeny graph. One consequence of this is that $E(\Fp) = \mathbb{Z}/(p+1)$; there is a unique order $\ell$-subgroup which generates an $\ell$-isogeny.

    If you have seen pictures of the CSIDH isogeny graphs, you may remember that each vertex has two edges. Although both of these edges are $\Fp$ rational isogenies (their codomains are curves $E/\Fp$), they are not both generated by $\Fp$ rational points. We will learn more about this later in "Twisted CSIDH Isogenies". For now, work under the assumption that all isogenies we compute are generated by rational points $P$ of order $\ell$ on $E/\Fp$.

    Let's look at this practically. Take the below curve and compute any point of order 5. Use this point to compute an isogeny of degree 5 and look at the curve equation. Now compute another point of order 5 and repeat the calculation. What do you see?

    To solve this challenge, compute the codomain of a degree 5 isogeny in the Montgomery model. The flag is the Montgomery coefficient A.

    $E_0 : y^{2} = x^{3} + x \mod 419$

    Resources:
      - Isogenies: The basics, some applications, and nothing much in between, Lorenz Panny
      - A simple and compact algorithm for SIDH with arbitrary degree isogenies, Craig Costello and Huseyin Hisil

    You must be logged in to submit your flag.


  • Prime Power Isogenies
    50 pts · 120 Solves · 3 Solutions
    For SIDH, we used a prime of the form $p = 2^{e_A} \cdot 3^{e_B} - 1$ and we computed isogenies of degree $\ell^{e}$ by finding a point of order $\ell^{e}$ and using this as a generator.

    The characteristic for CSIDH primes is instead a product of many small primes with exponent equal to one. To compute a $\ell^{e}$ isogeny in CSIDH, one should instead compute a point of order $\ell$, then compute the codomain of the isogeny generated by this point and repeat the whole process $e$ times.

    Let's explore the structure of the $\ell$-isogeny graph in CSIDH by computing repeated $\ell$-isogenies. Take the below starting curve and compute a degree $5^{9}$ isogeny. Compare this to your starting curve. What do you see?

    $E_0 : y^{2} = x^{3} + x \mod 419$

    To solve this challenge, calculate how many 7-isogenies you must take from the below curve to end up back on the starting curve!

    You may have already noticed that $p + 1 = 2^2 \cdot 3 \cdot 5 \cdot 7$. Take this opportunity to look at the isogeny graphs for $\ell = 3, 5, 7$. If you are a visual learner and use SageMath, take a look at the function isogeny_ell_graph().

    Resources:
      - Isogenies: The basics, some applications, and nothing much in between, Lorenz Panny
      - A simple and compact algorithm for SIDH with arbitrary degree isogenies, Craig Costello and Huseyin Hisil

    You must be logged in to submit your flag.


  • Secret Exponents
    60 pts · 112 Solves · 2 Solutions
    In the CSIDH key exchange, a private key is a list of integers as long as the number of odd primes dividing $(p+1)$. This data represents an exponent vector $[e_0, e_1, e_2, ..., e_k]$ which dictates the path of Alice and Bob's secret isogenies.

    Before implementing CSIDH let us begin by computing an isogeny with the secret vector $[2,3,4]$ from the starting curve

    $E_0 : y^{2} = x^{3} + x \mod 419$

    The flag for this challenge is the Montgomery coefficient A of the codomain.

    Essentially what this challenge is asking you to do is compute an isogeny of degree $n = 3^{2} \cdot 5^{3} \cdot 7^{4}$. You will need this code again throughout this section, think about how to write this efficiently so you can generalise it to other vectors and other characteristics!

    You must be logged in to submit your flag.


  • Twisted CSIDH Isogenies
    70 pts · 111 Solves · 1 Solutions
    In the challenge "CSIDH prime power isogenies" we explored the $\ell$-isogeny graphs for the curves we use in CSIDH and saw that they were cyclic. We were able to compute how many vertices there were in the graph and effectively walk all the way around until we reached the starting node again.

    We also know that given some point of order $\ell$ on the curve, there seems to be only one way to walk from each node and that this graph is directed. This challenge is about how we can effectively (and efficiently) take one step "backwards" on the graph. This means if the $\ell$-isogeny graph has k nodes, instead of computing k-1 $\ell$-isogenies to go backwards we can compute just a single isogeny in the other direction.

    To do this, we will need to be able to compute the quadratic twist $E^{t}$ of a curve. Look at this curve in Montgomery form. Notice that it is not isomorphic to $E$. Compute their j-invariants. Compute their order, are they isogenous?

    To walk backwards on the graph we temporarily work on the quadratic twist. Practically, to walk one step backwards we map $E \to E^t$. From this twisted curve, we compute as normal an isogeny of degree $\ell$ using a point of order $\ell$ on the twisted curve. Then, we untwist the codomain (by computing a second quadratic twist) to finish the computation.

    To test your code, use the solution of "CSIDH prime power isogenies" and compare the result of taking $k-1$ "forward" 7-isogenies and a single "backwards" isogeny.

    Note: if you are computing x-only isogenies you do not need to explicitly compute the twist, but instead compute random $x$-coordinates in $\Fp$. A point is on $E$ when $x^{3} + Ax^{2} + x$ is a square and $E^t$ when it is not. From this, we see that checking the squareness of $y^{2}$ is enough to determine if you will take a step forwards or backwards when this $x$-only point is used to compute an isogeny.

    To compute the flag, walk one step "backwards" on the three-isogeny graph from the below curve. The flag is the Montgomery coefficient of this curve.

    $E_0 : y^{2} = x^{3} + x \mod 419$

    In the CSIDH exponent vector, when an integer is positive we take $e$ steps from the curve on the $\ell$-isogeny graph. When the integer is negative, we take $e$ steps from the quadratic twist of the curve on the $\ell$-isogeny graph.

    Resources:
      - The quadratic twist of an elliptic curve, Section 7.6, Andrew Sutherland
      - Isogenies: The basics, some applications, and nothing much in between, Lorenz Panny

    You must be logged in to submit your flag.


  • CSIDH Key Exchange
    90 pts · 105 Solves · 2 Solutions
    You are now ready to implement a full CSIDH key exchange! In the source file you are given a prime modulus, a starting curve $E_0$, an array of odd primes and two arrays of private keys with values between $\pm 3$.

    The secret isogeny is computed by stepping "forward" with $e$ $\ell$-isogenies when $e$ is positive, and stepping backwards when $e$ is negative. Note that it doesn't matter which order you compute these steps (all the $\ell$ are coprime) and it is the commutativity of these $\ell$-isogenies which you will compute which allows us to use these isogenies to build a non-interactive key exchange.

    This means, given some exponent vector, a public key is set as the Montgomery coefficient A after computing the corresponding isogeny from $E_0$. If Alice and Bob compute their public keys and then compute the same isogeny (same exponent vector) from each others public curves, they effectively will have walked from $E_0$ with an isogeny computed from the sum of their two secret exponent vectors. As addition is associative, so is CSIDH (there's a lot more to this fact) and the codomain of their second isogenies will match. Their shared secret is then the Montgomery coefficient of this final curve.

    To get the flag, use the private keys provided to compute Alice and Bob's public keys. Send these keys between the two parties and then compute the shared secret. Use this to decrypt the flag and finish the section! Good Luck and well done with the hard work :)

    Challenge files:
      - source.sage

    Resources:
      - CSIDH: An Efficient Post-Quantum Commutative Group Action, Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes

    You must be logged in to submit your flag.



Isogeny Challenges

Toggle

Level Up

level up icon

You are now level Current level