Crypto - knutsacque

Behold my original knut sacque scheme in 4D -sera

Full Implementation

Challenge

import secrets

F.<i,j,k> = QuaternionAlgebra(-1, -1)
A = []
B = [1, i, j, k]

msg_bin = b"irisctf{redacted_redacted_redacted_}"
assert len(msg_bin) % 4 == 0
msg = [F(sum(Integer(msg_bin[idx+bi])*b for bi, b in enumerate(B))) for idx in range(0, len(msg_bin), len(B))]
targ = 2^64

for _ in range(len(msg)):
    a = F(sum(secrets.randbelow(targ)*b for b in B))
    A.append(a)

sm = F(0)
for idx in range(len(msg)):
    sm += msg[idx] * A[idx]

print("A =", A)
print("s =", sm)

Now, let's break down the code and see how the message is being encrypted.

F.<i,j,k> = QuaternionAlgebra(-1, -1)

Here, i, j and k can be thought of unit vectors in a Cartesian plane except for the fact that $i\times i,j\times j ,k \times k = -1$.

msg = [F(sum(Integer(msg_bin[idx+bi])*b for bi, b in enumerate(B))) for idx in range(0, len(msg_bin), len(B))]

This takes 4 bytes at a time and converts it into the format $(m_{idx} + m_{idx+1}*i + m_{idx+2}*j + m_{idx+3}*k)$

for _ in range(len(msg)):
    a = F(sum(secrets.randbelow(targ)*b for b in B))
    A.append(a)

A is similarly produced as $(a_{idx} + a_{idx+1}*i + a_{idx+2}*j + a_{idx+3}*k)$ for each corresponding pair in msg

sm = F(0)
for idx in range(len(msg)):
    sm += msg[idx] * A[idx]

sm is the sum of all the products of the pairs of msg and A. For example, the first product form is $(m_{0} + m_{1}*i + m_{2}*j + m_{3}*k) * (a_{0} + a_{1}*i + a_{2}*j + a_{3}*k) = {sm}_0 + sm_1*i + sm_2*j + sm_3*k$

On simplifying, we get

$(m_0*a_0-m_1*a_1-m_2*a_2-m_3*a_3)+(m_0*a_1+m_1*a_0+m_2*a_3-m_3*a_2)*i + (m_0*a_2-m_1*a_3+m_2*a_0+m_3*a_1)*j + (m_0*a_3+m_1*a_2-m_2*a_1+m_3*a_0)*k$

Separating $i,j,k$ and rewriting into matrix form, we get

$$\begin{bmatrix} m_0 & m_1 & m_2 & m_3 \end{bmatrix} \cdot \begin{bmatrix} a_0& a_1 & a_2 & a_3 \\ -a_1 &a_0 & -a_3 & a_2 \\ -a_2 &a_3 & a_0 & -a_1 \\ -a_3 & -a_2 & a_1 & a_0 \end{bmatrix} = \begin{bmatrix} sm_0 & sm_1 & sm_2 & sm_3 \end{bmatrix}$$

We can generalize this by considering all the pairs, which will be in the form

$$\begin{bmatrix} m0 & m1 & \cdots & \cdots & m_n \end{bmatrix} \cdot \begin{bmatrix} a_i& a_{i+1} & a_{i+2} & a_{i+3} \\ -a_{i+1} &a_{i} & -a_{i+3} & a_{i+2} \\ -a_{i+2} &a_{i+3} & a_{i} & -a_{i+1}\\ -a_{i+3} & -a_{i+2} & a_{i+1} & a_{i} \end{bmatrix} = \begin{bmatrix} s_o & s_1 & s_2 & s_3 \end{bmatrix}$$

Generally we can solve for $m_i$ using A.solve_left() in sage , but since the values of $a_i$ are much bigger than the values of $m_i$ , we have to solve it using LLL.

This is similar to the knapsack problem, except the key values are in the range of ascii instead of {0,1}

Usually while solving knapsack cryptosystems, we only need one vector (public key) to find the short vector. However, due to the size difference between $m_i$ and $a_i$, we will be using all the four vectors that we have inorder for LLL to produce a vector that isn't too short and fits to our solution. In the CJLOSS algorithm, since the key consists of 0/1, we use ½ in the last row to increase the density. Similarly, since $m_i$ are ascii characters, we approximate that they are in the range {60,100} and we use 80 in the last row

$$\begin{bmatrix} 1 & 0 & \cdots & \cdots & \vdots & a_{i} & a_{i+1} & a_{i+2} & a_{i+3} \\ 0 & \ddots & 0 & \vdots & \vdots & -a_{i+1} & a_{i} & -a_{i+3} & a_{i+2} \\ \vdots & \cdots & \ddots & \vdots & \vdots & -a_{i+2} & a_{i+3} & a_i & -a_{i+1} \\ 0 & 0 & \cdots & \ddots & \cdots & -a_{i+3} & -a_{i+2} & a_{i+1} & a_i \\ 0 & \cdots & \cdots & \cdots & 1 & \vdots & \vdots & \vdots & \vdots \\ 80 & \cdots & \cdots & \cdots & \cdots & s_{0} & s_{1} & s_2 & s_3 \end{bmatrix}$$

After applying LLL on this matrix we get all the values of $m_i$, and after converting to ascii we get the flag.

a = []
for i in A:
    for j in i:
      a.append(j)  
l1 = []
l2 = []
l3 = []
l4 = []
for i in range(0,len(a),4):
    l1+= [a[i],-a[i+1],-a[i+2],-a[i+3]]
    l2+= [a[i+1],a[i],a[i+3],-a[i+2]]
    l3+= [a[i+2],-a[i+3],a[i],a[i+1]]
    l4+= [a[i+3],a[i+2],-a[i+1],a[i]]
M = Matrix.identity(ZZ,len(a))
M = M.augment(vector(list(l1)))
M = M.augment(vector(list(l2)))
M = M.augment(vector(list(l3)))
M = M.augment(vector(list(l4)))
M = M.stack(vector([80 for i in range(len(a))]+list(s)))
M1 = M.LLL()
for i in M1[-1][:-4]:
    print(chr(abs(i-80)),end='')
b'irisctf{wow_i_cant_believe_its_lll!}'