# 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
n = 0xe77c4035292375af4c45536b3b35c201daa5db099f90af0e87fedc480450873715cffd53fc8fe5db9ac9960867bd9881e2f0931ffe0cea4399b26107cc6d8d36ab1564c8b95775487100310f11c13c85234709644a1d8616768abe46a8909c932bc548e23c70ffc0091e2ed9a120fe549583b74d7263d94629346051154dad56f2693ad6e101be0e9644a84467121dab1b204dbf21fa39c9bd8583af4e5b7ebd9e02c862c43a426e0750242c30547be70115337ce86990f891f2ad3228feea9e3dcd1266950fa8861411981ce2eebb2901e428cfe81e87e415758bf245f66002c61060b2e1860382b2e6b5d7af0b4a350f0920e6d514eb9eac7f24a933c64a89
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}
```