# Challenge: weak RSA

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
dc4157ab20bd69cf67971e265931b20e35f597186597da5199b8```

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

```-----BEGIN PUBLIC KEY-----
ZmNGcPwhwGe3u/PCV65WlZZqFierEFXxzm29/k+mVOG/gfeX+/aaq+txAicpgjPd
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”

1. Alessio Zennaro says:

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!

```# It computes n such that n % mod = number. The range covers the length in bit from len(number) to precision
def reverseModulus(number,mod,precision):
startLength = len(bin(mod)[2:])
toRet = []

current = len(bin(number)[2:])
while current <= precision:
number = number + mod # to compute mod we subtract, so here we add!
current = len(bin(number)[2:])
if current >= startLength and current <= precision: # if the length in bit is the one we want
toRet.append(number) # we save it

# It computes the cubic root
def cuberoot(x):
y, y1 = None, 2

while y != y1:
y = y1
y3 = y ** 3
d = (2 * y3 + x)
y1 = (y * (y3 + 2 * x) + d // 2) // d

if y * y * y != x: # if it's not a perfect cube
return -1 # we're not dealing with negative numbers so -1 can be use as a flag
else: # if it is a perfect cube we return it (without 0x and L)
toRet = hex(y)[2:]

# We try to print the decrypted string!
def toASCII(hexString):
charList = []
ind = 0

while hexString != "":
ind += 1

currentChar = hexString[len(hexString) - 2:]
hexString = hexString[0:len(hexString) - 2]
charList.append(chr(int(currentChar,16)))

toRet = ""
for item in charList[::-1]:
toRet = toRet + item

candidates = reverseModulus(message,modulus,1032)

for i in range(len(candidates)):
check = cuberoot(candidates[i])
if check != -1:
print toASCII(check)

```

I wish everybody a nice evening (and weekend).

2. Alessio Zennaro says:

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 🙁

3. riccardo says:

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

```root = gmpy.root(cipher,3)
if root != 0: # this is a perfect cube
print root # this is the cube root
```
4. Alessio Zennaro says:

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! 🙂

5. riccardo says:

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.