Problem 059

[satyres]

Solved ! thanks for your help !

[aware]

" and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text."


This doesn't tell me anything. It only tells me that at least one English word exists in the decrypted message, since "must" says it's a necessary but not necessarily sufficient condition. The rest could be two spaces to the side of this word, and a random string of letters. Is the message composed of random symbols, like "%?@&$"? There is not enough information to solve this problem.

[dawghaus4]

" and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text."


This doesn't tell me anything. It only tells me that at least one English word exists in the decrypted message, since "must" says it's a necessary but not necessarily sufficient condition. The rest could be two spaces to the side of this word, and a random string of letters. Is the message composed of random symbols, like "%?@&$"? There is not enough information to solve this problem.

Do I detect frustration?

Since the problem has been solved by more than 23,000 people, there is enough information to solve it. The file contains an encrypted English language message. As such, the characters (represented by the numbers) in the file are not random. However, it would be the hope of an encryption scheme to make the characters appear to be random. If you had the three letter password key, the message would be decrypted by XORing the first letter of the key with the first character in the file, XORing the second letter of the key with the second character in the file, XORing the third letter of the key with the third character in the file, XORing the first letter of the key with the fourth character in the file, etc.

So you task is to figure out what the password key is. Knowing that the password key is 3 lower-case characters, makes the problem doable. (On my laptop, my program solves the problem in 0.01 seconds.)

Tom

[TripleM]

This doesn't tell me anything. It only tells me that at least one English word exists in the decrypted message, since "must" says it's a necessary but not necessarily sufficient condition. The rest could be two spaces to the side of this word, and a random string of letters. Is the message composed of random symbols, like "%?@&$"?

That's an overly strict way of interpreting that sentence. You should interpret it as you would expect, and in the same way that any codebreaking system must do: the entire decrypted text makes sense in English.

[aware]

This doesn't tell me anything. It only tells me that at least one English word exists in the decrypted message, since "must" says it's a necessary but not necessarily sufficient condition. The rest could be two spaces to the side of this word, and a random string of letters. Is the message composed of random symbols, like "%?@&$"?

That's an overly strict way of interpreting that sentence. You should interpret it as you would expect, and in the same way that any codebreaking system must do: the entire decrypted text makes sense in English.

The sentence "This is a percent sign: %" makes perfect sense. So does "The letters sdgvsgsc are gibberish." The two sentences meet the criteria of *necessarily* containing English words, i.e. they must contain English words and they do.

[Marcus_Andrews]

The sentence "This is a percent sign: %" makes perfect sense. So does "The letters sdgvsgsc are gibberish." The two sentences meet the criteria of *necessarily* containing English words, i.e. they must contain English words and they do.

Yes, those sentences make sense in English -- and even if the real message was of a similar format to what you describe, there are still some simple heuristics you could use to determine which decoded text is likely to be correct (by virtue of knowing that it is a message containing English words). The message is also on the longer side, which means that many first-order statistical assumptions become viable.

Edit: Actually, you've already solved this problem on the main site, so feel free to check out the solution forum and see how others tackled it.

[solarmew]

I converted text into ASCii and Plus@@ 'ed the list of numbers corresponding to all the characters ... why is it saying the number isn't right? ....

[dawghaus4]

I converted text into ASCii and Plus@@ 'ed the list of numbers corresponding to all the characters ... why is it saying the number isn't right? ....

Did you find the encryption key and decrypt the message? The decrypted message is a plain English message and you will know when you have it decrypted.

If yes, it is the ASCII codes for the decrypted message that one must sum. If that is what you are doing, I suggest that you count the number of characters in the file and count the number of ASCII codes you are summing.

Tom

[solarmew]

Dammit, you're right, the decoded text is one character short but the beginning and end chars are there... Wtf XD ... Must've dropped a space somewhere, maybe when flattening the list or something ....

[fefelatornade]

Hello,

I have recently attempted problem #59, and after going crazy for a while, even trying to solve some parts manually, I gave a look at the input data, and noticed a mismatch between what's been used by other people, and the file I was proposed.

Unless I am extremely mistaken, the input data is supposed to start with the following numbers:
79,59,12,2,79,35,8,28,20,2,3,68,8,9...

whereas the file at https://projecteuler.net/project/resour ... cipher.txt starts with:
36,22,80,0,0,4,23,25,19,17,88,4,4,19...

Could someone please double check this please ??

Also, after using an input file I found on the web, I was able to decode the message and found sensible a sensible message. I also found the value of the sum of the decoded ascii chars, but it was rejected. (I used my code, but since I was at it, I looked at the value found by other - not their logic - and I had the same result as them.)

Is it possible that you have changed the input and expected value, but not the updated the problem statement or something ? or simply have a misplaced value somewhere ?

Thanks a lot.

[MHealy]

The input data was changed earlier this year; the linked file starting "36,22,80,0,0,4,23,25,19,17,88,4,4,19..." is correct.

[hk]

Merged with the existing thread for Problem 059.

[fefelatornade]

Thanks for the quick answer!
Finally found it... That was silly of me

Is it possible to know why you have to change the input?

[hk]

The original message was a part of the Bible. Some members took offense with that, so we changed the message.
Well, you can read that in the first message in the forum for this problem, can't you?

[Junglemath]

This problem statement is so confusing. It's hard to solve a problem when I can't even figure out what is being asked. I suggest the problem statement be heavily edited.

[hk]

You're being asked to decrypt the given message. As answer you must give the sum of the ascii values of the decrypted text.
Easier we can't state it.

[TristenR]

I have decrypted the message and checked the number of characters against the encrypted number of characters and they are equal. I am summing the values of the decrypted characters but im not getting approval for the submission. Java uses Unix but the values in the decrypted message match the ASCII table values. I feel if I can successfully decrypt this I should have no problem summing values lol. I'm not sure what else to do.

[kenbrooker]

Using Java, I was surprised to learn that the
following summing statements
REQUIRED parentheses --

Code: Select all

sum = sum + (array[i]^key1);
sum = sum + (array[i+1]^key2);
sum = sum + (array[i+2]^key3);

[Junglemath]

I'm still having trouble understanding the problem.

What does it mean "the key is repeated cyclically throughout the message" and "as the encryption key consists of three lower case characters"?

As I understand it, each letter was given a number, and that same number is used each time the same letter appears. Now what exactly is a decryption key? If it is supposed to give you the values for every letter, how can it consist of three characters?

This is probably the worst-worded problem of the 714 problems.

[Animus]

As I understand it, each letter was given a number, and that same number is used each time the same letter appears.

No, that would have been encryption via substitution and has nothing to do with the described XOR encryption.

Now what exactly is a decryption key? If it is supposed to give you the values for every letter, how can it consist of three characters?

The encryption key is is a series of (probably different) bytes, in this case of length 3. Which byte is used to XOR the input character does not depend on the value of that character, but only on its position in the text.
There is no separate decryption key, it is the same as the encryption key

What does it mean "the key is repeated cyclically throughout the message" and "as the encryption key consists of three lower case characters"?

The ASCII-value of the first character is XOR-ed with the value of the first encryption byte, the second character with the second byte and the third character with the third byte.
Now, we have used all bytes of the encryption key and reuse it from the beginning. That is the forth character of the input text is XOR-ed with the first byte of the encryption key, the fifth with the second, and so on.
"the encryption key consists of three lower case characters" means that the three bytes of the encryption key contain the ASCII values of three lower case letters.