Young Cryptography — UIUCTF 2026

Description

No separate organizer prose was included in the supplied package. The challenge consisted of chal.py and the five-line out instance.

The source creates three random symmetric 64 x 64 nonnegative matrices. It publishes G, AG = my_prod(A, G), and GB = my_prod(G, B), then derives an AES-CBC key from the secret matrix AGB = my_prod(A, GB). The output also contains the ciphertext and IV.

The title is literal: the max/min recurrence in my_prod is Fomin's tropical RSK growth rule. Its boundary encodes a semistandard Young tableau, and matrix multiplication becomes multiplication in the plactic monoid.

Analysis

1. Splitting my_prod into a growth boundary and its inverse

The important detail in the source is this loop:

r = [z] * (n + 1)
for row in A + B:                 # list concatenation, not matrix addition
    s = [z]
    for j, x in enumerate(row, 1):
        s.append(f(r[j-1], r[j], s[-1], x))
    r = s

The function f is the tropical local rule. Processing a matrix produces a boundary

[ r=(\lambda^{(0)},\lambda^{(1)},\ldots,\lambda^{(N)}), ]

where every tuple is a partition/shape vector. The number of copies of symbol j in tableau row i is

[ r[j][i]-r[j-1][i]. ]

Thus the boundary-to-tableau conversion is only:

def tableau_from_boundary(r, n):
    P = [[] for _ in range(n)]
    for j in range(1, n + 1):
        for i in range(n):
            P[i] += [j] * (r[j][i] - r[j - 1][i])
    return [row for row in P if row]

The second half of my_prod sweeps the triangular growth diagram backwards. Given r, phase2(r) constructs the corresponding symmetric matrix. On valid boundaries these operations satisfy

[ \operatorname{phase1}(\operatorname{phase2}(r))=r. ]

...