Cryptography: Caesar, Vigenère and RSA

In Year 5 (the final year of Italian high school), in the computing and telecommunications programme at technical institutes, cryptography arrives inside the block on networks: after the layered model and the protocols, the teacher moves on to how what travels over the network is protected. If the test or oral questioning falls in five to eight weeks, it is the right moment to sort this topic out, because it is one of those where those who have understood the mechanism write three lines and get the mark, while those who have memorised the scheme freeze at the first variant.

The typical question takes three forms: write a Caesar cipher in Python, explain the difference between symmetric and asymmetric cryptography, encrypt and decrypt a message with RSA using small numbers. The three things are connected and I tackle them in that order, as in a tutoring hour.

A warning: there is not yet a dedicated practice test on computing, so here you will find only the worked exercises at the end. For the picture of what lies underneath (layers, protocols, ports) I refer you to the post on the OSI and TCP/IP model; for VLANs, firewalls and VPNs from the design side there is the post on Year 5 systems and networks. Here I deal only with how ciphers work.

The minimum vocabulary

The plaintext is the original message; the ciphertext is what comes out of the algorithm; the key is the secret parameter that decides how you encrypt; encrypting goes from plain to cipher, decrypting goes back with the key. Someone who tries to read the message without the key is doing cryptanalysis.

Kerckhoffs’s principle, which teachers often cite: security must depend only on the secrecy of the key, not on that of the algorithm.

Substitution ciphers: Caesar

In the Caesar cipher each letter is shifted forward by $k$ positions in the alphabet; the key is the number $k$ . With $k = 3$ A becomes D, B becomes E, and so on; at the end the alphabet wraps round: X becomes A, Y becomes B, Z becomes C.

To write it properly you need the modulus. Numbering the letters from 0 (A) to 25 (Z), the encryption of the letter of index $x$ is:

c = (x + k) mod 26

and decryption is the inverse operation:

x = (c - k) mod 26

Here is the Python code, the one you are asked to write by hand in a test:

def caesar(text, k):
    out = ""
    for c in text.upper():
        if c.isalpha():
            out += chr((ord(c) - 65 + k) % 26 + 65)
        else:
            out += c
    return out

ord(c) returns the code of the letter (A is 65), subtracting 65 gives the index 0-25, you add $k$ , reduce modulo 26 and with chr(... + 65) you go back to a letter. Spaces and punctuation pass through unchanged.

Example: caesar("HELLO WORLD", 3) returns KHOOR ZRUOG. To decrypt you don’t need a second function: just call caesar("KHOOR ZRUOG", -3) and you get HELLO WORLD back, because in Python % with a negative number still gives a result between 0 and 25.

A limitation of the code, useful to mention if you are asked: accented letters pass isalpha() but fall outside the 26-letter alphabet, and upper() loses the distinction between upper and lower case.

Why Caesar is not secure. There are only 25 possible keys (with $k = 0$ nothing changes): a brute-force attack tries them all in an instant. But even without trying them all there is frequency analysis: in English the most frequent letters are E, T, A, O (in Italian, E, A, I, O). If in the ciphertext the most common letter is, say, H, it is plausible that H corresponds to E and so $k = 3$ . Caesar is a monoalphabetic substitution cipher: every letter of the plaintext is always replaced by the same letter of the ciphertext, and this leaves the frequencies intact.

Vigenère: more alphabets, same idea

The Vigenère cipher was born to correct exactly that flaw. The key is not a number but a word, and each letter of the word gives a different shift, used in turn. With the key LUNA the shifts are L=11, U=20, N=13, A=0, then it starts again.

I encrypt the first four letters of ATTACK with the key LUNA (indices A=0, T=19):

A + L: $0 + 11 = 11$ , that is L
T + U: $19 + 20 = 39$ , $39 mod 26 = 13$ , that is N
T + N: $19 + 13 = 32$ , $32 mod 26 = 6$ , that is G
A + A: $0 + 0 = 0$ , that is A

The ciphertext begins LNGA. Notice: the two Ts of ATTACK have become different letters (N and G). That is the point: the cipher is polyalphabetic, and simple frequency analysis no longer works, because the same plaintext letter ends up as different letters.

It is not invulnerable, though: if the key is $m$ letters long, the text can be divided into $m$ columns and each one is a Caesar cipher, attackable with frequencies. The hard part for the attacker is estimating $m$ . A random key, as long as the message and used only once, gives the perfect cipher (the one-time pad), but distributing keys like that is impractical: it is the problem of the next section.

Symmetric or asymmetric

Caesar and Vigenère are symmetric ciphers: the same key is used to encrypt and to decrypt. The modern algorithms of this family (AES is the one to cite) are much more robust and very fast, but they keep one problem: sender and recipient must already possess the same secret key. If they have never met, how do they exchange it over a network that is not trusted?

Asymmetric cryptography solves this problem by using a pair of keys: a public one, which can be given to anyone, and a private one, which stays with the owner. What is encrypted with one can only be decrypted with the other.

	Symmetric	Asymmetric
Keys	a single, shared one	public/private pair
Speed	high	low (calculations on enormous numbers)
Main problem	secure exchange of the key	slowness
Examples	Caesar, Vigenère, AES	RSA

In practice they are used together: asymmetric to agree on a key, symmetric to encrypt the data. You can see it in HTTPS.

RSA by hand with small numbers

RSA rests on one fact: multiplying two prime numbers is easy, but finding the two factors again from the product is extremely hard if the numbers have hundreds of digits. Here I use $p = 5$ and $q = 11$ , which are more than enough for a test.

1. Key generation.

I calculate the modulus:

n = p \cdot q = 5 \cdot 11 = 55

Then Euler’s totient function:

φ (n) = (p - 1) (q - 1) = 4 \cdot 10 = 40

I choose the public exponent $e$ coprime with 40 and less than 40: $e = 3$ will do because $g cd (3, 40) = 1$ .

I calculate the private exponent $d$ as the inverse of $e$ modulo 40, that is such that:

e \cdot d \equiv 1 (mod 40)

Trying: $3 \cdot 27 = 81 = 2 \cdot 40 + 1$ , so $d = 27$ .

Public key: $(n, e) = (55, 3)$
Private key: $(n, d) = (55, 27)$

( $p$ , $q$ and $φ (n)$ are thrown away: anyone who knows them can recalculate $d$ .)

2. Encryption of the message $m = 7$ (it must be less than $n$ ):

c = m^{e} mod n = 7^{3} mod 55

$7^{3} = 343$ and $343 = 6 \cdot 55 + 13$ (because $6 \cdot 55 = 330$ ), so $c = 13$ .

3. Decryption:

m = c^{d} mod n = 1 3^{27} mod 55

You never calculate $1 3^{27}$ in full: you square the remainders, reducing modulo 55 each time.

$1 3^{2} = 169 = 3 \cdot 55 + 4 \Rightarrow 4$
$1 3^{4} \equiv 4^{2} = 16$
$1 3^{8} \equiv 1 6^{2} = 256 = 4 \cdot 55 + 36 \Rightarrow 36$
$1 3^{16} \equiv 3 6^{2} = 1296 = 23 \cdot 55 + 31 \Rightarrow 31$

Since $27 = 16 + 8 + 2 + 1$ :

1 3^{27} \equiv 31 \cdot 36 \cdot 4 \cdot 13 (mod 55)

I multiply in pairs, reducing: $31 \cdot 36 = 1116 = 20 \cdot 55 + 16$ , so 16; then $16 \cdot 4 = 64 \equiv 9$ ; finally $9 \cdot 13 = 117 = 2 \cdot 55 + 7$ , so 7. The original message is back. The calculation agrees with the rule: $e \cdot d = 81 \equiv 1 (mod 40)$ guarantees that encrypting and decrypting cancel out.

With $n = 55$ you can only encrypt numbers up to 54: that is why in reality $n$ has thousands of bits.

Digital signature and hash

The key pair can also be used the other way round. If I encrypt with my private key, anyone with my public key can decrypt, and so knows that only I could have produced that data: this is the idea of the digital signature. With our example: to sign $m = 9$ I calculate $9^{27} mod 55 = 4$ (the signature); whoever receives it calculates $4^{3} = 64 \equiv 9 (mod 55)$ and finds the expected message. Authenticity and integrity are checked without the private key ever being revealed.

In reality you don’t sign the whole document but its hash: a function that turns any file into a string of fixed length. A good hash is one-way (you can’t get back to the file from that fingerprint), is very sensitive (changing one letter changes the whole fingerprint) and it is almost impossible to find two files with the same hash. You sign the fingerprint because it is short, and the recipient recalculates the hash of the document received and compares it with the one obtained from the signature.

Where you see all this: HTTPS and TLS

When the browser opens a site over HTTPS, the TLS protocol does these things in sequence, and it is a scheme worth being able to recount:

the server presents its certificate, which contains its public key and is signed by a certification authority that the browser trusts;
the browser verifies the signature, that is, checks that the certificate really belongs to that site (authentication);
the two parties agree, with asymmetric cryptography mechanisms, on a session key;
from then on all the traffic is encrypted with a symmetric algorithm using that key, because it is much faster.

The same principle is behind the VPNs discussed in the post on Year 5 networks.

Typical mistakes

Saying that RSA encrypts all HTTPS traffic. It isn’t true: it is used only for the agreement on the key; the traffic is encrypted symmetrically.
Confusing who uses which key. To encrypt a confidential message you use the recipient’s public key; to sign you use your own private key. Never the other way round.
Choosing $e$ not coprime with $φ (n)$ . If $g cd (e, φ (n)) \neq = 1$ the inverse $d$ doesn’t exist.
Calculating $m^{e}$ in full instead of reducing at each step: by hand it becomes unmanageable.
Forgetting the modulus in Caesar: the code goes beyond Z and produces strange characters.
Saying that the hash is “decrypted”. The hash is not inverted; it is recalculated and compared.
Calling encoding (Base64, ASCII) “cryptography” too: there is no key, so it protects nothing.

Three worked exercises

Exercise 1. Decrypt KHOOR, knowing that it is a Caesar cipher with an unknown key and that the message is an English word of five letters.

I try $k = 3$ : I subtract 3 from each letter. K becomes H, H becomes E, O becomes L, O becomes L, R becomes O: HELLO. It makes sense, so the key is 3. (In a real exercise you try the keys in order and stop at the first that gives a sensible word.)

Exercise 2. RSA with $p = 3$ , $q = 11$ . Determine the keys, encrypt $m = 4$ and decrypt the result.

$n = 33$ , $φ (n) = 2 \cdot 10 = 20$ . I choose $e = 3$ (coprime with 20). I look for $d$ with $3 d \equiv 1 (mod 20)$ : $3 \cdot 7 = 21 = 20 + 1$ , so $d = 7$ .

I encrypt: $4^{3} = 64 = 33 + 31$ , so $c = 31$ .

I decrypt: $3 1^{7} mod 33$ . Note that $31 \equiv - 2 (mod 33)$ , so $3 1^{7} \equiv (- 2)^{7} = - 128$ . To bring $- 128$ back into the range 0 to 32 I add $4 \cdot 33 = 132$ : $- 128 + 132 = 4$ . The result is 4, the original message.

Exercise 3. A Vigenère cipher with a 4-letter key is used on a text of 100 letters. How many different keys exist and why is it not worth trying them all by hand? And how many letters of the text are encrypted with the same key letter?

Each key position has 26 choices, so the keys number $2 6^{4} = 456976$ : too many by hand, but very few for a computer (that is why brute force alone is not a defence, and key length matters). Each letter of the key is used in turn: $100/4 = 25$ times each, so 25 letters of the text for each key letter, and it is on these 25 letters (a Caesar cipher) that an attacker would work with frequencies.

Before the test

For the test: rewrite the caesar function on your own without looking, then redo the RSA with $p = 5$ , $q = 11$ and another message. If the Python code still gives you basic problems, start from Python programming from scratch; to reason about how much it costs to try all the keys there is the post on algorithm complexity. The overview of the subject is on the computer science page. If you want me to look at how you set up the modular arithmetic or the code, write to me at contact for a free introductory call.

Cryptography: Caesar, Vigenère and RSA explained