Abstract
An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n, of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n.
- 1 Diffie, W., and Hellman, M. New directions in cryptography. IEEE Trans. Inform. Theory IT-22, 6 (Nov. 1976), 644-654.Google ScholarDigital Library
- 2 Diffie, W., and Hellman, M. Exhaustive cryptanalysis of the NBS data encryption standard. Computer 10 (June 1977), 74-84.Google ScholarDigital Library
- 3 Knuth, D. E. The Art of Computer Programming, Vol 2: Seminumerical Algorithms. Addison-Wesley, Reading, Mass., 1969. Google ScholarDigital Library
- 4 Levine, J., and Brawley, J.V. Some cryptographic applications of permutation polynomials. Cryptologia 1 (Jan. 1977), 76-92.Google ScholarCross Ref
- 5 Merkle, R. Secure communications over an insecure channel. Submitted to Comm. ACM. Google ScholarDigital Library
- 6 Miller, G.L. Riemann's hypothesis and tests for primality. Proc. Seventh Annual ACM Symp. on the Theory of Comptng. Albuquerque, New Mex., May 1975, pp. 234-239; extended vers. available as Res. Rep. CS-75-27, Dept. of Comptr. Sci., U. of Waterloo, Waterloo, Ont., Canada, Oct. 1975. Google ScholarDigital Library
- 7 Niven, I., and Zuckerman, H.S. An Introduction to the Theory of Numbers. Wiley, New York, 1972.Google Scholar
- 8 Pohlig, S.C., and Hellman, M.E. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. To appear in IEEE Trans. Inform. Theory, 1978.Google ScholarCross Ref
- 9 Pollard, J.M. Theorems on factorization and primality testing. Proc. Camb. Phil. Soc. 76 (1974), 521-528.Google ScholarCross Ref
- 10 Potter, R.J., Electronic mail. Science 195, 4283 (March 1977), 1160-1164.Google Scholar
- 11 Rabin, M.O., Probabilistic algorithms. In Algorithms and Complexity, J. F. Traub, Ed., Academic Press, New York, 1976, pp. 21-40.Google Scholar
- 12 Solovay, R., and Strassen, V. A Fast Monte-Carlo test for primality. SIAM J. Comptng. 6 (March 1977), 84-85.Google ScholarCross Ref
- 13 Federal Register, Vol. 40, No. 52, March 17, 1975.Google Scholar
- 14 Federal Register, Vol. 40, No. 149, August 1, 1975.Google Scholar
Index Terms
- A method for obtaining digital signatures and public-key cryptosystems
Recommendations
A method for obtaining digital signatures and public-key cryptosystems
Special 25th Anniversary IssueAn encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences:
- Couriers or other secure means are not needed to transmit ...
Fail-Stop Signatures
Fail-stop signatures can briefly be characterized as digital signatures that allow the signer to prove that a given forged signature is indeed a forgery. After such a proof has been published, the system can be stopped. This type of security is strictly ...
On-line/off-line digital signatures
CRYPTO '89: Proceedings on Advances in cryptologyWe introduce and exemplify the new concept of ON-LINE/OFF-LINE digital signature schemes. In these schemes the signing of a message is broken into two phases. The first phase is off -line. Though it requires a moderate amount of computation, it presents ...
Comments