//Very Cool Cryptosystem

>Very Cool Cryptosystem — Full Writeup

Category: Crypto (BSides) \

Author: scalio \

Flag format: shellmates{...}

This document retraces every step I used to solve "Very Cool Cryptosystem" from scratch, including the tooling, solver scripts, command outputs, and the reasoning links that got me to the final flag. My goal was to treat the challenge like a research note so it can double as a contest-quality writeup.

>1. Recon & Threat Model

I began by reviewing the only source file, chall.sage. The encryption flow quickly revealed a structure reminiscent of the Cayley–Purser cryptosystem: a pair of random invertible matrices over Z_n (with n = pq), a hidden commuting relation, and a conjugation-based public key. Unlike the classical version, the author complicated the private key by constructing a 4×4 upper-triangular matrix whose diagonal depends on two hidden scalars a and c. The ciphertext splits the 110-byte flag into two pieces: the first 30 bytes help derive the private key, the remaining 80 bytes are encrypted under a fresh exponentiated secret matrix gam = D^(5s).

Reference for the Cayley–Purser idea: Wikipedia – Cayley–Purser algorithm. Seeing the same conjugation pattern (B = D^{-1} A^{-1} D) immediately suggested the known attacks would translate if I could recover D.

>2. Factoring the RSA Modulus

The script does not protect n, so the obvious first step was to factor it. PARI/GP (gp) handled the 200-bit primes instantly after enlarging the stack:

$ gp -q <<'GP'

allocatemem(400000000);

n = 445274615059837074703074129112359915057174632831812151523967;

factor(n)

GP

Output:

So p = 460787053387729396804743714197 and q = 966334908470530797510120137411.

>3. Solving for the Hidden Scalars a and c

The priv_key builder uses two unknown scalars a, c ∈ Z_n plus a published array b_s. The three off-diagonal entries of D^5 given in out.txt provide just enough equations to solve for a and c. To keep the systems small I worked modulo p and modulo q separately, using Sage’s Gröbner basis engine.

3.1 Modulo p

Script: solve_gb.sage

p = 460787053387729396804743714197

GFp = GF(p)

a, c = PolynomialRing(GFp, 2, names=('a','c')).gens()

# ... (load b_list and g_list) ...

polys = [cs0 * S0 - gl[0], cs1 * S1 - gl[1], cs2 * S2 - gl[2]]

I = ideal(polys)

print(I.groebner_basis())

Running it:

$ sage solve_gb.sage

verbose 0 (...) Warning: falling back to very slow toy implementation.

[a + 280298606918854739350729747621, c + 61756496956266078424452139909]

So modulo p, a ≡ -2802986069… and c ≡ -6175649695….

3.2 Modulo q

Script: solve_gb_q.sage

$ sage solve_gb_q.sage

verbose 0 (...) Warning: falling back to very slow toy implementation.

[a + 505635856485732946428464125503, c + 4369968139429109021813532246]

CRT’ing both solutions produced the full residues:

With (a, c) known, rebuilding the private matrix D (and therefore D^5) is straightforward because every entry is now explicit.

>4. Recovering the Session Matrix gam and the Conjugator k

The public key contains A, B = D^{-1} A^{-1} D, and Dr = D^5. Encryption randomises D further by setting gam = Dr^s for secret s, then releasing eps = gam^{-1} A gam and U_ = k U k with k = gam^{-1} B gam.

To undo this, I needed the matrix G satisfying A·G = G·eps. Over a field this is a standard matrix intertwiner problem; the solutions form the kernel of (I ⊗ A – epsᵀ ⊗ I).

4.1 Solve modulo p

Script: solve_gam_p.sage

I = identity_matrix(GFp, 4)

M = I.tensor_product(A) - eps.transpose().tensor_product(I)

ker = M.right_kernel()

print('dimension', ker.dimension())

vec = ker.basis()[0]

G = Matrix(GFp, 4, 4, vec)

Terminal snippet:

4.2 Solve modulo q

Script: solve_gam_q.sage

The kernel has dimension 4 because eps is similar to A; I only needed one basis vector. After CRT and reshaping column-major, G equals gam up to right-multiplication by a scalar matrix, which is fine because both eps and B respect that scaling. Using this G, I recomputed k = G^{-1} B G in Z_n and decrypted the second half of the flag via U = k^{-1} U_ k^{-1}. A short SymPy script performed the heavy lifting:

U_plain = (k_inv * U_cipher * k_inv).applyfunc(lambda x: x % n)

print(U_plain)

Result:

Each entry is below 256^5, so I decoded them as 5-byte words, yielding the readable tail:

>5. Recovering the First 30 Bytes

The first stage of the challenge hides flag[:30] inside the scalars a and c. Specifically, c = m^6 mod n where m is the integer representation of those 30 bytes. With (a, c) known, I solved the 6th root modulo p and q separately, then CRT’d the four possibilities:

$ sage -c '...; (x^6 - c).roots()'

roots count p 2:  (275183045595513927822784217075, ...)

roots count q 2:  (857179754891755301397013588281, ...)

Combining the pairs gives four candidate messages {m_i}. Only one should match a printable ASCII string starting with the known prefix shellmates{. I enforced this constraint using Z3:

from z3 import Int, Solver, And, sat

prefix = 'shellmates{'

remaining = 19

for m in m_values:

    R = (m - prefix_int * 256**remaining) % n

    s = Solver()

    ys = [Int(f'y{i}') for i in range(remaining)]

    for y in ys: s.add(And(y >= 32, y <= 126))

    s.add(sum(coeff*y for coeff,y in zip(coeffs, ys)) - R == k * n)

    if s.check() == sat:

        ...

Output:

So the missing prefix was shellmates{CayleyPurser_withou.

>6. Final Flag

Appending the decrypted suffix finishes the flag:

Length check (requested by the challenge):

$ python3 - <<'PY'

flag = 'shellmates{CayleyPurser_without_pub_key?_grobner?_anyway_hope_u_used_the_right_monomial_ordering_isthisenough}'

print(len(flag))

PY

110

>7. Files & Scripts

| Purpose | File |

| --- | --- |

| Factor-independent recovery of a, c modulo p | solve_gb.sage |

| Same as above modulo q | solve_gb_q.sage |

| Kernel computation for G modulo p | solve_gam_p.sage |

| Kernel computation for G modulo q | solve_gam_q.sage |

| SymPy helper (inline) | Included in Section 4 |

| Z3 prefix solver (inline) | Included in Section 5 |

Each Sage helper is self-contained, so anyone can rerun the exact steps.

>8. Lessons & Ideas

1. Cayley–Purser attack surface: The moment I saw matrices A, B = D^{-1} A^{-1} D, and a hidden conjugation gam, I knew the textbook Cayley–Purser break (see reference link) would apply if I could reverse-engineer D.
2. Symbolic solving beats guessing: The private-key noise b_s looks intimidating, but it only hides two scalars. Gröbner bases modulo the prime factors quietly peel away all the obfuscation.
3. Linear algebra still wins: Once a and c are known, G lives in the kernel of a giant linear system, no discrete logarithms required.
4. CRT pipeline: Solving everything modulo p and q made the intermediate objects tiny, which in turn sped up Sage and SymPy tremendously.

>9. References

1. Cayley–Purser algorithm, Wikipedia, https://en.wikipedia.org/wiki/Cayley–Purser_algorithm — identifies the structure of the scheme and motivates the conjugation attack.
2. SageMath documentation — for Gröbner bases and linear algebra over finite fields.

Happy hacking! If you rerun the scripts above, you should be able to reproduce the compromise end-to-end.