Challenge

耐量子計算機暗号って知ってますか？

import os
from random import SystemRandom

FLAG = os.getenv("FLAG", "Alpaca{dummy_flag!!!!!!!!!!!}").encode()
assert FLAG.startswith(b"Alpaca{") and FLAG.endswith(b"}")
flag = FLAG.lstrip(b"Alpaca{").rstrip(b"}")
assert len(flag) == 21

n = 7
m = 10
p = 8380417
F = GF(p)

random = SystemRandom()

A = matrix(F, [[random.randrange(0, p) for _ in range(n)] for _ in range(m)])
s = vector(F, [int.from_bytes(flag[3*i:3*(i+1)], "big") for i in range(n)])
e = vector(F, [random.randrange(0, 2) for _ in range(m)])
b = A * s + e

print("A =", [v.list() for v in A])
print("b =", b.list())

A = [[978223, 4103264, 2434930, 67809, 6689879, 8055109, 7358908], [704310, 752283, 1297100, 5467548, 2062034, 1748259, 393695], [2137404, 1207017, 4202172, 7586405, 8338363, 66015, 2477572], [2415274, 3971353, 4875079, 5152330, 5802762, 6727030, 3467171], [120474, 8076081, 4913437, 7056765, 4114904, 165323, 7714928], [57003, 259088, 6290590, 6813182, 7431019, 54935, 6547376], [5714777, 1965973, 3869597, 6806257, 3429400, 7138992, 2684187], [902807, 5735163, 4236221, 7359799, 7035051, 5481646, 3562173], [681907, 1263527, 4069317, 233811, 608502, 2907035, 625938], [2993255, 2217495, 6923674, 1947351, 3575140, 3447543, 5071692]]
b = [4564535, 3088331, 4021737, 2387590, 7844407, 3965605, 7334578, 356862, 1345100, 2445644]

Solution

小さなLWEが与えられます。

$b=As+e \pmod p$

eは長さ10のベクトルであり、0か1であるため、1024通りしかなく、総当たり可能です。

$As=e-b$

で、sを求めたいので、sageでA.solver_right(b-e)をすればよいです。

Final Script

from itertools import product
p=8380417; F=GF(p); M=1<<24

A=matrix(F,[
[978223,4103264,2434930,67809,6689879,8055109,7358908],
[704310,752283,1297100,5467548,2062034,1748259,393695],
[2137404,1207017,4202172,7586405,8338363,66015,2477572],
[2415274,3971353,4875079,5152330,5802762,6727030,3467171],
[120474,8076081,4913437,7056765,4114904,165323,7714928],
[57003,259088,6290590,6813182,7431019,54935,6547376],
[5714777,1965973,3869597,6806257,3429400,7138992,2684187],
[902807,5735163,4236221,7359799,7035051,5481646,3562173],
[681907,1263527,4069317,233811,608502,2907035,625938],
[2993255,2217495,6923674,1947351,3575140,3447543,5071692],
])
b=vector(F,[4564535,3088331,4021737,2387590,7844407,3965605,7334578,356862,1345100,2445644])

for mask in range(1<<A.nrows()):
    e=vector(F,[(mask>>i)&1 for i in range(A.nrows())])
    try: s=A.solve_right(b-e)
    except: continue
    if A*s+e!=b: continue
    S=[ZZ(x) for x in s]
    O=[[x]+([x+p] if x+p<M else []) for x in S]
    for xs in product(*O):
        inner=b"".join(int(v).to_bytes(3,"big") for v in xs)
        if all(32<=c<127 for c in inner):
            print("Alpaca{"+inner.decode()+"}"); quit()