|=-----------------------------=[ 0x03-3 ]=------------------------------=|
|=---=[ All Hackers Need To Know About Elliptic Curve Cryptography ]=----=|
|=-----------------------------------------------------------------------=|
|=----------------------------=[ f86c9203 ]=-----------------------------=|
---[ Contents
0 - Abstract
1 - Algebraical Groups and Cryptography
2 - Finite Fields, Especially Binary Ones
3 - Elliptic Curves and their Group Structure
4 - On the Security of Elliptic Curve Cryptography
5 - The ECIES Public Key Encryption Scheme
6 - The XTEA Block Cipher, CBC-MAC and Davies-Meyer Hashing
7 - Putting Everything Together: The Source Code
8 - Conclusion
9 - Outlook
A - Appendix: Literature
B - Appendix: Code
---[ 0 - Abstract
Public key cryptography gained a lot of popularity since its invention
three decades ago. Asymmetric crypto systems such as the RSA
encryption scheme, the RSA signature scheme and the Diffie-Hellman Key
Exchange (DH) are well studied and play a fundamental role in modern
cryptographic protocols like PGP, SSL, TLS, SSH.
The three schemes listed above work well in practice, but they still
have a major drawback: the data structures are large, i.e. secure
systems have to deal with up to 2048 bit long integers. These are
easily handled by modern desktop computers; by contrast embedded
devices, handhelds and especially smartcards reach their computing
power limits quickly. As a second problem, of course, the
transportation of large integers "wastes" bandwidth. In 2048 bit
systems an RSA signature takes 256 bytes; that's quite a lot,
especially for slow communication links.
As an alternative to RSA, DH and suchlike the so called Elliptic Curve
Cryptography (ECC) was invented in the mid-eighties. The theory behind
it is very complicated and much more difficult than doing calculations
on big integers. This resulted in a delayed adoption of ECC systems
although their advantages over the classic cryptographic building
blocks are overwhelming: key lengths and the necessary processing
power are much smaller (secure systems start with 160 bit keys). Thus,
whenever CPU, memory or bandwidth are premium resources, ECC is a good
alternative to RSA and DH.
This article has two purposes:
1. It is an introduction to the theory of Elliptic Curve Cryptography.
Both, the mathematical background and the practical implementability
are covered.
2. It provides ready-to-use source code. The C code included and
described in this article (about 500 lines in total) contains a
complete secure public key crypto system (including symmetric
components: a block cipher, a hash function and a MAC) and is
released to the public domain.
The code doesn't link against external libraries, be they of
bigint, cryptographic or other flavour; an available libc is
sufficient. This satisfies the typical hacker need for compact and
independent programs that have to work in "inhospitable"
environments; rootkits and backdoors seem to be interesting
applications.
As mentioned above the theory behind EC cryptography is rather
complex. To keep this article brief and readable by J. Random Hacker
only the important results are mentioned, theorems are not proven,
nasty details are omitted. If on the other hand you are into maths and
want to become an ECC crack I encourage to start reading [G2ECC] or
[ECIC].
---[ 1 - Algebraical Groups and Cryptography
Definition. A set G together with an operation G x G -> G denoted by
'+' is called an (abelian algebraical) group if the following axioms
hold:
G1. The operation '+' is associative and commutative:
(a + b) + c = a + (b + c) for all a,b,c in G
a + b = b + a for all a,b in G
G2. G contains a neutral element '0' such that
a + 0 = a = 0 + a for all a in G
G3. For each element 'a' in G there exists an "inverse element",
denoted by '-a', such that
a + (-a) = 0.
For a group G the number of elements in G is called the group order,
denoted by |G|.
Example. The sets Z, Q and R of integers, rational numbers and real
numbers, respectively, form groups of infinite order in respect to
their addition operation. The sets Q* and R* (Q and R without 0) also
form groups in respect to multiplication (with 1 being the neutral
element and 1/x the inverse of x).
Definition. Let G be a group with operation '+'. A (nonempty) subset H
of G is called a subgroup of G if H is a group in respect to the same
operation '+'.
Example. Z is a subgroup of Q is a subgroup of R in respect to '+'.
In respect to '*' Q* is a subgroup of R*.
Theorem (Lagrange). Let G be a group of finite order and H be a
subgroup of G. Then |H| properly divides |G|.
It follows that if G has prime order, G has only two subgroups,
namely {0} and G itself.
We define the "scalar multiplication" of a natural number k with a
group element g as follows:
k * g := g + g + ... + g + g
\____ k times ____/
Theorem. For a finite group G and an element g in G the set of all
elements k * g (k natural) forms a subgroup of G. This subgroup
is named the "cyclic subgroup generated by g".
Thus a prime order group is generated by any of its nonzero elements.
We now introduce the Diffie-Hellman Key Exchange protocol: let G be a
prime order group and g a nonzero element. Let two players, called
Alice and Bob respectively, do the following:
1. Alice picks a (secret) random natural number 'a', calculates
P = a * g and sends P to Bob.
2. Bob picks a (secret) random natural number 'b', calculates
Q = b * g and sends Q to Alice.
3. Alice calculates S = a * Q = a * (b * g).
4. Bob calculates T = b * P = b * (a * g).
By definition of the scalar multiplication it is apparent that S =
T. Therefore after step 4 Alice and Bob possess the same value S. The
eavesdropper Eve, who recorded the exchanged messages P and Q, is able
to calculate the same value if she manages to determine 'a' or
'b'. This problem (calculating 'a' from G, g and 'a * g') is called
the group's Discrete Logarithm Problem (DLP).
In groups where DLP is too 'hard' to be practically solvable it is
believed to be out of reach for eavesdroppers to determine the value
S, hence Alice and Bob can securely establish a secret key which can
be used to protect further communication.
If an attacker is able to intercept the transmission of P and Q and to
replace both by the group's neutral element, obviously Alice and Bob
are forced to obtain S = 0 = T as shared key. This has to be
considered a successful break of the crypto system. Therefore both
Alice and Bob have to make sure that the received elements Q and P,
respectively, indeed do generate the original group.
The presented DH scheme may also serve as public key encryption scheme
(called ElGamal encryption scheme): let Alice pick a random natural
number 'a' as private key. The element P = a * g is the corresponding
public key. If Bob wants to encrypt a message for her, he picks a
random number 'b', symmetrically encrypts the message with key T = b *
P and transmits the cipher text along with Q = b * g to Alice. She
can reconstruct T = S via S = a * Q and then decrypt the message.
Note the direct relationship between this and the DH scheme!
Conclusion: Cryptographers are always seeking for finite prime order
groups with hard DLP. This is where elliptic curves come into play:
they induce algebraical groups, some of them suitable for DH and
ElGamal crypto systems. Moreover the elliptic curve arithmetic
(addition, inversion) is implementable in a relatively efficient way.
You will find more information about groups and their properties in
[Groups], [Lagrange], [CyclicGroups] and [GroupTheory]. Read more
about the DLP, DH key exchange and ElGamal encryption in [DLP], [DH]
and [ElGamal].
---[ 2 - Finite Fields, Especially Binary Ones
Definition. A set F together with two operations F x F -> F named
'+' and '*' is called a field if the following axioms hold:
F1. (F, +) forms a group
F2. (F*, *) forms a group (where F* is F without the
'+'-neutral element '0')
F3. For all a,b,c in G the distributive law holds:
a * (b + c) = (a * b) + (a * c)
For 'a + (-b)' we write shorter 'a - b'. Accordingly we write 'a / b'
when we multiply 'a' with the '*'-inverse of b.
To put it clearly: a field is a structure with addition, substraction,
multiplication and division that work the way you are familiar with.
Example. The sets Q and R are fields.
Theorem. For each natural m there exists a (finite) field GF(2^m) with
exactly 2^m elements. Fields of this type are called binary fields.
Elements of binary fields GF(2^m) can efficiently be represented by
bit vectors of length m. The single bits may be understood as
coefficients of a polynomial of degree < m. To add two field elements
g and h just carry out the polynomial addition g + h (this means: the
addition is done element-wise, i.e. the bit vectors are XORed
together). The multiplication is a polynomial multiplication modulo a
certain fixed reduction polynomial p: the elements' product is the
remainder of the polynomial division (g * h) / p.
The fact that field addition just consists of a bitwise XOR already
indicates that in binary fields F each element is its own additive
inverse, that is: a + a = 0 for all a in F. For a,b in F as
consequence 2*a*b = a*b + a*b = 0 follows, what leads to the (at the
first glance surprising) equality
(a + b)^2 = a^2 + b^2 for all a,b in F.
More about finite fields and their arithmetical operations can be
found in [FiniteField], [FieldTheory], [FieldTheoryGlossary] and
especially [FieldArithmetic].
---[ 3 - Elliptic Curves and their Group Structure
Definition. Let F be a binary field and 'a' and 'b' elements in F.
The set E(a, b) consisting of an element 'o' (the "point at
infinity") plus all pairs (x, y) of elements in F that satisfy
the equation
y^2 + x*y = x^3 + a*x^2 + b
is called the set of points of the binary elliptic curve E(a, b).
Theorem. Let E = E(a, b) be the point set of a binary elliptic curve
over the field F = GF(2^m). Then
1. E consists of approximately 2^m elements.
2. If (x, y) is a point on E (meaning x and y satisfy the above
equation) then (x, y + x) is also a point on E.
3. If two points P = (x1, y1) and Q = (x2, y2) on E with x1 != x2 are
connected by a straight line (something of the form y = m*x + b),
then there is exactly one third point R = (x3, y3) on E that is
also on this line. This induces a natural mapping f:(P, Q) -> R,
sometimes called chord-and-tangent mapping.
Exercise. Prove the second statement.
The chord-and-tangent mapping 'f' is crucial for the group structure
given naturally on elliptic curves:
a) The auxiliary element 'o' will serve as neutral element which may
be added to any curve point without effect.
b) For each point P = (x, y) on the curve we define the point
-P := (x, y + x) to be its inverse.
c) For two points P = (x1, y1) and Q = (x2, y2) the sum 'P + Q'
is defined as -f(P, Q).
It can be shown that the set E together with the point addition '+'
and the neutral element 'o' defacto has group structure. If the
curve's coefficients 'a' and 'b' are carefully chosen, there exist
points on E that generate a prime order group of points for which the
DLP is hard. Based on these groups secure crypto systems can be built.
The point addition on curves over the field R can be visualized. See
[EllipticCurve] for some nice images.
In ECC implementations it is essential to have routines for point
addition, doubling, inversion, etc. We present pseudocode for the
most important ones:
Let (x, y) be a point on the elliptic curve E(a, b). The point
(x', y') := 2 * (x, y) can be computed by
l = x + (y / x)
x' = l^2 + l + a
y' = x^2 + l*x' + x'
return (x', y')
For two points P = (x1, y1), Q = (x2, y2) the sum (x3, y3) = P + Q
can be computed by
l = (y2 + y1) / (x2 + x1)
x3 = l^2 + l + x1 + x2 + a
y3 = l(x1 + x3) + x3 + y1
return (x3, y3)
Some special cases where the point at infinity 'o' has to be
considered have been omitted here. Have a look at [PointArith] for
complete pseudocode routines. But nevertheless we see that point
arithmetic is easy and straight forward to implement. A handful of
field additions, multiplications plus a single division do the job.
The existence of routines that do point doubling and addition is
sufficient to be able to build an efficient "scalar multiplier": a
routine that multiplies a given curve point P by any given natural
number k. The double-and-add algorithm works as follows:
H := 'o'
let n be the number of the highest set bit in k
while(n >= 0) {
H = 2 * H;
if the nth bit in k is set:
H = H + P;
n--;
}
return H;
Example. Suppose you want to calculate k*P for k = 11 = 1011b. Then
n is initialized to 3 and H calculated as
H = 2 * (2 * (2 * (2 * 'o' + P)) + P) + P
= 2 * (2 * (2 * P) + P) + P
= 2 * (5 * P) + P
= 11 * P
Some elliptic curves that are suitable for cryptographic purposes have
been standardized. NIST recommends 15 curves (see [NIST]), among them
five binary ones called B163, B233, B283, B409 and B571. The
parameters of B163 are the following ([NISTParams]):
Field: GF(2^163)
Reduction poly: p(t) = t^163 + t^7 + t^6 + t^3 + 1
Coefficient a: 1
Coefficient b: 20a601907b8c953ca1481eb10512f78744a3205fd
x coordinate of g: 3f0eba16286a2d57ea0991168d4994637e8343e36
y coordinate of g: 0d51fbc6c71a0094fa2cdd545b11c5c0c797324f1
group order: 2 * 5846006549323611672814742442876390689256843201587
The field size is 2^163, the corresponding symmetric security level is
about 80 bits (see chapter 4). The field elements are given in
hexadecimal, the curve's order in decimal form as h * n, where h (the
"cofactor") is small and n is a large prime number. The point g is
chosen in a way that the subgroup generated by g has order n.
The source code included in this article works with B163. It can
easily be patched to support any other binary NIST curve; for this it
is sufficient to alter just 6 lines.
Exercise. Try it out: patch the sources to get a B409 crypto
system. You will find the curve's parameters in [NISTParams].
Read [EllipticCurve], [PointArith] and [DoubleAndAdd] for further
information.
---[ 4 - On the Security of Elliptic Curve Cryptography
We learned that the security of the DH key exchange is based on the
hardness of the DLP in the underlying group. Algorithms are known that
determine discrete logarithms in arbitrary groups; for this task no
better time complexity bound is known than that for Pollard's "Rho
Method" ([PollardRho]):
Theorem. Let G be a finite (cyclic) group. Then there exists an
algorithm that solves DLP in approximately sqrt(|G|) steps (and low
memory usage).
For elliptic curves no DLP solving algorithm is known that performs
better than the one mentioned above. Thus it is believed that the
ECCDLP is "fully exponential" with regard to the bit-length of
|G|. RSA and classical DH systems can, by contrast, be broken in
"subexponential" time. Hence their key lengths must be larger than
those for ECC systems to achieve the same level of security.
We already saw that elliptic curves over GF(2^m) contain about 2^m
points. Therefore DLP can be solved in about sqrt(2^m) steps, that is
2^(m/2). We conclude that m-bit ECC systems are equivalent to
(m/2)-bit symmetric ciphers in measures of security.
The following table compares equivalent key sizes for various crypto
systems.
ECC key size | RSA key size | DH key size | AES key size
-------------+--------------+-------------+-------------
160 | 1024 | 1024 | (80)
256 | 3072 | 3072 | 128
384 | 7680 | 7680 | 192
512 | 15360 | 15360 | 256
---[ 5 - The ECIES Public Key Encryption Scheme
Earlier we presented the DH Key Exchange and the ElGamal public key
crypto system built on top of it. The Elliptic Curve Integrated
Encryption Scheme (ECIES, see ANSI X9.63) is an enhancement of ElGamal
encryption specifically designed for EC groups. ECIES provides
measures to defeat active attacks like the one presented above.
Let E be an elliptic curve of order h * n with n a large prime
number. Let G be a subgroup of E with |G| = n. Choose a point P in G
unequal to 'o'.
We start with ECIES key generation:
Alice picks as private key a random number 'd' with 1 <= d < n;
She distributes the point Q := d * P as public key.
If Bob wants to encrypt a message m for Alice he proceeds as follows:
1. Pick a random number 'k' with 1 <= k < n.
2. Compute Z = h * k * Q.
3. If Z = 'o' goto step 1.
4. Compute R = k * P.
5. Compute (k1, k2) = KDF(Z, R) (see below).
6. Encrypt m with key k1.
7. Calculate the MAC of the ciphertext using k2 as MAC key.
8. Transmit R, the cipher text and the MAC to Alice.
Alice decrypts the cipher text using the following algorithm:
1. Check that R is a valid point on the elliptic curve.
2. Compute Z = h * d * R.
3. Check Z != 'o'.
4. Compute (k1, k2) = KDF(Z, R) (see below).
5. Check the validity of the MAC using key k2.
6. Decrypt m using key k1.
If any of the checks fails: reject the message as forged.
KDF is a key derivation function that produces symmetric keys k1, k2
from a pair of elliptic curve points. Just think of KDF being the
cryptographic hash function of your choice.
ECIES offers two important features:
1. If an attacker injects a curve point R that does not generate a
large group (this is the case in the attack mentioned above), this
is detected in steps 2 und 3 of the decryption process (the
cofactor plays a fundamental role here).
2. The message is not only encrypted in a secure way, it is also
protected from modification by a MAC.
Exercise. Implement a DH key exchange. Let E be a binary elliptic
curve or order h * n. Let G be a subgroup of E with |G| = n. Choose a
point g in G unequal to 'o'. Let Alice and Bob proceed as follows:
1. Alice picks a random number 'a' with 1 <= a < n and sends P = a * g
to Bob.
2. Bob picks a random number 'b' with 1 <= b < n and sends Q = b * g
to Alice.
3. Alice checks that Q is a point on the curve that generates a group
of order n (see the ECIES_public_key_validation routine). Alice
calculates S = a * Q.
4. Bob checks that P is a point on the curve that generates a group of
ordern n. He calculates T = b * P.
If everything went OK the equality S = T should hold.
---[ 6 - The XTEA Block Cipher, CBC-MAC and Davies-Meyer Hashing
XTEA is the name of a patent-free secure block cipher invented by
Wheeler and Needham in 1997. The block size is 64 bits, keys are 128
bits long. The main benefit of XTEA over its competitors AES, Twofish,
etc is the compact description of the algorithm:
void encipher(unsigned long m[], unsigned long key[])
{
unsigned long sum = 0, delta = 0x9E3779B9;
int i;
for(i = 0; i < 32; i++) {
m[0] += ((m[1] << 4 ^ m[1] >> 5) + m[1]) ^ (sum + key[sum & 3]);
sum += delta;
m[1] += ((m[0] << 4 ^ m[0] >> 5) + m[0]) ^ (sum + key[sum >> 11 & 3]);
}
}
Let E be a symmetric encryption function with block length n,
initialized with key k. The CBC-MAC of a message m is calculated as
follows:
1. Split m in n-bit-long submessages m1, m2, m3, ...
2. Calculate the intermediate values t0 = E(length(m)),
t1 = E(m1 XOR t0), t2 = E(m2 XOR t1), t3 = E(m3 XOR t2), ...
3. Return the last value obtained in step 2 as MAC(k, m) and
discard t0, t1, t2, ...
Next we show how a block cipher can be used to build a cryptographic
hash function using the "Davies-Meyer" construction. Let m be the
message that is to be hashed. Let E(key,block) be a symmetric
encryption function with block length n and key length l.
1. Split m in l-bit-long submessages m1, m2, m3, ...
2. Calculate the intermediate values h1 = E(m1, 0), h2 = E(m2, h1) XOR
h1, h3 = E(m3, h2) XOR h2, ...
3. If h is the last intermediate value obtained in step 2 return
E(length(m), h) XOR h as hash value and discard h1, h2, h3, ...
The code included in this article uses the block cipher XTEA in
counter mode (CTR) for encryption, a CBC-MAC garantees message
authenticity; finally KDF (see chapter 5) is implemented using XTEA in
Davies-Meyer mode.
Read [XTEA] and [DMhashing] to learn more about the XTEA block cipher
and the Davies-Meyer construction.
---[ 7 - Putting Everything Together: The Source Code
The public domain source code you find at the end of this document
implements the ECIES public key encryption system over the curve
B163. The code is commented, but we outline the design here.
1. The central data structure is a bit vector of fixed but "long"
length. It is the base data type used to represent field elements
and suchlike. The dedicated typedef is called bitstr_t.
Appropriate routines for bit manipulation, shifting, bitcounting,
importing from an ASCII/HEX representation, etc do exist.
2. The functions with "field_" prefix do the field arithmetic:
addition, multiplication and calculation of the multiplicative
inverse of elements are the important routines.
3. ECC points are represented as pairs of elem_t (an alias for
bitstr_t), the special point-at-infinity as the pair (0,0). The
functions prefixed with "point_" act on elliptic curve points and
implement basic point operations: point addition, point doubling,
etc.
4. The function "point_mult" implements the double-and-add algorithm
to compute "k * (x,y)" in the way described in chapter 3 .
5. The "XTEA"-prefixed functions implement the XTEA block cipher,
but also the CBC-MAC and the Davies-Meyer construction.
6. The "ECIES_"-routines do the ECIES related work.
ECIES_generate_key_pair() generates a private/public key pair,
ECIES_public_key_validation() checks that a given point is
on the curve and generates a group of order "n".
ECIES_encryption/ECIES_decryption do what their names imply.
7. A demonstration of the main ECIES functionalities is given in the
program's main() section.
The code may be compiled like this:
gcc -O2 -o ecc ecc.c
---[ 8 - Conclusion
We have seen how crypto systems are built upon algebraical groups that
have certain properties. We further gave an introduction into a special
class of appropriate groups and their theory, namely to the binary
elliptic curves. Finally we presented the secure public key encryption
scheme ECIES (together with necessary symmetrical components). All
this is implemented in the source code included in this article.
We recall that besides security the central design goal of the code
was compactness, not speed or generality. Libraries specialized on EC
cryptography benefit from assembler hand-coded field arithmetic
routines and easily perform a hundred times faster than this code.
If compactness is not essential for your application you might opt for
linking against one of the following ECC capable free crypto libraries
instead:
Crypto++ (C++) http://www.eskimo.com/~weidai/cryptlib.html
Mecca (C) http://point-at-infinity.org/mecca/
LibTomCrypt (C) http://libtomcrypt.org/
borZoi (C++/Java) http://dragongate-technologies.com/products.html
---[ 9 - Outlook
You have learned a lot about elliptic curves while reading this
article, but there still remains a bunch of unmentioned ideas. We
list some important ones:
1. Elliptic curves can be defined over other fields than binary ones.
Let p be a prime number and Z_p the set of nonnegative integers
smaller than p. Then Z_p forms a finite field (addition and
multiplication have to be understood modulo p, see
[ModularArithmetic] and [FiniteField]).
For these fields the elliptic curve E(a, b) is defined to be the
set of solutions of the equation
y^2 = x^3 + ax + b
plus the point at infinity 'o'. Of course point addition and
doubling routines differ from that given above, but essentially
these "prime curves" form an algebraical group in a similar way as
binary curves do. It is not that prime curves are more or less
secure than binary curves. They just offer another class of groups
suitable for cryptographic purposes.
NIST recommends five prime curves: P192, P224, P256, P384 and P521.
2. In this article we presented the public key encryption scheme
ECIES. It should be mentioned that ECC-based signature schemes
(see [ECDSA]) and authenticated key establishment protocols ([MQV])
do also exist. The implementation is left as exercise to the
reader.
3. Our double-and-add point multiplicator is very rudimentary. Better
ones can do the "k * P" job in half the time. We just give the idea
of a first improvement:
Suppose we want to calculate 15 * P for a curve point P. The
double-and-add algorithm does this in the following way:
15 * P = 2 * (2 * (2 * (2 * 'o' + P) + P) + P) + P
This takes three point doublings and three point additions
(calculations concerning 'o' are not considered).
We could compute 15 * P in a cleverer fashion:
15 * P = 16 * P - P = 2 * 2 * 2 * 2 * P - P
This takes four doublings plus a single addition; hence we may
expect point multiplicators using this trick to be better
performers than the standard double-and-add algorithm. In practice
this trick can speed up the point multiplication by about 30%.
See [NAF] for more information about this topic.
4. In implementations the most time consuming field operation is
always the element inversion. We saw that both the point addition
and the point doubling routines require one field division each.
There is a trick that reduces the amount of divisions in a full "k
* P" point multiplication to just one. The idea is to represent the
curve point (x,y) as triple (X,Y,Z) where x = X/Z, y = Y/Z. In this
"projective" representation all field divisions can by deferred to
the very end of the point multiplication, where they are carried
out in a single inversion.
Different types of coordinate systems of the projective type
are presented in [CoordSys].
---[ A - Appendix: Literature
A variety of interesting literature exists on elliptic curve
cryptography. I recommend to start with [G2ECC] and [ECIC]. Other good
references are given in [ECC].
Elliptic curves and cryptographical protocols using them have been
standardized by IEEE [P1363], ANSI (X9.62, X9.63) and SECG [SECG], to
list just some.
See [Certicom] and [ECCPrimer] for two tutorials about ECC.
The best reference about classical cryptography is [HAC].
[G2ECC] Hankerson, Menezes, Vanstone, "Guide to Elliptic Curve
Cryptography", Springer-Verlag, 2004
http://www.cacr.math.uwaterloo.ca/ecc/
[ECIC] Blake, Seroussi, Smart, "Elliptic Curves in Cryptography",
Cambridge University Press, 1999
http://www.cambridge.org/aus/catalogue/catalogue.asp?isbn=0521653746
[HAC] Menezes, Oorschot, Vanstone: "Handbook of Applied Cryptography",
CRC Press, 1996, http://www.cacr.math.uwaterloo.ca/hac/
[Groups] http://en.wikipedia.org/wiki/Group_(mathematics)
[Lagrange] http://en.wikipedia.org/wiki/Lagrange's_theorem
[CyclicGroups] http://en.wikipedia.org/wiki/Cyclic_group
[GroupTheory] http://en.wikipedia.org/wiki/Elementary_group_theory
[DLP] http://en.wikipedia.org/wiki/Discrete_logarithm
[DH] http://en.wikipedia.org/wiki/Diffie-Hellman
[ElGamal] http://en.wikipedia.org/wiki/ElGamal_discrete_log_cryptosystem
[AliceAndBob] http://en.wikipedia.org/wiki/Alice_and_Bob
[FiniteField] http://en.wikipedia.org/wiki/Finite_field
[FieldTheory] http://en.wikipedia.org/wiki/Field_theory_(mathematics)
[FieldTheoryGlossary] http://en.wikipedia.org/wiki/Glossary_of_field_theory
[FieldArithmetic] http://en.wikipedia.org/wiki/Finite_field_arithmetic
[ModularArithmetic] http://en.wikipedia.org/wiki/Modular_arithmetic
[ECC] http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
[EllipticCurve] http://en.wikipedia.org/wiki/Elliptic_curve
[PointArith] http://wikisource.org/wiki/Binary_Curve_Affine_Coordinates
[DoubleAndAdd] http://en.wikipedia.org/wiki/Exponentiation_by_squaring
[NIST] http://csrc.nist.gov/CryptoToolkit/dss/ecdsa/NISTReCur.ps
[NISTParams] http://wikisource.org/wiki/NIST_Binary_Curves_Parameters
[PollardRho] http://en.wikipedia.org/wiki/
Pollard's_rho_algorithm_for_logarithms
[XTEA] http://en.wikipedia.org/wiki/XTEA
[DMhashing] http://en.wikipedia.org/wiki/Davies-Meyer_construction
[ECDSA] http://en.wikipedia.org/wiki/Elliptic_Curve_DSA
[MQV] http://en.wikipedia.org/wiki/MQV
[NAF] http://en.wikipedia.org/wiki/Non-adjacent_form
[CoordSys] http://wikisource.org/wiki/Wikisource:Cryptography
[P1363] http://en.wikipedia.org/wiki/IEEE_P1363
[SECG] http://en.wikipedia.org/wiki/SECG
[Certicom] http://www.certicom.com/index.php?action=ecc,ecc_tutorial
[ECCPrimer] http://linuxdevices.com/articles/AT7211498192.html
---[ B - Appendix: Code
$ cat ecc.c.uue
begin 644 ecc.c
M+RH@"B`@5&AI7!E('=I;&P@"D@
M+R`S,ET@/CX@*"AI9'@I("4@,S(I*2`F(#$I"B-D969I;F4@8FET"D@34%#
M4D\H($%;*&ED>"D@+R`S,ET@)CT@?B@Q(#P\("@H:61X*2`E(#,R*2D@*0H*
M(V1E9FEN92!B:71S=" )?8vqe87(h02d@34%#4d\h(&ue;7-e="A!+" `p+"!s m:7ie;v8h8fet2A!+"!"+"!S:7IE;V8H8FETF5O9BAB:71S=')?="DI*0H*:6YT(&)I='-T"LK.R!I*RLI.PH@(')E='5R;B!I
M(#T]($Y535=/4D13.PI]"@H@("`@("`@("`@("`@("`@("`@("`@("`@("`@
M("`O*B!R971UF5I;F)I=',H8V]N"D*>PH@(&EN="!I.PH@('5I;G0S,E]T(&UA"`F(&UA2`G8V]U;G0G(&1I9VETPH@(" `@9f]r*&d@ 2!.54u73u)$4r`m(#$[(&d@ b`p.r!i+2ti"b`@ m("`@($%;:5t@ 2`h05mi72`\ "!c;w5n="D@?" `h05mi("t@,5t@ cx@*#,r m("t@8v]u;g0i*3l*("`@($%;,%t@ #p](&-o="6YT.PH@('T*?0H*("`@("`@" m("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`o*b`h"`K/2!.54U73U)$4RP@:2`](#`[(&D@/"!.54U73U)$4SL@:2LK+"!S
M("L](#0I"B`@("`J+2UX(#T@0TA!4E,R24Y4*',I.PI]"@H@("`@("`@("`@
M("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@+RH@*')A=RD@
M97AP;W)T('1O(&$@8GET92!A2`J+PIV;VED(&)I='-T'!O"D*>PH@(&EN="!I.PH@(&9O'!O"`K/2!.
M54U73U)$4RP@:2`](#`[(&D@/"!.54U73U)$4SL@:2LK+"!S("L](#@I"B`@
M("!S<')I;G1F*',L("(E,#AX(BP@*BTM>"D["GT*"B`@("`@("`@("`@("`@
M("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@+RH@:6UP;W)T
M(&9R;VT@82!H97@@"P@8V]NPH@(&EN="!L96X["B`@:68@*"AS6VQE
M;B`]('-TPH@("`@"D["B`@("`J>"`^/CT@,S(@
M+2`T("H@*&QE;B`E(#@I.PH@("`@F5O9BAE;&5M7W0I("T@-"D@*0H*:6YT(&9I
M96QD7VES,2AC;VYS="!E;&5M7W0@>"D*>PH@(&EN="!I.PH@(&EF("@J>"LK
M("$](#$I(')E='5R;B`P.PH@(&9O2D@(" `@+rh@9fee;&0@861d:71i;vx@*b\*>PH@(&EN="!I.PH@
M(&9OBLK(#T@*G@K
M*R!>("IY*RL["GT*"B-D969I;F4@9FEE;&1?861D,2A!*2!-04-23R@@05LP
M72!>/2`Q("D*"B`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@
M("`@("`@("`@("`@("`@("`@("\J(&9I96QD(&UU;'1I<&QI8V%T:6]N("HO
M"G9O:60@9FEE;&1?;75L="AE;&5M7W0@>BP@8V]N2D[("HO"B`@8FET"D["B`@:68@
M*&)I='-T2P@,"DI"B`@("!B:71S=')?8V]P>2AZ+"!X*3L*
M("!E;'-E"B`@("!B:71S=')?8VQE87(H>BD["B`@9F]R*&D@/2`Q.R!I(#P@
M1$5'4D5%.R!I*RLI('L*("`@(&9OBP@
M>BP@8BD["B`@?0I]"@IV;VED(&9I96QD7VEN=F5R="AE;&5M7W0@>BP@8V]N
M"D["B`@8FET2D["B`@8FETBD["B`@=VAI;&4@*"$@9FEE;&1?
M:7,Q*'4I*2!["B`@("!I(#T@8FETF5I;F)I=',H=2D@+2!B:71S
M=')?PH@("`@("!B:71S
M=')?BD[(&D@/2`M:3L*("`@
M('T*("`@(&)I='-T"P@>2D@*&)I='-T2DI"B-D969I;F4@<&]I;G1?"P@>2D@34%#4D\H(&)I=" -t#(L('DR*2!-04-2
M3R@@8FET#$L('@R*3L@7`H@("`@("`@("`@("`@("`@("`@
M("`@("`@("`@("`@("`@("`@("`@("!B:71S=')?8V]P>2AY,2P@>3(I("D*
M"B`@("`@("`@("`@("`@("`@("`@("`@("`@("\J(&-H96-K(&EF('E>,B`K
M('@J>2`]('A>,R`K("IX7C(@*R!C;V5F9E]B(&AO;&1S("HO"FEN="!I__"P@8V]NF5R;RAX+"!Y*2D*
M("`@(')E='5R;B`Q.PH@(&9I96QD7VUU;'0H82P@>"P@>"D["B`@9FEE;&1?
M;75L="AB+"!A+"!X*3L*("!F:65L9%]A9&0H82P@82P@8BD["B`@9FEE;&1?
M861D*&$L(&$L(&-O969F7V(I.PH@(&9I96QD7VUU;'0H8BP@>2P@>2D["B`@
M9FEE;&1?861D*&$L(&$L(&(I.PH@(&9I96QD7VUU;'0H8BP@>"P@>2D["B`@
M2D@*B\*>PH@(&EF("@A(&)I='-TPH@("`@96QE;5]T(&$["B`@("!F:65L9%]I;G9E"D["B`@("!F:65L9%]M=6QT*&$L(&$L('DI.PH@("`@9FEE;&1?861D*&$L
M(&$L('@I.PH@("`@9FEE;&1?;75L="AY+"!X+"!X*3L*("`@(&9I96QD7VUU
M;'0H>"P@82P@82D["B`@("!F:65L9%]A9&0Q*&$I.R`@("`@("`@"B`@("!F
M:65L9%]A9&0H>"P@>"P@82D["B`@("!F:65L9%]M=6QT*&$L(&$L('@I.PH@
M("`@9FEE;&1?861D*'DL('DL(&$I.PH@('T*("!E;'-E"B`@("!B:71S=')?
M8VQE87(H>2D["GT*"B`@("`@("`@("`@("`@("`@("`O*B!A9&0@='=O('!O
M:6YT#$L('DQ*2`Z/2`H>#$L('DQ*2`K("AX,BP@>3(I
M("HO"G9O:60@<&]I;G1?861D*&5L96U?="!X,2P@96QE;5]T('DQ+"!C;VYS
M="!E;&5M7W0@>#(L(&-O;G-T(&5L96U?="!Y,BD*>PH@(&EF("@A('!O:6YT
M7VES7WIE#(L('DR*2D@>PH@("`@:68@*'!O:6YT7VES7WIE#$L
M('DQ*2D*("`@("`@<&]I;G1?8V]P>2AX,2P@>3$L('@R+"!Y,BD["B`@("!E
M;'-E('L*("`@("`@:68@*&)I='-T#(I*2!["@EI
M9B`H8FET3$I.PH)96QS92`*"2`@<&]I;G1?#$L('DQ*3L*("`@
M("`@?0H@("`@("!E;'-E('L*"65L96U?="!A+"!B+"!C+"!D.PH)9FEE;&1?
M861D*&$L('DQ+"!Y,BD["@EF:65L9%]A9&0H8BP@>#$L('@R*3L*"69I96QD
M7VEN=F5R="AC+"!B*3L*"69I96QD7VUU;'0H8RP@8RP@82D["@EF:65L9%]M
M=6QT*&0L(&,L(&,I.PH)9FEE;&1?861D*&0L(&0L(&,I.PH)9FEE;&1?861D
M*&0L(&0L(&(I.PH)9FEE;&1?861D,2AD*3L*"69I96QD7V%D9"AX,2P@>#$L
M(&0I.PH)9FEE;&1?;75L="AA+"!X,2P@8RD["@EF:65L9%]A9&0H82P@82P@
M9"D["@EF:65L9%]A9&0H>3$L('DQ+"!A*3L*"6)I='-T'!?
M="!B87-E7V]R9&5R.PH*("`@("`@("`@("`@("`@("`@("`@("`@("\J('!O
M:6YT(&UU;'1I<&QI8V%T:6]N('9I82!D;W5B;&4M86YD+6%D9"!A;&=O2P@8V]N
M" `i("t@,3l@:2`^ 2`p.r!i+2ti('l*("`@('!o:6yt7v1o="6)L92A8" m+"!9*3l*("`@(&ef("ab:71s=")?9V5T8FET*&5X<"P@:2DI"B`@("`@(" !o m:6yt7v%d9"a8+"!9+"!x+"!y*3l*("!]"b`@<&]i;g1?8v]p>2AX+"!Y+"!8
M+"!9*3L*?0H*("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("\J(&1R
M87<@82!R86YD;VT@=F%L=64@)V5X<"<@=VET:"`Q(#P](&5X<"`\(&X@*B\*
M=F]I9"!G971?PH@(&-H87(@
M8G5F6S0@*B!.54U73U)$4UT["B`@:6YT(&9H+"!R+"!S.PH@(&1O('L*("`@
M(&EF("@H9F@@/2!O<&5N*$1%5E]204Y$3TTL($]?4D1/3DQ9*2D@/"`P*0H@
M("`@("!&051!3"A$159?4D%.1$]-*3L*("`@(&9O'`L(&)U9BD[" b`@("!f m;w(h__**'`L
M('(I.PH@('T@=VAI;&4H8FET2`K(#`I.R!K6S%=(#T@0TA!4E,R24Y4*&ME>2`K
M(#0I.PH@(&M;,ET@/2!#2$%24S))3E0H:V5Y("L@."D[(&M;,UT@/2!#2$%2
M4S))3E0H:V5Y("L@,3(I.PI]"@H@("`@("`@("`@("`@("`@("`@("`@("`@
M("`@("`@("`@("`@("`@("`@("`@("`@("`@("\J('1H92!85$5!(&)L;V-K
M(&-I<&AE****2`]($-(05)3
M,DE.5"AD871A*3L@>B`]($-(05)3,DE.5"AD871A("L@-"D["B`@9F]R*&D@
M/2`P.R!I(#P@,S([(&DK*RD@>PH@("`@>2`K/2`H*'H@/#P@-"!>('H@/CX@
M-2D@*R!Z*2!>("AS=6T@*R!K6W-U;2`F(#-=*3L*("`@('-U;2`K/2!D96QT
M83L*("`@('H@*ST@*"AY(#P\(#0@7B!Y(#X^(#4I("L@>2D@7B`HF4@+3T@;&5N.PH@('T*?0H*
M("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@
M("`@("`@("`O*B!C86QC=6QA=&4@=&AE($-"0R!-04,@*B\*=F]I9"!85$5!
M7V-B8VUA8RAC:&%R("IM86,L(&-O;G-T(&-H87(@*F1A=&$L(&EN="!S:7IE
M+"!C;VYS="!C:&%R("IK97DI"GL*("!U:6YT,S)?="!K6S1=.PH@(&EN="!L
M96XL(&D["B`@6%1%05]I;FET7VME>2AK+"!K97DI.PH@($E.5#)#2$%24RAM
M86,L(#`I.PH@($E.5#)#2$%24RAM86,@*R`T+"!S:7IE*3L*("!85$5!7V5N
M8VEP:&5R7V)L;V-K*&UA8RP@:RD["B`@=VAI;&4HPH@("`@;&5N
M(#T@34E.*#@L('-I>F4I.PH@("`@9F]R*&D@/2`P.R!I(#P@;&5N.R!I*RLI
M"B`@("`@(&UA8UMI72!>/2`J9&%T82LK.PH@("`@6%1%05]E;F-I<&AE65R(&-O;G-T65R*&-H87(@*F]U="P@8V]N2!P86ER("HO"GL*("!C
M:&%R(&)U9ELX("H@3E5-5T]21%,@*R`Q72P@*F)U9G!T****"P@>2P@8F%S95]X+"!B87-E7WDI.PH@('!O:6YT7VUU;'0H>"P@
M>2P@:RD["B`@<')I;G1F*")(97)E(&ES('EO=7(@;F5W('!U8FQI8R]P2!P86ER.EQN(BD["B`@8FET"AB=68L('@I.R!P
M5]V86QI9&%T:6]N
M*&-O;G-T(&5L96U?="!0>"P@8V]N"D@/B!$14=2144I(" q\("ab:71s=")?
M2D@/B!$14=2144I(" q\"b`@("!p;ven="%]I**__2D@?'P@(2!I____"P@4'DI(#\@+3$@
M.B`Q.PI]"@H@("`@("`O*B!S86UE('1H:6YG+"!B=70@8VAE8VL@86QS;R!T
M:&%T("A0>"Q0>2D@9V5N97)A=&5S(&$@9W)O=7`@;V8@;W)D97(@;B`J+PII
M;G0@14-)15-?<'5B;&EC7VME>5]V86QI9&%T:6]N*&-O;G-T(&-H87(@*E!X
M+"!C;VYS="!C:&%R("I0>2D*>PH@(&5L96U?="!X+"!Y.PH@(&EF("@H8FET
M2P@4'DI
M(#P@,"DI"B`@("!R971UF5R;RAX+"!Y*2`_(#$@.B`M,3L*?0H*=F]I9"!%0TE%4U]K9&8H
M8VAA__**2D*>PH@(&EN=" !b="69S:7IE(#T@*#,@*B`H-"`J" m($y535="/4D13*2`K(#$@*R`Q-2D@)B!^,34["B`@8VAA****'!O2D["B`@8G5F6S$R("H@3E5-5T]21%-=(#T@,#L@6%1%05]D879I97-?;65Y
M97(H:S$L(&)U9BP@8G5F65R*&LR("L@."P@8G5F+"!B
M=69S:7IE("\@,38I.PI]"@HC9&5F:6YE($5#24537T]615)(14%$("@X("H@
M3E5-5T]21%,@*R`X*0H*("`@("`@("`@("`@("`@("`@+RH@14-)15,@96YC
M7!T:6]N*&-H87(@*FUS9RP@8V]N2P@6G@L(%IY.PH@(&-H87(@:S%;
M,39=+"!K,ELQ-ET["B`@97AP7W0@:SL*("!D;R!["B`@("!G971?"D["B`@("!B
M:71S=')?<&%R"P@6GDI.R`@("`@("`@("`@("`@("`@
M("`@("`@("`@("\J(&-O9F%C=&]R(&@@/2`R(&]N($(Q-C,@*B\*("!]('=H
M:6QE*'!O:6YT7VES7WIE2A2>"P@
M4GDL(&)A"P@8F%S95]Y*3L*("!P;VEN=%]M=6QT*%)X+"!2>2P@:RD[
M"B`@14-)15-?:V1F*&LQ+"!K,BP@6G@L(%)X+"!2>2D["@H@(&)I='-T'!O"D["B`@8FET7!T*&US9R`K(#@@*B!.54U73U)$4RP@
M;&5N+"!K,2D["B`@6%1%05]C8F-M86,H;7-G("L@."`J($Y535=/4D13("L@
M;&5N+"!M2D*>PH@(&5L96U?="!2>"P@4GDL
M(%IX+"!:>3L*("!C:&%R(&LQ6S$V72P@:S);,39=+"!M86-;.%T["B`@97AP
M7W0@9#L*("!B:71S=')?:6UP;W)T*%)X+"!M"P@4GDI(#P@,"D*("`@(')E
M='5R;B`M,3L*("!B:71S=')?<&%R2D["B`@<&]I;G1?
M8V]P>2A:>"P@6GDL(%)X+"!2>2D["B`@<&]I;G1?;75L="A:>"P@6GDL(&0I
M.PH@('!O:6YT7V1O=6)L92A:>"P@6GDI.R`@("`@("`@("`@("`@("`@("`@
M("`@("`@("`@+RH@8V]F86-T;W(@:"`](#(@;VX@0C$V,R`J+PH@(&EF("AP
M;VEN=%]I**__2DI"B`@("!R971U2D["B`@"B`@6%1%05]C8F-M86,H;6%C
M+"!M2AT97AT+"!M'0L
M(&-O;G-T(&-H87(@*G!U8FQI8U]X+`H)"0D)8V]N'0I("L@,3L*("!C:&%R("IE;F-R>7!T960@/2!M86QL;V,H;&5N("L@
M14-)15-?3U9%4DA%040I.PH@(&-H87(@*F1E8W)Y<'1E9"`](&UA;&QO8RAL
M96XI.PH*("!P'0Z("5S7&XB+"!T97AT*3L*("!%
M0TE%4U]E;F-R>7!T:6]N*&5N8W)Y<'1E9"P@=&5X="P@;&5N+"!P=6)L:6-?
M>"P@<'5B;&EC7WDI.R`@("\J(&5N8W)Y<'1I;VX@*B\*"B`@:68@*$5#2453
M7V1E8W)Y<'1I;VXH9&5C7!T960L(&QE;BP@<')I=F%T
M92D@/"`P*2`O*B!D96-R>7!T:6]N("HO"B`@("!P7!T:6]N+V1E8W)Y<'1I;VXZ("5S7&XB+"!D96-R>7!T960I.PH@(`H@(&9R
M964H96YCR`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@("`@
M("`@("`@("\J('1H92!C;V5F9FEC:65N=',@9F]R($(Q-C,@*B\*("!B:71S
M=')?<&%R2P@(C@P,#`P,#`P,#`P,#`P,#`P,#`P,#`P,#`P,#`P
M,#`P,#`P,#`P,&,Y(BD["B`@8FET2!P86ER("HO"@H@(&5N8W)Y<'1I;VY?9&5C7!T960B+`H)"0D@("`@("(Q8S4V9#,P,F-F-C0R83AE,6)A-&(T.&-C
M-&9B93(X-#5E93,R9&-E-R(L(`H)"0D@("`@("(T-68T-F5B,S`S961F,F4V
M,F8W-&)D-C@S-CAD.3__