Cracking Elliptic Curves with the MOV Attack
Elliptic Curve Cryptography (ECC) is wiping the floor with other key exchange, signing and encryption methods. Overall it is well defined for a scale up in security, and where a 256-bit ECC key is equivalent in security to a 3,072-bit RSA key. But ECC still has one weakness: the MOV Attack, and which uses pairing-based cryptography.
With key pairing we have two cyclic groups (G1 and G2), and which are of an order of a prime number (n). A pairing on (G1,G2,GT) defines the function e:G1×G2→GT, and where g1 is the generator for G1 and g2 is the generator for G2. If we have the points of P on G1 and Q on G2, we get a pairing of:
e(P,Q)
Now if we select a private key value of x, and then the public key will become:
Ppub=xP
In order to find x, we would have to search the values of x to match P to x. In pairing, we can reduce the difficulty with:
e(xP,Q)=e(P,Q)^x
This now becomes a discrete logarithm problem within a finite field, and which makes it easier to find x.
Coding
Let’s keep it simple by generating a value of x between 0 and 4096, and just use brute force to find x. The outline coding using the library from the MIRACL library [here] is:
