0
$\begingroup$

I'm doing some research into the RSA cryptosystem but I just need some clarity on how it worked when it was published in the 70s. Now I know that it works with public keys but did it also work with private keys back then or did it use a shared public key first and then private keys were introduced later?

$\endgroup$
  • 5
    $\begingroup$ Your question makes no sense. Maybe you should read this first: en.wikipedia.org/wiki/RSA_(cryptosystem) $\endgroup$ – Elias Oct 25 '17 at 5:16
  • 1
    $\begingroup$ RSA has always used both private keys (for decryption) and public keys (for encryption). $\endgroup$ – Elias Oct 25 '17 at 5:16
  • 2
    $\begingroup$ "... need some clarity on how it worked when it was published in the 70s" How about reading the actual publication? $\endgroup$ – tylo Oct 25 '17 at 11:56
7
$\begingroup$

RSA never was intended as a symmetric/secret key cryptosystem, or extensively used as such. Public/Private key pairs have been used for RSA from day one.

A very close cousin of RSA, also using Public/Private key pairs, was known (but not published) at the GCHQ significantly before RSA was published. See Clifford Cocks's declassified A Note on 'Non-secret Encryption' (1973). Public-key cryptography was theorized at the GCHQ even before, see James Ellis's declassified The Possibility of Secure Non-Secret Encryption (1969), and his account in the declassified The history of Non-Secret Encryption (1987). See this question for more references on these early works.


As kindly reminded by poncho: the Pohlig-Hellman exponentiation cipher is a symmetric analog of textbook RSA. It uses as public parameters a large public prime $p$ with $(p-1)/2$ also prime, and two random odd secret exponents $e$ and $d$ with the relation $e\cdot d\equiv1\pmod{(p-1)}$; encryption of $m$ with $1<m<p$ is $c\gets m^e\bmod p$, decryption is $m\gets c^e\bmod p$. By incorporating the computation of $d$ from the encryption key $e$ into the decryption, and using cycle walking to coerce down the message space to bitstrings and remove a few fixed points, it becomes a full-blown block cipher by the modern definition of that. Security is related to the discrete logarithm problem in $\mathbb Z_p^*$ . An algorithm for solving that is the main subject of the article, and what Pohlig-Hellman now designates. The encryption algorithm has little practical interest, because it is very slow for a symmetric-only algorithm. It never caught in practice, and I believe never was intended to do so.

I found no earlier reference than: Stephen C. Pohlig and Martin E. Hellman, An Improved Algorithm for Computing Logarithm over $GF(p)$ and Its Cryptographic Significance published in IEEE Transactions on Information Theory, Volume 24 Issue 1, January 1978.

RSA was clearly known to the authors when they submitted this correspondence. They make explicit reference to:

  1. Ronald L. Rivest, Adi Shamir, and Leonard Adleman, On Digital Signatures and Public-Key Cryptosystems, Technical Memo MIT/LCS/TM-82, dated April 1977 (received by the Defense Documentation Center on May 3, 1977; publication date unknown).
  2. Ronald L. Rivest, Adi Shamir, and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems published in Communications of the ACM, Volume 21 Issue 2, February 1978 (received April 4, 1977; revised September 1, 1977).

Note: I discovered (1.) only because it is referenced by Pohlig and Hellman; it has a number of rough edges fixed in (2.), including a byzantine and unnecessary complication in the handling of messages not coprime with the public modulus, that are telling of the novelty.

I refer to poncho's account on chronology.

$\endgroup$
  • 2
    $\begingroup$ "Modular exponentation was proposed after RSA as a building block for symmetric cryptography"; actually, according to a talk that Hellman gave, he and Polig created a design for using modexp (using a prime modulus) to do symmetric crypto shortly before RSA; however it ended up being published afterwards (as RSA was seen as a breakthough, hence its publication was fasttracked...) $\endgroup$ – poncho Oct 25 '17 at 12:54
  • $\begingroup$ @poncho: I failed to locate a transcript of Hellman's talks (or even a recording/video). Any source? $\endgroup$ – fgrieu Oct 25 '17 at 15:43
  • $\begingroup$ Hmmmm, it was an invited talk at Crypto99; I wouldn't know if there are any recordings... $\endgroup$ – poncho Oct 25 '17 at 16:02
  • $\begingroup$ On second thought, it might have been Ralph Merkle's invited talk at Crypto05... $\endgroup$ – poncho Oct 25 '17 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.