comcomplexx

Co-authors: @JOHNKRAM.

Attachment:

from Crypto.Util.number import *
import random
from secret import flag, key

p, q, e, d = key
n = p * q

assert isPrime(p) and isPrime(q) and p.bit_length() == 512 and q.bit_length() == 512
print('d_len:', d.bit_length())
# d_len: 500

class QN:
    def __init__(self, a, b, c, d, n):
        self.a = a % n
        self.b = b % n
        self.c = c % n
        self.d = d % n
        self.n = n
    def __mul__(self, other):
        if isinstance(other, QN) and self.n == other.n:
            n = self.n
            a1, b1, c1, d1 = self.a, self.b, self.c, self.d
            a2, b2, c2, d2 = other.a, other.b, other.c, other.d
            a = (a1*a2 - b1*b2 - c1*c2 - d1*d2) % n
            b = (a1*b2 + b1*a2 + c1*d2 - d1*c2) % n
            c = (a1*c2 - b1*d2 + c1*a2 + d1*b2) % n
            d = (a1*d2 + b1*c2 - c1*b2 + d1*a2) % n
            return QN(a, b, c, d, n)
        return NotImplemented
    def __pow__(self, exp):
        if exp <= 0:
            return QN(1, 0, 0, 0, self.n)
        result = QN(1, 0, 0, 0, self.n)
        base = self
        while exp > 0:
            if exp & 1:
                result = result * base
            base = base * base
            exp >>= 1
        return result
    def __repr__(self):
        return f"({self.a}, {self.b}, {self.c}, {self.d})"
    def __eq__(self, other):
        return (self.a == other.a and self.b == other.b and 
                self.c == other.c and self.d == other.d and self.n == other.n)

if __name__ == "__main__":
    m = QN(bytes_to_long(flag), random.randint(1,n-1), random.randint(1,n-1), random.randint(1,n-1), n)
    c = pow(m, e)
    assert pow(c,d) == m

    print(f"n = {n}")
    print(f"e = {e}")
    print(f"c = {c}")

'''
n = 85481717157593593434025329804251284752138281740610011731799389557859119300838454555657179864017815910265870318909961454026714464920305413622061116245330661303912116693461205161551044610609272231860357133575507519403908786715597649351821576114881230052647979679534076432015415470679178775688932706964062378627
e = 622349328830189017262721806176220642327451718814004869262654184548169579851269489422592218838968239824917128227573062775020729663341881800222644869706115998147909113383905386637703321110321003518025501597602036772247509043126119242571435842445265921450671551669304835480011469949693693324643919337459251944818821206437044742271947245399811180478630764346756372873090874700249814285609571282905316777766489385036566372369518133091334281269104669836052038324087775082397535339943512028851288569342237442241378961242047171826362264504999955091800815867645003788806864324904993634075730184915611726197403247247938385732000097424282851846018331719216174462481994636142469669316961566262677169345291992925101965060785779535371861314213957527417556275049382603735394888681049143483994633920712406197215676594926797093225468201559158552767178665382859062516627874818691572997614241454801824762125841557409876879638813879540588189811
c = (36509962693210047517809190780500733945629638467721636016118307831299153205787169088399018032858962653944360359037757238416729623515314461908869670066385367461579954207170900898502608201371741903312247217007567631584237670049543882850246347784852813361080564895289678219739976819925055830837232548960336550804, 14959247128290207711158598578966149380261887381574636597156641284189267790471920774170808806288580563577492441070024491886953389517733477847472737986545246252874395600374486543947605977380365673302757291495953658030048738906460472042379676160137626447499571382731894905380992263233204548600668812780247601325, 36653805985529315558503796353782648503316310086826701482263862429608379730584363732938416744191295088641419179725673205148217999183797829423539295825286947419128575063946728227807922575922697370871241826105471260524875137135999213015948866472957081351066130709476717779611974377854714476824268335455979590736, 44619982799889884704010277482810139576960205880619960462167175653326841572868809642692412859814472796539211092403704130039198480671655784971458045667408446084843398171460450068014922244839889367385992492875980531522963147513445040259751323986442839404788429909271285196520486381047903450020895598546088952188)
'''

The problem: Given e, n and c=pow(m, e, n), solve quaternion m. @JOHNKRAM pointed out that: d<n, so d=pow(e,-1,n) (why?).

Attack script

#!/usr/bin/env python3
from Crypto.Util.number import *

# Given values
n = 85481717157593593434025329804251284752138281740610011731799389557859119300838454555657179864017815910265870318909961454026714464920305413622061116245330661303912116693461205161551044610609272231860357133575507519403908786715597649351821576114881230052647979679534076432015415470679178775688932706964062378627
e = 622349328830189017262721806176220642327451718814004869262654184548169579851269489422592218838968239824917128227573062775020729663341881800222644869706115998147909113383905386637703321110321003518025501597602036772247509043126119242571435842445265921450671551669304835480011469949693693324643919337459251944818821206437044742271947245399811180478630764346756372873090874700249814285609571282905316777766489385036566372369518133091334281269104669836052038324087775082397535339943512028851288569342237442241378961242047171826362264504999955091800815867645003788806864324904993634075730184915611726197403247247938385732000097424282851846018331719216174462481994636142469669316961566262677169345291992925101965060785779535371861314213957527417556275049382603735394888681049143483994633920712406197215676594926797093225468201559158552767178665382859062516627874818691572997614241454801824762125841557409876879638813879540588189811

c = (
    36509962693210047517809190780500733945629638467721636016118307831299153205787169088399018032858962653944360359037757238416729623515314461908869670066385367461579954207170900898502608201371741903312247217007567631584237670049543882850246347784852813361080564895289678219739976819925055830837232548960336550804,
    14959247128290207711158598578966149380261887381574636597156641284189267790471920774170808806288580563577492441070024491886953389517733477847472737986545246252874395600374486543947605977380365673302757291495953658030048738906460472042379676160137626447499571382731894905380992263233204548600668812780247601325,
    36653805985529315558503796353782648503316310086826701482263862429608379730584363732938416744191295088641419179725673205148217999183797829423539295825286947419128575063946728227807922575922697370871241826105471260524875137135999213015948866472957081351066130709476717779611974377854714476824268335455979590736,
    44619982799889884704010277482810139576960205880619960462167175653326841572868809642692412859814472796539211092403704130039198480671655784971458045667408446084843398171460450068014922244839889367385992492875980531522963147513445040259751323986442839404788429909271285196520486381047903450020895598546088952188,
)


class QN:
    def __init__(self, a, b, c, d, n):
        self.a = a % n
        self.b = b % n
        self.c = c % n
        self.d = d % n
        self.n = n

    def __mul__(self, other):
        if isinstance(other, QN) and self.n == other.n:
            n = self.n
            a1, b1, c1, d1 = self.a, self.b, self.c, self.d
            a2, b2, c2, d2 = other.a, other.b, other.c, other.d
            a = (a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2) % n
            b = (a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2) % n
            c = (a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2) % n
            d = (a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2) % n
            return QN(a, b, c, d, n)
        return NotImplemented

    def __pow__(self, exp):
        if exp <= 0:
            return QN(1, 0, 0, 0, self.n)
        result = QN(1, 0, 0, 0, self.n)
        base = self
        while exp > 0:
            if exp & 1:
                result = result * base
            base = base * base
            exp >>= 1
        return result

    def __repr__(self):
        return f"({self.a}, {self.b}, {self.c}, {self.d})"


# Compute d = e^{-1} mod n
print("Computing d = e^{-1} mod n...")
try:
    d = pow(e, -1, n)
    print(f"d = {d}")
    print(f"d bit length: {d.bit_length()}")

    # Check if d < n (should be true since it's mod n)
    print(f"d < n? {d < n}")

    # Now decrypt c
    c_qn = QN(c[0], c[1], c[2], c[3], n)
    print("\nDecrypting c with d...")
    m = c_qn**d

    print(f"Decrypted quaternion m = {m}")

    # The flag is in the 'a' component
    flag_int = m.a
    flag_bytes = long_to_bytes(flag_int)
    print(f"\nFlag (as integer): {flag_int}")
    print(f"Flag (as bytes): {flag_bytes}")

    # Try to decode as string
    try:
        flag_str = flag_bytes.decode("utf-8")
        print(f"Flag (as string): {flag_str}")
    except:
        print("Flag bytes not valid UTF-8")

    # Check if it looks like a flag
    if b"hkcert" in flag_bytes or b"flag" in flag_bytes or b"{" in flag_bytes:
        print("\n✓ Found flag!")

except Exception as ex:
    print(f"Error: {ex}")
    import traceback

    traceback.print_exc()