Question

An affine encryption y=E−​[a,b](x)=(ax+b)mod13 (note: both a and b belong to Z_13) can be considered a double encryption, where one encryption is multiplying by a and the other is a shift by b. If we use a "meet-in-the-middle* attack to find out the key [a, b], how many steps (mathematical operations) it will take at most? (not including comparison operations). Hint: think about the number of possibilities for a and b first. Your Answer: Answer

Answer 1

In affine encryption, the maximum number of steps required for a meet-in-the-middle attack to find the key [a, b] is 169.

Step-by-step explanation:

In affine encryption, the key is represented by the values of a and b which belong to Z13, the set of integers modulo 13. The encryption process involves multiplying the plaintext by a and then adding b, followed by taking the result modulo 13. A meet-in-the-middle attack is a method used to find the key [a, b]. To determine the maximum number of steps required, we need to consider the number of possibilities for a and b in Z13. Since Z13 has 13 elements, there are 13 choices for both a and b. Therefore, the total number of possibilities for the key is 13^2 = 169. Hence, the maximum number of steps, excluding comparison operations, required for the meet-in-the-middle attack is 169.