On the morning of April 27., we convened to read “A method for Obtaining Digital Signatures and Public-Key Cryptosystems” by Rivest, Shamir, and Alderman [1]. The following Summary was written by Mathias C. Cornjäger:

This paper (first published in 1978) outlined the first practicable Public-Key encryption-system. This encryption-system is still in wide use today, and known by the initials of the paper’s three authors–RSA.

The paper itself is well written and readable. The first 4 sections give an introduction to the theory of “public key cryptosystems” (an already known concept at the time the paper was written), after which the authors outline their proposed implementation of such a system along with arguments why they think the system ought to be hard to break.

The goal of a “public key cryptosystem” is to establish a protocol for how to exchange private messages between two parties via insecure channels of communication without relying on shared secrets between the two parties or a trusted third party. Such protocols had already been proposed earlier by Deffie and Hellman [2], who elaborated on how a class of encryption- and decryption-functions satisfying a list of four axioms could in theory be used to facilitate private messages and digital signatures. It is worth reiterating that the main contribution this paper made was to give the first example of a class of functions which satisfied these four axioms.

An interesting detail in these first sections which the paper laid out quite clearly, was the difference between authentication and signature of messages. A message sent from Alice to Bob is authentifiable if Bob is able to satisfy himself that the message he has just received was indeed sent by Alice (or at least someone with knowledge of Alice’s private key), and that it has not been modified in transit. The same message is regarded as signed only if Bob can convince not only himself, but also a third party (say a judge should a contractual dispute arise), that the message he has received was in fact sent by Alice and that no-one (including Bob himself) could have altered/forged that signed message.

In the proposed encryption-scheme, a public-private key-pair consists of two tuples (e,n) and (d,n), where n is the product of two large primes p and q. If these numbers satisfy the conditions that

1. d is co-prime to (p-1)*(q-1), and
2. e*d = 1 holds modulo (p-1)*(q-1),

it can be proven that for any non-negative integer M < n the identity ((M^e)^d) = ((M^d)^e) = M holds modulo n. Encryption then consists of exponentiating a number by e modulo n, and decryption in exponentiation by d (again, modulo n).

The proposed method for encrypting a message intended for the owner of the public-key (e,n) is then to encode a message as a number M<n, and from  M to obtain the cipher C = M^e (mod n) (if the message is to long, it is broken up into blocks).
This cipher C can then be transmitted, and the intended recipient can decode it by computing C^d = (M^e)^d) = M (mod n). Anyone else who obtains C will have a hard time recovering M, since they don’t know d.

Since (e,n) is public, and d can be computed form (e, p , q) using the generalized Euclidian algorithm, the security of the cryptosystem relies on large numbers being difficult to factor (it would otherwise be easy for a third party to obtain p and q from n). The problem of factorizing integers is a well studied problem in number-theory, and no efficient methods of doing so have been developed in the past 300 years (and it is unknown if any exist). With this in mind, the authors argue that the system is unlikely to be broken any time soon.

The last sections of the paper briefly outline proposed algorithms on how to efficiently generate key-pairs, as well as discussions of why other methods of obtaining d from (e,n) can be conjectured to be at least has hard as factoring n.

Next meeting (May 18.) we intend to review Shor’s Paper [3] where he proposes a polynomial time factoring algorithm (on quantum computers).

References:
[1] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Commun. ACM, vol. 21, no. 2, pp. 120–126, 1978.
[2] Diffie, W., and Hellman, M. New directions in cryptography. IEEE Trans. Inform. Theory IT-22, (Nov. 1976), 644-654.
[3] P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Rev., vol. 41, no. 2, pp. 303–332, Jan. 1999.