Partial Tenacity

3 minutes to read

We are given the Python source code that encrypts the flag:

from secret import FLAG
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

class RSACipher:
    def __init__(self, bits):
        self.key = RSA.generate(bits)
        self.cipher = PKCS1_OAEP.new(self.key)  
    
    def encrypt(self, m):
        return self.cipher.encrypt(m)

    def decrypt(self, c):
        return self.cipher.decrypt(c)

cipher = RSACipher(1024)

enc_flag = cipher.encrypt(FLAG)

with open('output.txt', 'w') as f:
    f.write(f'n = {cipher.key.n}\n')
    f.write(f'ct = {enc_flag.hex()}\n')
    f.write(f'p = {str(cipher.key.p)[::2]}\n')
    f.write(f'q = {str(cipher.key.q)[1::2]}')

We also have the output of the script:

n = 113885866414967666002972488658501581523252563769498903942813659534669192201155190251383326523008134606996199193472232684661637386940661594327513591391999626564784682500337524012474617483098011060289946582371155292302705685943021986766584545105444481270761266224342249010400461266963638157749562695294713843509  
ct = 44a45518f4b49c2985a4e696d6fb48bc94e2e9e10b1b518786ab7205298d47250ae85ef69acd04f5daafdcdeda748eff1510ec8a42f1923dfd1bf893082eb7ebed7ca88441f92c1dac61ca5fdf0e9d968cf8213e2ca0a8e24dbfec2bbd58205c60abceb242025a1e8412a0a92a0ae7dd3d6bb0cde0bf28511376003ae907a52b
p = 169785301867063487293453013833911015973907683687605489113424565682424824172371
q = 02316166678868901218282182600315316354684047272123731927933503134218133661721

Source code analysis

The server uses a standard RSA-OAEP encryption to encrypt the flag. The thing is that we are given some information about the private key (prime numbers $p$ and $q$):

    f.write(f'p = {str(cipher.key.p)[::2]}\n')  
    f.write(f'q = {str(cipher.key.q)[1::2]}')

The above code means that we have some digits of both prime numbers represented as decimal numbers. But they are alternated.

We can express the above as follows:

$$ p = \sum_{i = 0}^{D / 2} {d_p}_i \cdot 10^{2i} \quad + \quad \sum_{i = 0}^{D / 2} {x_p}_i \cdot 10^{2i + 1} $$

$$ q = \sum_{i = 0}^{D / 2} {d_q}_i \cdot 10^{2i + 1} \quad + \quad \sum_{i = 0}^{D / 2} {x_q}_i \cdot 10^{2i} $$

Where $D$ is the number of digits; $d_p$ and $d_q$ are the known digits from $p$ and $q$; and $x_p$ and $x_q$ are the unknown digits of $p$ and $q$.

Solution

Since we know that $n = p \cdot q$, the following condition must hold:

$$ \begin{align} n & = p \cdot q \\ & = \left(\sum_{i = 0}^{D / 2} {d_p}_i \cdot 10^{2i} + \sum_{i = 0}^{D / 2} {x_p}_i \cdot 10^{2i + 1}\right) \cdot \left(\sum_{i = 0}^{D / 2} {d_q}_i \cdot 10^{2i + 1} + \sum_{i = 0}^{D / 2} {x_q}_i \cdot 10^{2i}\right) \end{align} $$

As a result, we can use modulo powers of $10$ to extract each unknown digit, because:

$$ \begin{align} n \mod{10} & = p \cdot q \mod{10} \\ & = {d_p}_0 \cdot {x_q}_0 \mod{10} \end{align} $$

Once we find ${x_q}_0$, we can increase the power of $10$ and find ${x_p}_0$:

$$ \begin{align} n \mod{10^2} & = p \cdot q \mod{10^2} \\ & = \left({x_p}_0 \cdot 10 + {d_p}_0 \right) \cdot \left({d_q}_0 \cdot 10 + {x_p}_0 \right) \mod{10^2} \end{align} $$

Then ${x_q}_1$:

$$ \begin{align} n \mod{10^3} & = p \cdot q \mod{10^3} \\ & = \left({d_p}_1 \cdot 10^2 + {x_p}_0 \cdot 10 + {d_p}_0 \right) \cdot \\ & \qquad \qquad \cdot \left({x_q}_1 \cdot 10^2 + {d_q}_0 \cdot 10 + {x_p}_0 \right) \mod{10^3} \end{align} $$

And so on and so forth until we have all digits of $p$ and $q$.

Implementation

The implementation is quite simple, using a loop and testing if condition matches for $p$ or $q$:

#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

n = 113885866414967666002972488658501581523252563769498903942813659534669192201155190251383326523008134606996199193472232684661637386940661594327513591391999626564784682500337524012474617483098011060289946582371155292302705685943021986766584545105444481270761266224342249010400461266963638157749562695294713843509  
ct = bytes.fromhex('44a45518f4b49c2985a4e696d6fb48bc94e2e9e10b1b518786ab7205298d47250ae85ef69acd04f5daafdcdeda748eff1510ec8a42f1923dfd1bf893082eb7ebed7ca88441f92c1dac61ca5fdf0e9d968cf8213e2ca0a8e24dbfec2bbd58205c60abceb242025a1e8412a0a92a0ae7dd3d6bb0cde0bf28511376003ae907a52b')
p = '169785301867063487293453013833911015973907683687605489113424565682424824172371'
q = '02316166678868901218282182600315316354684047272123731927933503134218133661721'

p_digits = []
q_digits = []

for d in str(p):
    p_digits.append(d)
    p_digits.append('0')

p = int(''.join(p_digits[:-1]))

for d in str(q):
    q_digits.append('0')
    q_digits.append(d)

q_digits.append('0')

q = int(''.join(q_digits))

for i in range(len(q_digits)):
    if i % 2 == 0:
        while n % (10 ** (i + 1)) != (p * q) % (10 ** (i + 1)):
            q += 10 ** i
    else:
        while n % (10 ** (i + 1)) != (p * q) % (10 ** (i + 1)):
            p += 10 ** i

assert p * q == n

e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
cipher = PKCS1_OAEP.new(RSA.construct((n, e, d)))
pt = cipher.decrypt(ct)
print(pt.decode())

We initially set the unknown digits to $0$, so on each iteration, when the condition fails, we add $10^i$ to the value of $p$ or $q$.

Flag

If we run the above script, we will get the flag:

$ python3 solve.py
HTB{RS4_w1th_p0w3rs_0f_10_4s_m0duli}

The full script can be found in here: solve.py.