2
$\begingroup$

How would I be able to show that a key $K=(a,b)$ is involutary for an Affine Cipher over the integers modulo n?

Similarly, is there a way to generalize the conditions for a key to be involutary for a substitution cipher?

(Involutary keys are keys for which the encryption function is equal to the decryption function $e_K=d_K$)

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Feb 2 '16 at 22:15
2
$\begingroup$

If $E(x) = ax+b \bmod n$, and $E(E(x)) = x$, then you need $a(ax+b)+b = x$, or $a^2x + ab + b = x$. So any (a, b) where $a^2 = 1$ and $b(a+1) = 0$ will do it. There are always solutions $(1, 0)$ (which corresponds to not encrypting) and $(-1, b)$. Depending on the value of $n$ there may be other solutions for $a$. There are only those two for $n = 26$, but there are a total of 4 solutions for $n = 36$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ To find the solutions, are you just testing that each element of (say) $\mathbb{Z}_{15}$, satisfies the above conditions or is there another method being used? $\endgroup$ – Cryptkeeper Feb 3 '16 at 5:24
  • $\begingroup$ For small values of n, that's easiest. For larger, I think you can use the factorization of n. $\endgroup$ – bmm6o Feb 3 '16 at 13:40
0
$\begingroup$

Similarly, is there a way to generalize the conditions for a key to be involutary for a substitution cipher?

Any substitution cipher $E$ over a set $M$ might be expressed as a permutation $\pi_E$ of the elements of $M$. Any permutation is uniquely identified by its decomposition into cycles, save for the order of the cycles. The condition $E(E(x)) = x$ will be met for all $x \in M$ if and only if the permutation $\pi_E$ is decomposed into cycles of length 1 or 2 only.

| improve this answer | |
$\endgroup$
  • $\begingroup$ For instance, if I had some sort of system where I was working over $\mathbb{Z}_4$, the conditions of the substitution cipher is $S_4$? (where $S_4$ denotes all possible permutations of elements in the symmetric group with four elements)? $\endgroup$ – Cryptkeeper Feb 3 '16 at 7:31
  • $\begingroup$ Sorry, I should've asked, is it all elements of $S_4$ with order $2$? $\endgroup$ – Cryptkeeper Feb 3 '16 at 8:19
  • $\begingroup$ The symmetric group $S_n$ is defined as the set of all permutations over the elements of $\mathbb{Z}_n$ with composition of permutations being the group operation. If and only if an element in such a group is of order 2, then it meets the condition in your question, yes. $\endgroup$ – Henrick Hellström Feb 3 '16 at 10:00

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.