Claw attack with p=17915903

p = 213 37 - 1 = 17915903. Number of supersingular j-invariants: 1492993, only showing 1312 of them.

Color legend: 2-isogenies, 3-isogenies, E0: y2 = x3 + x, Alice, Intermediate curves, E1.

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 213 + 212 possible private keys for Alice. The claw attack is an improvement on this.

What we can do is explore all curves connected to E0 via isogenies of degree 26 and store them in a hash table. After that, we may start a DFS exploration from EA bounded to depth 27 until we find a collision with the stored values, E1.

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