Very Smooth

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

We’re given two files, gen.py, which was used to encrypt the flag, and output.txt. Here is gen.py with my analysis comments:

1
#!/usr/bin/python
2

3
from binascii import hexlify
4
from gmpy2 import *
5
import math
6
import os
7
import sys
8

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

13
_DEBUG = True
14

15
FLAG  = open('flag.txt').read().strip()
16
FLAG  = mpz(hexlify(FLAG.encode()), 16)
17
SEED  = mpz(hexlify(os.urandom(32)).decode(), 16)
18
STATE = random_state(SEED)
19

20
def get_prime(state, bits):
21
    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))
22

23
# random(0, 2**(bits - 1)), inclusive | 2**(bits - 1) --> random() + 2**(bits - 1)
24
# adds 2**(bits - 1) unless random = 2**(bits - 1)
25
# next prime number greater than above
26
# always less than 2**(bits)
27

28
def get_smooth_prime(state, bits, smoothness=16):
29
    p = mpz(2)
30
    p_factors = [p]
31
    while p.bit_length() < bits - 2 * smoothness: # 992 for p, 990 for q
32
        factor = get_prime(state, smoothness)
33

34
# gets smaller primes for p, larger primes for q
35
# always 2**(smoothness - 1) <= prime < 2**(bits)
36

37
        p_factors.append(factor)
38
        p *= factor
39

40
    bitcnt = (bits - p.bit_length()) // 2 # half of the remaining bits left to get to 1024 bits
41

42
    while True:
43
        prime1 = get_prime(state, bitcnt) # halfway to 1024 bits
44
        prime2 = get_prime(state, bitcnt) # also halfway to 1024 bits
45
        # together they should get to 1024 bits (or at least close)
46
        tmpp = p * prime1 * prime2
47
        if tmpp.bit_length() < bits:
48
            bitcnt += 1
49
            continue
50
        if tmpp.bit_length() > bits:
51
            bitcnt -= 1
52
            continue
53
        # above two if statements make sure that p will be 1024 bits
54
        if is_prime(tmpp + 1):
55
            p_factors.append(prime1)
56
            p_factors.append(prime2)
57
            p = tmpp + 1
58
            break
59

60
    p_factors.sort()
61

62
    return (p, p_factors) # p = all p_factors multiplied and then +1
63

64
e = 0x10001
65

66
while True:
67
    p, p_factors = get_smooth_prime(STATE, 1024, 16) # smoothness = 16
68
    if len(p_factors) != len(set(p_factors)): # if not all distinct primes
69
        continue
70
    # Smoothness should be different or some might encounter issues
71
    q, q_factors = get_smooth_prime(STATE, 1024, 17) # smoothness = 17
72
    if len(q_factors) != len(set(q_factors)):
73
        continue
74
    factors = p_factors + q_factors
75
    if e not in factors: # e can't be in factors
76
        break
77

78
# above while loop results in distinct primes in p_factors, q_factors;
79
# e is not in p_factors or e_factors
80

81
if _DEBUG:
82
    import sys
83
    sys.stderr.write(f'p = {p.digits(16)}\n\n')
84
    sys.stderr.write(f'p_factors = [\n')
85
    for factor in p_factors:
86
        sys.stderr.write(f'    {factor.digits(16)},\n')
87
    sys.stderr.write(f']{len(p_factors)}\n\n')
88

89
    sys.stderr.write(f'q = {q.digits(16)}\n\n')
90
    sys.stderr.write(f'q_factors = [\n')
91
    for factor in q_factors:
92
        sys.stderr.write(f'    {factor.digits(16)},\n')
93
    sys.stderr.write(f']{len(q_factors)}\n\n')
94

95
n = p * q
96

97
m = math.lcm(p - 1, q - 1)
98
d = pow(e, -1, m)
99

100
c = pow(FLAG, e, n)
101

102
print(f'n = {n.digits(16)}')
103
print(f'c = {c.digits(16)}')

After analyzing gen.py, I decided to do some research about what “smooth” numbers were, as that seemed to be what the problem was implying. I found this Wikipedia page about it.

Reading through it, I realized that B-smooth numbers are numbers with no prime factors greater than B. Given my program analysis, I realized that $p-1$ is a $2^{16}$ -smooth number, and $q-1$ is a $2^{17}$ -smooth number. So our problem likely somehow deals with smooth numbers in RSA.

I did a little bit of Googling until I found this article. The title included something called Pollard’s attack, so I searched that up. This time, I found a Columbia University article about Pollard’s attack, which explained how it could be used to break RSA when $p-1$ is a B-smooth number. Now we’re getting somewhere!

At this point, I understood the process. All I needed to do was confirm that this would run in time, given that it seemed like we needed to compute $65537!$ , which would certainly be very large. Thankfully, this program clarified for me that I did not have to in fact compute $65537!$ and that the program would run in time with a worst case time complexity of $O( ( B * log(B) + log(N) ) * log^2(N) )$ .

Therefore, here is the implementation of the solution:

1
from gmpy2 import *
2
import binascii
3

4
n = 'a1355e27e1419c3f129f1db20915bf2a2d8db159b67b55858ccb2fbe4c6f4f8245411928326496b416f389dc88f6f89f1e7dc2f184a4fb5efd40d53c4f578bd4643aea45971c21bde2ddfc6582c2955466cb8f5f2341d11ad3bdcb678efeadd043d203105545d104b1c6bde632fe72e89e37af6c69b8ca3c0d7f1367e3f9967f719e816ff603544530999eda08d28b6390fc9e3c8e0eb7432e9506bf5e638c4f548dd8c6c6c0791915f2e31b4f4114c89036650ebf541fec907017d17062114f6d2008aa641166a27734c936e7cb0f4c9df4ca5c7b57019901cbb4f3d3bbc78befbfb770ca8cbf0f3d9b752d55b81f57379e9a13bd33cf3ee17f131c16db8b21'
5
c = '73d31ba14f88d1343a774e5d4315e1733af382318d7bf99116e5e42f0b11dc9561dfa7eafca3e061504538396fd5e463247596e8524df1c51600644d9ea7e607d5be8f79ef237907616d2ab958debc6bef12bd1c959ed3e4c2b0d7aff8ea74711d49fc6e8d438de536d6dd6eb396587e015289717e2c6ea9951822f46aae4a8aa4fc2902ceeddefd45e67fe6d15a6b182bafe8a254323200c728720bfd2d727cc779172f0848616ed37d467179a6912e8bbeb12524c7ac5cda79eee31b96cc7e36d9d69ef673f3016d0e6f0444b4f9de3d05f9d483ee6c1af479a0ffb96e9efab8098e12c7160fe3e4288364be80633a637353979c3d62376abfc99c635b703c'
6

7
n = int(n, 16)
8
c = int(c, 16)
9

10
'''
11
# Pollard's attack
12
a = 2
13
B = 2**16
14
for i in range(2, B + 1):
15
        if i % 1000 == 999:
16
                print(i)
17
        a = pow(a, i, n)
18

19
        d = gcd(a - 1, n)
20

21
        if 1 < d and d <n:
22
                print('Prime Factorization of', n)
23
                print('(', d, ',', n//d, ')')
24
'''
25
p = 154714566007807784658217453973430067124002427483243197849791456415176834246233278559337287163780143729239757891659989122025191209127201898935320797851763250468612618658207399696173578206890458794774190054174795187906918498063579076533339922893829854809748220803577061068137039229503960574560413271008097993583
26
q = n // p
27
phi = lcm(p - 1, q - 1)
28
e = 0x10001
29
d = pow(e, -1, phi)
30
m = pow(c, d, n)
31
m = format(m, 'x')
32
print(binascii.unhexlify(m))

1
picoCTF{p0ll4rd_f4ct0r1z4at10n_FTW_148cbc0f}