CrossCTF_2018: BabyRSA 3

Category: Crypto Points: 476 Description:

So I heard that you can flip the private and public information for RSA... Creator - prokarius (@prokarius)

Write-up

So we get a file, with the following information inside it,

c = 5499541793182458916572235549176816842668241174266452504513113060755436878677967801073969318886578771261808846567771826513941339489235903308596884669082743082338194484742630141310604711117885643229642732544775605225440292634865971099525895746978617397424574658645139588374017720075991171820873126258830306451326541384750806605195470098194462985494
d = 15664449102383123741256492823637853135125214807384742239549570131336662433268993001893338579081447660916548171028888182200587902832321164315176336792229529488626556438838274357507327295590873540152237706572328731885382033467068457038670389341764040515475556103158917133155868200492242619473451848383350924192696773958592530565397202086200003936447
phi(n) = 25744472610420721576721354142700666534585707423276540379553111662924462766649397845238736588395849560582824664399879219093936415146333463826035714360316647265405615591383999147878527778914526369981160444050742606139799706884875928674153255909145624833489266194817757115584913491575124670523917871310421296173148930930573096639196103714702234087492

Firstly, we see that we have the ciphertext, c, the decryption variable d and the weirdest variable, phi(n). Well, in order to decrypt, we need the classic m = c^d mod n. We have c, d but not n and we all know that n=pq, so we have to get p and q.

Well, we do have some way of working on that, primarily, phi(n) = (p-1) * (q-1), so perhaps we can bruteforce it? We do need the factors of phi(n) but thankfully, we don't have to factorize it ourselves, @prokarius has done a wonderful job of making the challenge easier <3.

Looking the factor up on FactorDB gets us the following factors,

25744472610420721576721354142700666534585707423276540379553111662924462766649397845238736588395849560582824664399879219093936415146333463826035714360316647265405615591383999147878527778914526369981160444050742606139799706884875928674153255909145624833489266194817757115584913491575124670523917871310421296173148930930573096639196103714702234087492 = 2 2 333600482773 1973804930501 1984419944251 2767687179787 3639128890921 3680247726403 4065711354007 4754509728797 6060693342503 6438418759151 6545600536253 6579600728639 6672422609813 6938103821809 7230980905199 7265658595571 8313722160551 9220079755217 9566431650679 * 2293498615990071511610820895302086940796564989168281123737588839386922876088484808070018553110125686555051

Considering that phi(n) is just (p-1) * (q-1), it becomes glaringly obvious that we can just attempt to bruteforce our factors to find (p-1) and (q-1), add 1 to both and see if they are primes.

This is a lot easier to do in script so here's a Python script that grabs a random subset of factors to form p and q, checks if they are prime and move on.

#! /usr/bin/env python3
##
import binascii
import gmpy2
from pwn import *

c = 5499541793182458916572235549176816842668241174266452504513113060755436878677967801073969318886578771261808846567771826513941339489235903308596884669082743082338194484742630141310604711117885643229642732544775605225440292634865971099525895746978617397424574658645139588374017720075991171820873126258830306451326541384750806605195470098194462985494
d = 15664449102383123741256492823637853135125214807384742239549570131336662433268993001893338579081447660916548171028888182200587902832321164315176336792229529488626556438838274357507327295590873540152237706572328731885382033467068457038670389341764040515475556103158917133155868200492242619473451848383350924192696773958592530565397202086200003936447
phi = 25744472610420721576721354142700666534585707423276540379553111662924462766649397845238736588395849560582824664399879219093936415146333463826035714360316647265405615591383999147878527778914526369981160444050742606139799706884875928674153255909145624833489266194817757115584913491575124670523917871310421296173148930930573096639196103714702234087492
factors = [2, 2, 333600482773, 1973804930501, 1984419944251, 2767687179787, 3639128890921,  3680247726403, 4065711354007, 4754509728797, 6060693342503, 6438418759151, 6545600536253, 6579600728639, 6672422609813, 6938103821809, 7230980905199, 7265658595571, 8313722160551, 9220079755217, 9566431650679, 2293498615990071511610820895302086940796564989168281123737588839386922876088484808070018553110125686555051]

with log.progress("CRACKING") as logger:
    for i in range((2**len(factors)) + 1):
        binary = bin(i)[2:]
        binary = "0" * (22 - len(binary)) + binary

        p = q = 1

        for e in range(len(binary)):
            if binary[e] == "1":
                p *= factors[e]
            else:
                q *= factors[e]

        p += 1
        q += 1

        if gmpy2.is_prime(p) and gmpy2.is_prime(q):
            try:
                n = p * q
                m = gmpy2.powmod(c, d, n)
                m = binascii.unhexlify(hex(m)[2:]).decode()
                logger.success(m)
                break
            except:
                pass

        if i % 100000 == 0:
            logger.status(binary)

Capture

Therefore, the flag is CrossCTF{Pub7ic_prIv4te_K3ys_4_R5A_t33ns}slightlylessshittypaddingslightlylessshittypaddingslightlylessshittypaddingslightlylessshittypadding

results matching ""

    No results matching ""