Skip to content

Instantly share code, notes, and snippets.

@mcieno
Last active March 15, 2020 12:01
Show Gist options
  • Save mcieno/94ee5af6305fd390bfd57bd2fdf9bc2f to your computer and use it in GitHub Desktop.
Save mcieno/94ee5af6305fd390bfd57bd2fdf9bc2f to your computer and use it in GitHub Desktop.
X-MAS CTF 2018 - Writeup of Hanukkah
#!/usr/bin/env python3
def xgcd(a, b):
x0, x1, y0, y1 = 0, 1, 1, 0
while a != 0:
(q, a), b = divmod(b, a), a
y0, y1 = y1, y0 - q * y1
x0, x1 = x1, x0 - q * x1
return b, x0, y0
def rabin_decrypt(m, p, q):
n = p * q
# Fast sqrt calculation is possible when p % 4 = 3 and q % 4 = 3
if p % 4 == q % 4 == 3:
mp = pow(m, (p + 1) // 4, p)
mq = pow(m, (q + 1) // 4, q)
else:
raise Exception('p or q are NOT congruent to 3 (mod 4)')
gcd, yp, yq = xgcd(p, q)
assert (yp * p + yq * q) == 1
# Calculate the 4 possible plaintexts
x = (yp * p * mq + yq * q * mp) % n
y = (yp * p * mq - yq * q * mp) % n
return [x, n - x, y, n - y]
flag_enc = 66888784942083126019153811303159234927089875142104191133776750131159613684832139811204509826271372659492496969532819836891353636503721323922652625216288408158698171649305982910480306402937468863367546112783793370786163668258764837887181566893024918981141432949849964495587061024927468880779183895047695332465
p = 10091467095486219386412925657038008994079750950818412327803970543226016138203830244281982855685318564926478052110051579561412412195187526673196657177343851
q = 57184980207755243189673245389882050966451922054637669857555833078280758116488758040722202677901531011185810382486226074211480927769032477693263422201893659
for flag in map(lambda x: x.to_bytes(2 * p.bit_length() // 8 + 1, 'big'), rabin_decrypt(flag_enc, p, q)):
if b'X-MAS' in flag:
print(flag)
# X-MAS{H4nukk4h_Rabb1_and_Rab1n_l0ok_4nd_s0und_v3ry_much_alik3_H4nukk4h}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment