3
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.)

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – user34734
    Commented May 31, 2016 at 19:07
  • $\begingroup$ @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$. $\endgroup$
    – Charles
    Commented May 31, 2016 at 19:23
  • $\begingroup$ 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? $\endgroup$
    – user34734
    Commented May 31, 2016 at 20:13
  • $\begingroup$ @Lada Where does D come from? I thought you only had WISK. $\endgroup$
    – Charles
    Commented May 31, 2016 at 20:27
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Ilmari Karonen
    Commented Jun 1, 2016 at 12:06
1
$\begingroup$

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...;)

Improve this answer
$\endgroup$
9
  • $\begingroup$ I will come with an answer tomorrow, interesting way of approaching the problem by the way, never thought of it. $\endgroup$
    – user34734
    Commented Jun 1, 2016 at 15:35
  • $\begingroup$ 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. $\endgroup$
    – user94293
    Commented Jun 1, 2016 at 16:25
  • $\begingroup$ I concur -- the problem, as written, is not solvable. $\endgroup$
    – Charles
    Commented Jun 1, 2016 at 19:52
  • $\begingroup$ @Charles @user94293 Well, this might be the issue: According to my teacher W I are encrypted to $064066$ and S K to $158368$ $\endgroup$
    – user34734
    Commented Jun 2, 2016 at 15:17
  • $\begingroup$ @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$. $\endgroup$
    – user94293
    Commented Jun 2, 2016 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.