**Tags:** rsa

Rating:

# The worst RSA joke (Crypto)

In the task we get [public key](public.pem) and [ciphertext](flag.enc).

The description of the task states that someone decided to use a single prime as modulus for RSA encryption.

The difficulty of breaking RSA is based on the fact that the number of co-prime numbers to the modulus (so-called Euler's totient function) is secret.

For a prime number this value is known and is simply `p-1`.

For product of two co-prime numbers it is `(p-1)*(q-1)`, and here is the strength of RSA - in order to calculate this value we need to know prime factors of the modulus, and finding those is hard.

In our case this whole problem doesn't exist, since we know `p` and therefore we know `p-1` as well.

Therefore we can simply calculate the private key exponent as `modinv(e,p-1)` and decrypt the ciphertext.

```python

import codecs

from Crypto.PublicKey import RSA

from crypto_commons.generic import bytes_to_long

from crypto_commons.rsa.rsa_commons import modinv, rsa_printable

def main():

with codecs.open("public.pem", "r") as input_file:

pub = input_file.read()

pub = RSA.importKey(pub)

print(pub.e, pub.n)

with codecs.open("flag.enc", 'r') as input_flag:

data = input_flag.read().decode("base64")

d = modinv(pub.e, pub.n-1)

print(rsa_printable(bytes_to_long(data), d, pub.n))

main()

```

And we get `Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}`

Original writeup (https://github.com/p4-team/ctf/tree/master/2018-03-24-securinets/crypto_worst_rsa).