0

QUESTION: An affine encryption function $f(n) \equiv an+b \ mod(41)$ has been used on plaintext composed of symbols from the alphabet

$$ \begin{array}{cccc} &A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V \\ &0 &1 &2 &3 &4 &5 &6 &7 &8&9&10&11&12&13&14&15&16&17&18&19&20&21\\ \end{array} $$ $$ \begin{array}{cccc} &W&X&Y&Z&0&1&2&3&4&5&6&7&8&9&;&,&.&?&! \\ &22&23&24&25&26&27&28&29&30&31&32&33&34&35&36&37&38&39&40\\ \end{array} $$ to produce the following ciphertext:

$7NIOQI,VEI7NI7IQ9E$

Use frequency analysis to determine the encryption key $(a,b)$, assuming that after "$E$", "$T$" is the most frequently occurring letter in plaintext messages of reasonable length written in English. Hence determine the decryption function and the plaintext.

SOLUTION:

Frequency analysis:

$$ \begin{array}{c|c|c|c} &7 &N &I &O &Q &, &V &E &9 \\ \hline &3 &2 &5 &1 &2 &1 &1 &2 &1\\ \end{array}. $$

"$I$" is the most frequent, so guess "$I$" stands for "$E$"

$f(n)=an +b\ mod(41)$ $\Rightarrow$ $f^{-1}(n)=a^{-1}(n -b) \ mod(41)$ Is this correct?

So, $f^{-1}(I) = E$ $\Rightarrow$ $f^{-1}(8)=4$

Subbing into formula:

$a^{-1}(8-b)=4$

$4a +b = 8$

So, the next most frequently occurring character is "$7$" which the question says should correspond to "$T$"

$\Rightarrow$ $f^{-1}(7)= T$

$f^{-1}(33)=19$

Again subbing in:

$a^{-1}(33-b)=19$

$19a +b=33$

This results in $a = \frac{5} {3}$ and $\frac{4}{3}$ ... So this is where my problems are. I believe these need to be integer values to continue? I know frequency analysis relies on guessing but this is a past exam question and it's supposed to be fairly straightforward (so that we have time to finish the rest of the paper) - "$I$" should equal "$E$" and "$7$" should equal "$T$" so I'm guessing there's something wrong with my method up to this point... Any help is greatly appreciated! :)

Swayy
  • 181

1 Answers1

2

You don't have $4a+b=8$ and $19a+b=33$. Rather, you have $4a+b\equiv8\pmod{41}$ and $19a+b\equiv33\pmod{41}$. (Also note that we derive $a$ and $b$ for the decrypting function itself, instead of determining the encrypting function and then invert it). We may still subtract these two modular equations to obtain $(19-4)a\equiv (33-8)\pmod{41}$, i.e. $$15 a\equiv 25\pmod{41}.$$ We are allowed to divide by $5$, so $$3 a\equiv 5\pmod{41}$$ may look a bit simpler. What we need, is an integer $a$ that when multiplied with $3$ is $\equiv5\pmod{41}$, that is $3a$ is one of the numbers $5, 46, 87, 128, \ldots$ As $87=3\cdot 29$, $a=29$ should be fine. Now from $4a+b\equiv 8\pmod{41}$ we arrive at $4\cdot29+b\equiv 8$, i.e. $b\equiv 8-116\equiv 15\pmod{41} $.

Hagen von Eitzen
  • 374,180