As an exercise, I went hunting for smallest possible RSA cryptosystem such that I could perform all of the encryption and decryption calculations in my head. This turns out to be quite silly, of course. But perhaps you could consider using this as a toy-box classroom example, or possibly like me, you may find it helps you remember the process by being able to exercise the whole thing concretely in your brain.
I'll use the same notation as in the Wikipedia: RSA (cryptosystem) article, which you may want to review (I'll avoid repeating the basic principles of the system here). So our system needs distinct primes p and q, the product n = pq, and decryption/encryption exponent keys d and e. I'll also use, as per the original RSA paper, φ(n) = (p − 1)(q − 1) as the value with which our keys need to avoid common factors.
Obviously, the fundamental calculation for both encryption and decryption is computations of me mod n. Which looks pretty simple, unless you have a large exponent e, and you're trying to do this in your head. Secondarily, having big plaintext values m complicates the job. Being able to reduce modulo n seems nice, but even as an intermediary step I don't want to be raising double-digits m's to double-digit e's, say.
So the first job is to find a usable encryption exponent e. As noted on Wikipedia, "the smallest (and fastest) possible value for e is 3". Let's just reflect on why that is for a second. You can't use e = 0, aside from collapsing every block to a value of 1, because gcd(0, φ(n)) = φ(n) ≥ 2, instead of the required 1 (since the minimal primes p and q are 2 and 3, the minimal φ(n) is (1)(2) = 2). You can't use e = 1, because that would send every block to itself, and not demonstrate any encryption at all. You can't use e = 2, because at least one of your pair of primes is odd, so either (p − 1) or (q − 1) has a factor of 2, which can't be shared by e; and for the same reason e can't be any other even number.
So our first valid option for exponentiation is e = 3, and the next one is e = 5, etc. I don't know about you, but I really don't think I can do 5th or 7th powers of arbitrary numbers reliably in my head (even modulo n), so I'm aiming to just use e = 3 here.
Now, what can we use for the primes p and q? Even using one as big as 7 causes problems; say if p = 7, then (p − 1) = 6 = 2(3), at which point the factor of 3 blocks you from using our desired encryption key of e = 3. If I used a pair like 5 and 11, then n = 55, and I'm poised to be cubing numbers as big as 54, which is way outside my mental times-tables. So it looks like I'll be compelled just use 3 and 5 as our prime pair.
In this case, if p = 3 and q = 5, so n = 15, then we don't even have sufficient space to encode all the letters of the alphabet (I said this was silly, right?). Also, we'll only be able to encode one of our limited characters at a time, which loses sight of the fact that RSA is a block cipher, but let's choose to forgive that. We'll enumerate the first part of the alphabet as A = 0, B = 1, C = 2, ... O = 14. Also note that
φ(n) = 2(4) = 8 (so the only factor we need to avoid in e is 2, and we can indeed use e = 3).
What about our decryption key exponent d? Well, there's a goofy coincidence here: solving the required congruence de ≡ 1 (mod φ(n)), that is, 3d ≡ 1 (mod 8)), we get d = 3 (because 3(3) = 9 = 8 + 1). Here we have d = e, so our encryption and decryption keys happen to be the exact same thing. On the one hand, this seems like a degenerate example for how the RSA system should work, but for our mental arithmetic, it's pretty darned nice that both keys are the smallest value possible. (As noted, I really didn't want to be raising values to a 7th power or something for decryption purposes!). So we can work with that.
Here's an example. Let's say we want to mentally encrypt the plaintext message "MIND". Using our number-encoding scheme, these four characters are represented by the numbers (12, 8, 13, 3). Computing the necessary cubings-modulo-15 to encrypt, we can feasibly find in our head:
- 12³ = (144)(12) = (135 + 9)(12) ≡ (9)(12) = 108 = 105 + 3 ≡ 3 (mod 15)
- 8³ = (64)(8) = (60 + 4)(8) ≡ (4)(8) = 32 = 30 + 2 ≡ 2 (mod 15)
- 13³ = (169)(13) = (165 + 4)(13) ≡ (4)(13) = 52 = 45 + 7 ≡ 7 (mod 15)
- 3³ = (9)(3) = 27 = 15 + 12 ≡ 12 (mod 15)
So our encrypted message is (3, 2, 7, 12), or "DCHM" if we send it as alphabetic characters. Decrypting is (fortunately or unfortunately, depending on your perspective) exercising the exact same mental algorithm:
- 3³ ≡ 12 (mod 15) [as above]
- 2³ ≡ 8 (mod 15) [super easy!]
- 7³ = (49)(7) = (45 + 4)(7) ≡ (4)(7) = 28 = 15 + 13 ≡ 13 (mod 15)
- 12³ ≡ 3 (mod 15) [as above]
And indeed we recover our original transmission of (12, 8, 13, 3), or "MIND".
Okay, hopefully you can appreciate that example. Because I had to work really, really hard to find one that avoided being totally nonsensical. Here's why: In our toy cryptosystem, most characters get sent to themselves under encryption! Specifically (looking at the numerical representations): 0 → 0, 1 → 1, 2 → 8, 3 → 12, 4 → 4, 5 → 5, 6 → 6, 7 → 13, 8 → 2, 9 → 9, 10 → 10, 11 → 11, 12 → 3, 13 → 7, 14 → 14.
In summary: Only the six plaintext values 2, 3, 7, 8, 12, and 13 get sent to other images; the other nine values all get sent to themselves. That is, the only letters that get transformed are C, D, H, I, M, N -- and you'll notice that I carefully constructed my example of "MIND" to use exclusively, and almost all of, these available characters. Note in particular that "I" is the only available vowel in that set (initially I considered encoding A = 1, B = 2, etc.; but in that case we get no vowels with images different from themselves.)
In case you want to memorize these transformations directly, then it might help to observe the pattern, starting with 14 and wrapping around, that you get 3 values sent to the same as themselves, then 2 with different images, then 3 same, 2 different, 3 same, and 2 different. (Again noting a total of 6 characters that get sent to images different from themselves.) And the decryption function is, obviously, identical.
Is that of any interest? As I opened with, it's pretty darned silly. We can only handle letters up to O, we lose the block-cipher action, the encryption and decryption keys are identical, and most of our values get sent to themselves under the transformation. But I thought it was an interesting puzzle to see if there as any example that I could compute mentally without any mechanical or even pen-and-paper aid, and it turns out there is.
Leave a comment if you ever use that in a class or paper as a warm-up demonstration!
