Tags: easy rsa

Rating: 5.0

# Mind your Ps and Qs

Category: Cryptography

AUTHOR: SARA

## Description

In RSA, a small e value can be problematic, but what about N? Can you decrypt this?


## Values

We have been given the following values:

Decrypt my super sick RSA:
c: 843044897663847841476319711639772861390329326681532977209935413827620909782846667
n: 1422450808944701344261903748621562998784243662042303391362692043823716783771691667
e: 65537

C is the ciphertext we wish to decode. N is the result of multiplying two prime numbers p and q, ie. n = p * q. E is the multiplicative inverse of a private exponent d modulo phi. Phi is equal to (p-1)*(q-1). Here in a more ordered fashion:

C = ciphertext
p and q = prime numbers
n = p * q
phi = (p-1) * (q-1)
e = some number that 1 < e < phi and gcd(e,phi) == 1
d = e^(-1) mod phi

Great! Now we just need to find p and q...

## Factor db

[Factordb](http://factordb.com/) is a database of factorised numbers. We could try out n:

n = 2159947535959146091116171018558446546179 * 658558036833541874645521278345168572231473

Awesome! Now we can just calculate.

## Solving

py
from Crypto.Util.number import inverse, long_to_bytes

c = 843044897663847841476319711639772861390329326681532977209935413827620909782846667
n = 1422450808944701344261903748621562998784243662042303391362692043823716783771691667
e = 65537
p = 2159947535959146091116171018558446546179
q = 658558036833541874645521278345168572231473

phi = (p-1)*(q-1)

d = inverse(e, phi)

m = pow(c,d,n)

print(long_to_bytes(m))

bash
python3 solve.py
b'picoCTF{sma11_N_n0_g0od_00264570}'

There we go!