AdventOfCTF 2024 Day 9: resa?

Day 9: resa?

Elf Theodred: Hey, I’m testing out a new… You: What? You lost me at “Hey, I’m testing.” Elf Theodred: What I said was, I encrypted… and missing q. You: Resa? Vesa? Are we talking about monitors or cybersecurity? And what’s this about a missing e and q? Is that supposed to be a type of screw? Huh? Elf Theodred: I’m not repeating myself to an intern. Figure it out, bud. And if you heard a word I said, it’s under 50.

We are given three values: n, p, and c. This is a simple RSA problem.

• n: Public key modulus: the result of p*q.
• p: A large prime number.
• c: The encrypted ciphertext.

To decrypt RSA, we need the private key, d, which relies on knowing p, q, and e. So, we’re missing two values. Luckily, we have n and p, which means we can compute q by doing q = n // p. Then, we just need to figure out e, which is (usually) 65537, but in this case, they mention “under 50”, so we can bruteforce it.

import math
from Crypto.Util.number import long_to_bytes
 
n = 14796477939003611775208041290348339020936676002454717224646251311708293201469184897483873509941865693809473126459329421641681364023167948749968330703736720102973359063469333188059740821023029754734348790951000190344725434181826714146206341535759458897968330526467533482043059528899390103382667493810391462225262830839080650123020531330437922519352683752900562956790917167821286707566070945501977829889638290916396721583750493508694371199246172248676755456956867908139894047255712093824958695471469193986023590431653571458714419577768587744910333974014399293363573408883808909700956297360313208260851637982241566005049
p = 95035264145462998106373959950852388512916398417336694051973007035267892127571038290551358518210018988802168144062568058000141570285306734135476955708641860308084865175837570650537276267265396611644179740194499506782555051319215145789689879081854479885459274078337276115880870922739027746148771680782305865397
c = 7834381455537086069556470828674580173937271064256312815617230923582264273260067511896680320170885743343862894164014864043792487985706669274975353978277862462944814782646749746217479200710773218743409525658958249817055354592575831865920206596021699022326281524908299055420849742148757177093582285192053105592180465511200588277457610702671508363048935552446809692594715753573724603294565113603946429767347234628199252177612170759392617992009035004668823723769453952068616628571785811538463850603629779083508146990944772896050051747702814005551146368404685501836088557927084895438654990821206561992369510510301944786242
 
# Calculate q
q = n // p
 
# Calculate phi
phi = (p - 1) * (q - 1)
 
# Bruteforce e
for e in range(2, 50):
    if math.gcd(e, phi) == 1:
        print(f"e: {e}")
        d = pow(e, -1, phi)
        m = pow(c, d, n)
        decrypted = long_to_bytes(m)
        if "csd" in str(decrypted):
            print(decrypted)
            break

csd{V3sA_R3sa_RSa?_1D3k}