RSA Security 5.2.2 manual Coefficients Over an Odd Prime Field, = 0·I ≡ 2·2m-1·Imod2m

Cryptography Overview

0 = 0·I

≡(2·2m–1)·Imod2m

= 2·(2m–1·I)

≡2·1 mod 2m

= 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 page xx.

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 = x3 + 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

6 8 R S A B S A F E C r y p t o - C D e v e l o p e r ’s G u i d e