I have been learning about Vigenere ciphers and then thought of this scenario: if a cryptographer encrypts a plaintext English message with a Vigenere cipher and then another cryptographer, who wants to ensure that the message is very secure, encrypts the ciphertext with another Vigenere cipher (with a different key length). Given only the ciphertext, how can you decrypt the message? A step by step explanation would be greatly appreciated.
A Vigenère cipher is easily breakable, when the ciphertext is reasonably larger than the key size.
This is due to the fact that its cipher-texts leak statistical information about the pair plaintext - key.
Applying a Vigenère cipher several times, with different keys and key-sizes, would not make your scheme much more secure. It might, at most, requires a larger ciphertext than usual, but anyhow some statistical information would be leaked, which in turn can be used to reveal the key and plaintext content.
The only approach to avoid this statistical leakage is by imposing key size == plain text. However, as you might know, this would not be a Vigenère cipher anymore. This cipher would be the One-Time Pad, which not by accident attains perfect secrecy.
Applying another round of vigenere would make the ciphtertext (in nearly every case) harder to break, yes. The problem is: This "new" algorithm is just a normal vigenere algorithm with a longer key (if the key lengths of both keys are not equal and not 1). You don't need to apply vigenere a second time, you can just calculate the new key in advance.
Example: We encrypt the plaintext "hello world hello world" with the key "ABC". (Encryption with A doesn't change the plaintext, it's like adding 0.)
Now we encrypt the intermediate result again with the key "DDBC":
The length of the first key is 3, of the second key is 4. The least common multiple of both numbers is 12. If we now repeat the first key 4 times and "encrypt" it with the second key, we get a new key which eliminates the need for a intermediate result:
If we encrypt the plaintext with this new key we immediately get the final ciphertext:
You see, double encryption (or more generally, multiple encryption) with vigenere doesn't add extra security by itself. You could just use a longer key from the beginning on. Search for generals attacks on vigenere to break this "double encryption".
What about the one-time-pad? You need a fully random, never before used key, which has to be as long as the plaintext for the one-time-pad. If you really use this scheme, you also don't need a double encryption: The one-time-pad is always fully secure if you tell nobody the key.