# 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, $e = 65537$, and $|n| = 18,329,632$ bits. On the other hand, the size of ciphertext (the file enc2.raw) is merely $17,195,744$ bits (use ls -l, multiply the resulting size by 8 to convert from bytes to bits).

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

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 = 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 $m^e < n$. 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, $n$ can be easily factored by hand. The crucial point is that $n$ has the form $2^a x + 2^b y + 1$, which is the product of $p=2^c w + 1$ and $q=2^d z + 1$.

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