Cryptography: Theory and Practice:Other Public-key Cryptosystems

cryptography: theory and practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


For example, to compute (x2 + 1)(x2 + x + 1) in , we first compute the product in , which is x4 + x3 + x + 1. Then we divide by x3 + x + 1, obtaining the expression

Hence, in the field , we have that

Below, we present a complete multiplication table for the non-zero field elements. To save space, we write a polynomial a2x2 + a1 x + a0 as the ordered triple a2a1 a0.

Computation of inverses can be done by using a straightforward adaptation of the extended Euclidean algorithm.

Finally, the multiplicative group of the non-zero polynomials in the field is a cyclic group of order seven. Since 7 is prime, it follows that any non-zero field element is a generator of this group, i.e., a primitive element of the field.

For example, if we compute the powers of x, we obtain

which comprise all the non-zero field elements.

It remains to discuss existence and uniqueness of fields of this type. It can be shown that there is at least one irreducible polynomial of any given degree n ≥ 1 in . Hence, there is a finite field with pn elements for all primes p and all integers n ≥ 1. There are usually many irreducible polynomials of degree n in . But the finite fields constructed from any two irreducible polynomials of degree n can be shown to be isomorphic. Thus there is a unique finite field of any size pn (p prime, n ≥ 1), which is denoted by GF(pn). In the case n = 1, the resulting field GF(p) is the same thing as . Finally, it can be shown that there does not exist a finite field with r elements unless r = pn for some prime p and some integer n ≥ 1.

We have already noted that the multiplicative group (p prime) is a cyclic group of order p - 1. In fact, the multiplicative group of any finite field is cyclic: GF(pn)\{0} is a cyclic group of order pn - 1. This provides further examples of cyclic groups in which the discrete log problem can be studied.

In practice, the finite fields GF(2n) have been most studied. Both the Shanks and Pohlig-Hellman discrete logarithm algorithms work for fields GF(2n). The index calculus method can be modified to work in these fields. The precomputation time of the index calculus algorithm turns out to be

and the time to find an individual discrete log is

However, for large values of n (say n > 800), the discrete log problem in GF(2n) is thought to be intractible provided 2n - 1 has at least one “large” prime factor (in order to thwart a Pohlig-Hellman attack).

5.2.2 Elliptic Curves

We begin by defining the concept of an elliptic curve.

DEFINITION 5.3  Let p > 3 be prime. The elliptic curve y2 = x3 + ax + b over , is the set of solutions to the congruence

where a, are constants such that 4a3 + 27b2 ≠ 0 (mod p), together with a special point O called the point at infinity.1


1Equation 5.1 can be used to define an elliptic curve over any field GF(pn), for p > 3 prime. An elliptic curve over GF(2n) or GF(3n) is defined by a slightly different equation.

An elliptic curve E can be made into an abelian group by defining a suitable operation on its points. The operation is written additively, and is defined as follows (where all arithmetic operations are performed in : Suppose

and

are points on E. If x2 = x1 and y2 = -y1, then ; otherwise P + Q = (x3, y3), where

and

Finally, define

for all PE. With this definition of addition, it can be shown that E is an abelian group with identity element (most of the verifications are tedious but straightforward, but proving associativity is quite difficult).

Note that inverses are very easy to compute. The inverse of (x, y) (which we write as -(x, y) since the group operation is additive) is (x, -y), for all (x, y) ∈ E.

Let us look at a small example.

Example 5.7

Let E be the elliptic curve y2 = x3 + x + 6 over . Let’s first determine the points on E. This can be done by looking at each possible , computing x3 + x + 6 mod 11, and then trying to solve Equation 5.1 for y. For a given x we can test to see if z = x3 + x + 6 mod 11 is a quadratic residue by applying Euler’s criterion. Recall that there is an explicit formula to compute square roots of quadratic residues modulo p for primes p ≡ 3 (mod 4). Applying this formula, we have that the square roots of a quadratic residue z are

The results of these computations are tabulated in Table 5.2.


Previous Table of Contents Next

Copyright © CRC Press LLC



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net