1
$\begingroup$

There are $26!$ permutations of the English alphabet. In Modern Cryptography textbook, William Easttom states that

the basic formula for any affine cipher is $ax + b \equiv \pmod{26}$.

I'm wondering whether this formula can express every possible permutation. It does not seem obvious that for every permutation $\sigma$ there exist $a$ and $b$ capable of expressing it. If this statement is true, what approach can be used to find $a$ and $b$?

$\endgroup$
1
  • $\begingroup$ Does your title should be Can all permutations be expressed with the formula? Since what you described is affine cipher. $\endgroup$ – kelalaka May 16 at 0:35
3
$\begingroup$

$a\cdot x +b $ means affine not permutation. And $a\cdot x +b \bmod 26$ is modular affine transformation.

$a\cdot x +b \bmod 26$ can have at most $26\cdot 26$ affine transformations some of which have no inverse and therefore without an inverse an affine transformation is not suitable for encryption where it is already not close to the modern encryption methods.

To have an inverse one must have $\gcd(a,26)=1$. This means $a$ cannot be divisible by 2 or 13. To find the actual number we can use Euler's Totient Function that counts the positive integers up to a given integer $n$ that are relatively prime to $n$. Then $$\phi(26) = (13-1)\cdot (2-1) = 13$$ So there are actually $26\cdot 12 =312$ possible affine transformations.

In any case, we have $26! = 403291461126605635584000000$ permutations and $312$ affine transformations, therefore the affine transformation cannot cover all possible permutations. The reverse is correct; the permutations can represent the invertible affine transformations.

$\endgroup$
4
  • 1
    $\begingroup$ Actually, there are only $12 \cdot 26 = 312$ affine permutations $\endgroup$ – poncho May 16 at 2:28
  • $\begingroup$ @poncho yes, you are correct. I've added that and I did not consider that since the value was so small compared to the factrial. $\endgroup$ – kelalaka May 16 at 9:10
  • $\begingroup$ Is there a generic name for a cipher that always maps one letter to another? $\endgroup$ – mark mark May 16 at 21:42
  • $\begingroup$ Do you mean that it has no fixed permutation, i.e. for every $m$, $Enc(m) \neq m$? $\endgroup$ – kelalaka May 16 at 21:44
-1
$\begingroup$

Yes, that formula can express every possible permutation - as long as a can become very large.

GCD(a,26) must equal 1 to get a valid permutation. When a is less that 26, that is constraining as even some primes, like 13, do not qualify. That is because, for prime p, there is a risk that p x n=26, for some n other than 1, i.e. they share a factor.

When a is prime and greater than 26, life is much easier. All primes are suitable, (because by definition a prime cannot share a factor with a smaller number)

However at some point there will be a repeat of the permutation as Pigeonhole principle there are 'only' 26! available. But 26! is very big.

$\endgroup$
1
  • 1
    $\begingroup$ Thats not true. When a is greater 26, it is equivalent to an a less than 26, because of the modulo. For example a=27 is equivalent to a=1. So a can not effectively be larger than 26 $\endgroup$ – jjj May 16 at 10:06

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.