Method and apparatus for public key exchange in a cryptographic system

DETAILED DESCRIPTION The present invention is an elliptic curve cryptosystem that uses elliptic curves defined over finite fields comprised of special classes of prime numbers.
Special fast classes of numbers are used to optimize the modulo arithmetic required in the enciphering and deciphering process.
The class of numbers used in the present invention is generally described by the form 2.
sup.
q -C where C is an odd number and is relatively small, (for example, no longer than the length of a computer word (16-32 bits)).
When a number is of this form, modulo arithmetic can be accomplished using shifts and adds only, eliminating the need for costly divisions.
One subset of this fast class of numbers is known as "Mersenne" primes, and are of the form 2.
sup.
q -1.
To perform an n mod p operation where p is a Mersenne prime of the form 2.
sup.
q -1, the q LSB's are latched and the remaining bits are added to these q bits.
The first q bits of this sum are latched and the remaining bits are added to them.
This process continues until the sum has q or fewer bits.
This sum is the solution.
Another class of numbers that can be used with the present invention are known as "Fermat" numbers of the form 2.
sup.
q +1, where q is equal to 2.
sup.
m and m is an integer.
Modulo arithmetic using a Fermat number involves shifting q bits and alternately subtracting and adding next successive groups of q bits until the resultant has q or fewer bits.
The present invention provides a system that has tunable levels of security, that is the level of security desired is adjustable.
q acts as an encryption bit depth parameter, such that larger values of q provide increased security.
By using a fast class of numbers, only shifts and adds are required for modulo arithmetic.
Inversion operations normally require an elliptic curve algebra can be avoided by selecting an inversionless parameterization of the elliptic curve.
Fast Fourier transform (FFT) multiply mod operations, optimized for efficient Mersenne arithmetic, allow the calculations of very large q to proceed more quickly than with other schemes