Claw attack with p=17915903

p = 2¹³ 3⁷ - 1 = 17915903. Number of supersingular j-invariants: 1492993, only showing 1312 of them.

Color legend: 2-isogenies, 3-isogenies, E₀: y² = x³ + x, Alice, Intermediate curves, E₁.

Explanation

If we wanted to brute-force attack an SIDH public key, we could try every possible private key (m, n). In our example, there are 2¹³ + 2¹² possible private keys for Alice. The claw attack is an improvement on this.

What we can do is explore all curves connected to E₀ via isogenies of degree 2⁶ and store them in a hash table. After that, we may start a DFS exploration from E_A bounded to depth 2⁷ until we find a collision with the stored values, E₁.

This way, we will recover the secret isogeny that Alice has as secret.