CPCTF 2023 | simple - crypto-writeup-public

#cpctf_2023

from Crypto.Util.number import inverse, bytes_to_long, getPrime
from flag import flag


class complex_over_p:
    """
    a + bi
    """

    def __init__(self, a, b, p):
        self.a = a
        self.b = b

        self.p = p

    def __mul__(self, other):
        return complex_over_p(
            (self.a * other.a - self.b * other.b) % self.p,
            (self.a * other.b + self.b * other.a) % self.p,
            self.p,
        )

    def __pow__(self, n: int):
        ret = complex_over_p(1, 0, self.p)
        x = complex_over_p(self.a, self.b, self.p)
        while n > 0:
            if n & 1:
                ret = ret * x
            x = x * x
            n >>= 1
        return ret

    def __str__(self):
        return str(self.a) + " + " + str(self.b) + "i"


p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537

m = bytes_to_long((flag).encode("utf-8"))
c_1 = complex_over_p(p, m, n) ** e
c_2 = complex_over_p(q, m, n) ** e

with open("cipher.txt", "w") as f:
    f.write(f"c_1 = {str(c_1)}\n")
    f.write(f"c_2 = {str(c_2)}\n")
    f.write(f"n = {n}\n")
    f.write(f"e = {e}\n")

$\mod p$ 上の複素数体上のRSA。 $c_1 = (p + mi)^e, c_2 = (q + mi)^e$

二項定理を考えると、というか単に展開すると、 $c_1$ の実部は $p^e - p^{e-2}m^2 + \dots pmi^{e - 1}$ となって、 $mi$ の偶数乗だけが集まるので、 $p$ で括れる。したがってgcdとると $p = \gcd(Re(c_1), n)$ (pythonのcomplexはfloatつかってて誤差がでるので注意）

あとは適当に $c_1 \mod p$ 考えると、 $p$ が消えるので $mi^e \mod p$

c_1 = [88947353384906315386142174915579230007708484691905461586249734733895208303904624706955572569717469153074453837889147058757297004159523404800499566731846573280606881057150101844929178328363240743156762837486978571114151912836342740869293096891054377782752248810122413624567401981982628574682163267589540717955, 105796218607197626508309219898970081654433389611035862776816738031930217893350585142033078143656160997324512315260317101196998029046142078518167267210684968483205795618377068578645969888568133775820377659323101885187136507439656053103103802476138541844262969937543381511564444761769799873705129093296227488320]
c_2 = [6246646181898635030418930144979030696163268885489193597189892517442414814959679853409630585655482080447639092928109757977342458025765218315720433756032748568912426451942636486110411038484872363928990656032625950245328223463301109739166158341796991125915052131277132622262221136515681121985807852466393611412, 53817519046828021036896927561082153848829725683909509411136093993919199941896521025977358288420902565544951255959786518459773639829589216874164688208953119794504853435052217109342811249935881805211646847973929482665869312260539685753735469177452027367949870932823024534083790996822338074496201028292592498398]
n = 115660927134746496667389439939121894365639159618801107805144217447831876345527158612296725729945512010246362315164908359385194177739042272399000609673334050698528059482827768728850630523188582862374516240503442919767592843273925939238586765096529791229982128395675821790738782110235716669724330392693672332699
e = 65537

from math import gcd

p = gcd(c_1[0], n)
q = n // p


d = pow(e, -1, (p - 1))
m = pow(c_1[1], d, p)
print(bytes.fromhex(hex(m)[2:]))