Cryptography Overview
68 RSA BSAFE Crypto-C Developer’s Guide
0=0·I
≡(2·2m–1)·Imod2m
=2·(2m–1·I)
≡2·1mod2m
=2
Instead, we create the field F2m in a completely abstract manner. We start by letting
the elements of the finite field F2m be the bit strings of bit-length m. Mathematicians
have shown that it is possible to create an addition and a multiplication that make
these strings, called m-tuples, into a field.
Addition is easy to define: to add two strings, just XOR them. This is the same as
adding them bit by bit, with no carry. Notice that with this field addition rule, for
every x in F2m, we have that x+x=0. That is already very different from addition in
the integers mod 2m.
Note: If you look closely, you will see that we are trying to create a system where 2
can equal 0. In fact, it is because of this property — that the number 1 added
to itself two times gives us 0 — that we say this is a field of “characteristic 2”
or “even characteristic.”
Multiplication is even more difficult to define. When you multiply two m-tuples, you
can’t just multiply them bit-by-bit, or else you would never be able to invert any
string that had a 0 in it somewhere. Instead, multiplication in F2m is a complicated
operation involving ordinary multiplication and addition of cross terms.
The mathematics underlying the construction of F2m is deep, but it is very well-
understood by mathematicians. For an in-depth discussion of this field, refer to
“Related Documents” on pagexx.
An elliptic curve, E, can be thought of as a particular type of equation. Elliptic curves
look slightly different in the two different cases.
Coefficients Over an Odd Prime Field
An elliptic curve E over an odd prime field Fp is all the pairs of points (x,y) that satisfy
the equation:
y2=x
3+ax+b
In this equation, x and y are elements of Fp, and so are a and b. The whole equation is
evaluated over Fp. For computational reasons, there is also a “point at infinity”, Ο,
that is included as well.
The numbers a and b are called the coefficients of the elliptic curve; they are part of the