Affine cipher converts a message $m$ to encrypted message $m^*$ using the transformation $Rem(a\cdot m + b, p)$, where $Rem(x,y)$ is remainder when x is divided by y.
$\therefore m^* \equiv a\cdot m + b $ (mod $p$)
Given three plain messages and their corresponding encrypted message, is it possible to find the affine transformation that was used? If so, would you please provide the solution and if not, would you please prove it.
More, specifically solve the following system of congruences.
$m_1^* \equiv a\cdot m_1 + b $ (mod $p$)
$m_2^* \equiv a\cdot m_2 + b $ (mod $p$)
$m_3^* \equiv a\cdot m_3 + b $ (mod $p$)
With the following assumptions:
- Assume, $a$, $b$ and $p$ are unknown.
- Moreover $gcd(a,p) = 1$.
- $p$ is NOT necessarily a prime.
- $m_1 \neq m_2 \neq m_3$
- $m_1^* \neq m_2^* \neq m_3^*$
Best Answer
The modulus $\ p\ $ must be larger than $\ \max\left(m_1^*, m_2^*, m_3^*\right)\ $, and $\ \left(m_1^*-m_2^*\right) \left(m_3^\ -m_2^\ \right)\equiv a \left(m_1-m_2\right) \left(m_3^\ -m_2^\ \right)\equiv$$\left(m_1^\ -m_2^\ \right) \left(m_3^*-m_2^*\right) \pmod{p}\ $, so $\ p\ $ must divide $\ \left(m_1^*-m_2^*\right) \left(m_3^\ -m_2^\ \right)-\left(m_1^\ -m_2^\ \right) \left(m_3^*-m_2^*\right)\ $. To be useable as cipher, the plain messages must also be restricted to a range of at most $\ p\ $ integers whose remainders mod $\ p\ $ are distinct, and $\ p\ $ must be larger than the largest remainder mod $\ p\ $ of that set of integers. Typically, the set would be $\ \mathbb{Z}\cap[0,p-1]\ $, but here I'll assume you don't know what it is.
In any case, $\ p\ $ must be a divisor of $\ \left(m_1^*-m_2^*\right) \left(m_3^\ -m_2^\ \right)-\left(m_1^\ -m_2^\ \right) \left(m_3^*-m_2^*\right)\ $ that exceeds $\ \max\left(m_1^*, m_2^*, m_3^*\right)\ $, of which there will only be a finite number. For each such possible value of $\ p\ $ you can then solve the linear equations for $\ a\ $ and $\ b\ $, provided that $\ gcd\left(m_1,m_2,m_3,p\right)=1\ $. If this is the case, let $\ \gamma=\gcd\left(m_1,m_2, m_3\right)\ $. Then $\ \gcd\left(\gamma,p\right)=1\ $, and you can find integers $\ k_1,k_2,k_3\ $ such that $\ k_1m_1+k_2m_2+k_3m_3=\gamma\ $, and \begin{align} a&=\gamma^{-1}\left(k_1m_1^*+k_2m_2^*+k_3m_3^*-\left(k_1+k_2+k_3\right)b\right)\pmod{p}\\ b&=m_1^*-am_1\pmod{p}\ . \end{align} If there is more than on one potential solution satisfying these conditions, there might still be some of them which fail to satisfy at least one of the congruences $$ m_i^*\equiv am_i+b\pmod{p}\ , $$ in which case, it can be eliminated as a possibility.
Example:
Suppose $\ m_1=15, m_2=17,m_3=22, m_1^*=7,m_2*=429, m_3^*=484\ $.Then \begin{align} \left(m_1^*-m_2^*\right) \left(m_3^\ -m_2^\ \right)-\left(m_1^\ -m_2^\ \right) \left(m_3^*-m_2^*\right)=-2000 \end{align} The only (positive) divisors of $\ -2000\ $ which exceed $\ \max\left(m_1^*,m_2^*,m_3^*\right)=$$484\ $ are $500$, $1000$, and $2000$, one of which must be the value of $\ p\ $. Also, $\ \gcd\left(m_1,m_2, m_3\right)=$$\gcd\left(15,17,22\right)=$$1=8\cdot15-7\cdot15\ $. Therefore \begin{align} a&\equiv8m_1^*-7m_2^*-b\pmod{p}\\ &\equiv-3289 \pmod{p}\\ &\equiv711 \pmod{p}\\ b&\equiv m_1^*+3289m_1 \pmod{p}\\ & \equiv 49342 \pmod{p}\\ & \equiv 1342\pmod{p}\ , \end{align} because all the possible values of $\ p\ $ are divisors of $2000$. Thus, the only possible solutions are \begin{align} p&=500, a=211, b=342\\ p&=1000, a=711, b=342\\ p&=2000, a=711, b=1342\ . \end{align} But \begin{align} 711m_3+1342\hspace{-0.5em}\pmod{2000}&=711m_3+342\hspace{-0.5em} \pmod{1000}\\ &=984\\ &\ne484=m_3^*\ , \end{align} so the only possible solution is $\ p=500, a=211,$ and $\ b=342\ $.
Thus it is certainly sometimes possible to recover $\ p,a\ $, and $\ b\ $ uniquely with only three matched plain and cipher pairs, but it is certainly also possible that there will not be a unique solution for such a small number of matched pairs.