0
$\begingroup$

I have always thought that using two Vigenère ciphers leads to another Vigenère cipher with key length of LCM (least common multiple) of the two previous Vigenère ciphers. But I have stumbled upon this problem:

Let $\mathcal{V}_1,\mathcal{V}_2, \mathcal{V}_3$ be Vigenère ciphers with key length $l_1, l_2\in\mathbb{N}$ and LCM$(l_1,l_2)$. Prove that for some $l_1, l_2\in\mathbb{N}$ is not $\mathcal{V}_1\times\mathcal{V}_2\approx\mathcal{V}_3$.

I have tried with some lengths but it worked so that the product was Vigenère with length of LCM. Would you give me example of lengths for which it doesn't work?

$\endgroup$
2
$\begingroup$

I have tried with some lengths but it worked so that the product was Vigenère with length of LCM.

Actually, the statement really isn't "is encrypting with cipher $\mathcal{V}_1$ and the cipher $\mathcal{V}_2$ always equivalent to some cipher $\mathcal{V}_3$.

Instead, it's "are the set of transforms that you can express by first encrypting by some transform (I'll say key, even those the members in the set are technically transforms and not keys) in $\mathcal{V}_1$ and then by some key in $\mathcal{V}_2$ precisely the same as the set of transforms you can reach by encrypting by some key in $\mathcal{V}_3$."

Expressed that way, it should be obvious that, for some lengths $l_1, l_2, LCM(l_1, l_2)$ there are keys in $\mathcal{V}_3$ that cannot be reached by $\mathcal{V}_1$ followed by $\mathcal{V}_2$

To take a simple example, if $l_1 = 2$, $l_2 = 3$ and we're doing Vigenère in base 26. In this case, the total number of transforms that can be expressed by $\mathcal{V}_1$ and $\mathcal{V}_2$ is at most $26^2 \times 26^3 = 26^5$ (and it's actually less than that). However $\mathcal{V}_3$ contains $26^6$ transforms, hence there must be quite a number that are not reachable via $\mathcal{V}_1$ and $\mathcal{V}_2$

$\endgroup$
  • $\begingroup$ I hadn't thought about that way of showing it. Usually to prove something is false, you just need a counter-example (hence my idea of l1 and l2 that returns identity, therefore key length = 0). Really nice proof ! $\endgroup$ – Biv Apr 5 '16 at 21:53
  • $\begingroup$ @Biv: actually, your example is equivalent to the key "aaaa"... $\endgroup$ – poncho Apr 5 '16 at 21:57
  • $\begingroup$ Which in Vigenère case is identity no ? Ho I guess I see your point. Because it can be seen as equivalent to aaaa, it satisfies the LCM condition. Got it ! $\endgroup$ – Biv Apr 5 '16 at 22:02
  • $\begingroup$ Thx for the answer - can I just ask, how did you get to the number of possibilities $26^2\times 26^3$? Thx $\endgroup$ – GorTeX Apr 6 '16 at 11:36
  • 1
    $\begingroup$ @Jean-FrançoisGagnon: and, if you examine it even closer, you'll see that $|\mathcal{V}_2 \times \mathcal{V}_3| = 26^4$; that's because for two keys $v_2, v_3$, you can add an integer ($\bmod 26$) to each character in $v_2$, subtract that same integer to each character in $v_3$, and you haven't changed the operation. Hence, for every possible transform in $\mathcal{V}_2 \times \mathcal{V}_3$, there are 26 possible pairs of keys that generate it. $\endgroup$ – poncho Apr 6 '16 at 13:13

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.