RSA Security 5.2.2 manual Odd Prime Fields, Fields of Even Characteristic

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 page 51. 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 mod 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–1cannot be invertible in the integers mod 2m (except for m = 1). To see this, consider the product 2·2m–1= 2m ≡ 0 mod 2m. If 2m–1

did have an inverse, I, then we would have:

C h a p t e r 3 C r y p t o g r a p h y 6 7