Chapter 3 Cryptography 67
Cryptography Overview
•An odd prime field, Fp, where p is an odd prime.
•A field of even characteristic, F2m.
For more information about finite fields, see the book by A. Menezes, I. Blake, X. Gao,
R. Mullin, S. Vanstone, and T. Yaghoobian, Applications of Finite Fields [18] and also
Chapter 2 of Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone’ s book,
Handbook of Applied Cryptography [17].
Odd Prime Fields
The odd prime field Fp is simply Zp, the integers mod p. Modular math is described in
the section “The RSA Algorithm” on page5 1. Recall that in modular math, we have
addition and multiplication, with the additional twist that the numbers loop around,
so that, for example, p+1= 1 mo d p.
Although you don’t need it to use the cryptosystem, a little background may help.
Because p is prime, Fp has an interesting property that not all modular math systems
have: except for 0, every number in Fp has a multiplicative inverse. That is, given any
number c between 1 and p–1, there is another number d in the same range such that
cd= 1 mod p. This is the crucial property that distinguishes Fp from other modular
math systems and makes it a field.
Not all moduli will give you a field. For instance, our earlier example, arithmetic mod
55, is not a field. You can see this by looking at the number 5 in this system. The first
ten multiples of 5 are: 5, 10, 15, 20, 25, 30, 35, 40, 45, and 50. When we multiply 5 by 11,
we get 55, which is just 0 mod 55. Now, when we multiply 5 by 12, we just fall back
down to 60= 60–55 = 5 mod 55. In fact, no matter by what we multiply 5, we will just
get a multiple of 5, which will reduce back down to the ten numbers listed above.
There is no way we can get to 1 as a multiple of 5 in this particular modular system.
In fact, the only numbers that will give a field in modular arithmetic are the primes.
So you can see that fields are fairly special. The crucial thing to remember is:
An odd prime field, Fp, is just modular arithmetic, where the modulus p is prime.
Fields of Even Characteristic
The fields of even characteristic, also known as characteristic 2, are more complicated. If
you were looking for a field of that size, you might start with the integers mod 2m.
However, it turns out that integers mod 2m cannot be a field for any m>1.
Why is this? Remember, we said every element in a field, except 0, has a
multiplicative inverse. But, for example, 2m–1 cannot be invertible in the integers mod
2m (except for m=1). To see this, consider th e product 2·2m–1 =2m≡0 mod 2m. If 2m–1
did have an inverse, I, then we would have: