Skip to content

Instantly share code, notes, and snippets.

@NthPortal
Last active February 7, 2017 08:15
Show Gist options
  • Save NthPortal/9be958ca0339b334e4c067ed8321fd21 to your computer and use it in GitHub Desktop.
Save NthPortal/9be958ca0339b334e4c067ed8321fd21 to your computer and use it in GitHub Desktop.
Project Euler problem 59

Regarding Project Euler problem 59

The problem contains one correct statement, which is that

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes.

Assuming that the bytes are actually random, there is said to be 'perfect secrecy' - the ciphertext reveals no information (other than length, obviously) about the plaintext. However, this approach has several problems, which will be covered below.

The problem goes on to say that, "[u]nfortunately, this method is impractical for most users," (yup) "so the modified method is to use a password as a key." (NO. BAD. VERY BAD. NONONONO)

It continues:

If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message.

(blah blah, that's just included so the method is clear)

Here's the really bad part.

The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

no

NO

NO

NO

There is no balance for which you can remember a sufficiently long password and have any security at all. Period. Full stop.

If the key is not as long as the message, there is no longer perfect secrecy. In practice, though it would be unlikely that the message can be cracked with the password only repeated one or two times IF THE PASSWORD WAS ACTUALLY RANDOM, WHICH IT ISN'T, the message will be cracked for a number of reasons.

  • Due to the length of the message, the password will be repeated a lot more than once or twice. Which opens it up to statistical analysis, which will very quickly break the encryption. It doesn't need much repetition of the password to crack.
  • THE PASSWORD IS NOT RANDOM. If the password is something you're going to remember, it's either stupidly short (maybe 8 bytes at most? That covers 8 characters, wee. Did you want to say more than "hi there"?), or it's NOT RANDOM. If the password is some word or phrase you can remember, then it's very, very, VERY not-random. It might even be possible to break the encryption with that information alone, without any repetition of the key.
  • You can't reuse the password for future messages, either, or that's just as bad as repeating the password for a longer message. Worse probably, because you have to start from the beginning of the password.

There are some other problems with the method, even if you use a fully-random key which is longer than the message.

  • You need to get the key to the other party somehow. To do this securely, this really requires meeting in person.
  • The key needs to be really random. Like, really random. Not kinda mostly random-ish. Actually random. Otherwise it can be cracked.
  • It's only good for one message, really. Which is not that useful.
  • You could in theory use it for more than one message, if the key is longer than your multiple messages combined. Except that you'd have to re-transmit the previous message at the beginning of the next one, so that the second message is decrypted starting at the right part of the key (it can't also start at the beginning of the key, or it's insecure). If you want to be able to transmit a lot of messages, the key needs to be REALLY BIG, and you have transmit ALL previous messages with each new message, so that decryption starts in the right place.
    • Theoretically, you don't have to re-transmit them, but if you don't, they might arrive in the wrong order. Or they other party might miss one (intercepted? who knows!), and then the other party can't decrypt them.
    • Or you could set up a complicated protocol to say that you have received a message, in such a way that even if the final response gets lost, it doesn't break future decryptions. Which uses up even more of your key.

In short, this type of encryption is not very practical, and rarely useful. It could perhaps be used for a single, small, very sensitive message, but you still need to worry about how to share the key.

If you want to encrypt messages, use PGP. Or an end-to-end encrypted messenger.

Don't do what this Project Euler problem suggests. Just don't. Please.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment