# Elliptic Curve Cryptography

Elliptic Curve Cryptography (ECC) is based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was independently suggested by Neal Koblitz and Victor Miller in 1985.

Crypto++ offers a numbers of schemes and algorithms which operate over elliptic curves. Fields include both F_{p} and F_{2m}, and schemes include:

- Elliptic Curve Diffie-Hellman Key Agreement (ECDH)
- Elliptic Curve Menezes-Qu-Vanstone Key Agreement (ECMQV)
- Hashed Menezes-Qu-Vanstone Key Agreement (HMQV)
- Fully Hashed Menezes-Qu-Vanstone Key Agreement (FHMQV)
- Elliptic Curve Integrated Encryption Scheme (ECIES)
- Elliptic Curve Digital Signature Algorithm (ECDSA)
- Elliptic Curve Nyberg Rueppel Signature Scheme (ECNR)
- X25519 and Ed25519
- Point Compression

Crypto++ conforms to Certicom's SEC 2 for most elliptic curve implementations.

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.

## Two Step Construction/Initialization of Keys

If you want to perform two-step construction and initialization of a private key, then perform the following. Note that `Initialize` takes a `RandomNumberGenerator`, which causes private key generation. An `Initialize` that lacks the PRNG does not generate a private key.

While the example below is written for `ECIES`, the technique applies to all Diffie-Hellman schemes over elliptic curves due to Crypto++'s use of interface programming. That means it works equally well for `ECMQV`, `ECDSA`, `ECMQV` and `ECNR`.

// From Wei Dai in a private email ECIES<ECP>::Decryptor d; d.AccessKey().GenerateRandom(GlobalRNG(), MakeParameters(Name::GroupOID(), ASN1::secp256r1()));

Alternative, but non-preferred methods include the following.

ECIES<ECP>::Decryptor decryptor; decryptor.AccessKey().AccessGroupParameters().Initialize(prng, ASN1::secp256r1());

As yet another alternative, you can set the private exponent (multiplicand) directly:

ECIES<ECP>::Decryptor decryptor; decryptor.AccessKey().AccessGroupParameters().Initialize(ASN1::secp256r1()); Integer x(prng, Integer::One(), decryptor.AccessKey().GetGroupParameters().GetSubgroupOrder()-1); decryptor.AccessKey().SetPrivateExponent(x);

## Minimizing Key Size for Persistence

Keys can be serialized in a number of different formats. Some formats are better for interoperability, while others are better for minimizing size. Keys and their formats are covered in detail at Keys and Formats.

Keys and Formats does not discuss minimizing a serialized key's size. Taking from Wei Dai on the Crypto++ mailing list:

To minimize the size of public and private keys, what you need to do is

encode only the private exponent of the private key, and the public point of

the public key.

// save private exponent privateKey.GetPrivateExponent().DEREncode(privFile); // load private exponent Integer x; x.BERDecode(privFile); privateKey.AccessGroupParameters().Initialize(CryptoPP::ASN1::secp160k1()); privateKey.SetPrivateExponent(x); // save public element publicKey.GetGroupParameters().GetCurve().EncodePoint(pubFile, publicKey.GetPublicElement(), true); // load public element ECP::Point p; publicKey.AccessGroupParameters().Initialize(CryptoPP::ASN1::secp160k1()); publicKey.GetGroupParameters().GetCurve().DecodePoint(p, pubFile, publicKey.GetGroupParameters().GetCurve().EncodedPointSize(true)); publicKey.SetPublicElement(p);

## Curve Operations

Sometimes you may want to perform curve operations directly, and not in the context of, say, a higher level encryptor or signer. The code below shows you how to exponentiate, multiple and add using the lower level primitives over secp256r1.

#include "integer.h" #include "eccrypto.h" #include "osrng.h" #include "oids.h" #include <iostream> #include <iomanip> int main(int argc, char* argv[]) { using namespace CryptoPP; typedef DL_GroupParameters_EC<ECP> GroupParameters; typedef DL_GroupParameters_EC<ECP>::Element Element; AutoSeededRandomPool prng; GroupParameters group; group.Initialize(ASN1::secp256r1()); // private key Integer x(prng, Integer::One(), group.GetMaxExponent()); std::cout << "Private exponent:" << std::endl; std::cout << " " << std::hex << x << std::endl; // public key Element y = group.ExponentiateBase(x); std::cout << "Public element:" << std::endl; std::cout << " " << std::hex << y.x << std::endl; std::cout << " " << std::hex << y.y << std::endl; // element addition Element u = group.GetCurve().Add(y, ECP::Point(2,3)); std::cout << "Add:" << std::endl; std::cout << " " << std::hex << u.x << std::endl; std::cout << " " << std::hex << u.y << std::endl; // scalar multiplication Element v = group.GetCurve().ScalarMultiply(u, Integer::Two()); std::cout << "Mult:" << std::endl; std::cout << " " << std::hex << v.x << std::endl; std::cout << " " << std::hex << v.y << std::endl; return 0; }

The program produces output similar to the following.

$ ./test.exe Private exponent: b48e35e8d60918f815857503b034681bc59db689dee0ffc35a140e365bb056dch Public element: bb9c8daaace9712f368bc98cf004a4594a14f9c330e2db141906ec67f05ab8d8h e37e5e161aae15f54f20d67b665311717305932a1479427fe063d84c5be82a1dh Sum: f5055cd23f23f5721d8a5f6f87bd61206e972a97c19478200cb0b1f24af398ach 107a532732098c4d051efc7f54d9bda78020a6e68f95e01a33700bab56a91f9ah Mult: 46628d3e4f43da4fd001c652682d33f608c34ce3cf6c13f45b9bd014cbb83ed4h 3b58f98bd0d70196036b77f6fcca6fe206bdf3beda4b2b604d5cb8ae0327a57ch

## Non-standard Curves

Crypto++ supplies a set of standard curves approved by ANSI, Brainpool, and NIST. Crypto++ does not provide curve generation functionality. If you need a custom curve, see Elliptic Curve Builder.

## Downloads

dpval-2.zip - Elliptic Curve Domain Parameter Validation. The program dumps the public and private keys, and validates the curve per Certicom's SEC 2 Whitepaper (the curve used for demonstration purposes is NIST P-192). In addition, the program demonstrates mathematics with the point of infinity and scalar multiplications using Crypto++.

ecctest.zip - Exercises encryption and decryption using ANSI, Brainpool, and NIST curves by way of #define

ECDSA-Test.zip - Crypto++ ECDSA sample program