With pairing-based cryptography we have two cyclic groups (\(G_1\) and \(G_2\)), and which are of an order of a prime number (\(n\)). If \(P\) is a point on \(G_1\), and \(Q\) is a point on \(G_2\), we get a bilinear mapping for the pairing: \(\hat{e}(aP,bQ)=\hat{e}(bP,aQ)\). In this example, we will reduce the security strength of elliptic curve method, and use a pairing of \(\hat{e}(xP,Q)=\hat{e}(P,Q)^x\) using the BLS12-381 curve (as used in Ethereum 2.0, ZCash Sapling, Algorand, Dfinity, Chia, and Filecoin.
Cracking Elliptic Curves with the MOV Attack using Kryptology |
Background
In a classic paper, Menezes and Vanstone [1] defined how we could reduce the strength of the elliptic curve method to a discrete logarithm problem. It uses key pairing where we have two cyclic groups (\(G_1\) and \(G_2\)), and which are of an order of a prime number (\(n\)). A pairing on \((G_1,G_2,G_T)\) defines the function \(e:G_1 \times G_2 \rightarrow G_T\), and where \(g_1\) is the generator for \(G_1\) and \(g_2\) is the generator for \(G_2\). If we have the points of \(P\) on \(G_1\) and \(Q\) on \(G_2\), we get a pairing of:
\(\hat{e}(P,Q)\)
Now if we select a private key value of \(x\), and then the public key will become:
\(P_{pub}=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:
\(\hat{e}(xP,Q)=\hat{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 1000, and just use brute force to find \(x\). The outline coding using the library from the Kryptology library is:
package main import ( "fmt" "math/big" "os" "strconv" bls12381 "github.com/coinbase/kryptology/pkg/core/curves/native/bls12-381" ) func main() { val1 := int64(10) argCount := len(os.Args[1:]) if argCount > 0 { val1, _ = strconv.ParseInt(os.Args[1], 10, 64) } fmt.Printf("Value to find: a=%d\n\n", val1) bls := bls12381.NewEngine() g1, g2 := bls.G1, bls.G2 gt := bls.GT() a := big.NewInt(val1) G1, G2 := g1.One(), g2.One() P2 := g2.New() g2.MulScalar(P2, G2, a) e0, _ := bls.AddPair(G1, P2).Result() fmt.Printf("P1: %x\n", P2) for i := 1; i < 1000; i++ { ival := big.NewInt(int64(i)) e1, _ := bls.AddPair(G1, G2).Result() gt.Exp(e1, e1, ival) if e0.Equal(e1) { // e(G1,aG2) = e(G1,G2)^a fmt.Printf("We have found the value at %d\n", i) break } } }
A sample run:
Value to find: a=100 We have found the value at 100 Time: 322 uS
Coding
Reference
[1] Menezes, A. J., Okamoto, T., & Vanstone, S. A. (1993). Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, 39(5), 1639–1646.