Quatum Safe

I heard Shor's algorithm can do all sorts of nasty things to RSA, so I've decided to be super modern and protect my flag with cool new maffs!

source.sage
from random import randint
from file import flag,r

pubkey = Matrix(ZZ, [
    [47, -77, -85],
    [-49, 78, 50],
    [57, -78, 99]
])

for c in flag:
    v = vector([ord(c), r1:=randint(0, 100), r2:=randint(0, 100)]) * pubkey + r
    print(v)

enc.txt
(-981, 1395, -1668)
(6934, -10059, 4270)
(3871, -5475, 3976)
(4462, -7368, -8954)
(2794, -4413, -3461)
(5175, -7518, 3201)
(3102, -5051, -5457)
(7255, -10884, -266)
(5694, -8016, 6237)
(4160, -6038, 2582)
(4940, -7069, 3770)
(3185, -5158, -4939)
(7669, -11686, -2231)
(5601, -9013, -7971)
(5600, -8355, 575)
(1739, -2838, -3037)
(2572, -4120, -3788)
(8055, -11985, 1137)
(7088, -10247, 5141)
(8384, -12679, -1381)
(-785, 1095, -1841)
(4250, -6762, -5242)
(3716, -5364, 2126)
(5673, -7968, 6741)
(5877, -9190, -4803)
(5639, -8865, -5356)
(1980, -3230, -3366)
(6183, -9334, -1002)
(2575, -4068, -2828)
(7521, -11374, -1137)
(5639, -8551, -1501)
(4194, -6039, 3213)
(2072, -3025, 383)
(2444, -3699, -502)
(6313, -9653, -2447)
(4502, -7090, -4435)
(-421, 894, 2912)
(4667, -7142, -2266)
(4228, -6616, -3749)
(6258, -9719, -4407)
(6044, -9561, -6463)
(266, -423, -637)
(3849, -6223, -5988)
(5809, -9021, -4115)
(4794, -7128, 918)
(6340, -9442, 892)
(5322, -8614, -8334)

Solution

we know the format of the flag HTB{....} so we know 5 charcters of the flag.

To find flag we need vector r so we have to make equations like

pubkey[0][0]*ord('H') + pubkey[0][1]*r1 + pubkey[0][2]*r2 +rx = -981
pubkey[1][0]*ord('H') + pubkey[1][1]*r1 + pubkey[1][2]*r2 +ry = 6934
pubkey[2][0]*ord('H') + pubkey[2][1]*r1 + pubkey[2][2]*r2 +rz = 3871

since we know 5 chacters so there will be 5*3 equations and 13 variables (3 for r and 10 for flag) so we can easily find vector 'r'. Once we have vector 'r'

pubkey[0][0]*fi + pubkey[0][1]*r1 + pubkey[0][2]*r2 = -981-rx
pubkey[1][0]*fi + pubkey[1][1]*r1 + pubkey[1][2]*r2 = 6934-ry
pubkey[2][0]*fi + pubkey[2][1]*r1 + pubkey[2][2]*r2 = 3871-rz

we can easily find the fc(character corresponding to ith output). The complete solution for this challenge is following

solve.sage
pubkey = Matrix(ZZ, [
    [47, -77, -85],
    [-49, 78, 50],
    [57, -78, 99]
])

cipher = [(-981, 1395, -1668),(6934, -10059, 4270),(3871, -5475, 3976),(4462, -7368, -8954),(2794, -4413, -3461),(5175, -7518, 3201),(3102, -5051, -5457),(7255, -10884, -266),(5694, -8016, 6237),(4160, -6038, 2582),(4940, -7069, 3770),(3185, -5158, -4939),(7669, -11686, -2231),(5601, -9013, -7971),(5600, -8355, 575),(1739, -2838, -3037),(2572, -4120, -3788),(8055, -11985, 1137),(7088, -10247, 5141),(8384, -12679, -1381),(-785, 1095, -1841),(4250, -6762, -5242),(3716, -5364, 2126),(5673, -7968, 6741),(5877, -9190, -4803),(5639, -8865, -5356),(1980, -3230, -3366),(6183, -9334, -1002),(2575, -4068, -2828),(7521, -11374, -1137),(5639, -8551, -1501),(4194, -6039, 3213),(2072, -3025, 383),(2444, -3699, -502),(6313, -9653, -2447),(4502, -7090, -4435),(-421, 894, 2912),(4667, -7142, -2266),(4228, -6616, -3749),(6258, -9719, -4407),(6044, -9561, -6463),(266, -423, -637),(3849, -6223, -5988),(5809, -9021, -4115),(4794, -7128, 918),(6340, -9442, 892),(5322, -8614, -8334)]

import numpy as np

A = np.array([[-49,57,0,0,0,0,0,0,0,0,1,0,0],
              [78,-78,0,0,0,0,0,0,0,0,0,1,0],
              [50,99,0,0,0,0,0,0,0,0,0,0,1],
              [0,0,-49,57,0,0,0,0,0,0,1,0,0],
              [0,0,78,-78,0,0,0,0,0,0,0,1,0],
              [0,0,50,99,0,0,0,0,0,0,0,0,1],
              [0,0,0,0,-49,57,0,0,0,0,1,0,0],
              [0,0,0,0,78,-78,0,0,0,0,0,1,0],
              [0,0,0,0,50,99,0,0,0,0,0,0,1],
              [0,0,0,0,0,0,-49,57,0,0,1,0,0],
              [0,0,0,0,0,0,78,-78,0,0,0,1,0],
              [0,0,0,0,0,0,50,99,0,0,0,0,1],
              [0,0,0,0,0,0,0,0,-49,57,1,0,0],
              ])

y = np.array([-981-47*ord('H') , 1395+77*ord('H') , -1668+85*ord('H') , 6934-47*ord('T') , -10059+77*ord('T') , 4270+85*ord('T') , 3871-47*ord('B') , -5475+77*ord('B') , 3976+85*ord('B') , 4462-47*ord('{') , -7368+77*ord('{') , -8954+85*ord('{') , 5322-47*ord('}')])

A_inv = np.linalg.pinv(A) # pseudo-inverse of A

x = np.dot(A_inv, y) # solve the linear system
# last 3 elements of x are the (rx, ry, rz)
r=vector([(x[-3]),(x[-2]),(x[-1])])
flag  = "HTB{"
for i in range(4,len(cipher)):
    B = np.array([[47,-49,57],
                  [-77,78,-78],
                  [-85,50,99]
                  ])
    z = np.array([cipher[i][0]-r[0],cipher[i][1]-r[1],cipher[i][2]-r[2]])
    x=np.dot(np.linalg.pinv(B),z)
    flag+=chr(int(x[0]))
print(flag)

After running the script we get the flag HTB{r3duc1nG_tH3_l4tTicE_l1kE_n0b0dY's_pr0bl3M}

Quatum Safe

Solution​

Solution