Win a copy of Reactive Streams in Java: Concurrency with RxJava, Reactor, and Akka Streams this week in the Reactive Progamming forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Junilu Lacar
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Ron McLeod
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Ganesh Patekar

How to break the Vigenère cipher if you know the length of the key?

 
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So I have an assignment for class to do a few things.  The first part is to write a program to encrypt and decrypt using the Vigenère cipher.  This is pretty simple, and I've already done that.  I'm pretty lost when it comes to the second part though.  We are supposed to take ciphertext that has been encrypted using the Vigenère cipher and decipher it, and the only information that should be known to the program is the key length, which is 3.  I know one way to do this would be to brute force the key, and just generate every possible combination of 3 letters and somehow find out which decrypted string looks the most like English (I'm a little confused about how to do this).  But I have a few questions.  

1. Is there any way to decipher the ciphertext with complete accuracy, without human input?  To put ciphertext into the program and it will, 100% of the time, correctly decipher it.  Because based on what I'm reading most of the methods involve ranking the deciphered outputs based on how much sense they make linguistically, and it seems like it could be possible for the program to think something that isn't actually the original plaintext is the correctly deciphered text.  

2. Is there any way to do it other than brute forcing the key?  Our professor suggested breaking the ciphertext into 3 groups of characters, one group for each letter in the key, because the characters within each group will be offset by the same amount from the original plaintext.  But I'm not really sure where to go with this concept.  
 
Saloon Keeper
Posts: 10649
227
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Jesse,

In general, cryptanalysis doesn't yield an answer with 100% certainty. Even when brute forcing a key, if 9 out of 10 decrypted messages yield garbage, and 1 yields plain English text, who's to say that the original sender didn't intend to encrypt garbage? Here's an example: If I have some sort of password that consists of a nonsensical string of characters, I could choose a key so that one of its decryptions would yield English text, thereby fooling the attacker.

A Vigenère cipher is basically just multiple interwoven Caesar ciphers. Once you know the length of the key, you can break up the ciphertext in separate smaller ciphertexts, one for each letter in the key. You would then apply normal cryptanalysis for the Caesar cipher.

In your example, you split up the ciphertext into one ciphertext that consists of the 1st, 4th, 7th character etc. from the original ciphertext, one ciphertext that consists of the 2nd, 5th, 8th character etc. and one ciphertext that consists of the 3rd, 6th, 9th character, etc. Then you try to guess the letter that each of the three separate messages was encrypted with using frequency analysis: The letters E and T are most common in English, while Q and Z are least common. Then you interweave the decrypted messages to find out if the combined message looks like an English phrase.

You can first try out if this really works by brute forcing the key, decrypting the message, and seeing if indeed the letters E and T are used most commonly.
 
He does not suffer fools gladly. But this tiny ad does:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!