Affine plaintext attack with GCD != 1

Question

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?

Answer 1

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.

Answer 2

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.