# Affine plaintext attack with GCD != 1

I'm trying to crack an affine cipher, but when cracking I cannot find the inverse of a number because the GCD is not 1. This is my plaintext and this is my ciphertext:

PLAIN:  072097 108108
CIPHER: 024328 164193


This is my function:

E(x) = ax + b (MOD 256256)


Gives:

E(072097) = 072097a + b (MOD 256256) = 024328
E(108108) = 108108a + b (MOD 256256) = 164193


So if we subtract these we get this:

139865 = 36012a (MOD 256256)
a = 139865 / 36012 (MOD 256256)
a = 139865 * 36012^-1 (MOD 256256)


Now GCD(256256, 36012) = 4. So there's no inverse because the GCD is not one.

I'm sure it's possible to crack this text but I just don't know how to do it because there's no inverse of 36012 and 256256.

Does anybody know how to crack this or get the inverse of 36012?

You seem to have made a mistake in your arithmetic: $$108108 - 72097 = 36011 \ne 36012.$$

The number $36011$ is invertible modulo $256256$, and thus you can find $a$ and $b$ in a straightforward manner.

More generally, you could end up in a situation where both the difference of the ciphertexts $d_c$ and the difference of the plaintexts $d_p$ might share the same common factor $g$ with the modulus $m$. In that case, what you can do is divide both of the differences and the modulus by this common factor to obtain $d'_c = d_c / g$, $d'_p = d_p / g$ and $m' = m / g$, and solve the reduced recurrence $d'_c \equiv a d'_p \pmod{m'}$. This will give you the value of $a$ modulo $m'$, which will correspond to $g$ different possible values of $a$ modulo $m$, differing by multiples of $m'$. If $g$ is relatively small, this can be almost as good for most purposes as obtaining a unique solution, since e.g. to decrypt any additional ciphertext you can just try all the possible solutions and see which of the results makes the most sense.

• No problem. BTW, even if the difference had been non-invertible, all might still not have been lost; I added a note about how to handle that case to my answer. – Ilmari Karonen Feb 16 '17 at 13:44
• Wow! That is really smart. – Wouter Doeland Feb 16 '17 at 16:03

This can easily be solved by brute force. Start with the following relationships:

$$72097a + b = 24328 \pmod{256256}$$ $$108108a + b = 164193 \pmod{256256}$$

then rearrange to obtain two expressions for $b$ in terms of $a$:

$$b_0 = 24328 - 72097a \pmod{256256}$$ $$b_1 = 164193 - 108108a \pmod{256256}$$

Now iterate through all the possible values of $a$ (i.e., $0 < a < 256256$) and find values of $a$ for which $b_0 = b_1$.

It turns out there is only one solution.