Huge (250 pts)

Question:

Bigger, Not Better!

Huge2

Write-Up:

Let us first inspect the RSA public key suing OpenSSL:

openssl rsa -pubin -in pubkey.pem -text -noout | grep 'Exponent\|bit'

which outputs:

Public-Key: (18329632 bit)
Exponent: 65537 (0x10001)

So, , and bits. On the other hand, the size of ciphertext (the file enc2.raw) is merely bits (use ls -l, multiply the resulting size by 8 to convert from bytes to bits).

Notice that the ciphertext is considerably smaller than the public modulus of RSA . This shows that plaintext was not padded prior to encryption. Since is so huge, one might guess that , so that modular computations were never used. In other words, it might be the case that rather than . If we find an such that , it is the unique decryption of .

The following Python script tests this idea (note that it uses the GmPy package for fast computations):

#!/usr/bin/env python3

import binascii
import gmpy

e = 65537
FILE = 'enc2.raw'

with open(FILE, "rb") as f:
    s = f.read()

s = binascii.hexlify(s)

num = gmpy.mpz(int(s, 16))
msg = num.root(e)[0]

print(binascii.unhexlify(hex(msg)[2:]))

And voilá! it finds the flag:

SharifCTF{d604a27c3abcbe3e077b98}

Further Notices

Notice 1

Care must be taken when incorporating the above approach: We must make sure that . This can be easily verified by the following code, which prints "True":

#!/usr/bin/env python3

import binascii
import math

SIZE_OF_N_IN_BITS = 18329632
e = 65537
msg = 'SharifCTF{d604a27c3abcbe3e077b98}'.encode('ascii')

m = int(binascii.hexlify(msg), 16)

print(math.ceil(e * math.log(m, 2)) < SIZE_OF_N_IN_BITS)

Notice 2

In this challenge, can be easily factored by hand. The crucial point is that has the form , which is the product of and .

It is easy to find the values for and , and compute the RSA private key. However, the computations required for decrypting is prohibitively slow!

Source Code

  1. Huge_Decrypt.py.
  2. Huge_Verify.py.