hidden-dimensions

Updated 13 Oct 2026

•
i forgot the chall name
•
Attribution
- •
  solved by rn (me).
- •
  AI use: only used Google Search AI Overview and my IDE's AI Code Snippets cause that's the rules
•
What it asked
- •
  recover the values to get the flag from the quaternion

Challenge

import json
import os
from math import gcd, isqrt
from secrets import randbelow

from Crypto.Util.number import getPrime


def matmul(a, b, q):
    return [
        [sum(a[i][k] * b[k][j] for k in range(4)) % q for j in range(4)]
        for i in range(4)
    ]


def matpow(matrix, exponent, q):
    result = [[int(i == j) for j in range(4)] for i in range(4)]
    while exponent:
        if exponent & 1:
            result = matmul(result, matrix, q)
        matrix = matmul(matrix, matrix, q)
        exponent >>= 1
    return result


def main():
    with open("flag.txt", "rb") as file:
        flag = file.read().rstrip(b"\r\n")
    q = getPrime(1024)
    bound = isqrt(q) // 8
    exponent = 65537

    m = int.from_bytes(flag, "big")
    if not flag or flag[0] == 0 or m >= bound // 2:
        raise ValueError("Invalid flag")

    while True:
        f = bound // 2 + randbelow(bound - bound // 2 + 1)
        g = bound // 2 + randbelow(bound - bound // 2 + 1)
        if gcd(f, g) == 1:
            break

    h = g * pow(f, -1, q) % q
    r = 2 + randbelow(bound - 1)
    ciphertext = (r * h + m) % q

    x, y, z = h + 3, 2 * import json
    import os
    from math import gcd, isqrt
    from secrets import randbelow
    
    from Crypto.Util.number import getPrime
    
    
    def matmul(a, b, q):
        return [
            [sum(a[i][k] * b[k][j] for k in range(4)) % q for j in range(4)]
            for import json
            import os
            from math import gcd, isqrt
            from secrets import randbelow
            
            from Crypto.Util.number import getPrime
            
            
            def matmul(a, b, q):
                return [
                    [sum(a[i][k] * b[k][j] for k in range(4)) % q for j in range(4)]
                    for i in range(4)
                ]
            
            
            def matpow(matrix, exponent, q):
                result = [[int(i == j) for j in range(4)] for i in range(4)]
                while exponent:
                    if exponent & 1:
                        result = matmul(result, matrix, q)
                    matrix = matmul(matrix, matrix, q)
                    exponent >>= 1
                return result
            
            
            def main():
                with open("flag.txt", "rb") as file:
                    flag = file.read().rstrip(b"\r\n")
                q = getPrime(1024)
                bound = isqrt(q) // 8
                exponent = 65537
            
                m = int.from_bytes(flag, "big")
                if not flag or flag[0] == 0 or m >= bound // 2:
                    raise ValueError("Invalid flag")
            
                while True:
                    f = bound // 2 + randbelow(bound - bound // 2 + 1)
                    g = bound // 2 + randbelow(bound - bound // 2 + 1)
                    if gcd(f, g) == 1:
                        break
            
                h = g * pow(f, -1, q) % q
                r = 2 + randbelow(bound - 1)
                ciphertext = (r * h + m) % q
            
                x, y, z = h + 3, 2 * h + 5, 4 * h + 9
                while True:
                    a = randbelow(q)
                    matrix = [
                        [a, -x, -y, -z],
                        [x, a, -z, y],
                        [y, z, a, -x],
                        [z, -y, x, a],
                    ]
                    capsule = matpow(matrix, exponent, q)
                    if (2 * capsule[1][0] - capsule[2][0]) % q != 0:
                        break
            
                with open("output.txt", "w", encoding="utf-8") as output:
                    json.dump({
                        "q": q,
                        "exponent": exponent,
                        "capsule": capsule,
                        "ciphertext": ciphertext,
                    }, output, indent=2)
            
            
            if __name__ == "__main__":
                main()
i in range(4)
        ]
    
    
    def matpow(matrix, exponent, q):
        result = [[int(i == j) for j in range(4)] for i in range(4)]
        while exponent:
            if exponent & 1:
                result = matmul(result, matrix, q)
            matrix = matmul(matrix, matrix, q)
            exponent >>= 1
        return result
    
    
    def main():
        with open("flag.txt", "rb") as file:
            flag = file.read().rstrip(b"\r\n")
        q = getPrime(1024)
        bound = isqrt(q) // 8
        exponent = 65537
    
        m = int.from_bytes(flag, "big")
        if not flag or flag[0] == 0 or m >= bound // 2:
            raise ValueError("Invalid flag")
    
        while True:
            f = bound // 2 + randbelow(bound - bound // 2 + 1)
            g = bound // 2 + randbelow(bound - bound // 2 + 1)
            if gcd(f, g) == 1:
                break
    
        h = g * pow(f, -1, q) % q
        r = 2 + randbelow(bound - 1)
        ciphertext = (r * h + m) % q
    
        x, y, z = h + 3, 2 * h + 5, 4 * h + 9
        while True:
            a = randbelow(q)
            matrix = [
                [a, -x, -y, -z],
                [x, a, -z, y],
                [y, z, a, -x],
                [z, -y, x, a],
            ]
            capsule = matpow(matrix, exponent, q)
            if (2 * capsule[1][0] - capsule[2][0]) % q != 0:
                break
    
        with open("output.txt", "w", encoding="utf-8") as output:
            json.dump({
                "q": q,
                "exponent": exponent,
                "capsule": capsule,
                "ciphertext": ciphertext,
            }, output, indent=2)
    
    
    if __name__ == "__main__":
        main()
h + 5, 4 * h + 9
    while True:
        a = randbelow(q)
        matrix = [
            [a, -x, -y, -z],
            [x, a, -z, y],
            [y, z, a, -x],
            [z, -y, x, a],
        ]
        capsule = matpow(matrix, exponent, q)
        if (2 * capsule[1][0] - capsule[2][0]) % q != 0:
            break

    with open("output.txt", "w", encoding="utf-8") as output:
        json.dump({
            "q": q,
            "exponent": exponent,
            "capsule": capsule,
            "ciphertext": ciphertext,
        }, output, indent=2)


if __name__ == "__main__":
    main()

•
Approach
- •
  The matrix is a quaternion
  - •
    basically, if a quaternion exponent, the raito of its $x, y, z$ are the same. here's how to get the h. i used x and y, but you can use any two pair
  - •
    $\begin{aligned} \frac{y}{x} &= \frac{2h+5}{h+3} \\ y(h+3) &= x(2h+5) \\ yh + 3y &= 2xh + 5x \\ yh - 2xh &= 5x - 3y \\ h(y - 2x) &= 5x - 3y \\ h &= \frac{5x-3y}{y - 2x} \end{aligned}$
- •
  then after getting $h$ , we need $f, g$
  - •
    from the chall, $h \equiv g f^{-1} \pmod q$ , maka $f h \equiv g \pmod q$
  - •
    so, the lattice matrix to LLL to get $(f, g)$ is
    
    •
    $\begin{bmatrix} 1 & h \\ 0 & q \end{bmatrix}$

•

Solution

•

# solve.sage
from secrets import randbelow
q = 156966348479027259344984193702364089433566156322387683464629321392389119569307000675325921607654782284604342398620919273316371770956037917300359658900187676329910829025779961431044226822675272694519024246486735992639698039221636707383068358540509947868319294779618242280573653330882606958830131263118492232529
exponent = 65537
F = GF(q)
capsule = matrix(F, [
    [
      126695402723219111022634024143568110912134819108892038985812449403667486188546957307708553922666233458534148952097355627956271461910464388361121300019445487451489481859247869752479477936989326100387654433283789266864764546494984077497421158862397280241854826068621112743967596440105642844975914002772012777207,
      106031027000976000155997216225472920963431698330252387906644969142408675924478187529158198537416773778851216471529629696115342276272448156194562637910859901034773367525490260637530468612352788266791560531803732726273599230721822961338097710134547610539518519262149289524423079903482338263358429323127683201388,
      105372807334902860501822219143033617882685047190000135517472141694554239204165849775557423120062164247580340385597038215783280881794112864810035411517792419861281039087660463589116533610574482865634880857283014502385989304512668984991416109111420762912411610891484792721225904009898359215011490015335592079365,
      104056368002756581193472224978155011721191744909495630739126486798845365763541174268355872285352945185038588213731855255119158092837442282040980958731657457514296382212000869492288663607017872063321521508241578054610769452094361032298052907065167067658197794150155799114831552222730401118317611399751409835319
    ],
    [
      50935321478051259188986977476891168470134457992135295557984352249980443644828813146167723070238008505753125927091289577201029494683589761105797020989327775295137461500289700793513758210322484427727463714683003266366098808499813746044970648405962337328800775517468952756150573427400268695471701939990809031141,
      126695402723219111022634024143568110912134819108892038985812449403667486188546957307708553922666233458534148952097355627956271461910464388361121300019445487451489481859247869752479477936989326100387654433283789266864764546494984077497421158862397280241854826068621112743967596440105642844975914002772012777207,
      104056368002756581193472224978155011721191744909495630739126486798845365763541174268355872285352945185038588213731855255119158092837442282040980958731657457514296382212000869492288663607017872063321521508241578054610769452094361032298052907065167067658197794150155799114831552222730401118317611399751409835319,
      51593541144124398843161974559330471550881109132387547947157179697834880365141150899768498487592618037024002013023881057533090889161925052490324247382395256468629789938119497841927693212100789828884143389203721490253708734708967722391652249429089184955907683888133449559347749320984247743818641247782900153164
    ],
    [
      51593541144124398843161974559330471550881109132387547947157179697834880365141150899768498487592618037024002013023881057533090889161925052490324247382395256468629789938119497841927693212100789828884143389203721490253708734708967722391652249429089184955907683888133449559347749320984247743818641247782900153164,
      52909980476270678151511968724209077712374411412892052725502834593543753805765826406970049322301837099565754184889064018197213678118595635259378700168530218815614446813779091938755563215657400631197502738245157938028928587127275675085015451475342880210121500629462443165742101108152205840512519863367082397210,
      126695402723219111022634024143568110912134819108892038985812449403667486188546957307708553922666233458534148952097355627956271461910464388361121300019445487451489481859247869752479477936989326100387654433283789266864764546494984077497421158862397280241854826068621112743967596440105642844975914002772012777207,
      106031027000976000155997216225472920963431698330252387906644969142408675924478187529158198537416773778851216471529629696115342276272448156194562637910859901034773367525490260637530468612352788266791560531803732726273599230721822961338097710134547610539518519262149289524423079903482338263358429323127683201388
    ],
    [
      52909980476270678151511968724209077712374411412892052725502834593543753805765826406970049322301837099565754184889064018197213678118595635259378700168530218815614446813779091938755563215657400631197502738245157938028928587127275675085015451475342880210121500629462443165742101108152205840512519863367082397210,
      105372807334902860501822219143033617882685047190000135517472141694554239204165849775557423120062164247580340385597038215783280881794112864810035411517792419861281039087660463589116533610574482865634880857283014502385989304512668984991416109111420762912411610891484792721225904009898359215011490015335592079365,
      50935321478051259188986977476891168470134457992135295557984352249980443644828813146167723070238008505753125927091289577201029494683589761105797020989327775295137461500289700793513758210322484427727463714683003266366098808499813746044970648405962337328800775517468952756150573427400268695471701939990809031141,
      126695402723219111022634024143568110912134819108892038985812449403667486188546957307708553922666233458534148952097355627956271461910464388361121300019445487451489481859247869752479477936989326100387654433283789266864764546494984077497421158862397280241854826068621112743967596440105642844975914002772012777207
    ]
  ])
ciphertext = 112648427937458772283805494482379421649242535609354384429952868314201559494481342648311342861332607935977782423213782637327457295830801743746930497336966492475849949805539113254369724913658483533437605077740647784685214373434736318344036633911659742823743736872492442506867665083275085929023286274735945971295

# capsule is a quartenion shit stuff
#
X = capsule[1][0]
Y = capsule[2][0]
Z = capsule[3][0]

# 2h+5
# h+3

h = (5*X-3*Y) * pow((Y-2*X), -1, q) % q
print(h)
h2 = (9*X - 3*Z) * pow((Z-4*X), -1, q) % q
assert h2 == h

bound = isqrt(q) // 8
for i in range(10):
    print(bound // 2 + randbelow(bound - bound // 2 + 1) % 2)

# possible = [783038823268808448814348585942260145542258154444809158826396548908661559999270703103628327670925338478680186857055284862494674116979868397181032344797970, 783038823268808448814348585942260145542258154444809158826396548908661559999270703103628327670925338478680186857055284862494674116979868397181032344797969]
# A = 783038823268808448814348585942260145542258154444809158826396548908661559999270703103628327670925338478680186857055284862494674116979868397181032344797969

def decrypt(ciphertext, f, g, q):
    combined = (f * ciphertext) % q
    masked_message = combined % g
    m = (masked_message * pow(f, -1, g)) % g
    length = (m.bit_length() + 7) // 8
    return m.to_bytes(length, "big")


M = Matrix(ZZ, [
    [1, h],
    [0, q]
])

M_lll = M.LLL()

for row in M_lll:
    f_cand = abs(row[0])
    g_cand = abs(row[1])

    if f_cand != 0 and gcd(f_cand, g_cand) == 1:
        if (f_cand * h) % q == g_cand:
            print(f"{f_cand = }, {g_cand = }")
            break
        elif (f_cand * h) % q == (q - g_cand):
            print(f"{f_cand = }, {(-g_cand % q) = }")
            break

•

# solve.py (after solve.sage)

q = 156966348479027259344984193702364089433566156322387683464629321392389119569307000675325921607654782284604342398620919273316371770956037917300359658900187676329910829025779961431044226822675272694519024246486735992639698039221636707383068358540509947868319294779618242280573653330882606958830131263118492232529
ciphertext = 112648427937458772283805494482379421649242535609354384429952868314201559494481342648311342861332607935977782423213782637327457295830801743746930497336966492475849949805539113254369724913658483533437605077740647784685214373434736318344036633911659742823743736872492442506867665083275085929023286274735945971295
f = 1075415613510665998387855140256046705210684413200741256375156708628429569887913048339209409597928119517113033642598941799612193940056256923546741912412495
g = 1317871350327010794490934180314149028208944653917367468278186811304757979260840134037802257092351881211528491651964695609429826745922017066033414477399732
def decrypt(ciphertext, f, g, q):
    combined = (f * ciphertext) % q
    masked_message = combined % g
    m = (masked_message * pow(f, -1, g)) % g
    length = (m.bit_length() + 7) // 8
    return m.to_bytes(length, "big")

print(decrypt(ciphertext, f, g, q))

•
Result
- •
- •
  COMPFEST18{f0ur_d1mens1ons_tw0_v3ct0rs_h0h0h0h0_c0ngr4tZzz}
•
Concepts
- •
  Quaternion
- •
  LLL Algorithm (Lattice Basis Reduction)

Linked references 1

compfest18-fin

◌ Explore connections in Graph view

hidden-dimensions

Attribution

What it asked

Challenge

Approach

Solution

Result

Concepts

Linked references 1