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\).
Cracking Elliptic Curves with the MOV Attack using Rust |
Background
With key pairing 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 4096, and just use brute force to find \(x\). The outline coding using the library from the MIRACL library is
extern crate rand_core; use mcore::bn254::big; use mcore::bn254::ecp; use mcore::bn254::ecp2; use mcore::bn254::fp2; use mcore::bn254::pair; use mcore::bn254::rom; use mcore::rand::{RAND,RAND_impl}; use rand::Rng; use std::env; fn get_random() ->RAND_impl{ let random_bytes = rand::thread_rng().gen::<[u8; 32]>(); let mut rng = RAND_impl::new(); rng.seed(32, &random_bytes); rng } fn main() { let mut rng = get_random(); let val:isize=4096; let mut q = big::BIG::new_int(val); let x = big::BIG::randomnum(&q, &mut rng); println!("\nSecret: {}\n",x.to_string()); let P = ecp::ECP::generator(); let Q = ecp2::ECP2::generator(); let xP = pair::g1mul( &P, &x); let RHS = pair::at\hat{e}(&Q,&P); let RHS=pair::fexp(&RHS); let LHS = pair::at\hat{e}(&Q,&xP); let LHS=pair::fexp(&LHS); println!("Pairing \hat{e}(Q,P) (first 20 bytes):\t{}\n",RHS.to_string()); println!("Pairing \hat{e}(Q,xP) (first 20 bytes):\t{}\n",LHS.to_string()); for i in 1..4096 { let pair2=RHS.pow(&big::BIG::new_int(i)); if (LHS.equals(&pair2)) { println!("\nFound it {}\n",&big::BIG::new_int(i)); // break; } }
A sample run:
Secret: 0000000000000000000000000000000000000000000000000000000000000D76 Pairing \hat{e}(Q,P) (first 20 bytes): [[[0D8A793B0DEFAEF46557B6694E97514CC17A5EF2A410A979113E53D0644F9A5A,1FF35A6F3BD5E17C32B319111480F860B6572335300A6F07EEC69FC89A586BE7],[17224135A9A5FB3989C3F4E890C01FF14C2F25BC365500E6CFA5BEACF99C030B,1E3FABD61BE8363430F4B6A50EF66F4DBDE24FD135BFBBCE2E3E515D6F382BD5]],[[02984D9EB6E0FB0E6254C036C9F110C4EDA9D0B47873483634E36219EF6D3667,21BB4DE1E9EFC68028A58DD3B3677400C6A4EDBB321A49B2554A3D94AF7049EE],[11A0963C0701D5089AE418EBE84A5A97B24089C688EB91A931068A7F91DB9339,20B7DC228DD3A27F9589FAE17D352DE2F2A1076FF56EB716026708945F53AFCF]],[[221FC0405A912AA6A474D891868725FF1A821017264E02F74021107F3E32775A,1C0C4FAE54227BE18B16ACBC49DDA4C3FAAFE051EA945152AD8A9BB4F5E734DF],[237331610F44927D30ADD64CA35C4D4C6DD776BB212D6EB6DA29BDBDB95408F2,23BC485AA8A38DFABB7DCB49CAED2E12B5B7CDFFC35F6E41BDAB5DF1D54D51D8]]] Pairing \hat{e}(Q,xP) (first 20 bytes): [[[029671468658D146992E1445F89B721DB9DA9607F57E08DA1A463FF24B295FFC,13DF030880C5B8B3959D24AE9D30D9836AF1F448232F399F8CE0E15C97C2C294],[0D1C189A975494A373A9358A4CE286B1BEDEA55932C960C74D17756A848E62B9,207885E3FC9784B5B3AF1781E72F9E4022128561B46C4489742981B585BAAB0D]],[[0C5C77504DA948233B1FD4A793D86197BB5155B149E3D742CAD37A29597EB5BC,13D25953C6E385568E5151145E076B38834DE79F88963723A59BB1156764D869],[1542871D7D3508BFBD32EC7B8586B701EBB984E266DB800644E858E8CBDF533F,10EBC2EA3672F857587BEBC8A06F72FC885E49FB16F8E212317E290E611C3E97]],[[24630CAA10956EC045E196B12078B12D0A965D9C26A7FAE8F6DCD8C88EAAA636,1ED2CCAEBFDBA9723647586F33C98FE0DA11CB7BA3915C1EE065A85F5876ACE0],[0B834561200C3FF367ADA680F50BA4902D9C24D4FC1604CAF105FE4EC50DD298,1C6F60E5B770BBE2132FE85A279CD50495AF71D64B3E1CEFD4BC513F71E5D68B]]] Found it 0000000000000000000000000000000000000000000000000000000000000D76