0
$\begingroup$

I'm currently learning cryptography at a university. I can't wrap my mind around how the involutional property of Engima reduces its possible ciphers while being poly-alphabetic. Can someone please explain this?

The German Wikipedia link says that if the plaintext is ABCD, then the ciphertext CADB is impossible.

We're looking at all possible permutations of ABCD and apparently the only possible permutations are:

  • BADC
  • CDAB
  • DCBA
Improve this question
$\endgroup$
2
  • $\begingroup$ Where did you find a reference about ABCD can't be turned into a cipher CADB? I looked (in the german version) and didn't find anything. Are you sure that you didn't misunderstood something? As far as I know it should be possible to turn the plaintext ABCD into the ciphertext CADB. $\endgroup$
    – AleksanderCH
    Aug 13, 2019 at 12:15
  • $\begingroup$ @AleksanderRas: I believe that he is referring to the transform of a single character (for example, the first). That is, if a key turns an initial plaintext A->C, then that same key cannot turn an initial plaintext B->A; that is, it cannot do a mapping AB** into CA**... $\endgroup$
    – poncho
    Aug 13, 2019 at 12:45

1 Answer 1

Reset to default
1
$\begingroup$

The number of involutions of size $n$ satisifies the recurrence relation:

$$I(n) = I(n-1) + (n-2)I(n-2)$$

(This recurrence is easy to deduce).

Given than $I(1) = 1$ and $I(2) = 2$, we can easily compute $I(4) = 8$, which is strictly smaller than the number of permutations of size 4 (which is 24).

This recurrence allows us to quickly compute the number of involutions of size 26 as 158,432,124,870,784; much smaller than the number of permutations 26! = 604,937,191,689,908,372,404,961,280

BTW: the involutions of size 4 are:

$$ABCD$$

$$ABDC$$

$$ACBD$$

$$ADCB$$

$$BACD$$

$$BADC$$

$$CBAD$$

$$CDAB$$

$$DBCA$$

$$DCBA$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your reply. I still don't understand, why for example ABCD can not be encrypted to CADB because of the involutional property, where is the conflict? Isn't there a conflict with the fact that enigma is poly-alphabetic, meaning the key changes slightly each encryption. $\endgroup$
    – Tim
    Aug 13, 2019 at 13:18
  • 1
    $\begingroup$ @Tim: actually, the plaintext ABCD can be encrypted to the ciphertext CADB; what can't happen is you have the plaintext A be encrypted to C, and (with the same key) have the plaintext B encrypted to A. $\endgroup$
    – poncho
    Aug 13, 2019 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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