Point Compression
Point Compression is discussed on the Crypto++ mailing list on occasion. This page will offer a test program to examine elliptic curve point compression using ECDSA.
Compression refers to sending the x
coordinate of the public point but omitting the y
coordinate (or 1 bit to indicate the quadrant of the y
coordinate, if needed). The person who reconstructs the public key would use x
to solve for y
.
Certicom claims they have a patent on some forms of point compression, but Daniel Bernstein disagrees in some instances. In fact, Bernstein cites prior art from 1986 that predates Certicom's claim date of 2000. Its now appears to be a moot point since the patent has expired in the US. See Irrelevant patents on elliptic-curve cryptography for details.
Ján Jančár showed Crypto++ 8.2 and below leaked timing information in elliptic curve gear. You should upgrade to Crypto++ 8.3 and above. Also see Issue 869, Elliptic Curve timing leaks.
EC Compression
Below is the sample program used for testing. The program generates a random private key and then creates uncompressed and compressed public keys from the private key. A typical run of the program is shown below, and Key 1 through Key 4 are the same public keys.
$ ./cryptopp-ec-compress.exe Key 1 (not compressed): 214 bytes 3081D33081A406072A8648CE3D0201308198020101302006072A8648CE3D0101021500FFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF7FFFFFFF302C0414FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFC0414 1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA450429044A96B5688EF573284664698968C38BB913CB FC8223A628553168947D59DCC912042351377AC5FB3202150100000000000000000001F4C8F927AED3 CA752257020101032A0004CBFD13CEB20D677D9D3781AFA2E66B7BD5BC0E3C4EB8702144AA62BE5235 DFC691567AA2A7101AB1 Key 2 (compressed): 174 bytes 3081AB30819006072A8648CE3D0201308184020101302006072A8648CE3D0101021500FFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF7FFFFFFF302C0414FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFC0414 1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA450415024A96B5688EF573284664698968C38BB913CB FC8202150100000000000000000001F4C8F927AED3CA75225702010103160003CBFD13CEB20D677D9D 3781AFA2E66B7BD5BC0E3C Key 3 public point (after deserialization of Key 1): y3.x: cbfd13ceb20d677d9d3781afa2e66b7bd5bc0e3ch y3.y: 4eb8702144aa62be5235dfc691567aa2a7101ab1h Key 4 public point (after deserialization of Key 2): y4.x: cbfd13ceb20d677d9d3781afa2e66b7bd5bc0e3ch y4.y: 4eb8702144aa62be5235dfc691567aa2a7101ab1h
The progrm first creates a random private key privateKey
to be used for signing. The program then creates two public keys publicKey1
and publicKey2
based on the private key. publicKey1
is not compressed, while publicKey2
is compressed.
Next, the program simply calls Save
on the public key to write the serialized keys into a string
. After serialization, publicKey1
is serialized uncompressed in p1
and publicKey2
is serialized compressed in p2
. p1
is 214 bytes while p2
is 174 bytes. The program then prints some information about the serialized publicKey1
and publicKey2
.
Next, the program creates publicKey3
and publicKey4
. It sets point compression on publicKey4
and then Loads
publicKey3
and publicKey4
from p1
and p2
respectively. At this point, publicKey3
is essentially a copy of publicKey1
(uncompressed); and publicKey4
is essentially a copy of publicKey2
(compressed).
Finally, the test program fetches the public element (denoted y
) and stores them in y3
and y4
. The public point for publicKey3
is stored in y3
; and the public point for publicKey4
is stored in y4
. The program then prints the values of y3
and y4
. When the program prints the keys, it does nothing special - the ECDSA<ECP, SHA1>::PublicKey
handles the details of point compression.
Test Program
AutoSeededRandomPool prng; // Generate a private key, and two public keys. // One with and one without compression ECDSA<ECP, SHA1>::PrivateKey privateKey; privateKey.Initialize(prng, secp160r1()); ECDSA<ECP, SHA1>::PublicKey publicKey1; privateKey.MakePublicKey(publicKey1); ECDSA<ECP, SHA1>::PublicKey publicKey2; privateKey.MakePublicKey(publicKey2); publicKey2.AccessGroupParameters().SetPointCompression(true); // Save the public keys string p1, p2; publicKey1.Save(StringSink(p1).Ref()); publicKey2.Save(StringSink(p2).Ref()); ////////////////////////////////////////////////////////////////////// // Print some stuff about them string s3, s4; StringSource ss3(p1, true, new HexEncoder(new StringSink(s3))); StringSource ss4(p2, true, new HexEncoder(new StringSink(s4))); cout << "Key 1 (not compressed): " << p1.size() << " bytes" << endl; cout << " " << s3 << endl; cout << "Key 2 (compressed): " << p2.size() << " bytes" << endl; cout << " " << s4 << endl; cout << endl; ////////////////////////////////////////////////////////////////////// // Two new keys to load up the persisted keys ECDSA<ECP, SHA1>::PublicKey publicKey3, publicKey4; publicKey4.AccessGroupParameters().SetPointCompression(true); publicKey3.Load(StringSource(p1, true).Ref()); publicKey4.Load(StringSource(p2, true).Ref()); // And validate them publicKey3.Validate(prng, 3); publicKey4.Validate(prng, 3); // Get the public elemnts of the loaded keys const ECP::Point& y3 = publicKey3.GetPublicElement(); const Integer& y3_x = y3.x; const Integer& y3_y = y3.y; const ECP::Point& y4 = publicKey4.GetPublicElement(); const Integer& y4_x = y4.x; const Integer& y4_y = y4.y; // Print some stuff about them cout << "Key 3 (after deserialization of Key 1):" << endl; cout << " y3.x: " << std::hex << y3_x << endl; cout << " y3.y: " << std::hex << y3_y << endl; cout << "Key 4 (after deserialization of Key 2):" << endl; cout << " y4.x: " << std::hex << y4_x << endl; cout << " y4.y: " << std::hex << y4_y << endl; cout << endl; ////////////////////////////////////////////////////////////////////// // Two new keys to load up the persisted keys, but crossing wires // so so there's a compress/uncompressed mismatch ECDSA<ECP, SHA1>::PublicKey publicKey5, publicKey6; publicKey6.AccessGroupParameters().SetPointCompression(true); // This should be `p1` publicKey5.Load(StringSource(p2, true).Ref()); // This should be `p2` publicKey6.Load(StringSource(p1, true).Ref()); // Get the public elemnts of the loaded keys const ECP::Point& y5 = publicKey5.GetPublicElement(); const Integer& y5_x = y5.x; const Integer& y5_y = y5.y; const ECP::Point& y6 = publicKey6.GetPublicElement(); const Integer& y6_x = y6.x; const Integer& y6_y = y6.y; // Print some stuff about them cout << "Key 5 (after deserialization of Key 1):" << endl; cout << " y5.x: " << std::hex << y5_x << endl; cout << " y5.y: " << std::hex << y5_y << endl; cout << "Key 6 (after deserialization of Key 2):" << endl; cout << " y6.x: " << std::hex << y6_x << endl; cout << " y6.y: " << std::hex << y6_y << endl; cout << endl;
Downloads
cryptopp-ec-compress.zip - Demonstrates compressing and serializing ECDSA keys.