The seminal Rivest, Shamir, Adleman (RSA) paper from 1977. A blast from the past, and a real treat (especially for a student of cryptography) to finally read it!

Why now?

I had been meaning to get to this paper for a while, but kept finding reasons to put it off. After all, it was already a decades old paper by the time I found out. Why not wait a few more years?

Recently I was implementing the RSA cryptosystem (as part of a Manning LiveProject 1). While the main goal of this exercise was to gauge my progress with Rust, I realized I was not going to find a better time than right now to read this classic 2.

Turns out it is only 20 pages and written very accessibly so embarrassed I waited.

A couple surprises

So the authors definitely dig into practical applications of and the math behind the cryptosystem, but I did discover two surprises.

First, I wonder if this was the first appearance of Alice and Bob? If so, wow!

Second, while I am familiar with Loren Kohnfelder’s later work (book and STRIDE model), I did not know he was an MIT student at this time nor that he contributed to this paper.

A small example

See section “VIII. A Small Example” at https://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-082.pdf.

Here is quick walkthrough.

$ python
Python 3.13.5 (main, Jun 25 2025, 18:55:22) [GCC 14.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> p = 47
>>> q = 59
>>> n = p * q
>>> n
2773
>>> d = 157
>>> phi = (p - 1) * (q - 1)
>>> phi
2668
>>> e = pow(d, -1, phi)
>>> e
17
>>> assert(e * d % phi == 1)
>>>

Given $p$, $q$, $d$ confirm the expected $\phi(n)$ and $e$. Also, assert that $ed \equiv 1\mod{\phi(n)}$. Interestingly, $e$ is computed after choosing $d$, which is backwards from how it is typically done now.

With such a small $n$ the authors decide on a two letters per block encoding, substituting a two-digit number for each letter. For the described “alphabet” the encoding will produce integers that fit under $n-1$.

How convenient. :-D

>>> message = b"IT'S ALL GREEK TO ME"
>>> alphabet = " ABCDEFGHIJKLMNOPQRSTUVWYZ"
>>> alphabet.find("I")
9
>>> alphabet.find("T")
20
>>>

In other words, the first block of two letters IT is encoded as integer $920$.

>>> M = 920
>>> c = pow(M, e, n)
>>> c
948
>>> p = pow(c, d, n)
>>> p
920
>>>

Confirm ciphertext $c = M^e\mod{n}$ matches the expected example output of $948$. Also, that plaintext $p = c^d\mod{n}$ matches the original message block $M$.

Stopping here should suffice. I leave the rest as an exercise for the reader 3. Have fun!!

– JW

Footnotes

  1. See source code and submitted solutions at https://github.com/jelaiw/rsa-alg. Manning is trying to innovate with the hands-on LiveProject idea and this was the first one I have tried. Glad I did it, but my review is mixed. Worth $10 though if you can get it on sale. ↩

  2. David Hoover and Adewale Oshineye exhort us to “Study the Classics” in their Apprenticeship Patterns book. Doing this already comes naturally to me (perhaps due to my stints in academia), but I welcome the nudge. ↩

  3. It may be more satisfying and realistic to encrypt the entire message, say, as a byte string converted to an integer. Just use a bigger modulus. If my quick math is correct $n$ needs to be bigger than 159 bits or 48 digits to accommodate that message. ↩