2
$\begingroup$

I was wondering, what is to be the shortest possible key using Vigenere encryption, if a text is ciphered one time with a key of length $i$ using Vigenere and second time with a key of length $j$ using Vigenere?

From what I understand, each time it is encrypted, each character shifts using the first key and then using the second one, so I believe that for each pair there's an equivalent shifting. but if the two keys have a different length, how can I find the shortest possible key?

I think it has to be something with lowest common denominator, but I am not sure. how can this be shown mathematically?

my previous edit was a mistake and i deeply sorry for it. i read the book wrong and didn't interpret what's written well. very sorry for it. yuval explained to me well and i continue to research it using his given information

| cite | improve this question | |
$\endgroup$
4
$\begingroup$

If you sum a sequence with period $a$ and a sequence with period $b$, then you get a sequence which is $\mathsf{LCM}(a,b)$-periodic. But the new sequence might have a smaller period, as the following example demonstrates (addition is modulo 10):

022441133502244113350224411335
000772999611888000772999611888
022113022113022113022113022113

The first sequence has period 10 (0224411335), the second sequence as period 15 (000772999611888), and the sum sequence has period 6 (022113), although the LCM is 30.

More generally, the sum of a sequence of period $i$ and a sequence of period $j$ could have period exactly $k$ iff $\mathsf{LCM}(i,j) = \mathsf{LCM}(i,k) = \mathsf{LCM}(j,k)$. See Restrepo and Chacon, On the period of sums of discrete periodic signals.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ so is there exists some kind of shortest key for what's described? for instence, if i cipher the message once with a key of size i(using vigenere) and second time with a key of length j(using vigenere) - is there a shortest key to decipher the message? $\endgroup$ – alberto123 Nov 21 '19 at 12:26
  • $\begingroup$ Yes, but the length of the shortest key could depend on the actual keys. $\endgroup$ – Yuval Filmus Nov 21 '19 at 12:27
  • $\begingroup$ thank you so much for explaining that to me and for the reference. i am going over the link and similar presentation i found at online colleges in addition to my book and it helps a lot. thanks again $\endgroup$ – alberto123 Nov 21 '19 at 13:44

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.