0
$\begingroup$

So I'm asked to decrypt the message YLFQX PCRIT which was encrypted using the affine transformation $C\equiv 21P+5 (mod 26)$

From here I find their numerical equivalence:

24 11 5 16 23 , 15 2 17 8 19

Now I have to rearrange the formula. I get up to

$P\equiv (C-5)/21 (mod 26)$

but am confused how to find the inverse. I'm supposed to end up with $P\equiv 5(C-5) (mod 26)$ but I don't know how they got $5$ from $21^{-1}$

I do not need the answer to the message but I would like to learn how to find the inverse so that I can figure it out myself.

$\endgroup$
0
$\begingroup$

The general algorithm is the Extended Euclidean algorithm.

Compute the gcd of $26$ and $5$ by Euclid's algorithm keeping track of coefficients:

$$\begin{align} 26 = & 1 \cdot 26 + 0 \cdot 21 \\ 21 = & 0 \cdot 26 + 1 \cdot 21 \end{align}$$

$21$ fits into $26$ $1$ time leaving a remainder of $5$, so we substract $1$ time the second equation from the first, making the second equation the first (so the smallest number becomes the largest and the smallest is replaced b y the remainder):

$$\begin{align} 21 = & 0 \cdot 26 + 1 \cdot 21 \\ 5 = & 1 \cdot 26 - 1 \cdot 21 \\ \end{align}$$

$5$ fits into $21$ $4$ times so we subtract $4$ times the second equation ($20 = 4 \cdot 26 - 4\cdot 21$) from the first, and swap in the same way to get

$$\begin{align} 5 = & 1 \cdot 26 - 1\cdot 21\\ 1 = & -4 \cdot 26 + 5 \cdot 21\\ \end{align}$$

And the final equation shows that $\gcd(21,26) =1$

Taking the final equation $1 = -4 \cdot 26 + 5 \cdot 21$ modulo $26$, the first term vanishes and we are left with $1 \equiv 5 \cdot 21 \bmod{26}$ which just says that $5$ and $21$ are each other's inverse modulo $26$. So $21^{-1} \bmod{26} = 5$.

Instead of the algorithmic approach (which is fail-safe) we could happen to note that $5 \cdot 5 = 25 = -1 \bmod{26}$, so taking $-$ on both sides we get $5 \cdot -5 = 1 \bmod{26}$ and $-5 = 21 \bmod{26}$ so we get the same inverse for $21$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy