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
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”

  1. 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
    
        return toRet
    
    # 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:]
            return toRet[0:len(toRet) - 1]
    
    # 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
    
        return toRet
    
    
    message = 0x44d9b36bc73ab46e2c9d446d7776f42ca005ff4052e7218ffae6df3b49c4842a3ad3c6f7159753dce09b227454aea156e03973c9a4195296bb2506f2578b2c2796f080c8a6f17c99b18646a967146c732d2bf251cab400f4adc2537138cf23a7847cd6c8f0fadc4157ab20bd69cf67971e265931b20e35f597186597da5199b8
    modulus = 0x00db030db2516421d01b48a005e6191118b5cbcd66634670fc21c067b7bbf3c257ae5695966a1627ab1055f1ce6dbdfe4fa654e1bf81f797fbf69aabeb710227298233dd72d51d429f32759ec44902c2ab39daf6ab75a5a28ac34d87921d54e96adc31a3689479446fc1a171ba4dfa7df1683c79481e5d471738d655c04259c2fb
    
    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. 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. 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[1] != 0: # this is a perfect cube
            print root[0] # this is the cube root
    
  4. 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! 🙂

Comments are closed.