1
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Would you please tell how you are getting $(a,b) = ( 18,15 )$ ? $\endgroup$ Aug 24, 2017 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.