Point Compression

From Crypto++ Wiki
Jump to navigation Jump to search

Point Compression is discussed on the Crypto++ mailing list on occassion. 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 ommitting 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 Bernsteain 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

Key 2 (compressed): 174 bytes

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;

ECDSA<ECP, SHA1>::PublicKey publicKey2;

// Save the public keys
string p1, p2;

// 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;

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;

// 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;


cryptopp-ec-compress.zip - Demonstrates compressing and serializing ECDSA keys.