I have this interview question that I have solved up to a point, but I couldn't reach a conclusion, can you please help me?
Question:Consider the following ciphertext and plaintext relation. For each plaintext letter, substitute
the ciphertext letter:
C = E([a, b], p) = (ap + b) mod 26
C: ciphertext
P: plaintext
a and b: integer numbers
A basic requirement of any encryption algorithm is that it be one-to-one. That is, if p !=q , then E(k,p) != E(k,q) . Otherwise, decryption is impossible, because more than one plain text character maps into the same cipher-text character. The above cipher is not one-to-one for all values of a. For example, for a=2 and b =3 , then E([a,b],0) = E([a,b],13) = 3 . a) Are there any limitations on the value of b? Explain why or why not. b) Determine which values of a are not allowed. c) Provide a general statement of which values of a are and are not allowed. Justify your statement.
This question should belong to Math, or Crypto, but I'll answer anyway, but beware that since it does not support math, the answer is difficult to see.
Suppose that we have p and q. The condition is to find a and b such that E([a,b], p) != E([a,b],q)
Math equation: ap + b != aq + b (mod 26).
Base on congruence arithmetic we can subtract b: ap != aq (mod 26), since b = b (mod n).
Base on cancellation law: p = q (mod n) if and only if gcd (a,n) = 1 and ap = aq (mod n) where all variables are positive integers. So to let p != q (mod 26) then gcd(a, 26) = 1, or a and 26 is coprime. Since 26 = 2x13, then a is an odd positive integer EXCLUDING 13.
Hope it helps.