Problem 059

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
satyres
Posts: 31
Joined: Thu Feb 20, 2014 2:48 pm

Re: Problem 059

Post by satyres »

Solved ! thanks for your help !

aware
Posts: 4
Joined: Sun Dec 28, 2014 11:11 pm

Re: Problem 059

Post by 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.

User avatar
dawghaus4
Posts: 56
Joined: Fri Nov 29, 2013 2:22 am

Re: Problem 059

Post by dawghaus4 »

aware wrote:" 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
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 059

Post by TripleM »

aware wrote: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
Posts: 4
Joined: Sun Dec 28, 2014 11:11 pm

Re: Problem 059

Post by aware »

TripleM wrote:
aware wrote: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.

User avatar
Marcus_Andrews
Administrator
Posts: 1517
Joined: Wed Nov 09, 2011 5:23 pm

Re: Problem 059

Post by Marcus_Andrews »

aware wrote: 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.
Image

User avatar
solarmew
Posts: 42
Joined: Thu Jan 01, 2015 3:52 pm

Re: Problem 059

Post by 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? ....
Image
366541_5799d51e95657e1a227f2cb86bd181de

User avatar
dawghaus4
Posts: 56
Joined: Fri Nov 29, 2013 2:22 am

Re: Problem 059

Post by dawghaus4 »

solarmew wrote: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

User avatar
solarmew
Posts: 42
Joined: Thu Jan 01, 2015 3:52 pm

Re: Problem 059

Post by 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 ....
Image
366541_5799d51e95657e1a227f2cb86bd181de

fefelatornade
Posts: 2
Joined: Tue Jul 16, 2019 10:58 pm

Problem 059

Post by 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
Posts: 40
Joined: Sat Nov 17, 2012 11:32 pm

Re: Input data for Problem 59

Post by 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.
Image

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 059

Post by hk »

Merged with the existing thread for Problem 059.
Image

fefelatornade
Posts: 2
Joined: Tue Jul 16, 2019 10:58 pm

Re: Problem 059

Post by 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?

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 059

Post by 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?
Image

Junglemath
Posts: 54
Joined: Fri Sep 20, 2019 1:25 pm
Location: Minsk

Re: Problem 059

Post by 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.

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 059

Post by 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.
Image

TristenR
Posts: 3
Joined: Wed Apr 08, 2020 6:20 pm

Re: Problem 059

Post by 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.

User avatar
kenbrooker
Posts: 162
Joined: Mon Feb 19, 2018 3:05 am
Location: Northern California, USA

Re: Problem 059

Post by 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);
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

Junglemath
Posts: 54
Joined: Fri Sep 20, 2019 1:25 pm
Location: Minsk

Re: Problem 059

Post by 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.

User avatar
Animus
Administrator
Posts: 1907
Joined: Sat Aug 16, 2014 1:23 pm

Re: Problem 059

Post by Animus »

Junglemath wrote:
Wed May 06, 2020 7:40 am
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.

Post Reply