# Huge (250 pts)¶

## Question:¶

Bigger, Not Better!

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