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.
Junglemath
Posts: 54
Joined: Fri Sep 20, 2019 1:25 pm
Location: Minsk

Re: Problem 059

Post by Junglemath »

Animus wrote:
Wed May 06, 2020 8:11 am
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.
Can you tell me if my understanding of the problem is correct? Consider the following example:

Suppose the original plain text was "HELLO WORLD", and the encryption key I chose was "97, 98, 99", which are the ascii values for a, b, c, respectively. To encrypt the plain text "HELLO WORLD", I would take the ascii value of H, which is 72, convert that to binary which is 1001000, then XOR the binary string using the binary value for 97 (1100010) to get the binary string 0101010, convert that to decimal (42), and finally take the associated ascii character (*) and present that as the encrypted form of H. I would then repeat this until all characters in HELLO WORLD are thus encrypted.

Do I understand the problem correctly?

EDIT: I've since solved this problem. Please my post below.
Last edited by Junglemath on Sat May 23, 2020 8:08 pm, edited 1 time in total.

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

Re: Problem 059

Post by kenbrooker »

By Animus, this is a key to answering your question --
There is no separate decryption key, it is the same as the encryption key
"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 »

kenbrooker wrote:
Fri May 22, 2020 6:59 pm
By Animus, this is a key to answering your question --
There is no separate decryption key, it is the same as the encryption key
Can you tell me if my understanding is correct, as reflected in my previous post? A simple yes or no will suffice.

mdean
Posts: 165
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 059

Post by mdean »

Junglemath wrote:
Fri May 22, 2020 6:25 pm
Can you tell me if my understanding of the problem is correct? Consider the following example:

Suppose the original plain text was "HELLO WORLD", and the encryption key I chose was "97, 98, 99", which are the ascii values for a, b, c, respectively. To encrypt the plain text "HELLO WORLD", I would take the ascii value of H, which is 72, convert that to binary which is 1001000, then XOR the binary string using the binary value for 97 (1100010) to get the binary string 0101010, convert that to decimal (42), and finally take the associated ascii character (*) and present that as the encrypted form of H. I would then repeat this until all characters in HELLO WORLD are thus encrypted.

Do I understand the problem correctly?
Well, according to Windows Calculator the XOR should be 41, which is ")". And you'd repeat with E and b, L and c, L and a, etc.
Image

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

Re: Problem 059

Post by hk »

Many languages have an operator that takes two integers and calculates the bitwise xor of those two integers.
That saves the tedious converting to binary and back.
In many languages that operator is ^. (C and derivatives, Java , Python)
In your case that would be: 72^97 which gives 41.
Image

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

Re: Problem 059

Post by Junglemath »

I finally solved this one. I beseech the moderators to completely overhaul the wording of this problem, because as it is written it might as well be a 50% difficulty problem rather than the 5% at which it is currently listed. Pretty much all the difficulty of this problem lies in figuring out what the problem is even talking about, which really shouldn't be the case. Please and thanks.

User avatar
rayfil
Administrator
Posts: 1405
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 059

Post by rayfil »

Do I understand the problem correctly?
That is hard to tell from your own description. Let's restart using your own data and hk's suggestion.

- First let's "encrypt" your HELLO WORLD with your encryption key 'abc'. Rotating the key for XORing each character of the message, the end result would be an unreadable string of the following 11 bytes:
H^a, E^b, L^c, L^a, O^b, space^c, W^a, O^b, R^c, L^a, D^b

- Your problem would be to find the encrypting key abc to use on those 11 bytes to transform them back into a readable message.
i.e. H^a^a=W, E^b^b=E, L^c^c=L, L^a^a=L, etc, etc.
When you assume something, you risk being wrong half the time.

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

Re: Problem 059

Post by Junglemath »

rayfil wrote:
Sat May 23, 2020 7:19 pm
Do I understand the problem correctly?
That is hard to tell from your own description. Let's restart using your own data and hk's suggestion.

- First let's "encrypt" your HELLO WORLD with your encryption key 'abc'. Rotating the key for XORing each character of the message, the end result would be an unreadable string of the following 11 bytes:
H^a, E^b, L^c, L^a, O^b, space^c, W^a, O^b, R^c, L^a, D^b

- Your problem would be to find the encrypting key abc to use on those 11 bytes to transform them back into a readable message.
i.e. H^a^a=W, E^b^b=E, L^c^c=L, L^a^a=L, etc, etc.
Thanks, but I've since solved the problem. See my post afterwards.

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

Re: Problem 059

Post by TristenR »

I have decrypted the message and have checked to make sure there are no other possibilities. I have made the program write out the decrypted characters next to their ascii values and it all checks out. I have used a for each loop to sum all the decrypted ascii values and I'm still being told it is wrong. I have "solved" this problem but cannot enter the right solution. Is there anyone I can contact that can help me resolve this? I wont post the decrypted message but I'd certainly be willing to share it with an administrator as proof who already knows the answer, or atleast compare decrypted values.

skoczian
Posts: 4
Joined: Sat May 25, 2013 4:43 pm

Re: Problem 059

Post by skoczian »

The answer by kenbrooker to your first question didn't help? Then how about the data type you use for the decrypted values and for the sum? Could you get an overflow?

When you say you checked the number of characters against the encrypted number of characters: did you check against the original file?

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

Re: Problem 059

Post by TristenR »

I'm using long as the data type but could use int since int goes up to ~ 2 million and the answer will not be that high at all. The original text has 1455 entries which i put into a list of equal length. Once I decrypt it, it still has the same length(I've made sure) and it's straight forward from there but my answer is still getting rejected. As for your mention of Kenbrooker, I've already decrypted the list so I dont have to worry about the sum and XOR combination he used. I made the program print the sum every step of the way with the corresponding decoded character and its ascii value side by side, and it all lines up. I even casted the numbers 32-126 to char to make sure they are all correct with the ascii table in java.

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

Re: Problem 059

Post by hk »

Tristen's problem solved, no need for further reactions.
Image

Post Reply