3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ $gcd(a,n)$ must be $1$. $\endgroup$ – Meysam Ghahramani Mar 9 '17 at 16:40
  • $\begingroup$ , and when that is $1$, there will be no collisions. ​ (Try a=2 and b=0 and n=5.) ​ ​ ​ ​ $\endgroup$ – user991 Mar 9 '17 at 16:42
  • $\begingroup$ 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. $\endgroup$ – tylo Aug 25 '17 at 9:30
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

Normally we use a prime n, which 26 is not. For any prime n and for any smaller positive number we get gcd(a,n)=1 Which causes any affine transformation to be a permutation. It should be trivial that addition is a permutation over Zp, we should also show multiplication is a permutation. We have ax = ay (mod p) Which means a(x-y) is devisble by p Since gcd(a,p)=1 this only leaves x=y mod p

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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