Supersingular Isogeny Diffie-Hellman¶

Toy implementation of the historical SIDH scheme. This implementation serves as an example of a class that implements KeyExchangeBase rather than CommutativeKeyExchangeBase.

Warning

This is a toy implementation of a broken cryptographic scheme for educational use only! Do not use this implementation, or any cryptographic features of Sage, in any setting where security is needed!

AUTHORS:

Taha Hedayat (2025-12-09): initial version
Vincent Macri (2026-01-13): parameter set generation and cleanup

class sage.crypto.public_key.key_exchange.sidh.SIDH(E: EllipticCurve_finite_field, PA: EllipticCurvePoint_finite_field, QA: EllipticCurvePoint_finite_field, PB: EllipticCurvePoint_finite_field, QB: EllipticCurvePoint_finite_field)[source]¶

Bases: KeyExchangeBase

Supersingular isogeny Diffie-Hellman key exchange.

This implementation uses the notation of [Cos2020].

For an easier-to-use constructor, see parameter_set_from_prime() which implements parameter set generation as described in [Jao2022].

EXAMPLES:

This example comes from [Cos2020].:

sage: e_A = 4
sage: e_B = 3
sage: p = 2^e_A * 3^e_B - 1
sage: K.<i> = GF(p^2, modulus=x^2 + 1)
sage: a0 = 329 * i + 423
sage: E = EllipticCurve(K, [0, a0, 0, 1, 0])
sage: PA = E(100 * i + 248, 304 * i + 199)
sage: QA = E(426 * i + 394, 51 * i + 79)
sage: PB = E(358 * i + 275, 410 * i + 104)
sage: QB = E(20 * i + 185, 281 * i + 239)
sage: toy_sidh = key_exchange.SIDH(E, PA, QA, PB, QB)
doctest:...: FutureWarning: SageMath's key exchange functionality is experimental and might change in the future.
             See https://github.com/sagemath/sage/issues/41218 for details.
sage: TestSuite(toy_sidh).run()

alice_compute_shared_secret(alice_secret_key, bob_public_key)[source]¶: Compute the shared secret using Alice’s secret key and Bob’s public key.

alice_public_key(alice_secret_key)[source]¶

Generate a valid public key for Alice.

INPUT:

alice_secret_key – Alice’s secret key that will be used to generate
the public key

OUTPUT:

Alice’s public key as a tuple \((E_A, P'_B, Q'_B)\).

alice_secret_key()[source]¶

Generate Alice’s secret key.

EXAMPLES:

sage: toy_sidh = key_exchange.SIDH.named_parameter_set('toy')
sage: 0 <= toy_sidh.alice_secret_key() <= 2^4 - 1
True

bob_compute_shared_secret(bob_secret_key, alice_public_key)[source]¶: Compute the shared secret using Bob’s secret key and Alice’s public key.

bob_public_key(bob_secret_key)[source]¶

Generate a valid public key for Alice.

INPUT:

alice_secret_key – Alice’s secret key that will be used to generate
the public key

OUTPUT:

Bob’s public key as a tuple \((E_B, P'_A, Q'_A)\).

bob_secret_key()[source]¶

Generate Bob’s secret key.

EXAMPLES:

sage: toy_sidh = key_exchange.SIDH.named_parameter_set('toy')
sage: 0 <= toy_sidh.bob_secret_key() <= 3^3 - 1
True

classmethod named_parameter_set(name)[source]¶

Return an SIDH instance corresponding to a named parameter set.

INPUT:

name – one of the following:
- "toy": a small SIDH instance over \(\GF{431^2}\),
  this toy example is from [Cos2020].
- "p434": SIDH instance with the same parameters
  as SIKEp434 from [Jao2022].
- "p503": SIDH instance with the same parameters
  as SIKEp503 from [Jao2022].
- "p610": SIDH instance with the same parameters
  as SIKEp610 from [Jao2022].
- "p751": SIDH instance with the same parameters
  as SIKEp751 from [Jao2022].

classmethod parameter_set_from_prime(prime)[source]¶

Generate an SIDH instance from the specified prime, generating the parameter set as in [Jao2022].

EXAMPLES:

sage: key_exchange.SIDH.parameter_set_from_prime(431)
SIDH with parameter set: (431, Elliptic Curve defined by y^2 = x^3 + 6*x^2 + x over Finite Field in i of size 431^2, ...

parameters()[source]¶

Return the parameter set of the SIDH instance.

OUTPUT:

A tuple (\(E\), \(PA\), \(QA\), \(PB\), \(QB\)) where:

\(p\) is the characteristic of the finite field \(\GF{p^2}\)
\(E\) is the starting curve
\(PA\) and \(QA\) are the generators for Alice’s secret key
\(PB\) and \(QB\) are the generators for Bob’s secret key

secret_isogeny_path(start_curve, secret_key, P, Q)[source]¶

Compute the secret isogeny and path of j-invariants. The kernel of returned isogeny is generated by P + secret_key * Q.

The purpose of this method is to demonstrate how implementations of KeyExchangeBase may implement additional methods besides those defined in KeyExchangeBase that compute some additional interesting information, in this case the path of j-invariants.

INPUT:

start_curve – the starting curve
secret_key – the secret key
P – first basis point
Q – second basis point

OUTPUT:

A tuple (iso, path) where iso is an elliptic curve isogeny with kernel generated by P + secret_key * Q and path is a list of the j-invariants of the isomorphism classes of the curves on the isogeny path.

EXAMPLES:

We work through the key generation example from [Cos2020]:

sage: toy_sidh = key_exchange.SIDH.named_parameter_set('toy')
sage: p, E0, PA, QA, PB, QB = toy_sidh.parameters()
sage: alice_secret_key = 11
sage: phi_A, alice_keygen_path = toy_sidh.secret_isogeny_path(E0, alice_secret_key, PA, QA)
sage: alice_keygen_path
[87*i + 190, 107, 344*i + 190, 350*i + 65, 222*i + 118]
sage: bob_secret_key = 2
sage: phi_B, bob_keygen_path = toy_sidh.secret_isogeny_path(E0, bob_secret_key, PB, QB)
sage: bob_keygen_path
[87*i + 190, 106*i + 379, 325*i + 379, 344*i + 190]