# Affine Cipher Cryptanalysis

I am trying to perform Cryptanalysis on Affine cipher . Given Plain Text "GO" and cipher text "TH"

We know , $G =6 , O=14 , T=19 , H= 7$

• By brute force method

I'm getting key $(a,b)$ as $(5,15 )$

• But by known plain text attack method

$6a + b = 19 \\ 14a +b = 7$

on solving the equations . im getting

$-8 a + 0 = 12$

taking addictive inverse of $-8 = 18$

We get , $18a +0 =12$ , Now

$a= 12*$ multiplicative inverse of $(18)$

Multiplicative inverse of 18 doesnt exist then how to proceed ? Is my approach correct ?

When working with modulo arithmetic, in case of trouble, get back at what the notation used truly leans. When the question correctly derives $18\,a+0=12$, that really is a shorthand for $18\,a+0\equiv12\pmod{26}$. By definition of the equivalence..modulo notation, that is meaning $(18\,a+0)-12$ is divisible by $26$ when computing in (signed) integers $\mathbb Z$. An integer is divisible by $26$ if and only if it is divisible by $2$ and $13$. The rest will follow.
More generally, when an equation holds modulo a squarefree integer, that equation is equivalent to the combination of equations obtained by replacing the modulo by each of its prime factors. So here we get $$18\,a\equiv12\pmod2\;\;\;\text{ and }\;\;\;\;18\,a\equiv12\pmod{13}$$ or, reducing, $$0\,a\equiv0\pmod2\;\;\;\text{ and }\;\;\;\;5\,a\equiv12\pmod{13}$$ The first is a tautology, and the second can be solved by multiplying by the inverse of $5$ modulo $13$, that is $8$, giving $a\equiv5\pmod{13}$.
That gives two possible $a$ modulo $26$: $a$ can be $5$ or $18$. The second is obtained by adding the modulus $13$ to $5$. More generally, given $a$ modulo $u$ with $0\le a<u$, there are $v$ values for $a$ modulo the product $u\;v$ with $0\le a<u\;v$ , and these are $a+k\;v$ with $0\le k<v$.
The value of $b$ corresponding to a given $a$ is obtained by moving that value of $a$ in either of the two equations $6\,a+b\equiv19\pmod{26}$ or $14\,a+b\equiv7\pmod{26}$, and pulling $b$. Both values of $a$ yield that $b$ is $15$ (modulo $26$). That's no coincidence.
Therefore, beyond $(a,b)=(5,15)$, there is an alternate solution $(a,b)=(18,15)$. More plaintext is required to recover the full key.
• Would you please tell how you are getting $(a,b) = ( 18,15 )$ ? – Akhil Nadh PC Aug 24 '17 at 4:17