Citibank, N.a.

Bell Communications Research, Inc.

Arjen K Lenstra

Peter M Winkler

Yacov Yacobi

Eric R Verheul

Improvements are obtained in key generation and cryptographic applications in public key cryptography, by reducing the bit-length of public keys, thereby reducing the bandwidth requirements of telecommunications devices, such as wireless telephone sets.

Efficient and compact subgroup trace representation ('XTR')

Cyclotomic polynomials are used to construct subgroups of multiplicative groups of finite fields that allow very efficient implementation of discrete logarithm based public key cryptosystems, including public key encryption schemes and digital signature schemes. A field is represented with an optimal normal basis, and a generator of a subgroup of the multiplicative group of the field is used to form a public key.

Cyclotomic polynomial construction of discrete logarithm cryptosystems over finite fields

Techniques are provided for generation of an RSA modulus having a predetermined portion. The predetermined portion may be the leading digits of the modulus, or split between the leading and trailing digits of the modulus. The resulting RSA modulus has the same security level as conventional RSA moduli, but requires less storage space. Significant performance improvements may be obtained for encryption, decryption, digital signature generation and digital signature verification when using RSA moduli in a specifically chosen format, as the division portion of a modulo operation is accomplished using only multiplication operations, and without using division operations.

Generating RSA moduli including a predetermined portion

Participants in a cryptosystem select their own elliptic curve and finite field, rather than using a centrally chosen elliptic curve. The curve is chosen from a predetermined set of elliptic curves expressed as Weierstra&bgr; model equations. The public key is based on a participant's unique ID, which must be exchanged during communication setup for non-cryptographic reasons, and a randomly chosen bitstring having a length based on security considerations. The public key can be readily constructed from parameters and mapping functions which are known system-wide and from a small amount of participant dependent data.

Cryptosystems with elliptic curves chosen by users

A key escrow technique is disclosed which permits cryptographic limits on wiretapping warrants. Specifically, time limits on wiretaps may be enforced. In addition, the wiretapper is targeted to a specific party or specific pairs of parties communicating in a network.

Growing community of inventors

Basking Ridge, NJ, United States of America

Arjen K Lenstra