Knowing the key, how do I decrypt the affine cipher?

Question

I have an encryption function

$$E(p) = (ap + b) \mod{26}$$

where the parameters are $a=7$, $b = 10$, and $p$ is the plaintext letter.

I was asked to decrypt the ciphertext

LJMKGM 

using this information.

So, I tried to solve in this way:

1. I wrote the letters and indexed them from 0 to 25.

2. For each indexed ciphertext letter, I used this function to decrypt $$D(c) = (ac-b) \mod{26}$$ where $c$ is the number that represents the ciphertext letter.

I know that the plaintext is "please". For the first ciphertext letter, my method works, but for the rest it doesn't work.. what is my mistake?

Answer 1

This is a special case of the affine cipher where $m=26$.

Let's encrypt a single letter using your $E$. Let it be m, say, which is at index 12. So, $$E(12) = (7 \cdot 12 + 10) \mod{26} = 16$$

Now if we try to use the $D$ in your question, we decrypt this as:

$$D(16) = (7 \cdot 16 - 10) \mod{26} = 24$$

which is obviously not right. The issue is that your $E$ and $D$ aren't really inverses. The general technique in math classes for finding simple function inverses is to swap the dependent/independent variables and solve, so let's do that to find the inverse for $E$.

Let $y = E(p)$ for convenience's sake. Now let's swap $y$ and $p$ in the encryption function (and swap over to modular arithmetic notation):

$$p \equiv ay+b \mod{26}$$

and try to solve for $y$ (aka $E(p)$). Well, we move $b$ over first, which is just your typical "Algebra" material from school.

$$p - b \equiv ay \mod{26}$$

Now here comes the kicker: you need to "divide by" $a$. Now, I don't know your abstract algebra background, but arithmetic modulo $n$ takes place in the ring $\mathbb{Z}/n\mathbb{Z}$, also sometimes written as $\mathbb{Z}_n$. The issue is that multiplicative inverses are not guaranteed to exist in rings. In the case of $\mathbb{Z}/n\mathbb{Z}$, an element $x$ only has a multiplicative inverse if $\gcd(x, n)=1$. Fortunately for us, $a = 7$ and $m = 26$ are coprime, so $a^{-1}$ does exist.

Hence, we can write:

$$a^{-1}(p - b) \equiv y \mod{26}$$

which gives us:

$$D(c) = a^{-1}(c - b) \mod{26}.$$

This agrees with Wikipedia's article on the affine cipher, so it's good to know that we're not totally off-track here. How do you find $a^{-1}$? The article Modular Multiplicative Inverse on Wikipedia gives you a few ways. In this case, I'd probably just try trial-and-error, but you can also use the Extended Euclidean Algorithm to do so if you dislike trial and error. Fortunately for us, someone at Princeton is hosting this modular inverse calculator, which tells us that $a^{-1} = 15$.

So, taking the above $E(12) = 16$, let's see if our new $D$ works:

$$D(16) = 15 \cdot (16 - 10) \mod{26} = 12$$

which succeeds! From there, I trust you can complete the computation for your ciphertext.