Cryptography – Particular algorithmic function encoding – Nbs/des algorithm
Patent
1997-08-18
1999-11-16
Gregory, Bernarr E.
Cryptography
Particular algorithmic function encoding
Nbs/des algorithm
380 9, 380 30, 380 49, 380 50, H04L 908, H04L 930
Patent
active
059871318
ABSTRACT:
A public-key method of cryptographic key exchange using modular exponentiation in which memory, for storing pre-computed results, can be flexibly traded off against the computational complexity of key-exchange. In a typical embodiment, the invention performs key exchange by the method of Diffie-Hellman but with exponents having a constrained form such that by use of a small table of pre-computed powers of a user's public key, any possible shared secret key within the allowed set can be computed with many fewer modular multiplications than the number of bits of effective key-length thereby obtained. The table of pre-computed powers is transmitted as part of the key exchange protocol. The party in receipt of the table uses the pre-computed powers of the sender's public key to replace calculations that would otherwise need to be done at key-exchange time. The method allows a flexible trade-off between computation and table size. The method of accelerating modular exponentiation can also be applied to other cryptographic operations in which the number to be raised to a power is fixed or known in advance and where the exponent is allowed to be of the specified form.
REFERENCES:
patent: 5274707 (1993-12-01), Schlafly
patent: 5369708 (1994-11-01), Kawamura et al.
patent: 5499299 (1996-03-01), Takenaka et al.
patent: 5588061 (1996-12-01), Ganesan et al.
patent: 5600725 (1997-02-01), Rueppel et al.
Odlyzko, "Discrete Logarithms and Smooth Polynomials," Contemporary Mathematics, vol. 168:269-278, 1994.
Montgomery, "Modular Multiplication Without Trial Division," Mathematics of Computation, vol. 44;519-521, Apr. 1985.
Digital Signature Standard, Federal Information Processing Standards Publication 186, May 19, 1994. U.S. Department of Commerce.
Bos, et al., "Addition Chain Heuristics," Lecture Notes in Computer Science, Advances in Cryptology-Crypto '89, 401-407.
Brickell, et al., "Fast Exponentiation with Precomputation (Extended Abstract)", Advances in Cryptology--Eurocrypt '92, Workshop on the Theory and Application of Cryptographic Techniques, 201-207, May 1992.
Sauerbrey, et al., Resource Requirements for the Application of Addition Chains in Modulo Exponentiation, Advances in Cryptology--Eurocrypt '92, Workshop on the Theory and . . ., 175-182, May 1992.
Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems," Advances in Cryptology--Crypto '96, 16th Annual International Cryptology Conference, 105-113, Aug. 1996.
Rivest, et al., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communication of the ACM, vol. 21: 120-126, Feb. 1978.
Coppersmith, "Fast Evaluation of Logarithms in Fields of Characteristic Two," IEEE Transactions Information Theory, vol. IT-30:587-594, Jul. 1984.
Diffie, et al., "New Directions in Cryptography," IEEE Transactions on Informaton Theory, vol. IT-22;644-654, Nov. 1976.
van Oorschot, et al., "Parallel Collision Search With Application to Hash Functions and Discrete Logarithms" Bell-Northern Research, 210-218, Aug. 1994.
Seminumerical Algorithms, vol. 2, The Art of Computer Programming, Second Edition. (index only).
Gregory Bernarr E.
PictureTel Corporation
LandOfFree
Cryptographic key exchange using pre-computation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cryptographic key exchange using pre-computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptographic key exchange using pre-computation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1334395