X25519
| Documentation |
#include <cryptopp/xed25519.h>
|
X25519 is a key agreement scheme using curve25519 by Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe and Bo-Yin Yang. The algorithm uses curve25519, and is about 20x to 30x faster than Certicom's secp256r1 and secp256k1 curves. Also see A state-of-the-art Diffie-Hellman function.
The Crypto++ library uses Andrew Moon's constant time curve25519-donna. The curve25519 gear appears to be like most other comparable public key objects in the Crypto++ library but it is mostly a facade. The Crypto++ classes are just wrappers around Moon's code that present some of the expected interface for callers. A side effect of the integration is, there is no general Point, Curve, or GroupParameters so you can't perform arbitrary calculations with curve25519.
x25519 is a Diffie-Hellman algorithm used for key agreement. Each run of a protocol should use new parameters selected at random. The parameters for each run is called an ephemeral or temporary key. Since each run of the protocol is supposed to use new parameters it is not convenient to retrieve a private key generated at random. The public key is easier to extract because you are expected to share it with the other party.
x25519 is not authenticated. x25519 by itself is susceptible to Man-in-the-Middle attacks. You should use a signature scheme to authenticate public keys, like ed25519.
To use x25519 in your code include the header file xed25519.h. The name was selected because the header includes both x25519 and ed25519, and the name should be unique and avoid collisions. The object you will primarily use is x25519.
Andrew Moon's code is in the donna source files, and directly accessible in the Donna namespace. The header of interest is donna.h, and the function of interest is curve25519_mult. However, we recommend you use high level Crypto++ objects rather than the low level Donna code.
The Donna code is inherently little-endian due to design choices by the Bernstein team. If an x25519 object takes or returns an Integer, then the library reverses they bytes for use in the Donna code. If an x25519 object takes or returns a byte array, then the array is little-endian and the Donna code uses it directly.
x25519 uses SHA512 as the hash. It is hard wired into the source files and there is no way to change it without recompiling sources. In the future we may add overloaded functions that allow the caller to specify a HashTransformation.
Also see Keys and Formats and Curve25519 keys on the Crypto++ wiki; and Add curve25519 for modern key agreement in the Crypto++ issue tracker.
Protocol Parameters
x25519 is a Diffie-Hellman algorithm used for key agreement. Each run of a protocol should use new parameters selected at random. The parameters for each run is called an ephemeral or temporary key. The primary way to create a x25519 object is with a random number generator:
AutoSeededRandomPool prng; x25519 ecdh(prng);
Because the contructor takes a random number generator, a new key pair is created when the object is constructed. Since each run of the protocol is supposed to use new parameters it is not convenient to retrieve the private key generated at random. The public key is easier to extract because you are expected to share it with the other party.
Generating Keys
Generating a key is as simple as the following. All code paths that generate a private key will clamp the key.
int main(int argc, char* argv[])
{
using namespace CryptoPP;
AutoSeededRandomPool prng;
x25519 ecdh(prng);
return 0;
}
You can create private and public keys with the following code.
int main(int argc, char* argv[])
{
using namespace CryptoPP;
AutoSeededRandomPool prng;
HexEncoder encoder(new FileSink(std::cout));
x25519 ecdh;
SecByteBlock x(x25519::SECRET_KEYLENGTH);
ecdh.GeneratePrivateKey(prng, x);
std::cout << "Private key: ";
StringSource(x, x.size(), true, new Redirector(encoder));
std::cout << std::endl;
SecByteBlock y(x25519::PUBLIC_KEYLENGTH);
ecdh.GeneratePublicKey(prng, x, y);
std::cout << "Public key: ";
StringSource(y, y.size(), true, new Redirector(encoder));
std::cout << std::endl;
return 0;
}
Running the program produces output similar to the following.
$ ./test.exe Private key: 7855D0A26A43B7AE95C89386C17D96252955707BBD4DE460D89501964CB16B49 Public key: 50A864D6C91158719A14040787F0177E968E606DB669DC37359F42E36853085C
Saving Keys
You can save private keys in PKCS #8 or Asymmetric Key Package format. You can save public keys in X.509 or Asymmetric Key Package format. Asymmetric Key Packages are a superset of PKCS #8 and X.509, and specified in RFC 5958.
The RFCs throw a curve ball with respect to presentation. Rather than using network byte ordering which is big-endian, they use little-endian for the ASN.1 presentation. That means the BIT STRING and OCTET STRING shown below are little-endian, and not big-endian like most ASN.1 data.
To save a private or public key perform the following. Note that the code below simply prints the hex encoded key to stdout.
int main(int argc, char* argv[])
{
using namespace CryptoPP;
AutoSeededRandomPool prng;
HexEncoder encoder(new FileSink(std::cout));
x25519 ecdh(prng);
std::cout << "Private key: ";
ecdh.Save(encoder);
std::cout << "\n" << std::endl;
return 0;
}
The program produces the following output.
$ ./test.exe Private key: 302E020100300506032B656E04220420E00775189E7B1A43C956DA4F538DE8B4D3F 2F8894707CFD32E99E6790BFC774E
You can save to a file with the following code.
int main(int argc, char* argv[])
{
using namespace CryptoPP;
AutoSeededRandomPool prng;
x25519 ecdh(prng);
FileSink fs("private.key.bin");
ecdh.Save(fs);
return 0;
}
A run of the code produces the following output.
$ ./test.exe
$ dumpasn1 private.key.bin
0 46: SEQUENCE {
2 1: INTEGER 0
5 5: SEQUENCE {
7 3: OBJECT IDENTIFIER curveX25519 (1 3 101 110)
: }
12 34: OCTET STRING, encapsulates {
14 32: OCTET STRING
: 80 2F 9D 41 21 0B 11 C5 1B 35 34 2F D5 75 D9 1A
: AA A5 54 2B 21 61 32 FB B8 EB 86 C3 CA 91 62 58
: }
: }
0 warnings, 0 errors.
Loading Keys
You can load private keys in PKCS #8 or Asymmetric Key Package format. You can load public keys in X.509 or Asymmetric Key Package format. Asymmetric Key Packages are a superset of PKCS #8 and X.509, and specified in RFC 5958.
The code below loads the private and public key and then validates them to ensure they are fit for service.
int main(int argc, char* argv[])
{
using namespace CryptoPP;
FileSource fs("private.key.bin", true);
x25519 ecdh;
ecdh.Load(fs);
AutoSeededRandomPool prng;
bool valid = ecdh.Validate(prng, 3);
if (valid == false)
throw std::runtime_error("Invalid private key");
std::cout << "Keys are valid" << std::endl;
return 0;
}
Running the code on the previous keys produces the message "Keys are valid" as expected.
Be careful when loading some keys, like those found in the RFCs. The keys are not clamped and fail validation.
Key Validation
You should always validate keys that you did not generate, including keys loaded via methods like Load and BERDecode. You should refrain from trusting the work of others. Trust is something to fall back to when you don't have security controls to place. In the case of private keys you do have controls to use.
Here is how the library validates x25519 private keys. The level 3 check is expensive because it performs a pairwise consistency check by performing the scalar multiplication and comparing the calculated public key to the original public key.
bool x25519::Validate(RandomNumberGenerator &rng, unsigned int level) const
{
CRYPTOPP_UNUSED(rng);
if (level >= 1 && IsClamped(m_sk) == false)
return false;
if (level >= 2 && IsSmallOrder(m_pk) == true)
return false;
if (level >= 3)
{
// Verify m_pk is pairwise consistent with m_sk
SecByteBlock pk(PUBLIC_KEYLENGTH);
SecretToPublicKey(pk, m_sk);
if (VerifyBufsEqual(pk, m_pk, PUBLIC_KEYLENGTH) == false)
return false;
}
return true;
}
Using Integers
Earlier the following private key was shown. It is a random key that was serialized using PKCS #8 or Asymmetric Key Package format.
$ dumpasn1 private.key.bin
0 46: SEQUENCE {
2 1: INTEGER 0
5 5: SEQUENCE {
7 3: OBJECT IDENTIFIER curveX25519 (1 3 101 110)
: }
12 34: OCTET STRING, encapsulates {
14 32: OCTET STRING
: 80 2F 9D 41 21 0B 11 C5 1B 35 34 2F D5 75 D9 1A
: AA A5 54 2B 21 61 32 FB B8 EB 86 C3 CA 91 62 58
: }
: }
0 warnings, 0 errors.
The IETF used little-endian presentation and the following does not work as expected:
// OCTET STRING from private key
const byte key[] = {
0x80, 0x2F, 0x9D, 0x41, 0x21, 0x0B, 0x11, 0xC5,
0x1B, 0x35, 0x34, 0x2F, 0xD5, 0x75, 0xD9, 0x1A,
0xAA, 0xA5, 0x54, 0x2B, 0x21, 0x61, 0x32, 0xFB,
0xB8, 0xEB, 0x86, 0xC3, 0xCA, 0x91, 0x62, 0x58
};
Integer x(key, sizeof(key));
If you want to load a little-endian array into an Integer then use the following overload. The integer will parse the byte array in reverse.
// OCTET STRING from private key
const byte key[] = {
0x80, 0x2F, 0x9D, 0x41, 0x21, 0x0B, 0x11, 0xC5,
0x1B, 0x35, 0x34, 0x2F, 0xD5, 0x75, 0xD9, 0x1A,
0xAA, 0xA5, 0x54, 0x2B, 0x21, 0x61, 0x32, 0xFB,
0xB8, 0xEB, 0x86, 0xC3, 0xCA, 0x91, 0x62, 0x58
};
Integer x(key, sizeof(key), UNSIGNED, LITTLE_ENDIAN_ORDER);
Or manually reverse the array before creating the Integer as shown below.
// OCTET STRING from private key
byte key[] = {
0x80, 0x2F, 0x9D, 0x41, 0x21, 0x0B, 0x11, 0xC5,
0x1B, 0x35, 0x34, 0x2F, 0xD5, 0x75, 0xD9, 0x1A,
0xAA, 0xA5, 0x54, 0x2B, 0x21, 0x61, 0x32, 0xFB,
0xB8, 0xEB, 0x86, 0xC3, 0xCA, 0x91, 0x62, 0x58
};
std::reverse(key, key+sizeof(key));
Integer x(key, sizeof(key));
Complete Example
Below is a complete example that generates temporary keys for two parties A and B, and then generates a shared secret for use between them.
#include <iostream>
#include <stdexcept>
#include <string>
#include "cryptlib.h"
#include "xed25519.h"
#include "filters.h"
#include "osrng.h"
#include "files.h"
#include "hex.h"
int main(int argc, char* argv[])
{
using namespace CryptoPP;
AutoSeededRandomPool rndA, rndB;
x25519 ecdhA(rndA), ecdhB(rndB);
//////////////////////////////////////////////////////////////
SecByteBlock privA(ecdhA.PrivateKeyLength());
SecByteBlock pubA(ecdhA.PublicKeyLength());
ecdhA.GenerateKeyPair(rndA, privA, pubA);
SecByteBlock privB(ecdhB.PrivateKeyLength());
SecByteBlock pubB(ecdhB.PublicKeyLength());
ecdhB.GenerateKeyPair(rndB, privB, pubB);
//////////////////////////////////////////////////////////////
SecByteBlock sharedA(ecdhA.AgreedValueLength());
SecByteBlock sharedB(ecdhB.AgreedValueLength());
if(ecdhA.AgreedValueLength() != ecdhB.AgreedValueLength())
throw std::runtime_error("Shared secret size mismatch");
if(!ecdhA.Agree(sharedA, privA, pubB))
throw std::runtime_error("Failed to reach shared secret (1)");
if(!ecdhB.Agree(sharedB, privB, pubA))
throw std::runtime_error("Failed to reach shared secret (2)");
size_t len = std::min(ecdhA.AgreedValueLength(), ecdhB.AgreedValueLength());
if(!len || !VerifyBufsEqual(sharedA.BytePtr(), sharedB.BytePtr(), len))
throw std::runtime_error("Failed to reach shared secret (3)");
//////////////////////////////////////////////////////////////
HexEncoder encoder(new FileSink(std::cout));
std::cout << "Shared secret (A): ";
StringSource(sharedA, sharedA.size(), true, new Redirector(encoder));
std::cout << std::endl;
std::cout << "Shared secret (B): ";
StringSource(sharedB, sharedB.size(), true, new Redirector(encoder));
std::cout << std::endl;
return 0;
}
Running the program will produce output similar to the following.
$ ./test.exe Shared secret (A): B5C105BC3B685869AFBDFE64F15D27D6D0EAAA1A22F03B45B86E09FC76522450 Shared secret (B): B5C105BC3B685869AFBDFE64F15D27D6D0EAAA1A22F03B45B86E09FC76522450
Donna Functions
The Donna namespace provides the function curve25519_mult. curve25519_mult creates a public key from a private key, and also performs applies thee Diffie-Hellman function during key agreement. The function is an entry point into Andrew Moon's constant time curve25519-donna.
The header of interest is donna.h, and the source files of interest are donna_32.cpp, donna_64.cpp and donna_sse.cpp depending on the platform. The functions are shown below for completeness, but you should avoid using them. The Donna functions may change without warning.
NAMESPACE_BEGIN(CryptoPP)
NAMESPACE_BEGIN(Donna)
int curve25519_mult_CXX(byte sharedKey[32], const byte secretKey[32], const byte othersKey[32])
{
using namespace CryptoPP::Donna::X25519;
FixedSizeSecBlock<byte, 32> e;
for (size_t i = 0; i < 32; ++i)
e[i] = secretKey[i];
e[0] &= 0xf8; e[31] &= 0x7f; e[31] |= 0x40;
bignum25519 nqpqx = {1}, nqpqz = {0}, nqz = {1}, nqx;
bignum25519 q, qx, qpqx, qqx, zzz, zmone;
size_t bit, lastbit;
curve25519_expand(q, othersKey);
curve25519_copy(nqx, q);
/* bit 255 is always 0, and bit 254 is always 1, so skip bit 255 and
start pre-swapped on bit 254 */
lastbit = 1;
/* we are doing bits 254..3 in the loop, but are swapping in bits 253..2 */
for (int i = 253; i >= 2; i--) {
curve25519_add(qx, nqx, nqz);
curve25519_sub(nqz, nqx, nqz);
curve25519_add(qpqx, nqpqx, nqpqz);
curve25519_sub(nqpqz, nqpqx, nqpqz);
curve25519_mul(nqpqx, qpqx, nqz);
curve25519_mul(nqpqz, qx, nqpqz);
curve25519_add(qqx, nqpqx, nqpqz);
curve25519_sub(nqpqz, nqpqx, nqpqz);
curve25519_square(nqpqz, nqpqz);
curve25519_square(nqpqx, qqx);
curve25519_mul(nqpqz, nqpqz, q);
curve25519_square(qx, qx);
curve25519_square(nqz, nqz);
curve25519_mul(nqx, qx, nqz);
curve25519_sub(nqz, qx, nqz);
curve25519_scalar_product(zzz, nqz, 121665);
curve25519_add(zzz, zzz, qx);
curve25519_mul(nqz, nqz, zzz);
bit = (e[i/8] >> (i & 7)) & 1;
curve25519_swap_conditional(nqx, nqpqx, bit ^ lastbit);
curve25519_swap_conditional(nqz, nqpqz, bit ^ lastbit);
lastbit = bit;
}
/* the final 3 bits are always zero, so we only need to double */
for (int i = 0; i < 3; i++) {
curve25519_add(qx, nqx, nqz);
curve25519_sub(nqz, nqx, nqz);
curve25519_square(qx, qx);
curve25519_square(nqz, nqz);
curve25519_mul(nqx, qx, nqz);
curve25519_sub(nqz, qx, nqz);
curve25519_scalar_product(zzz, nqz, 121665);
curve25519_add(zzz, zzz, qx);
curve25519_mul(nqz, nqz, zzz);
}
curve25519_recip(zmone, nqz);
curve25519_mul(nqz, nqx, zmone);
curve25519_contract(sharedKey, nqz);
return 0;
}
int curve25519_mult(byte publicKey[32], const byte secretKey[32])
{
using namespace CryptoPP::Donna::X25519;
#if (CRYPTOPP_CURVE25519_SSE2)
if (HasSSE2())
return curve25519_mult_SSE2(publicKey, secretKey, basePoint);
else
#endif
return curve25519_mult_CXX(publicKey, secretKey, basePoint);
}
int curve25519_mult(byte sharedKey[32], const byte secretKey[32], const byte othersKey[32])
{
#if (CRYPTOPP_CURVE25519_SSE2)
if (HasSSE2())
return curve25519_mult_SSE2(sharedKey, secretKey, othersKey);
else
#endif
return curve25519_mult_CXX(sharedKey, secretKey, othersKey);
}
NAMESPACE_END // Donna
NAMESPACE_END // CryptoPP
The Donna code is used similar to the following in the library source code. Most Donna functions return a useless value and can be ignored.
void x25519::SecretToPublicKey(byte y[PUBLIC_KEYLENGTH], const byte x[SECRET_KEYLENGTH]) const
{
Donna::curve25519_mult(y, x);
}
Benchmarks
TODO...
Downloads
No downloads available.