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}