Tags: cryptography factoring rsa

Rating:

# 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 hexlify
from gmpy2 import *
import math
import os
import sys

if sys.version_info < (3, 9):
math.gcd = gcd
math.lcm = lcm

_DEBUG = False

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)}')





# Code Analysis

First of all, let's analyze the challenge code.\
This section will produce two factors (p,q) for key generation.

py
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


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)

py
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()


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 factors
6. if g == 1 select larger B and try again
7. if g == n select smaller B and try again

## Pollard's p − 1 Algorithm's proof
Let'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 = 1
or
a**(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 = 1
or
a**[k*(p-1)] -1 = p*s


### The proof
From previous equations we can conclude:

gcd(a**[k*(p-1)]-1 = p*s, n) = p
B = 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 code
After proving the algorithm, let's code all these steps to find p,q and recover private key d and decrypt the flag:
py
from gmpy2 import fac
from math import gcd
from Crypto.Util.number import *
from sympy import true

a = 2
B = 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 : 155886972960664534013041814351782927840465950022742711153704061512767231252254923859358385447688708709761645561788434482490726299524712681978677060822069411804436435368518028882769406676617745559724738774782701625211779174370759988895228070938831967483401953816901269670197361506466713077188578114638897325343
b'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**

Original writeup (https://kooroshrz.github.io/CTF-Writeups/PicoCTF2022/Cryptography/VerySmooth/).