# PicoCTF 2022

Writeups # Category: Cryptography

## Very Smooth (300 points)

Forget safe primes… Here, we like to live life dangerously… >:)

This challenge is a classic example of the Pollard p-1 algorithm. The Pollard p-1 algorithm is, essentially, an algorithm that is able to factor out a number n if one of it’s factors (p, in this case) is smooth. Smooth numbers are numbers whos prime factors are all less than a certain number (in this case: B).

The gen.py script, upon closer examination, generates p and q by computing prime numbers and multiplying them together. Afterwards, it computes two additional prime numbers and multiplies them with p, basically ensuring that p+1 is a prime number. After p and q are generated through this method, e (public exponent) is checked to see if it is a factor. If not, then p and q are multiplied together to create n, and the rest is standard RSA.

Knowing this, and viewing the script execute with a dummy flag and with Debug set to true, it is evident that the factors of p-1 are all smaller than the number 0xffff, and the factors of q-1 are all smaller than the number 0xfffff. The actual number for q-1 does not matter however, since p-1 was the number we were working with.

Then, with the help of this lovely writeup, I was able to recreate the algorithm in a python script which successfully factored p from n, allowing us to get q by performing `n/p`. With that complete, we can calculate phi(n) and get private exponent d via performing the modular inverse of e mod phi(n).

Decrypt the ciphertext using d, and boom, we have the flag.

### Script

``````from math import factorial, gcd, lcm
from Crypto.Util.number import long_to_bytes, inverse
from tqdm import tqdm

#define the variables
c = 0x671028df2e2d255962dd8685d711e815cbea334115c30ea2005cf193a1b972e275c163de8cfb3d0145a453fec0b837802244ccde0faf832dc3422f56d6a384fbcb3bfd969188d6cd4e1ca5b8bc48beca966f309f52ff3fc3153cccaec90d8477fd24dfedc3d4ae492769a6afefbbf50108594f18963ab06ba82e955cafc54a978dd08971c6bf735b347ac92e50fe8e209c65f946f96bd0f0c909f34e90d67a4d12ebe61743b438ccdbcfdf3a566071ea495daf77e7650f73a7f4509b64b9af2dd8a9e33b6bd863b889a69f903ffef425ea52ba1a293645cbac48875c42220ec0b37051ecc91daaf492abe0aaaf561ffb0c2b093dcdabd7863b1929f0411891f5

#first, define a variable B such that:
#   B!|(p-1)
#   q-1 contains a prime factor > B
B = factorial(0xffff)

#bruteforce a
a = 2
for _ in tqdm(range(0xf6)):
#compute b and increment a for the next iteration
b = pow(a, B, n)
a += 1

#compute GCD(b-1, n) to get p
#if p is 1, then b is invalid and we continue
p = gcd(b-1, n)
if p == 1:
continue

#now that we have P, notify and divide it from N to get Q
print("possibly found p")
q = n//p

#calculate d using phi
phi = lcm(p-1, q-1)
d = inverse(0x10001, phi)

#compute the plaintext and print it
plain = pow(c, d, n)
print(f"Plaintext: {long_to_bytes(plain)}")

#OH MY GOD OH MY GOD OH MY GOD IT WORKED OH MY GOD I WASNT EXPECTING IT TO WORK YESSS
#picoCTF{94287e17}``````