# Very Smooth
Here is the challenge code and Description.
## Description```Forget safe primes... Here, we like to live life dangerously... >:)```
## Challenge code and Output
```py#!/usr/bin/python
from binascii import hexlifyfrom gmpy2 import *import mathimport osimport sys
if sys.version_info < (3, 9):    math.gcd = gcd    math.lcm = lcm
_DEBUG = False
FLAG  = open('flag.txt').read().strip()FLAG  = mpz(hexlify(FLAG.encode()), 16)SEED  = mpz(hexlify(os.urandom(32)).decode(), 16)STATE = random_state(SEED)
def get_prime(state, bits):    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))
def get_smooth_prime(state, bits, smoothness=16):    p = mpz(2)    p_factors = [p]    while p.bit_length() < bits - 2 * smoothness:        factor = get_prime(state, smoothness)        p_factors.append(factor)        p *= factor
    bitcnt = (bits - p.bit_length()) // 2
    while True:        prime1 = get_prime(state, bitcnt)        prime2 = get_prime(state, bitcnt)        tmpp = p * prime1 * prime2        if tmpp.bit_length() < bits:            bitcnt += 1            continue        if tmpp.bit_length() > bits:            bitcnt -= 1            continue        if is_prime(tmpp + 1):            p_factors.append(prime1)            p_factors.append(prime2)            p = tmpp + 1            break
    p_factors.sort()
    return (p, p_factors)
e = 0x10001
while True:    p, p_factors = get_smooth_prime(STATE, 1024, 16)    if len(p_factors) != len(set(p_factors)):        continue    # Smoothness should be different or some might encounter issues.    q, q_factors = get_smooth_prime(STATE, 1024, 17)    if len(q_factors) != len(set(q_factors)):        continue    factors = p_factors + q_factors    if e not in factors:        break
if _DEBUG:    import sys    sys.stderr.write(f'p = {p.digits(16)}\n\n')    sys.stderr.write(f'p_factors = [\n')    for factor in p_factors:        sys.stderr.write(f'    {factor.digits(16)},\n')    sys.stderr.write(f']\n\n')
    sys.stderr.write(f'q = {q.digits(16)}\n\n')    sys.stderr.write(f'q_factors = [\n')    for factor in q_factors:        sys.stderr.write(f'    {factor.digits(16)},\n')    sys.stderr.write(f']\n\n')
n = p * q
m = math.lcm(p - 1, q - 1)d = pow(e, -1, m)
c = pow(FLAG, e, n)
print(f'n = {n.digits(16)}')print(f'c = {c.digits(16)}')```
```n = c5261293c8f9c420bc5291ac0c14e103944b6621bb2595089f1641d85c4dae589f101e0962fe2b25fcf4186fb259cbd88154b75f327d990a76351a03ac0185af4e1a127b708348db59cd4625b40d4e161d17b8ead6944148e9582985bbc6a7eaf9916cb138706ce293232378ebd8f95c3f4db6c8a77a597974848d695d774efae5bd3b32c64c72bcf19d3b181c2046e194212696ec41f0671314f506c27a2ecfd48313e371b0ae731026d6951f6e39dc6592ebd1e60b845253f8cd6b0497f0139e8a16d9e5c446e4a33811f3e8a918c6cd917ca83408b323ce299d1ea9f7e7e1408e724679725688c92ca96b84b0c94ce717a54c470d035764bc0b92f404f1f5c = 1f511af6dd19a480eb16415a54c122d7485de4d933e0aeee6e9b5598a8e338c2b29583aee80c241116bc949980e1310649216c4afa97c212fb3eba87d2b3a428c4cc145136eff7b902c508cb871dcd326332d75b6176a5a551840ba3c76cf4ad6e3fdbba0d031159ef60b59a1c6f4d87d90623e5fe140b9f56a2ebc4c87ee7b708f188742732ff2c09b175f4703960f2c29abccf428b3326d0bd3d737343e699a788398e1a623a8bd13828ef5483c82e19f31dca2a7effe5b1f8dc8a81a5ce873a082016b1f510f712ae2fa58ecdd49ab3a489c8a86e2bb088a85262d791af313b0383a56f14ddbb85cb89fb31f863923377771d3e73788560c9ced7b188ba97```
# Code Analysis
First of all, let's analyze the challenge code.\This section will produce two factors `(p,q)` for key generation.
```pywhile True:    p, p_factors = get_smooth_prime(STATE, 1024, 16)    if len(p_factors) != len(set(p_factors)):        continue    # Smoothness should be different or some might encounter issues.    q, q_factors = get_smooth_prime(STATE, 1024, 17)    if len(q_factors) != len(set(q_factors)):        continue    factors = p_factors + q_factors    if e not in factors:        break```
These 2 functions will generate a prime number with these conditions:1. The `get_smooth_prime(STATE, 1024, 16)` function will generate a `16bit-smooth` number.2. According to this [link](https://en.wikipedia.org/wiki/Smooth_number), an `n-smooth` number is an integer whose prime factors are all less than or equal to n.3. Regarding the above definition, the output of `get_smooth_prime` will be a prime number which `p-1` is a `65536-smooth` number. that means all prime factors of the `p-1` will be less than `65536` and there is also no duplicate factors.4. The `get_smooth_prime(STATE, 1024, 17)` will be called again for the second prime factor `(q)` which `q-1` is a `17bit-smooth` number `(131072-smooth)`
```pydef get_prime(state, bits):    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))
def get_smooth_prime(state, bits, smoothness=16):    p = mpz(2)    p_factors = [p]    while p.bit_length() < bits - 2 * smoothness:        factor = get_prime(state, smoothness)        p_factors.append(factor)        p *= factor
    bitcnt = (bits - p.bit_length()) // 2
    while True:        prime1 = get_prime(state, bitcnt)        prime2 = get_prime(state, bitcnt)        tmpp = p * prime1 * prime2        if tmpp.bit_length() < bits:            bitcnt += 1            continue        if tmpp.bit_length() > bits:            bitcnt -= 1            continue        if is_prime(tmpp + 1):            p_factors.append(prime1)            p_factors.append(prime2)            p = tmpp + 1            break
    p_factors.sort()```
After investigating the overall code, it will generate primes `p,q` which `p-1` and `q-1` are both `16bit and 17bit smooth` numbers which means all of the `p-1` factors are less than `2**16` or `65536` and all of the `q-1` factors are less than `2**17` or `131072`.
Here is the hint picoCTF offered:```Don't look at me... Go ask Mr. Pollard if you need a hint!```
So Let's search `pollard` and `smooth number` keywords
# Solution
We wanna factor `n` and recover `p,q` then `d` and decrypt the ciphertext `c`.\After searching about `pollard` and `smooth number` keywords, I found [Pollard's p−1](https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm) algorithm.\As we see, it's an integer factorization algorithm that can be applied for those numbers whose prime factors(`p-1`) are `power-smooth`\By definition ```Further, m is called B-powersmooth (or B-ultrafriable) if all prime powers p**v dividing m satisfy:
p**v <= B```
Here we can use `Pollard's p − 1` algorithm because our integer `n`'s factor `p` is `65536-powersmooth` and factor `q` is `131072-powersmooth` which satisfies our conditions.
## Pollard's p − 1 Algorithm
Here are the overall steps:
1. select a smoothness bound `B` (we should use 65535)2. choose a random base `a` coprime to `n`3. define `M = factorial(B)`4. compute `g = gcd(a**M - 1, n)`5. if `1 < g < n` then `g` is one of the factors6. if `g == 1` select larger `B` and try again7. if `g == n` select smaller `B` and try again
## Pollard's p − 1 Algorithm's proofLet's see how this algorithm works
### Fermat's Little Theorem
We know that for every prime number `p` and a random number `a` coprime to `p` we can write```a**(p-1) % p = 1ora**(p-1) -1 = p*r```In other words `a**(p-1) - 1` has two factors `p,r` and `p` is prime\We can also multiply `p-1` with `k`:```a**[k*(p-1)] % p = 1ora**[k*(p-1)] -1 = p*s```
### The proofFrom previous equations we can conclude:```gcd(a**[k*(p-1)]-1 = p*s, n) = pB = k*(p-1)gcd((a**B)-1, n) = p```
If we can calculate `B` and choose any integer `a` co-prime to `n`(2 is the best choice), then we can find `p` with `gcd` operation. simple huh?! But how to find `B`\We know that:```B = k*(p-1)p-1 = p1 * p2 * p3 ... * px```And we know that `p-1` is `powesmooth` which means that all factors of `p-1`(`p1, p2, ..., px`) is less than `65536`So if we choose `B=1*2*3*4*...*65535` and calculate that we can assure that `B` has `p` inside its factor and gcd of `a**B - 1` with `n` will result in `p` which is one of the factors. Sounds cool!
## solve codeAfter proving the algorithm, let's code all these steps to find `p,q` and recover private key `d` and decrypt the flag:```pyfrom gmpy2 import facfrom math import gcdfrom Crypto.Util.number import *from sympy import true
n = 0xc5261293c8f9c420bc5291ac0c14e103944b6621bb2595089f1641d85c4dae589f101e0962fe2b25fcf4186fb259cbd88154b75f327d990a76351a03ac0185af4e1a127b708348db59cd4625b40d4e161d17b8ead6944148e9582985bbc6a7eaf9916cb138706ce293232378ebd8f95c3f4db6c8a77a597974848d695d774efae5bd3b32c64c72bcf19d3b181c2046e194212696ec41f0671314f506c27a2ecfd48313e371b0ae731026d6951f6e39dc6592ebd1e60b845253f8cd6b0497f0139e8a16d9e5c446e4a33811f3e8a918c6cd917ca83408b323ce299d1ea9f7e7e1408e724679725688c92ca96b84b0c94ce717a54c470d035764bc0b92f404f1f5c = 0x1f511af6dd19a480eb16415a54c122d7485de4d933e0aeee6e9b5598a8e338c2b29583aee80c241116bc949980e1310649216c4afa97c212fb3eba87d2b3a428c4cc145136eff7b902c508cb871dcd326332d75b6176a5a551840ba3c76cf4ad6e3fdbba0d031159ef60b59a1c6f4d87d90623e5fe140b9f56a2ebc4c87ee7b708f188742732ff2c09b175f4703960f2c29abccf428b3326d0bd3d737343e699a788398e1a623a8bd13828ef5483c82e19f31dca2a7effe5b1f8dc8a81a5ce873a082016b1f510f712ae2fa58ecdd49ab3a489c8a86e2bb088a85262d791af313b0383a56f14ddbb85cb89fb31f863923377771d3e73788560c9ced7b188ba97
a = 2B = 65535
while True:
	b = fac(B)
	tmp1 = n	tmp2 = pow(a, b, n) - 1	gcd_value = gcd(tmp1, tmp2)
	if gcd_value == 1:		B += 1	elif gcd_value == n:		B -= 1	else:		print(f"[+] p factor : {gcd_value}")
		p = gcd_value		q = n // p		e = 0x10001
		print(f"[+] q factor : {q}")
		phi = (p-1)*(q-1)		d = inverse(e, phi)
		m = pow(c, d, n)
		flag = long_to_bytes(m)
		print(flag)
		break
```
After running the above code we recovered `p,q` and decrypted the flag:```bash~/CTF/picoctf2022/Crypto/VerySmooth  python3.9 solve.py[+] p factor : 159652342260602436611264882107764540496206777532515381978886917602247902747922672308128228056532167311635408138845484288179466203049041882723045592330122232567342518194630068422135188545880928509542459095514667379085548962076958641693004621121073173222707331672786582779407036356311260724097659870075337003627[+] q factor : 155886972960664534013041814351782927840465950022742711153704061512767231252254923859358385447688708709761645561788434482490726299524712681978677060822069411804436435368518028882769406676617745559724738774782701625211779174370759988895228070938831967483401953816901269670197361506466713077188578114638897325343b'picoCTF{7c8625a1}'```Here is the flag:```picoCTF{7c8625a1}```
[solution code](https://github.com/KooroshRZ/CTF-Writeups/blob/main/PicoCTF2022/Cryptography/VerySmooth/solve.py)> KouroshRZ for **Evento**