0
$\begingroup$

I am currently working on a problem where an attacker knows that a user's password is either "pqrs" or "jmlo" and also knows that the encryption scheme is using the Vigenere cipher with a key length of 2 (Obviously, the attacker also knows the ciphertext). I must either describe how to find out with 100% certainty that the password is either pqrs or jmlo, or describe why this cannot be broken.

After working through it, I cannot see how this would be broken. The plaintext is only 4 characters, so statistical analysis and Kasiskis method of searching for bigrams/trigrams wont work either. Is there anything you can do to crack this encryption scheme?

$\endgroup$
4
  • $\begingroup$ You know the ciphertext. You know it must decrypt to one of two possible plaintexts. It's trivial from there to work out the only two keys that could possibly have been used. At that point you should be able to come up with the answer on your own. $\endgroup$ Sep 24, 2020 at 21:21
  • $\begingroup$ Even with brute force brute force you can answer that definitely in less than 52 attempts ($26*2$) since you can brute force each key character separately. Or you can use a not-completely-stupid attack and reduce it to 4 attempted keys total. I'll let you figure out the rest. $\endgroup$
    – Serpent27
    Sep 24, 2020 at 22:15
  • $\begingroup$ I don't believe you can use knowledge of the repeated key to decide which plaintext it is 100%. Knowledge of the repeated key can get you to the point that you know that (if the plaintext is $c_0,\dots, c_3\in\mathbb{Z}_{26}$, and the messages are mapped to this range in the standard way) $(c_0 - c_2) \equiv (m_0 - m_2)$ and $(c_1-c_3)\equiv (m_1-m_3)\bmod 26$. But for both messages $m_0-m_2 = 2$ and $m_1-m_3 = 2$, so knowledge of the repeated key does not lead to a "check" that one of the messages fails. This isn't conclusive evidence against the question, but the "easy" strategy fails. $\endgroup$
    – Mark
    Sep 24, 2020 at 22:41
  • $\begingroup$ @Mark I'll say it definitively... In this case there's no way to differentiate between the 2 passwords; if each choice is a possible plaintext, each can be encrypted to the same ciphertext using some 2-character key. Within the given parameters there's simply not enough information to distinguish. If any letter in one of the choices was different, this system could be solved. I guess OP is just a bit unlucky. $\endgroup$
    – Serpent27
    Sep 25, 2020 at 0:20

1 Answer 1

1
$\begingroup$

If I can prove there's no single key that can encrypt to both outputs I can prove with 100% certainty which message it is, but if not I can't.

"pqrs" or "jmlo"

You can identify which password it is by comparing each letter with the corresponding letter once encrypted. For example, compare $P-R$ with $J-L$ (treating each letter as a number

They look like variables in this notation but they're not.


  • P and R are 2 letters apart; J and L are also 2 letters apart so that's inconclusive.
  • Q and S are 2 letters apart. M and O are also 2 letters apart; so that's also inconclusive.

This means there exists a 2-character key mapping each password to the same ciphertext (the mathematical relations between the letters are insufficient to distinguish). As such, there's no way in this case to identify which password it is.

$\endgroup$

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.