Given a user's 32-byte secret key, Curve25519 computes the user's 32-byte public key. Given the user's 32-byte secret key and another user's 32-byte public key, Curve25519 computes a 32-byte secret shared by the two users. This secret can then be used to authenticate and encrypt messages between the two users.
Getting started. Download and unpack the curve25519 library:
wget https://cr.yp.to/ecdh/curve25519-20050915.tar.gz
gunzip < curve25519-20050915.tar.gz | tar -xf -
To get an idea of how the library is structured, compile it:
cd curve25519-20050915
env CC='gcc -O2' make
Make sure to use appropriate compiler options for your platform,
such as -m64 for the UltraSPARC.
The library will refuse to compile
if it doesn't pass some stringent internal tests;
this normally means that your CPU or OS is currently unsupported.
(This is a very early curve25519 release:
it supports only x86 chips, such as the Pentium and Athlon,
and it isn't fully optimized for those chips.
But it does hold a bunch of speed records already.)
Copy the library source files into your project:
cp `cat FILES.lib` yourproject/
cat Makefile.lib >> yourproject/Makefile
For any C program that will use Curve25519,
modify the program to include curve25519.h;
also modify your Makefile
to link the program with curve25519.a
and to declare that the program depends on
curve25519.a and curve25519.h.
Computing secret keys. Inside your program, to generate a 32-byte Curve25519 secret key, start by generating 32 secret random bytes from a cryptographically safe source: mysecret[0], mysecret[1], ..., mysecret[31]. Then do
mysecret[0] &= 248;
mysecret[31] &= 127;
mysecret[31] |= 64;
to create a 32-byte Curve25519 secret key
mysecret[0], mysecret[1], ..., mysecret[31].
Future library releases will support a curve25519_compress function that hashes 128 bytes into 32 bytes, adding some protection against deficient random-number generators; a curve25519_clamp function that converts 32 bytes into a secret key; and, easiest to use, a combined curve25519_secret function that converts 128 bytes into a secret key.
Computing public keys. To generate the corresponding 32-byte Curve25519 public key mypublic[0], mypublic[1], ..., mypublic[31], call
curve25519(mypublic,mysecret,basepoint);
where the constant basepoint is 9 followed by all zeros:
const unsigned char basepoint[32] = {9};
Future library releases will support a more concise curve25519_public function.
Computing shared secrets. Given someone else's Curve25519 public key hispublic[0], hispublic[1], ..., hispublic[31], call
curve25519(shared,mysecret,hispublic);
to generate a 32-byte secret
shared[0], shared[1], ..., shared[31].
The other user can compute the same secret
by applying his secret key to your public key.
Both of you can then hash this shared secret
and use the result as a key for, e.g.,
Poly1305-AES.
Future library releases will support a curve25519_expand function that hashes 32 bytes into 128 bytes suitable for use as a key; and, easiest to use, a combined curve25519_shared function.
Reporting usage. Please make sure to set up a Googleable web page identifying your program and saying that it is ``powered by Curve25519.''
There are some unusual non-Diffie-Hellman elliptic-curve protocols that need to ensure ``contributory'' behavior. In those protocols, you should reject the 32-byte strings that, in little-endian form, represent 0, 1, 325606250916557431795983626356110631294008115727848805560023387167927233504 (which has order 8), 39382357235489614581723060781553021112529911719440698176882885853963445705823 (which also has order 8), 2^255 - 19 - 1, 2^255 - 19, 2^255 - 19 + 1, 2^255 - 19 + 325606250916557431795983626356110631294008115727848805560023387167927233504, 2^255 - 19 + 39382357235489614581723060781553021112529911719440698176882885853963445705823, 2(2^255 - 19) - 1, 2(2^255 - 19), and 2(2^255 - 19) + 1. But these exclusions are unnecessary for Diffie-Hellman.
This paper gives the complete definition of Curve25519, explains the Curve25519 design decisions, discusses the security of Curve25519, and explains how to compute Curve25519 quickly.
This paper discusses Montgomery's elliptic-curve-scalar-multiplication recurrence in much more detail than Appendix B of the curve25519 paper. In particular, it shows that the X_0 formulas work for all Montgomery-form curves, not just curves such as Curve25519 with only 2 points of order 2. This paper also discusses the elliptic-curve integer-factorization method (ECM) and elliptic-curve primality proving (ECPP).
This paper describes older work introducing some of the ideas used in Curve25519. Never released, and entirely superseded by the curve25519 paper.
This paper discusses various old and new constructions of differential addition chains in one and two dimensions. The current Curve25519 software uses the obvious binary one-dimensional differential addition chain; perhaps one could save time using other one-dimensional differential addition chains; non-Diffie-Hellman applications such as ECDSA can use two-dimensional differential addition chains.
Relevant talks: