Criminals have been storing all information about illegal activities on a password-protected server. They exchange the password encrypted. Here is an intercepted ciphertext:

1 2 3 |
44d9b36bc73ab46e2c9d446d7776f42ca005ff4052e7218ffae6df3b49c4842a3ad3c6f7159753dce09b227454aea156e03973 c9a4195296bb2506f2578b2c2796f080c8a6f17c99b18646a967146c732d2bf251cab400f4adc2537138cf23a7847cd6c8f0fa dc4157ab20bd69cf67971e265931b20e35f597186597da5199b8 |

We have managed to find out the public key used for encryption:

1 2 3 4 5 6 |
-----BEGIN PUBLIC KEY----- MIGdMA0GCSqGSIb3DQEBAQUAA4GLADCBhwKBgQDbAw2yUWQh0BtIoAXmGREYtcvN ZmNGcPwhwGe3u/PCV65WlZZqFierEFXxzm29/k+mVOG/gfeX+/aaq+txAicpgjPd ctUdQp8ydZ7ESQLCqzna9qt1paKKw02Hkh1U6WrcMaNolHlEb8GhcbpN+n3xaDx5 SB5dRxc41lXAQlnC+wIBAw== -----END PUBLIC KEY----- |

Rumors say the encrypted message is only 43 bytes long. Finding the encrypted password is of ultimately importance. Can you help us?

Hi everybody!

I’ve been able to find the password! 😀

First of all I used OpenSSL to get the public exponent and the modulus starting from the key in PEM format. I immediately noticed that the modulus is 1024 bits long but the public exponent is 3. Given that the message is only 43 bytes long I guessed that this challenge could be won with a small exponent attack!

The ciphertext is 1023 bits long and initially I got fooled by the math: if the plaintext was made of 341 bits (43 characters, the first char with the three most significant bits set to 0), once raised to the 3rd i’d have got a result of 1023 bits… That would have meant that the mod didn’t change the result of exponentiation… But trying to compute the cubic root I immediately noticed that it wasn’t a perfect cube!

So the mod actually took place!

The maximum amount of bits of plaintext raised to the 3rd is 43 * 8 * 3 = 1032. So it means 8 bits (1 byte) more than the length of the modulus…

The easiest way to compute a % b is to subtract b from a as long as a > b. When a < b then a is the result! So i tried to reverse this process by adding the modulus to the ciphertext and I took into account all the results a number of bits in the range [1024:1032]. I found 298 possible results.

On the internet I found a rather efficient algorithm to compute the cubic root and I adapted it to be used. This algorithm found that only 1 number out 298 is a perfect cube and once computed I tried to print it as a normal string made of ASCII chars…

The result is this: password = 55a2b5543421fe8cccb01aa020f4a1bc

All the computation has been done with a Python (I followed Prof. Riccardo's suggestion 😉 ) program written by me.

The following is the code (which is perfectly working). Modulus and message are hardcoded!

I wish everybody a nice evening (and weekend).

Oh no, what happened??

I used the tags to write the source code (as usual) but everything is messed up!! The indentations are gone! 🙁

Sorry but I don’t know why it’s happened 🙁

Alessio, I’ve fixed the source code. Very good!

One minor note: in python you have functions to convert from hex to ascii and viceversa. Here you can replace toASCII(check) with check.decode(‘hex’) (encode does the other conversion)

I like the idea of reusing code for the cube root. There’s also a very powerful library for math: gmpy (a python interface to GMP). You have to install it. There you have gmpy.root that already tells you if the number is a perfect cube. For example

Thank you for the advice! 🙂

I suspected there was a standard function to convert from hex to ASCII, but it was rather late so I didn’t google for it and I wrote the algorithm. :p

Obviously using the decode method is way better!

I installed the gmpy (2) library but I think that it doesn’t work very well on my computer since it is a MacOS X and I read that gmpy has some troubles with the Mac environment… In fact I tried to use your code but the root method does not return an array but a floating point value… I’ll try to understand what’s wrong! 🙂

Thank you so much for all the hints! 🙂

Ah yes gmpy is not obvious to install on MAC. If you succeed let me know 🙂