Cryptanalysis Affine Cipher: Brute-Force Search Vs. Meet-in-the-middle

Question

Affine Cipher:

$Enc(x) = (ax + b) \mod m$

$Dec(x) = a^{-1}(x-b) \mod m$

For a brute-force key search, we need to do $a \cdot b$ encryptions in the worst case.

For a meet-in-the-middle attack, how many encryptions/decryptions do we need to do in the worse case?

Meet-in-the-middle attack definition: Affine cipher can be broken up into two separate encryptions and decryptions.

$Enc(x) = (ax)\mod m = c_1$

$Enc(c_1) = (c_1 + b) \mod m = c_2$

$Dec(c_2) = (x-b) \mod m = c_1$

$Dec(c_1) = a^{-1}(c_1) \mod m = x$

Now you can start by encryption x over all possible values of $a$ and decrypt $c_2$ over all possible values of $b$ then compare the two tables and find a match over $c_1$

Which now I realize has answered my question that it uses $a + b$ encryptions.

Side question: How is $a^{-1}$ calculated? $m - a = a^{-1}$ or maybe $m - a \mod m = a^{-1}$

Answer 1

I don't know what you mean by a 'meet-in-the-middle' attack. The obvious way to attack this cipher is a known plaintext attack, that is, encrypt any two distinct plaintexts $x_1, x_2$ (and hence two encryptions), getting their encryptions $y_1, y_2$ :

$y_1 = (a x_1 + b) \mod m$

$y_2 = (a x_2 + b) \mod m$

and solve for $a, b$ as:

$a = (y_1 - y_2) (x_1 - x_2) ^ {-1} \mod m$

$b = (x_1y_2 - x_2y_1) (x_1 - x_2) ^ {-1} \mod m$

Now, as for your side question of what $a^{-1}$ means, well, that is the modular inverse of $a$; if we claim that $c = a^{-1}$, this is equivalent to claiming that $a \cdot c = 1 \mod m$

The modular inverse of $a$ can be found efficiently (given a, m) by the Extended Euclidean Method