Neal Koblitz has located prior art destroying this patent: an article by Bender and Castagnoli in the CRYPTO '89 proceedings.
The patent was filed in September 1991. The proceedings of CRYPTO '89 were, according to Springer, published in June 1990. I would like to hear confirmation from people who received the proceedings in June, July, or August 1990, or who received a preprint handed out at CRYPTO '89 and can verify that it contained the same text as the proceedings.
The Bender-Castagnoli article reports an implementation of the Diffie-Hellman system on various elliptic curves, including an elliptic curve modulo 2^127+24933, ``which is convenient in computer arithmetic.''
Claim 1 of the patent is for the Diffie-Hellman system on an elliptic curve over a finite field of characteristic p ``where p is one of a class of numbers such that mod p arithmetic is performed in a processor using only shift and add operations.'' Claim 2 is for an example: p of the form 2^q-C ``where C is a binary number having a length no greater than 32 bits.'' Claim 3 is for another example: Mersenne numbers 2^q-1. Claim 4 is for another example: Fermat numbers 2^q+1. Claims 5, 11, and 12 are equivalent to claim 1. Claims 6, 7, and 8 are claim 1 with FFT-based methods of performing the elliptic-curve computations. Claim 9 is claim 1 ``further including encrypting means.'' Claim 10 is claim 9 ``further including decrypting means.''
Claims 1, 2, 5, 9, 10, 11, and 12 are automatically invalid, because each of them includes the system published by Bender and Castagnoli more than a year before the patent was filed. Claim 3 is invalid, because it is an obvious variant. Nobody cares about claims 4, 6, 7, and 8.