Cryptosystems

What a Cryptosystem Is#

Everything in this topic is an application of machinery we have already built; nothing genuinely new gets defined. The situation is this: a sender wants to get a message to a receiver over a channel that a third party can listen in on, and wants that third party to learn nothing. The fix is to scramble the message before it goes out and unscramble it at the other end.

Basically, encryption and decryption are inverse functions, and the whole game is arranging things so that the encryption function is easy to apply, easy to invert if you hold one extra piece of information, and hopeless to invert if you do not. The message before encryption is called the plaintext and the message after encryption is the ciphertext.

Two ideas run through this entire lecture. The first is that letters have to be turned into numbers before any arithmetic can happen, and the choice of letter-to-number dictionary matters. The second is that "hard to invert" always ends up meaning some specific computational problem is believed to be slow — factorising for RSA, discrete logarithms for Diffie-Hellman.

The Caesar Shift#

The classic toy cryptosystem is the Caesar shift cypher: shift every letter of the message forward some fixed number of positions in the alphabet, wrapping back around to $A$ once you pass $Z$. For example, the letters of $BABA$ shifted four places down the alphabet become $FEFE$.

To do this arithmetically, the encryption function is built in two steps. First we map each letter to a number giving its position in the alphabet, then we shift the numbers modulo $26$:

$$\text{letter} \longrightarrow \text{number} \longrightarrow x \mapsto (x + a) \bmod 26,$$

where $a$ is a fixed secret integer. The decryption function reverses both steps in the opposite order,

$$y \mapsto (y - a) \bmod 26 \longrightarrow \text{number} \longrightarrow \text{letter}.$$

The letter-to-number dictionary is the usual one, with one quirk. The natural choice is $A \to 1$, $B \to 2$, all the way to $Z \to 26$; but we are working in $\mathbb{Z}_{26} = \{0, 1, \dots, 25\}$, and $26 = 0$ there. So the dictionary we actually use is:

In the Caesar shift, $Z$ must be sent to $0$, not $26$; and going backwards, a $0$ decrypts to $Z$, never to "the zeroth letter". This is purely an artefact of reducing mod $26$ and is the single most common slip in these questions. It does not cause any trouble because $26 \equiv 0 \pmod{26}$, so the arithmetic is identical either way; it is only the final translation back to letters that needs care.

Example. Encrypt the message $JAZZ$ using a Caesar shift with $a = 3$.
Converting to numbers with the table above, $J \to 10$, $A \to 1$, and $Z \to 0$ (twice). Applying $x \mapsto (x+3) \bmod 26$,

$$\begin{align*} 10 + 3 &= 13, \\ 1 + 3 &= 4, \\ 0 + 3 &= 3, \\ 0 + 3 &= 3, \end{align*}$$

giving the numbers $(13, 4, 3, 3)$, which translate back to $M$, $D$, $C$, $C$. Therefore, the ciphertext is $MDCC$. As a sanity check by hand, counting three letters forward from $Z$ gives $A, B, C$; so $Z \to C$, exactly as the arithmetic said.

Example. The message $MDCC$ was encrypted with a Caesar shift of $a = 3$. Decrypt it.
Converting to numbers gives $(13, 4, 3, 3)$, and we apply $y \mapsto (y - 3) \bmod 26$:

$$\begin{align*} 13 - 3 &= 10, \\ 4 - 3 &= 1, \\ 3 - 3 &= 0, \\ 3 - 3 &= 0. \end{align*}$$

Now $10 \to J$, $1 \to A$, and $0 \to Z$ twice. Therefore, the plaintext is $JAZZ$; notice how the $0$ has to be read as $Z$ on the way back, which is the same quirk seen from the other side.

The Caesar shift is a genuine cryptosystem, but a hopeless one. There are only $26$ possible values of $a$, and one of them ($a=0$) does nothing, so an attacker simply tries all $25$ non-trivial shifts and reads whichever output is English. A cryptosystem whose key space is small enough to enumerate is worthless no matter how clever the operation is. What we want is a system where the operation is still cheap to compute but the key space is astronomically large, and that is exactly what happens if we replace "add a secret number" with "raise to a secret power".

The RSA Cryptosystem#

The upgrade from Caesar is to work modulo a large $n$ and encrypt by $x \mapsto x^s$ rather than $x \mapsto x + a$. The resulting system is the Rivest–Shamir–Adleman, or RSA, cryptosystem, and it is the system that makes public-key cryptography possible: the sender can publish everything needed to encrypt without giving away how to decrypt.

Basically, $n$ and $s$ are shouted from the rooftops so that anybody can send you an encrypted message, while the factorisation $n = pq$ is kept secret; and knowing the factorisation is exactly what lets you compute $\phi(n)$, which in turn is exactly what lets you compute $t$. Everyone can lock the box, only you can open it.

A few points about the set-up that are easy to skip past:

• We need $\gcd(s, \phi(n)) = 1$ precisely so that $s$ is a unit in $\mathbb{Z}_{\phi(n)}$ and the decryption exponent $t = s^{-1}$ exists at all. If $s$ is not coprime to $\phi(n)$ there is no $t$ whatsoever, and the "cryptosystem" cannot be decrypted by anybody, including the intended receiver.
• Because $n = pq$ with $p, q$ distinct primes, $\phi$ is multiplicative on coprime arguments and $\phi(p) = p - 1$, so $\phi(n) = (p-1)(q-1)$. This is $(p-1)(q-1)$, not $n - 1$; writing $\phi(55) = 54$ instead of $40$ wrecks everything downstream.
• The plaintext numbers must be smaller than $n$, otherwise two different messages could reduce to the same element of $\mathbb{Z}_n$ and decryption would be ambiguous.
• Finding the two large primes in the first place is done with the tests in Primality Tests; you never need to factorise anything to set up RSA, only to break it.

Why RSA Decryption Works#

The claim we need is that raising to the power $s$ and then to the power $t$ gets you back where you started. The source slides justify this in one line with Euler's Theorem, and that line is correct for units; but the messages we actually encrypt are arbitrary numbers less than $n$, and some of them will not be units. It is worth doing this properly.

Proof. Since $st \equiv 1 \pmod{\phi(n)}$ and $st \geq 1$, we may write $st = 1 + k\phi(n)$ for some integer $k \geq 0$, where $\phi(n) = (p-1)(q-1)$.

First suppose $\gcd(x, n) = 1$. Then Euler's Theorem from Fermats Little Theorem and Eulers Theorem gives $x^{\phi(n)} = 1$ in $\mathbb{Z}_n$, so

$$\begin{align*} x^{st} &= x^{1 + k\phi(n)} \\ &= x \left( x^{\phi(n)} \right)^k \\ &= x \cdot 1^k \\ &= x \text{ in } \mathbb{Z}_n, \end{align*}$$

which is the easy case. Now drop the assumption and work modulo $p$ and modulo $q$ separately. Modulo $p$ there are two possibilities:

• If $p \mid x$, then $x \equiv 0 \pmod p$, and since $st \geq 1$ we get $x^{st} \equiv 0 \equiv x \pmod p$.
• If $p \nmid x$, then Fermat's Little Theorem gives $x^{p-1} \equiv 1 \pmod p$; and $(p-1) \mid \phi(n)$, so writing $\phi(n) = (p-1)m$,

$$\begin{align*} x^{st} &= x \left( x^{(p-1)m} \right)^k \\ &\equiv x \cdot 1^{mk} \\ &\equiv x \pmod p. \end{align*}$$

Either way $x^{st} \equiv x \pmod p$, and the identical argument with $q$ in place of $p$ gives $x^{st} \equiv x \pmod q$. So $p \mid (x^{st} - x)$ and $q \mid (x^{st} - x)$; since $p$ and $q$ are distinct primes they are coprime, so $pq = n$ divides $x^{st} - x$ as well (this is the coprime-divisibility argument behind Simultaneous Congruences and the CRT). Hence $x^{st} \equiv x \pmod n$ for every integer $x$. $\blacksquare$

Basically, splitting into the two prime factors rescues the non-units: an $x$ that is divisible by $p$ is $0$ mod $p$ and stays $0$ forever, which is exactly what we wanted anyway, and it is still a unit mod $q$ so Fermat handles that half. Do not let anyone tell you RSA "only works on units"; it works on every $x \in \mathbb{Z}_n$, and we will see a message below whose letters $E$ and $T$ are genuinely not units mod $55$.

The statement the slides give, $x^k \equiv x^{k \bmod \phi(n)} \pmod n$, is the unit version of the same fact, and is the reason the exponents live modulo $\phi(n)$ rather than modulo $n$. Reduce exponents modulo $\phi(n)$; reduce bases modulo $n$. Mixing these two up is the most expensive mistake available in this topic.

Finding the Decryption Function#

Everything in the previous section reduces the practical problem to one line: invert $s$ modulo $\phi(n)$. That is a job for the extended Euclidean algorithm from Bezouts Identity and the Extended Euclidean Algorithm. The working method is:

• Factorise the public modulus as $n = pq$.
• Compute $\phi(n) = (p-1)(q-1)$.
• Check $\gcd(s, \phi(n)) = 1$; if not, the system is broken and there is nothing to find.
• Run the EEA on $s$ and $\phi(n)$ to write $1 = us + v\phi(n)$; then $t \equiv u \pmod{\phi(n)}$.
• If $u$ came out negative, add $\phi(n)$ until it lands in $\{1, \dots, \phi(n) - 1\}$.
• The decryption function is $y \mapsto y^t \bmod n$.

Example. An RSA cryptosystem uses the encryption function $x \mapsto x^{27} \bmod 55$. Find the decryption function.
The modulus factorises as $n = 55 = 5 \times 11$, so $p = 5$ and $q = 11$, and

$$\begin{align*} \phi(55) &= (5-1)(11-1) \\ &= 4 \times 10 \\ &= 40. \end{align*}$$

Since $27 = 3^3$ and $40 = 2^3 \times 5$ share no prime factors, $\gcd(27, 40) = 1$ and the decryption exponent exists. Running the Euclidean algorithm on $27$ and $40$,

$$\begin{align*} 40 &= 1 \times 27 + 13, \\ 27 &= 2 \times 13 + 1, \\ 13 &= 13 \times 1 + 0, \end{align*}$$

so $\gcd(27,40) = 1$ as expected. Back-substituting to get Bézout coefficients,

$$\begin{align*} 1 &= 27 - 2 \times 13 \\ &= 27 - 2(40 - 1 \times 27) \\ &= 3 \times 27 - 2 \times 40. \end{align*}$$

Reducing this modulo $40$ kills the $40$ term and leaves $27 \times 3 \equiv 1 \pmod{40}$, so $t = 3$. Therefore, the decryption function is

$$y \mapsto y^3 \bmod 55.$$

As a check, $27 \times 3 = 81 = 2 \times 40 + 1$, so indeed $st \equiv 1 \pmod{40}$. Always run this one-line check on your $t$; it costs one multiplication and catches sign errors from the back-substitution instantly.

Example. Find the decryption function for the RSA encryption function $x \mapsto x^{11} \bmod 7171$.
Here $7171 = 71 \times 101$ (both prime), so

$$\begin{align*} \phi(7171) &= 70 \times 100 \\ &= 7000, \end{align*}$$

and $\gcd(11, 7000) = 1$ since $7000 = 2^3 \times 5^3 \times 7$. The Euclidean algorithm gives

$$\begin{align*} 7000 &= 636 \times 11 + 4, \\ 11 &= 2 \times 4 + 3, \\ 4 &= 1 \times 3 + 1, \end{align*}$$

and back-substituting,

$$\begin{align*} 1 &= 4 - 3 \\ &= 4 - (11 - 2 \times 4) \\ &= 3 \times 4 - 11 \\ &= 3(7000 - 636 \times 11) - 11 \\ &= 3 \times 7000 - 1909 \times 11. \end{align*}$$

So $-1909 \times 11 \equiv 1 \pmod{7000}$, and since we want a positive exponent we take

$$\begin{align*} t &= 7000 - 1909 \\ &= 5091. \end{align*}$$

Therefore, the decryption function is $y \mapsto y^{5091} \bmod 7171$; checking, $11 \times 5091 = 56001 = 8 \times 7000 + 1$, as required. Notice how the EEA gave a negative coefficient here and a positive one in the previous example; the sign is not something you can predict, so always finish by normalising $t$ into the range $1 \leq t < \phi(n)$.

Example. Find the decryption function for the RSA encryption function $x \mapsto x^5 \bmod 26$.
Here $26 = 2 \times 13$, so $\phi(26) = 1 \times 12 = 12$ and $\gcd(5,12) = 1$; this one is small enough to spot by inspection, since $5 \times 5 = 25 = 2 \times 12 + 1 \equiv 1 \pmod{12}$. Therefore $t = 5$ and the decryption function is $y \mapsto y^5 \bmod 26$ — the same function as encryption. This happens whenever $s^2 \equiv 1 \pmod{\phi(n)}$, and is a reminder that a small modulus gives a rubbish cryptosystem; here anybody who can encrypt can also decrypt.

Decrypting a Full Message#

With the decryption exponent in hand, decrypting is just a pile of modular exponentiations followed by a translation back to letters. For RSA the letters are usually numbered $A \to 1$, $B \to 2$, up to $Z \to 26$, with no wrap-around quirk, because the modulus is bigger than $26$ and $26$ is a perfectly good element of $\mathbb{Z}_n$.

Example. An encrypted message using the cryptosystem $x \mapsto x^{27} \bmod 55$ is $(15, 2, 25, 7, 1, 4, 49, 49, 4, 49, 4, 15)$. Decrypt this message.
From the previous section the decryption function is $y \mapsto y^3 \bmod 55$. The message only uses seven distinct ciphertext values, namely $15, 2, 25, 7, 1, 4$ and $49$, so we cube each of those once, working in $\mathbb{Z}_{55}$ and using $49 = -6$ to keep the numbers small:

Now substitute back into the message in order:

Therefore, the decrypted message is $THEMAIDDIDIT$, i.e. "the maid did it". As a check on the whole system, encrypting the first letter again should return the ciphertext: $20^{27} \bmod 55$, and since $20^3 = 8000 = 145 \times 55 + 25$, we get $20^3 = 25$, $20^9 = 25^3 = 5$, $20^{27} = 5^3 = 125 = 2 \times 55 + 15 = 15$, which is exactly the ciphertext we started from.

That last check is worth pausing on. Note that $\gcd(20, 55) = 5$ and $\gcd(5, 55) = 5$, so the plaintext letters $T$ and $E$ are not units in $\mathbb{Z}_{55}$; Euler's Theorem says nothing at all about them, and yet they encrypt and decrypt perfectly. That is the general decryption theorem doing its job, and it is why we bothered proving the non-unit case.

Example. Decrypt the message $(16, 5, 48, 4)$, given that the encryption function was $x \mapsto x^{13} \bmod 62$.
First find $t$. We have $62 = 2 \times 31$, so $\phi(62) = 1 \times 30 = 30$, and $\gcd(13, 30) = 1$. The Euclidean algorithm gives $30 = 2 \times 13 + 4$ and $13 = 3 \times 4 + 1$, so

$$\begin{align*} 1 &= 13 - 3 \times 4 \\ &= 13 - 3(30 - 2 \times 13) \\ &= 7 \times 13 - 3 \times 30, \end{align*}$$

giving $t = 7$ (and indeed $13 \times 7 = 91 = 3 \times 30 + 1$). Now compute $y^7$ in $\mathbb{Z}_{62}$ for each ciphertext value by repeated squaring, writing $7 = 4 + 2 + 1$:

$$\begin{align*} 16^2 &= 256 = 4 \times 62 + 8 = 8, \\ 16^4 &= 8^2 = 64 = 2, \\ 16^7 &= 2 \times 8 \times 16 = 256 = 8, \\ 5^2 &= 25, \\ 5^4 &= 625 = 10 \times 62 + 5 = 5, \\ 5^7 &= 5 \times 25 \times 5 = 625 = 5, \\ 48^2 &= (-14)^2 = 196 = 3 \times 62 + 10 = 10, \\ 48^4 &= 10^2 = 100 = 38, \\ 48^7 &= 38 \times 10 \times (-14) = 380 \times (-14) = 8 \times (-14) = -112 = 12, \\ 4^2 &= 16, \\ 4^4 &= 256 = 8, \\ 4^7 &= 8 \times 16 \times 4 = 512 = 8 \times 62 + 16 = 16. \end{align*}$$

So the plaintext numbers are $(8, 5, 12, 16)$, which read as $H, E, L, P$. Therefore, the message is $HELP$. Notice how replacing $48$ by $-14$ and reducing $380$ to $8$ before multiplying kept every intermediate number small; reduce after every single multiplication, never at the end.

Why RSA Is Secure#

An attacker sees the ciphertext, the modulus $n$ and the exponent $s$. To decrypt they need $t$, to get $t$ they need $\phi(n)$, and to get $\phi(n)$ they need the factorisation $n = pq$. So the security of RSA rests entirely on the following claim:

Multiplying two $2048$-bit primes together takes essentially no time; recovering them from the product is, as far as anybody knows, completely infeasible. That gap is the asymmetry the whole system is built on, and it is genuinely remarkable that it exists, since the operation and its inverse look equally innocent written down.

It is worth noticing how thin the margin is. Knowing either prime is enough, since $q = n/p$ and then $\phi(n) = (p-1)(q-1)$ falls out. Knowing $\phi(n)$ is also enough without ever naming the primes, because $\phi(n) = n - p - q + 1$ gives you $p + q$, and with $pq = n$ known you can solve the resulting quadratic. So $\phi(n)$ is every bit as secret as $p$ and $q$; never publish it, and never let a question trick you into thinking it is public information. If $p$ and $q$ are chosen badly — too close together, too small, or of a guessable special shape — the system falls apart even though $n$ is enormous.

The Diffie-Hellman Key Exchange#

RSA solves one problem, but plenty of cryptosystems need the sender and receiver to share a secret key beforehand — and if they have never met, there is no obvious way to agree on one over a channel that is being listened to. The Diffie-Hellman(-Merkle) system solves exactly this: two people who have exchanged nothing private can end up holding a common secret number.

The reason this works is one line of index laws:

$$\begin{align*} (y_A)^t &= (x^s)^t \\ &= x^{st} \\ &= (x^t)^s \\ &= (y_B)^s \text{ in } \mathbb{Z}_p, \end{align*}$$

so both parties end up holding the same number $z = x^{st} \bmod p$. Basically, exponentiation commutes, so it does not matter in which order the two secret exponents are applied; $A$ and $B$ arrive at the same place along different routes, and neither ever transmitted their own exponent. Nobody listening in ever sees $s$ or $t$ — only $p$, $x$, $y_A$ and $y_B$ — and $z$ can then be used as the key for whatever symmetric cypher they like.

The shared secret is $x^{st}$, not $x^{s+t}$ and not $y_A y_B$. Multiplying the two announced numbers together gives $x^{s+t}$, which an eavesdropper can compute for free; a surprising number of students write this down.

Recall from Order and Primitive Elements that a primitive element $x$ of $\mathbb{Z}_p^*$ has $\operatorname{ord}_p(x) = \phi(p) = p - 1$, and that its powers sweep out the whole of $\mathbb{Z}_p^*$. Two consequences matter here: exponents are only ever meaningful modulo $p-1$, and every possible element of $\mathbb{Z}_p^*$ is a candidate value of $y_A$. Reduce Diffie-Hellman exponents modulo $p - 1$, never modulo $p$.

Cracking Diffie-Hellman by Brute Force#

With small numbers you can attack the system directly, by tabulating the powers of $x$ until you find the announced value. That is a discrete logarithm computation, and doing one by hand is the best way to see why the real system uses gigantic primes.

Example. Ada and Byron have set up a Diffie-Hellman cryptosystem with modulus $79$ and primitive element $3$. Ada announces that her encrypted number is $75$, and Byron announces that his is $2$. Find their shared secret key.
We need $s$ with $3^s = 75$ or $t$ with $3^t = 2$ in $\mathbb{Z}_{79}$; either one on its own is enough, because once we know one secret exponent we can apply it to the other person's announced number. So tabulate the powers of $3$ modulo $79$, reducing at every step:

Byron's number appears almost immediately: $3^4 = 81 = 79 + 2 = 2$, so Byron's secret key is $t = 4$. That is all we need. Applying it to Ada's announced number, and writing $75 = -4$ in $\mathbb{Z}_{79}$,

$$\begin{align*} z &= (y_A)^t \\ &= 75^4 \\ &= (-4)^4 \\ &= 256 \\ &= 3 \times 79 + 19 \\ &= 19 \text{ in } \mathbb{Z}_{79}. \end{align*}$$

Therefore, the shared secret key is $z = 19$.

For completeness, let us also find Ada's key by continuing the table until $75$ shows up:

So $3^{47} = 75$ and Ada's secret key is $s = 47$. Notice the landmark at $k = 39$: since $3$ is primitive and $\operatorname{ord}_{79}(3) = 78$, we must have $3^{39} = -1 = 78$, and the table confirms it. That single fact halves the work, because $3^{39 + j} = -3^j$; for instance $3^8 = 4$ immediately gives

$$3^{47} = 3^{39} \times 3^8 = -4 = 75 \text{ in } \mathbb{Z}_{79},$$

without tabulating anything past $k = 39$. Cross-checking the shared key three different ways,

$$\begin{align*} (y_A)^t &= 75^4 = 19, \\ (y_B)^s &= 2^{47} = 19, \\ x^{st} &= 3^{47 \times 4} = 3^{188} = 3^{188 \bmod 78} = 3^{32} = 19, \end{align*}$$

where the last line reduced the exponent $188 = 2 \times 78 + 32$ modulo the order $78$ and then read $3^{32} = 19$ straight off the table. All three agree, which is a strong sign that the two discrete logarithms were read correctly.

Example. You and a friend have set up a Diffie-Hellman cryptosystem with modulus $23$ and primitive element $5$. Your friend announces that their encrypted number is $8$. Find their secret key.
Tabulate the powers of $5$ in $\mathbb{Z}_{23}$:

Reading along, $5^6 = 8$. Therefore, your friend's secret key is $6$. (Strictly, any exponent congruent to $6$ modulo $\operatorname{ord}_{23}(5) = 22$ would produce the same announced number, so the key is only determined modulo $22$; the smallest positive choice is $6$.)

Why the Base Must Be Primitive#

The last two examples show the whole system being broken by hand in under a minute, which is precisely what a real Diffie-Hellman set-up is trying to make impossible. The defence is to make $p$ enormous, and — crucially — to insist that $x$ is a primitive element.

The reason is that a brute-force attacker only ever has to search through the set of numbers that are actually reachable as powers of $x$, namely $\langle x \rangle$. If $x$ is primitive then $\langle x \rangle = \mathbb{Z}_p^*$, which has $p - 1$ elements and is as large as the search space can possibly be. If $x$ is not primitive, then $\operatorname{ord}_p(x)$ is a proper divisor of $p-1$, so it is at most $(p-1)/2$; choosing a non-primitive base instantly halves (at best) the number of possibilities an attacker has to check, and usually does far worse than that.

The extreme case makes the point vividly. Suppose someone chose $x = p - 1 \equiv -1 \pmod p$. Then

$$\begin{align*} x^k &= (-1)^k \\ &= \begin{cases} 1, & k \text{ even}, \\ -1, & k \text{ odd},\end{cases} \end{align*}$$

so the only numbers that can ever be announced are $1$ and $-1$, the shared secret is one of two values, and an attacker guesses it on the first or second try. All the size of $p$ has bought you is nothing at all; the security came from the order of the base, not the size of the modulus. This is the same lesson as the $26$-key Caesar shift, dressed up differently.

Basically, computing $x^s \bmod p$ by repeated squaring is fast even when $s$ has hundreds of digits, while going backwards from $x^s$ to $s$ has no known fast method for a general large prime $p$. That one-way behaviour is the entire foundation, and it is a different hard problem from the factorising problem that props up RSA; if somebody found a fast factorising algorithm tomorrow, Diffie-Hellman would not automatically fall with it (and vice versa).

Common Exam Traps#

Almost every mark lost in this topic comes from one of the following, so it is worth reading this list before an exam.

• $s$ must be coprime to $\phi(n)$. If $\gcd(s, \phi(n)) \neq 1$ then no decryption exponent exists at all. Check the gcd before you start the EEA rather than discovering it halfway through.
• Exponents live modulo $\phi(n)$, bases live modulo $n$. Solve $st \equiv 1 \pmod{\phi(n)}$, never $\pmod n$. In Diffie-Hellman the corresponding modulus for exponents is $p - 1$, never $p$.
• $\phi(pq) = (p-1)(q-1)$, not $pq - 1$. For $n = 55$ this is $40$, not $54$. Every subsequent number is wrong if this one is.
• Normalise $t$ to a positive value. The EEA cheerfully returns things like $-1909$; add $\phi(n)$ until $t$ lands in $\{1, \dots, \phi(n) - 1\}$, then verify $st \equiv 1$ by direct multiplication.
• Do not reduce the exponent modulo the order of a non-unit. In the $x \mapsto x^{27} \bmod 55$ system, the plaintexts $5$ and $20$ are not units mod $55$; the decryption theorem covers them, but Euler's Theorem applied blindly does not.
• Get the letter dictionary right. For the Caesar shift, $Z \to 0$ because we work in $\mathbb{Z}_{26}$; for RSA the standard is $A \to 1$ through $Z \to 26$ with no wrap. Check which one the question is using before converting anything.
• In Diffie-Hellman, you only need one of the two secret keys. Once you have found $t$ from $y_B$, apply it to $y_A$; there is no need to solve the second discrete logarithm as well, and doing so wastes exam time.
• The Diffie-Hellman shared secret is $x^{st}$. It is not $x^{s+t}$, and it is not $y_A y_B$.
• Reduce at every step of a modular exponentiation and use small negative representatives ($49 = -6$ mod $55$, $75 = -4$ mod $79$); this is the same advice as in Modular Arithmetic and it is what keeps these computations doable by hand.
• Remember what is public. In the RSA set-up the pair $(n, s)$ is public and $p, q, \phi(n), t$ are all secret; in the Diffie-Hellman set-up the pair $(p, x)$ is public along with the announced $y_A, y_B$, while $s$, $t$ and $z$ are secret. Questions frequently hinge on noticing that $\phi(n)$ is not public information.