# How is the affine cipher a permutation?

It seems there would be some collisions in what the different symbols map to, resulting in loss of information.

For example, say we use the English alphabet, multiply by 2 and take the congruence mod 26. In this case, A and N will both map to the same ciphertext letter, regardless of what the shift value is. Same with B and O, etc. In fact, if the formula is $(ax + b) \mod n$ where $n$ is the size of the plaintext alphabet, then the ciphertext alphabet will have only $1 \over a$ as many symbols as the plaintext alphabet.

Am I misunderstanding something?

• $gcd(a,n)$ must be $1$. – Meysam Ghahramani Mar 9 '17 at 16:40
• , and when that is $1$, there will be no collisions. ​ (Try a=2 and b=0 and n=5.) ​ ​ ​ ​ – user991 Mar 9 '17 at 16:42
• For any kind of encryption scheme, decryption must be possible. That means the encryption must be injective - otherwise it's not an encryption scheme. The only exception I can think of ist he Rabin cryptosystem - where you need some other way to figure out which root is the correct one. The decryption process just returns both. – tylo Aug 25 '17 at 9:30

Multiplication by 2 modulo 26 is indeed not a permutation. For example, $$2 \times 13 = 26 \equiv 0 = 2 \times 0 \pmod{26}.$$
The necessary and sufficient criterion for the affine map $x \mapsto ax + b$ to be a permutation of the integers modulo $m$ is that the multiplicative constant $a$ and the modulus $m$ must be coprime; that is, their greatest common divisor must be 1.
If this is the case, then we can find the modular multiplicative inverse $a^{-1}$ of $a$ modulo $m$ and use that to define the inverse map $x \mapsto a^{-1}(x-b)$. It's easy to verify, based on the fact that $a^{-1} a \equiv 1 \pmod m$, that the composition of these two maps (in either order) yields the identity map $x \mapsto x$, which is sufficient to show that these maps must be bijective.
Conversely, if $a$ and $m$ share a common divisor $g > 1$, then the map $x \mapsto ax + b$ cannot be a bijection. In particular, both $0$ and $m/g$ will be mapped to the same element $b$ by this map.
If there was $x_1 \neq x_2$ in the ring of integers modulo $n$ such that $$ax_1+b \equiv a x_2+b \pmod n$$ subtracting the two sides would give $a(x_1-x_2) \mid n$ and since $\gcd(a,n)=1,$ this means $x_1 \equiv x_2 \pmod n$ implying the map is a permutation under this assumption.