../

DeFUNct Ransomware

Cryptography

Santa got infected by a ransomware! His elves managed to extract the public key, but couldn’t break it. Help Santa decrypt his memos and save Christmas!

memos.enc

key.txt

Solution

This is a RSA challenge with given N and e in key.txt and ciphertext in memos.enc.

Lookup the N at factordb.com, and you get the two factors for P and Q. It turned out that the N is squared, so here is the solution script with the actual values:

import math
import codecs

def getModInverse(a, m):
    if math.gcd(a, m) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m

    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (
            u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m


n = 28205840949042550050375060175461550675872057306348525019794792025366267703366963350546190265683480293098224696154769777214758340593627880393290492256281553041775628653782036383202053381983191251113155877395626529862597348058155103738470894969594639420282288681892698451569124061054300200195467048229965431939824291564665303806612842827502575604907691109328004173882904743841936884481372112188484896463926548203220470155459957143424820371692190920143729796065820774139710837841351475943323350906653365111266390215568742675559933299828725457523167767855271316604868298940471505320328500540335136652731375589653582517367
p = 167945946509710528501147140850136444757936485900233494350920365296618466491038783888459340376962572176658471433672446105042569166930066764067458760954444542315723029727275896055594485064790247910216515269672809063208736956951590237500845779868099616110730494457247861971337900144361732424961936041908032639503
q = 167945946509710528501147140850136444757936485900233494350920365296618466491038783888459340376962572176658471433672446105042569166930066764067458760954444551181379291048040552484392012079612125237961930510490682072102514499883651342766510399652317335461788686135874608722851478273373669551946245262568601067289
e = 13337

c = int('8f14c50f968c43fe3d40ce2692b95fb4e94c17a5dda5eee162fde77a3d0ceb7012a8b367a134194f2d3975def1adfef62657ad456fa527614218c06debaa9348011f3456fa276080e8630f2cbc806273452f4991fd269b97ca158f0264d16f1c76083f3444c6f866b5dcadebddb0687a63a9836380f750be41d423fb07dd595201af564d592a4bf4c2abac822e7d4380a5f795c022a9b2d22d43c129a159d0c5f1b957df94321e10df7c50af3f1dea36808bfa5f164a6a9a65dddee13133fe19ece35f75a969b0f8cff773c32f97cb99e759a6c5f6560c44f0bf6170b4b56c2663ca0d352cf3bb424ee059d375c78fd1ea623c44aaf307bad822f48b8ff881e27c49219d821edadd9e5de82ce9f2ff2eddf76d006adbf16a25e957b692db7c1fe40a2b2d8836039d499893c20aff7d550680c7d3d6bbe0f79dc51676215f1271d7f04ab756ae990f80e1225637ddf5c090a8c446a3a01e3c96368e2ae6b1509e22a6a8c1cf8e120b0c221eeb8fb088460b9177dc52804149504620ecb1c966d44bb6c29eb3c4a4106c486dc9da1562092dc82786628650aea5726f0742d61a40be1a7eb998450a4936bc0d99e3655735532f61c2589c535a77e10a3ae0bea0d8a01aad62e10765190593b2e09f13a6d5bc73b36a5f822542f37115ece855d087232a6d4198b7d1dbdfedf71516199fd5694a1d24993156263f0cb3fb574e491f', 16)

phi = (p - 1) * (q - 1)
d = getModInverse(e, phi)
m = pow(c, d, n)

print(codecs.decode(hex(m)[2:], 'hex'))

flag: X-MAS{yakuhito_should_n0t_b3_0n_th3_n@ughty_l1st_941282a75d89e080}