A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

R.L Rivest, A. Shamir, L. Adleman - MIT Laboratory for Computer Science

Communications of the ACM, February 1978

 

 

In one of the ground-breaking papers in the field of public-key cryptosystems, Rivest, Shamir and Adleman discuss how to use modular exponentiation algorithms to implement a secure, authenticated cryptosystem. Their cryptosystem efficiently provides 1) security from eavesdroppers, 2) digital signatures for authentication, 3) the inability of 3rd party users to splice in their own message into a pre-authenticated message.

The method they accomplish this is described as follows.

 

  1. Represent the message to be sent as an integer M.
  2. The public key consists of (e, n) where n is the product of two very large primes, and e is the encryption exponent (described in more detail below).
  3. The private key consists of (d, n) where n is the product described above, and d is the decryption exponent (described in more detail below).
  4. To encrypt message M,
  1. Raise M to publicly specified power e
  2. Take remainder when result is divided by publicly specified product n
  3. e.g. E(M) = Me (mod n), where 0 £ M £ n - 1
  1. To decrypt ciphertext C = E(M),
  1. Raise C to privately held power d
  2. Take remainder when result is divided by publicly specified product n
  3. e.g. D(C) = Cd (mod n) = M, where 0 £ C £ n - 1
  1. The public-private key pair is generated as follows,
  1. Choose two large, random primes p and q, and define product n = p * q
  2. Pick integer d to be a large, random, relative prime to (p - 1) * (q - 1)

    3. (e.g. gcd(d, (p - 1) * (q - 1)) = 1)

  3. Finally e is computed to be the "multiplicative inverse" of d, modulo (p - 1) * (q - 1).

    4. (e.g. e * d = 1 (mod (p - 1) * (q - 1)), note: this is a number theoretic congruency, not an equivalence)
  1. To efficiently encrypt (decryption uses the same algorithm, only different variable names),
  1. Let ekek-1 … e1e0 be the binary representation of e
  2. Set variable C to 1
  3. Repeat i. and ii. for i = k, k-1, …, 1, 0
  1. Set C to C2 (mod n)
  2. If ei = 1, set C to (C * M) (mod n)
  1. Halt. C is the ciphertext message.

 

 

The cryptographical power behind this algorithm lies in the fact that E(M) is a one-way function. It is very easy to compute E(M) = C, but given only C, e, and n, it is very difficult to get the message M back. The problem is reducible to factoring n to its constituent primes p and q, which is historically very difficult. It has not been proven so, but over decades of research, no one has been able to find a logarithmic-time algorithm to factor integers. The fastest known factoring algorithms are (or were, in 1978) O(n1/4) for Pollard's Algorithm, and O((ln n)sqrt(ln n / ln (ln n))) for Schroeppel's Algorithm.

The paper discusses various possible security holes, including methods involving cracking the key without actually factoring the number n. One includes computing the function f (n), which indicates the set of integers less than n which are relatively prime to n. The authors contend that all such approaches are at least as hard as factoring.

 

 

New Directions in Cryptography

 

Whitfield Diffie and Martin E. Hellman - IEEE Transactions on Information Theory, 1976.

 

In another very famous cryptography paper, Diffie and Hellman outline a public-key cryptosystem built on the difficulty in computing the logarithmic function. The paper begins by giving a very broad, general description of the current state of cryptography. Before the Diffie-Hellman algorithm, secure cryptographic required the prescence of a secure channel on which to exchange keys before transmission of encrypted data. Furthermore, the more secure cryptographic systems at that time were computationally very difficult. For example, the one-time pad was a secure system but required combining the plaintext with a randomly chosen key of the same length. The computation time was unefficient. Other general cryptographic methods were described (e.g. block ciphers which act in a combinatorial way on large blocks of text and produce large changes in the ciphertext output as a result of very small changes in the input plaintext; and stream ciphers which process plaintext in small chunks such as bits or characters).

The possible attacks on a cryptography system are distinguished as follows. A ciphertext only attack is one where the cryptanalyst (person trying to break the code) possesses only ciphertext, from which he attempts to decipher the original message. A known plaintext attack is when the cryptanalyst possesses a substantial portion of the original plaintext, as well as the whole ciphertext. A chosen plaintext attack is an attempt to discover the cipher key by submitting random plaintext messages (or intelligently chosen messages) to the cryptographic algorithm. The cryptanalyst can keep submitting such messages until one matches the ciphertext, at which point he knows the key.

There are three main goals to a secure cryptography system. One, prevention of 3rd party eavesdropping. Two, provide authentication to prevent 3rd party impersonation of the real sender. Three, accomplish the first two goals in a computationally feasible algorithm, with no need for a secure key-distribution channel. Diffie and Hellman proceeded to propose such a system.

Their idea makes use of the apparent difficulty in computing logarithms over a finite field GF(q) with a prime (q) number of elements.

 

  1. The one-way encryption function is as follows,
  1. Raise fixed primitive element a of GF(q) to the integer representation of M.

    2. e.g. Y = aX (mod q), where 1 £ X £ (q - 1)

  2. Exponentiation can be done in logarithmic time complexity, O(log q).
  1. The (difficult) decryption function involves finding X, given Y,
  1. One would need to compute the logarithm base a, modulo q.

    2. e.g. X = loga Y (mod q), where 1 £ Y £ (q - 1)

  2. Calculating a logarithm is apparently a very intractable function, O(Ö q), unless one knows the base a.
  1. Therefore two users, i and j, wishing to communicate can use the following as cipher key,
  1. Kij = aXiXj (mod q) = YjXi (mod q) = YiXj (mod q)
  2. No one can compute Kij except users i and j, since only they possess Xi and Xj
  3. For the same reason, the message will be known to originate from the real sender

 

The power of this cryptosystem lies in the relative intractability of computing logarithms compared with exponentiation. Exponentiation is an example of a one-way function, since computing the inverse of the function is harder than computing the function itself. Choosing very large numbers makes this difference in compute time very significant.

 

Digitalized Signatures and Public-Key Functions as Intractable as Factorization

 

Michael O. Rabin

Visiting Professor of Applied Mathematics, MIT

Professor of Mathematics, Hebrew University, Jerusalem

January 1979

 

This paper is a follow-up to Rivest, Shamir, and Adleman's "Method for Obtaining…" and was intended to prove that their system is in fact as intractable as factorization. The paper took the form of mathematical definitions of algorithms for breaking RSA and reduction proofs, which I did not completely decipher. But the gist of it was that breaking RSA was formerly known to be at most as hard as factoring. Rabin proved that RSA was in fact equivalent in difficulty to factoring.

He showed mathematical proofs that reduced both the problem of cracking an RSA digital signature, and the problem of cracking RSA encryption to the problem of factorization. He shows that we cannot invert y = En(x) (where En(x) is the RSA encryption function) for even a small percentage of the values y, and thus we cannot factor n.