Nativity

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-23 | Status: Solved Techniques: gf2_linear_system, mod2_noise_cancellation, native_integer_overflow

Summary

Task: LWE-like encryption using numpy uint16 (mod 2^16) with noise 2*e. Public key and ciphertexts given. Solution: since noise is even, reduce everything mod 2 to cancel noise; solve linear system over GF(2) to recover secret key mod 2; decrypt each ciphertext bit using LSB only.

Nativity — CryptoHack (Post-Quantum / LWE)

Description

I've been studying Regev's cryptosystem and I think I've made a native implementation.

An LWE-based encryption scheme using numpy uint16 (native 16-bit unsigned integer arithmetic, i.e., all operations are implicitly mod 2^16):

 python read-only • copy allowed Copy
n = 64       # dimension
m = 512      # samples
dtype = np.uint16

def keygen():
    A = uniform((n, m))                          # random n×m matrix
    s = uniform((n,))                            # random secret
    pk = np.vstack((A, s @ A + 2*sample(normal)))  # public key: (n+1)×m
    sk = np.append(-s, 1).astype(dtype)           # secret key: n+1 vector
    return pk, sk
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def encrypt(pk, msg_bit):
    r = sample((m,), binary)                      # random binary vector
    c = pk @ r + np.append(np.zeros(n), msg_bit)  # ciphertext: n+1 vector
    return c.astype(dtype)

def decrypt(sk, c):
    return sk.dot(c) & 1                          # LSB of inner product

The flag is encrypted bit-by-bit. We are given public_key.txt and ciphertexts.txt.

Analysis

The critical observation is that the noise term is 2 * e — it is always even. In uint16 arithmetic (mod 2^16), this means the noise vanishes when we reduce mod 2. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Public key structure:

pk[0..n-1] = A          (rows 0 to n-1)
pk[n]      = s @ A + 2*e   (last row)

Mod 2 reduction:

pk[n] mod 2 = (s @ A) mod 2 = s @ (A mod 2) mod 2

The noise 2*e disappears! This gives us a linear system over GF(2):

pk[n] ≡ s · pk[0..n-1]  (mod 2)

With m = 512 equations and n = 64 unknowns, the system is heavily overdetermined. We can recover s mod 2.

Decryption only needs the LSB:

decrypt(sk, c) = sk · c & 1 = (c[n] - s · c[0..n-1]) & 1

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Since we know s mod 2, and the & 1 operation only cares about the LSB, we can decrypt perfectly.

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import numpy as np
from sage.all import GF, Matrix, vector
from Crypto.Util.number import long_to_bytes

# Load data
pk = np.loadtxt("public_key.txt", dtype=np.uint16)   # (n+1) x m = 65 x 512
cts = np.loadtxt("ciphertexts.txt", dtype=np.uint16)  # num_bits x (n+1)

n = 64
m = 512

A = pk[:n, :]     # n x m
b = pk[n, :]      # m

# Reduce mod 2 and solve over GF(2)
F2 = GF(2)
A_mod2 = Matrix(F2, A.astype(int) % 2).transpose()  # m x n
b_mod2 = vector(F2, b.astype(int) % 2)              # m
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Solve A_mod2.T * s_mod2 = b_mod2 (overdetermined)
s_mod2 = A_mod2.solve_right(b_mod2)  # n-vector over GF(2)

# Convert to numpy uint16
s_recovered = np.array([int(x) for x in s_mod2], dtype=np.uint16)

# Decrypt each ciphertext
bits = []
for c in cts:
    c_top = c[:n]
    c_last = c[n]
    # msg = (c_last - s · c_top) & 1
    val = np.uint16(c_last - s_recovered.dot(c_top))
    bits.append(int(val) & 1)

# Convert bits to bytes
bitstring = ''.join(str(b) for b in bits)
flag_int = int(bitstring, 2)
flag = long_to_bytes(flag_int)
print(flag.decode())

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍