Multicast

Multicast

"Furthermore, I consider that Carthage RSA must be destroyed!"

nc multicast.ecsc23.hack.cert.pl 5002

import os

from Crypto.Util.number import getPrime, bytes_to_long


def pad(data, bitsize):
    missing = (bitsize - len(data) * 8) // 8
    return os.urandom(missing // 2) + data + os.urandom(missing // 2)


def main():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    e1 = getPrime(32)
    e2 = getPrime(32)
    assert p != q
    assert e1 != e2

    m = bytes_to_long(pad(open("flag.txt", 'rb').read(), 2047))
    c1 = pow(m, e1, N)
    c2 = pow(m, e2, N)
    print(f'N = {N}')
    print(f'e1 = {e1}')
    print(f'e2 = {e2}')
    print(f'c1 = {c1}')
    print(f'c2 = {c2}')


main()

Solution

A solution to this exact task can be found online by looking for ways to crack RSA used with 2 different expontents, e.g. here. A script to decrypt the ciphertexts might look like this:

from Crypto.Util.number import long_to_bytes


def egcd(a, b):
    if a == 0 :
        return b, 0, 1

    gcd, x1, y1 = egcd(b % a, a)

    x = y1 - (b // a) * x1
    y = x1
     
    return gcd, x, y


N = 16801413151908283487791189663329493578012846628030868572561945401556114933848884063131893167626726380563946554240309029863739130427168639757567754241602226448391570370954874754714097679345228987490063695179379495149211669754252276084888210751383802717621354571816121757468518387307219970098013043749995525353151245711525962260254819700263677950895160081894668822813785159297542655250020135009445396141034383696934541429556539491286972911589628257124903611948942649403228001959071679930046055144327735896064233938505913729042636979130723252486740790114550157308696012595641166400835179544902984053811641511733064338259
e1 = 3136791673
e2 = 3573222353
c1 = 16481631224743323819675532542258362703058461981079654559076325651915387924248703763417709311950331908263151437721162315099196280466775768219212299626343121681300915319626627740608633494756310317998929967902496926397863882213791496785729116454992695253826344129315607732093166563793274797563810551294845185732671924894343906271189426878621354275900038367669905726267405070110837298645675754495877198207438321773882738460997430691411675093559670446237498983948273151963484505347040999006538841941390306926161545225334774232600377100101038987771343126360422783370773149023051458396189310267944402653227967893339574477298
c2 = 2544467819691556225164177270554250748471343930378051361390193261209036900357164884392411218087197639023395712153187686000803329169907955493451873445508291514372551132088270210928017598314958938879455429694066912681640151605024343190805276429629145311456287066439059616266669824822411858685968605377220795952022617438728802243517224601929778382795924004169326230299097517845783398314450390488351695811834314630670279910729755612170815074902017207304013895912734640514597786806405214652937912325749725198532228887946534313863040394317507345214735423786619742214949413576976590907445400444195768716887195020807468427363

_, a, b = egcd(e1, e2)

if a < 0:
	a = -a
	c1 = pow(c1, -1, N)
elif b < 0:
	b = -b
	c2 = pow(c2, -1, N)

m = long_to_bytes((pow(c1, a, N) * pow(c2, b, N)) % N)
start = m.find(b'ecsc')
end = m.find(b'}', start) + 1
print(m[start:end].decode('utf-8'))

Flag

ecsc23{every_ctf_needs_some_rsa_breaking_challenge}