0
$\begingroup$

In the Affine cipher, the key $k = (a, b)$ should have the following property, i.e. GCD of $a$ and the modulus should be 1:

$\gcd (a, m) = 1$, where $m$ is the set of possible moduli

My question is, why it is required that $a$ should have the above property? What is the significance of this? And why is $b$ excluded from this condition?

$\endgroup$
  • 1
    $\begingroup$ This is explained directly in the article you linked "The multiplicative inverse of a only exists if a and m are coprime". Essentially, you won't be able to decrypt the message unless gcd(a,m) = 1. This doesn't hold for b because b is not multipled into the equation, it is added, which is reversible under the modulus operation. $\endgroup$ – Jacob H Jul 30 '17 at 20:20
3
$\begingroup$

OK, to understand this issue, let's first recap how the affine cipher is defined:

$$c=a\cdot x+b\bmod m$$

Note that the following holds: $a\cdot x+b=c\iff a\cdot x=c-b$, where you would calculate $-b$ as $m-b$ which is $>0$ because $m>b$ because otherwise you could reduce $b\bmod m$ further.

Ok, so on our way to decryption we now only need to get $x$ out of $a\cdot x=c'\bmod m$ (with $c'=c-b\bmod m$).

Now if $d=\gcd(a,m)>1$ then this equation has either $0$ or $d$ solutions, neither being what you want from a decyption function (no plaintext recovery or uncertain plaintext recovery).

So this is why we make the restriction $\gcd(a,m)=1$, which will ensure that there is exactly one integer solution to $a\cdot x=c'\bmod m$ with $0\leq x<m$.

If you want illustration of the lack of solutions, have a look at the modular multiplication table of for example 15. You will note for example that there is no $x$ such that $6\cdot x=5\bmod 15$ however, there are three $x$ such that $6\cdot x=3\bmod 15$ and note that $\gcd(15,6)=3>1$.

$\endgroup$
  • $\begingroup$ a very clear explanation. worth reading all the references you cited. thanks. :) $\endgroup$ – Vishrant Jul 30 '17 at 21:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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