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.