Month: April 2021

Project Euler – Powers of Two

~ frededison ~ Leave a comment

Problem 686 has a bit of a cryptic explanation:

Maybe that’s done on purpose because the math behind the challenge is not very complicated. But I’ll get back to that in a minute.

Problem 686 is all about the powers of two:

21 = 2
22 = 4
23 = 8
24 = 16
…

Some of these powers will start with “123…” For example 290 = 1.23794003928538e27.
This is actually the first power of two having that exact property.

Unfortunately, it is not the first number you have to find, but the 678919th one.
And just calculating powers of two is definitely not an option. So, what’s the “trick” here?

If I had payed closer attention to my calculator, I would have been on track right from the start.
As my binary friend does not show me a big number like 1237940039285… but 1.23794003928538e27 instead.
A base of 1.23 is small enough to handle. I just have to figure out how to deal with the exponential part.

If I just had…

In the end I was stuck on some “pattern” I discovered regarding the rise of the exponent, and had to ask on math.stackexchange.com for help. Just waiting to get insulted for my sheer stupidity and lack of basic math skills.

Instead, I received two very nice responses, which you can find here.

The coding itself was just a couple of lines.

So, what are the key lessons learned?

1. Keep reading the problem and play with the given examples. You will figure it out!
2. When dealing with large numbers, listen to your calculator. It tells you perfectly how to handle them.
3. Don’t be shy, just ask for help.You will actually learn something. Otherwise you might be stuck forever.

Project Euler – XOR decryption

~ frededison ~ Leave a comment

Welcome to Project Euler’s Problem 59, a decryption challenge.

This is a sample of the encrypted text:

Hard to imagine that I have spent two and a half years with a data encryption company not having any idea on how to crack it?

Even more embarrassing, I posted the problem on my Instagram story and received a screenshot of the correct answer roughly two hours later by a friend who is still working professionally in the field of data security and endpoint protection.

So, how did I solve it? First on reading up on the basics of XOR decryption. Which I didn’t need at all in the end. But at least I did learn something new.

Let’s have a look at a very simple XOR encryption, as given in the problem’s description.

65 XOR 42 = 107. How comes?

ASCII 65 is a capital “A” or 1000001 in binary. 42 is an “*”. In binary it is represented by 0101010.
So…

1000001
0101010
XOR
1101011

The XOR-table (exclusive OR) is simple.
0 and 0 become 0.
0 and 1 become 1.
1 and 0 become 1.
1 and 1 become 0.

That’s all there is to know.

Therefore, 1000001 XOR 0101010 = 1101011 (107, “k”).

The good thing about modern programming languages like Java is that XOR is a built-in operator, ^.
For example 65 ^ 42 = 107. There is absolutely no need to shift any bits around.

Next, I did look up some decryption strategies online. Usually the key length is not known, and one has to figure it out first. Luckily, this is not the case for Problem 59. The key length of 3 is given. Also, the information that it consists of lower case characters only.

Once I understood what is meant by “the key is repeated cyclically throughout the message”, I divided the encrypted text into three blocks. Block one: blue. Block 2: red. Block 3: green.

Behause that’s how the text is encrypted, assuming that the key is “abc”:

For each block I found out which ASCII number occurs most often.

Next, I assumed that this number represents the most common letter in the English language, which is “e”.
A faulty assumption by the way. By reading a bit more about the problem, it occurred to me that the most common character in the text is not an “e” but actually a “SPACE”.

The rest was easy. I XORed each of the three numbers with a SPACE, which gave me three lower case characters.

Next, I pasted the encrypted text into an online tool and provided a guess of the key based on those three characters. The decryption process returned an English text instantaneously.

All that was left was to convert the resulting text back to ASCII codes and calculate their sum. Done!