Partial Tenacity

Flag

HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}

Intro

File: source.py

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 have simple RSA algorithm with $n = p \times q$ , where p and q are primes. We receive n completely, but as for p and q, half of the alternating digits are missing.

File: output.txt

n = 118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003
ct = 7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476
p = 151441473357136152985216980397525591305875094288738820699069271674022167902643
q = 15624342005774166525024608067426557093567392652723175301615422384508274269305

So, p and q might have looked like:

p = 1 _ 5 _ 1 _ 4 _ 4 _ ... _ 0 _ 2 _ 6 _ 4 _ 3 _?
q = _ 1 _ 5 _ 6 _ 2 _ 4 ... _ 6 _ 9 _ 3 _ 0 _ 5 _?

Walkthrough

For both the numbers, we can't be sure if the last digit was cut out or not, but we can use bruteforce as there are 4 possibilities only.

Now, to actually find the numbers, I filled the blank spaces with 9's and made the following script to loop over both the number while decreasing the 9's until the product of p and q is just above n.

p = 1 9 5 9 1 9 4 9 4 9 ... 9 0 9 2 9 6 9 4 9 3 
q = 9 1 9 5 9 6 9 2 9 4 ... 9 6 9 9 9 3 9 0 9 5 9

p = 19591949491949793939597919396919592999895929196999890939997959295959991939095989795909994929898979398989290969999909699929791969794909292919697999092969493
q = 91959692949394929090959797949196969592959092949690989096979492969595979099939596979399929695929792939197959390919691959492929398949590989297949296999390959

(defvar n 118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003)

(defvar p 151441473357136152985216980397525591305875094288738820699069271674022167902643)
(defvar q 15624342005774166525024608067426557093567392652723175301615422384508274269305)

(defvar p- 19591949491949793939597919396919592999895929196999890939997959295959991939095989795909994929898979398989290969999909699929791969794909292919697999092969493)
(defvar q- 91959692949394929090959797949196969592959092949690989096979492969595979099939596979399929695929792939197959390919691959492929398949590989297949296999390959)

(defun main ()
  (loop with p = p-
        with q = q-
        for i from 0
        for test = (zerop (mod i 2))
        for index = (- 155 i)
        for expt = (expt 10 index)
        while (>= index 0)
        do (if (not test)
               (loop with q-del = q
                     while (>= (* p q-del) n)
                     do (decf q-del expt)
                     finally (setf q (+ q-del expt)))
               (loop with p-del = p
                     while (>= (* p-del q) n)
                     do (decf p-del expt)
                     finally (setf p (+ p-del expt))))
        ; do (format t "~A : ~A~%" p q)
        finally (return (list p q))))

(main)

(10541549431842783633587614316112542499895727166990860537947158205451961334065983715903944224868775308489240169949600619123741969714205272515647199022167453
 11254692541324720060752707148186767582750062945630785066774422168535575089335596479399029695524722638167959390210621853422825328846580189277644256392390351)

Multiplying these newly found p and q returns original n. So all that's left now to do is to decrypt the original ciphertext.

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

p = 10541549431842783633587614316112542499895727166990860537947158205451961334065983715903944224868775308489240169949600619123741969714205272515647199022167453
q = 11254692541324720060752707148186767582750062945630785066774422168535575089335596479399029695524722638167959390210621853422825328846580189277644256392390351

n = p * q
e = 65537
d = inverse_mod(e, (p - 1) * (q - 1))
# d = 85757724352702431827886972802028468016689575746643928124240678718545284336060719588898832664263673373411636190989027155063891429250014808778398039364210984988405968669946329995864364744572664222825260167476565773916025056718053556306635111840461543208403494163130356069615517642385418555252908998266075992673

key = RSA.construct((n, e, d, p, q))
cipher = PKCS1_OAEP.new(key)
print(cipher.decrypt(bytes.fromhex('7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476')).decode())

HTB{v3r1fy1ng_pr1m3s_m0dul0_p0w3rs_0f_10!}