Criminals have been storing all information about illegal activities on a password-protected server. They exchange the password encrypted. Here is an intercepted ciphertext:
44d9b36bc73ab46e2c9d446d7776f42ca005ff4052e7218ffae6df3b49c4842a3ad3c6f7159753dce09b227454aea156e03973 c9a4195296bb2506f2578b2c2796f080c8a6f17c99b18646a967146c732d2bf251cab400f4adc2537138cf23a7847cd6c8f0fa dc4157ab20bd69cf67971e265931b20e35f597186597da5199b8
We have managed to find out the public key used for encryption:
-----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?
5 thoughts on “Challenge: weak RSA”
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 🙂
Comments are closed.