X-MAS CTF 2018 - Writeup of Hanukkah

rabin.py

#!/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}