ctf-writeups

Somkracht 65537

Challenge:

from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)
N = p*q

e = 65537

msg = bytes_to_long(b"flag{dummy_flag}")

ct1 = pow(msg, e, N)
ct2 = pow(msg, p+q, N)

print(f"{N = }")
print(f"{ct1 = }")
print(f"{ct2 = }")

"""
N = 13172635138210286640933237746072073728198869440440273861514688422430115450596963502627269613634657978751692320585777768877613321668778514462972611542147278205792418292362109100597755668571861738781190210255903465162483813897653948305531342676537057130369323555420200545974179860718822410192595079238246216026529376260568656408216009127973127738250617629330070723654601189310430802429585919291621479622419163092371272056180409609142738265178224163465585013019636286435078812898907472859171136422659050412212315590509027225331104292443193693974638004592849794819591007103879538185323581422819852185166422985403024630123
ct1 = 8499526321488266762028127474977263983474334713646962923180757984708039537289636737028409522654349845032612940144246996001396064450188534247830979105036627472087587636695469693411422088223080856169980341928057477564688506588678465277896123712776169270866525885072607021419929184184301722442524104467963680432737243478200661224741027413690099507128782156810842444314483076587935222998920241102484844741597333281611874849648935849985954902264102662618041817365284648356127737145896858259709819593359264714426125676691235985164360773645489923563993927995838346085066937602961724919392025887999986486672200850129835569774
ct2 = 2263178005282615069738169250508811825030372342139636879043114251227029802177975391784856426659871916802959302578620910469427367218786299839311310420522660987052055310279591316813828952756984548230575321772825193775083404279028090110850848262192595930920326368607665856808251531130234210906413358662814500632504899088517752958423466186872534450108628371006268110210630017230741670440780982809417986017372337888735465439382827207990030719121834402226087906249993820193417658352914727984318783025375497623944699995700474418221251293446038111913247755996471673024017921092527032486774115935601292346440934530921157935322
"""

Math:

• Known:
  • $N = p * q$
  • $e = 65537$
  • $ct1 = msg ^ e \bmod N$
  • $ct2 = msg ^ {p + q} \bmod N$
  • $msg^{(p-1)(q-1)} \bmod N = 1$
• Simplify:
  • $msg^{pq-p-q+1} \bmod N = 1$
  • $msg^{p+q} \bmod N = ct2$
  • $msg^{pq+1} \bmod N = ct2$
  • $msg^{N+1} \bmod N = ct2$
• Solve:
  • Find $x, y$ such that $65537x + (N + 1)y = 1$ using extended euclid
  • Compute $ct1^x ct2^y \bmod N = msg^{65537x + (N+1)y} \bmod N = msg \bmod N$

Code generated by DeepSeek:

from Cryptodome.Util.number import inverse, long_to_bytes

def extended_gcd(a, b):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

N = 13172635138210286640933237746072073728198869440440273861514688422430115450596963502627269613634657978751692320585777768877613321668778514462972611542147278205792418292362109100597755668571861738781190210255903465162483813897653948305531342676537057130369323555420200545974179860718822410192595079238246216026529376260568656408216009127973127738250617629330070723654601189310430802429585919291621479622419163092371272056180409609142738265178224163465585013019636286435078812898907472859171136422659050412212315590509027225331104292443193693974638004592849794819591007103879538185323581422819852185166422985403024630123
ct1 = 8499526321488266762028127474977263983474334713646962923180757984708039537289636737028409522654349845032612940144246996001396064450188534247830979105036627472087587636695469693411422088223080856169980341928057477564688506588678465277896123712776169270866525885072607021419929184184301722442524104467963680432737243478200661224741027413690099507128782156810842444314483076587935222998920241102484844741597333281611874849648935849985954902264102662618041817365284648356127737145896858259709819593359264714426125676691235985164360773645489923563993927995838346085066937602961724919392025887999986486672200850129835569774
ct2 = 2263178005282615069738169250508811825030372342139636879043114251227029802177975391784856426659871916802959302578620910469427367218786299839311310420522660987052055310279591316813828952756984548230575321772825193775083404279028090110850848262192595930920326368607665856808251531130234210906413358662814500632504899088517752958423466186872534450108628371006268110210630017230741670440780982809417986017372337888735465439382827207990030719121834402226087906249993820193417658352914727984318783025375497623944699995700474418221251293446038111913247755996471673024017921092527032486774115935601292346440934530921157935322

e = 65537
a = e
b = N + 1

g, x0, y0 = extended_gcd(a, b)

if g != 1:
    print("gcd(e, N+1) is not 1, exiting...")
    exit()

if x0 < 0:
    base1 = inverse(ct1, N)
    exp1 = -x0
else:
    base1 = ct1
    exp1 = x0

if y0 < 0:
    base2 = inverse(ct2, N)
    exp2 = -y0
else:
    base2 = ct2
    exp2 = y0

part1 = pow(base1, exp1, N)
part2 = pow(base2, exp2, N)

m = (part1 * part2) % N
flag = long_to_bytes(m)
print(flag)

Solved!