CrossCTF 2018 Final Crypto BabyRSA Write-up

Introduction

I do not understand why the crypto challenge is easier than qual…

Exploit

This challenges gives the following information:

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

Since the phi(n) can be obviously factorised, we factorise it first here[1] and find prime P and Q by iterating over all feasible P-1 and Q-1. In the end, decrypt the message.

The final exploit is given below.

import gmpy2
from gmpy2 import mpz
import itertools
import binascii

def getMultiple(numSet):
    ans = 1;
    for elem in numSet:
        ans = ans * elem;

    return ans;

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

c = 5499541793182458916572235549176816842668241174266452504513113060755436878677967801073969318886578771261808846567771826513941339489235903308596884669082743082338194484742630141310604711117885643229642732544775605225440292634865971099525895746978617397424574658645139588374017720075991171820873126258830306451326541384750806605195470098194462985494;

d = 15664449102383123741256492823637853135125214807384742239549570131336662433268993001893338579081447660916548171028888182200587902832321164315176336792229529488626556438838274357507327295590873540152237706572328731885382033467068457038670389341764040515475556103158917133155868200492242619473451848383350924192696773958592530565397202086200003936447;

print(phi);

numberList = [ 2,2,333600482773,1973804930501,1984419944251,2767687179787,3639128890921,3680247726403,4065711354007,4754509728797 ,6060693342503,6438418759151,6545600536253,6579600728639,6672422609813,6938103821809,7230980905199,7265658595571,8313722160551,9220079755217,9566431650679,2293498615990071511610820895302086940796564989168281123737588839386922876088484808070018553110125686555051];

for L in range(0, len(numberList)+1):
        for subset in itertools.combinations(numberList, L):
            if(len(subset) == 0):
                continue;
            num1 = getMultiple(subset);
            num2 = phi/num1;
            num1 = num1 + 1;
            num2 = num2 + 1;
            if(gmpy2.is_prime(num1) and gmpy2.is_prime(num2)):
                n = num1 * num2;
                m = gmpy2.powmod(c, d, n);
                print(m);
                print(binascii.unhexlify(hex(m)[2:]));

Reference

[1] https://www.alpertron.com.ar/ECM.HTM

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.