Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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! :)

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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} $.

share|improve this answer
    
Thanks so much, I got it "THEYREFUSETHETERMS"! :) –  Swayy Apr 28 '13 at 21:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.