# How does this affine cipher work?

I have a question about how I need to solve the following:

A sentence has been changed to ASCII and then encrypted with the formula $E(x) = ax + b \bmod 256256$. All I know is that the first 4 letters are: W I S K

This is the encrypted message:

 064066 158368 092525 143358 099354 141643 110102 051667 024006 190286 133343


How do I go about solving this? I first tried to program a brute force but I actually want to understand how to solve it. I tried working with the extended euclidean algorithm as well, but didn't get far.

W is 87 in ASCII, so $$87a+b\equiv064066\pmod{256256}.$$

I is 73 in ASCII, so $$73a+b\equiv158368\pmod{256256}.$$

Subtracting, you get $$14a\equiv-94302\equiv161954\pmod{256256}.$$

Unfortunately 14 is not coprime to 256256, so you'll need to use other letters to figure this out. Once you get an equation of the form $$ma\equiv n\pmod{256256}$$ you can solve for $a\pmod{256256}$ and then substitute to find $b\pmod{256256}.$

(In fact, you already have enough to solve with trial and error, but it's nicer to avoid that.)

• Thanks for the reply, I got a few questions though. What exactly do you mean by, substitute? Assuming the first seven letters are: W I S K U N D E, can I do the following? E is 73 in ASCII and N is 78 in ASCII. Therefore having: $$78a+b\equiv141643\pmod{256256}.$$ and $$73a+b\equiv092525\pmod{256256}.$$ Subtracting them $$5a+b\equiv49118\pmod{256256}.$$ I believe 5 is coprime to 256256. If I follow your equation: $$5a\equiv49118\pmod{256256}.$$ How exactly do I calculate b? Sorry if the questions seem obvious, having a hard time comprehending. – user34734 May 31 '16 at 19:07
• @Lada: $78a+b-(73a+b)=5a$, not $5a+b.$ You then get $a$ from the extended Euclidean algorithm, and to get $b$ you compute, say, $092525-73a$. – Charles May 31 '16 at 19:23
• What am I doing wrong? I in ASCII is 73 and Din ASCII is 68. Substracting them I get the formula: $$5a\equiv48266\pmod{256256}.$$ Using the extended Euclidean algorithm I find that a 214658 is. I also calculate that b: $$110102 - 68 * 214658\equiv119950\pmod{256256}.$$ Whenever I insert these values ( a and b ) in the original formula: $$E(x)=ax+bmod256256$$ I only get the correct values for I and D. What am I doing wrong this time? I can not find a coprime in 256256 with just the letters W I S K by the way, or did I forget something? – user34734 May 31 '16 at 20:13
• @Lada Where does D come from? I thought you only had WISK. – Charles May 31 '16 at 20:27
• @Lada: A simple brute force check shows that $14 a \equiv 161954 \pmod{256256}$ has no solutions. Thus, either your known plaintext (or ciphertext) or your description of the ciphering method is incorrect. (Also, while asking how to solve a particular type of cipher is OK, asking to have a particular piece of ciphertext decoded is considered off-topic here. Thus, even though it may not help you with this specific ciphertext, Charles's answer really does cover the entire on-topic part of your question.) – Ilmari Karonen Jun 1 '16 at 12:06

W = 87; I = 73; S = 83; K = 75

This yields the following system of equations:

$\begin{cases} 87a+b \equiv 64066 \pmod {256256}\\ 73a+b \equiv 158368 \pmod {256256}\\ 83a+b \equiv 92525 \pmod {256256}\\ 75a+b \equiv 143358 \pmod {256256} \end{cases}$

The following proposition is useful.

Proposition If $x \equiv y \pmod {n}$ then $x \equiv y \pmod {n/d}$ for any divisor $d$ of $n$.

You can therefore solve the above system modulo the factors of $256256 = 2^8 \cdot 7 \cdot 11 \cdot 13$.

For example, modulo $7$, we obtain:

$\begin{cases} 3a+b \equiv 2\pmod {7}\\ 3a+b \equiv 0 \pmod {7}\\ 6a+b \equiv 6 \pmod {7}\\ 5a+b \equiv 5 \pmod {7} \end{cases}$

The two first equations (modulo $7$) are impossible. This means that $a$ and $b$ cannot be recovered modulo $7$.

Let us now look modulo $11$:

$\begin{cases} 10a+b \equiv 2\pmod {11}\\ 7a+b \equiv 1 \pmod {11}\\ 6a+b \equiv 4 \pmod {11}\\ 9a+b \equiv 6 \pmod {11} \end{cases}$

The two first equations yield $a\equiv 4 \pmod {11}$ and $b\equiv 6 \pmod {11}$. However, these solutions are incompatible with the two last equations.

I suspect that there are some errors in the problem. Can you check the values of the ciphertext. Or I made mistakes in the calculation...;)

• I will come with an answer tomorrow, interesting way of approaching the problem by the way, never thought of it. – user34734 Jun 1 '16 at 15:35
• Since decryption is given by $E^{-1}(y) = (y-b)\cdot a^{-1} \bmod 256256$, the value of $a$ defining encryption should be relatively prime to $256256$; i.e., $\gcd(a,256256) = 1$. You should check that with your teacher. – user94293 Jun 1 '16 at 16:25
• I concur -- the problem, as written, is not solvable. – Charles Jun 1 '16 at 19:52
• @Charles @user94293 Well, this might be the issue: According to my teacher W I are encrypted to $064066$ and S K to $158368$ – user34734 Jun 2 '16 at 15:17
• @Lada: Assuming that ASCII codes are concatenated (i.e., $x = 087073$ for WI and $x=083057$ for SK), this yields $a=249951$ and $b=158979$. The problem is that this $a$ cannot be inverted modulo $256256$: $\gcd(249951,256256) = 13$. – user94293 Jun 2 '16 at 15:59