Post-Quantum Криптографія: готуємось до Q-Day — повний технічний гайд з реалізацією

2030-й рік. Хтось запускає квантовий комп'ютер з 4000 логічних кубітів. За кілька годин він ламає RSA-2048. Всі банківські транзакції, зашифровані за останні 20 років — відкриті. Державні секрети, дипломатичне листування — на столі у зловмисників. Bitcoin-гаманці ранніх adopters — обнулені.

Фантастика? Ні. Це «Q-Day» — день, коли квантові комп'ютери зламають сучасну криптографію. Точна дата невідома. Може 2030, може 2040. Але він наближається з кожним прогресом у квантових обчисленнях.

Post-quantum криптографія (PQC) — це алгоритми, які виживуть цей день. У серпні 2024 року NIST офіційно стандартизував перші PQ алгоритми. Найбільша криптографічна міграція в історії людства вже почалась.

Чому квантові комп'ютери небезпечні: технічний аналіз

Алгоритм Шора (Shor's Algorithm, 1994)

Петер Шор довів, що квантовий комп'ютер може факторизувати числа за polynomial time замість exponential.

Математика атаки:

RSA-2048 security: факторизувати N = p × q
де p, q — прості числа по ~1024 біт

Класичний комп'ютер:
- Best known: General Number Field Sieve
- Складність: O(exp((64/9)^(1/3) × (ln N)^(1/3) × (ln ln N)^(2/3)))
- Для RSA-2048: ~2^112 операцій
- Час: мільярди років на найпотужніших суперкомп'ютерах

Квантовий комп'ютер (Shor):
- Складність: O((log N)^3)
- Для RSA-2048: ~4096^3 ≈ 2^36 операцій
- Час: години-дні на достатньо потужному QC

Що ламає Shor:

• RSA — базується на складності факторизації
• DSA — базується на discrete logarithm
• ECDSA/ECDH — elliptic curve discrete logarithm
• DH — Diffie-Hellman key exchange
• Практично ВСЯ асиметрична криптографія

Алгоритм Гровера (Grover's Algorithm, 1996)

Прискорює brute-force пошук у √N разів.

Симетрична криптографія:
AES-128: 2^128 можливих ключів
- Класичний brute-force: 2^128 операцій
- Grover: 2^64 операцій (квадратний корінь)
- AES-128 → ефективно AES-64

Рішення: подвоїти key size
AES-256: 2^256 → Grover: 2^128 (все ще безпечно)

Що ламає Grover:

• Хеш-функції (collision resistance зменшується)
• Симетричне шифрування (потрібні довші ключі)
• НЕ повністю ламає, тільки послаблює

Поточний стан квантових комп'ютерів

# Прогрес квантових обчислень
quantum_progress = {
    2019: {"qubits": 53, "provider": "Google Sycamore", "note": "quantum supremacy claim"},
    2021: {"qubits": 127, "provider": "IBM Eagle"},
    2022: {"qubits": 433, "provider": "IBM Osprey"},
    2023: {"qubits": 1121, "provider": "IBM Condor"},
    2024: {"qubits": 1180, "provider": "Atom Computing (neutral atoms)"},
}

# Що потрібно для Shor на RSA-2048:
# ~4000 ЛОГІЧНИХ кубітів
# Логічний кубіт = багато фізичних (error correction)
# Оцінка: 4000 логічних ≈ 4-20 МІЛЬЙОНІВ фізичних кубітів

# Песимістична оцінка Q-Day: 2040+
# Оптимістична оцінка: 2030-2035

«Harvest Now, Decrypt Later»: чому міграція потрібна ЗАРАЗ

Сценарій атаки:

Timeline:
┌─────────────────────────────────────────────────────────┐
│ 2024: Зловмисник записує зашифрований TLS трафік        │
│       (державний секрет, медичні дані, M&A угоди)       │
│                         ↓                               │
│ 2024-2034: Зберігає на HDD (storage дешевий: $15/TB)    │
│                         ↓                               │
│ 2035: Q-Day настає                                      │
│                         ↓                               │
│ 2035: Розшифровує ВСЕ за години                         │
│       - Дипломатичне листування 2024 року               │
│       - Медичні записи пацієнтів                        │
│       - Корпоративні таємниці                           │
│       - Фінансові транзакції                            │
└─────────────────────────────────────────────────────────┘

Хто вже в зоні ризику:

| Категорія | Lifetime секретності | Ризик |

|-----------|---------------------|-------|

| Державні секрети | 50+ років | КРИТИЧНИЙ |

| Медичні дані | Lifetime пацієнта | КРИТИЧНИЙ |

| Генетична інформація | Назавжди | КРИТИЧНИЙ |

| Фінансові транзакції | 7-10 років | ВИСОКИЙ |

| Корпоративні таємниці | 5-15 років | ВИСОКИЙ |

| Персональні комунікації | Variable | СЕРЕДНІЙ |

Висновок: Якщо дані мають залишатися секретними >10 років — міграція потрібна СЬОГОДНІ.

NIST Post-Quantum Standards (FIPS 203, 204, 205 — August 2024)

ML-KEM (Module-Lattice Key Encapsulation Mechanism)

Раніше відомий як Kyber. Для обміну ключами (замість RSA/DH).

"""
ML-KEM (Kyber) Implementation Concepts

Базова ідея: Learning With Errors (LWE) problem
"""

import numpy as np
from dataclasses import dataclass
from typing import Tuple

@dataclass
class MLKEMParameters:
    """Параметри для різних рівнів безпеки."""
    n: int       # Dimension of ring
    k: int       # Number of polynomials
    q: int       # Modulus
    eta1: int    # Noise parameter for secret
    eta2: int    # Noise parameter for encryption
    du: int      # Bits for compression (ciphertext)
    dv: int      # Bits for compression (ciphertext)

# NIST стандартизовані параметри
MLKEM_512 = MLKEMParameters(n=256, k=2, q=3329, eta1=3, eta2=2, du=10, dv=4)
MLKEM_768 = MLKEMParameters(n=256, k=3, q=3329, eta1=2, eta2=2, du=10, dv=4)
MLKEM_1024 = MLKEMParameters(n=256, k=4, q=3329, eta1=2, eta2=2, du=11, dv=5)


class PolynomialRing:
    """Арифметика в кільці Z_q[X]/(X^n + 1)."""

    def __init__(self, params: MLKEMParameters):
        self.n = params.n
        self.q = params.q

    def add(self, a: np.ndarray, b: np.ndarray) -> np.ndarray:
        """Додавання поліномів mod q."""
        return (a + b) % self.q

    def multiply_ntt(self, a: np.ndarray, b: np.ndarray) -> np.ndarray:
        """
        Множення через Number Theoretic Transform (NTT).
        Аналог FFT для finite fields.
        """
        # NTT перетворює O(n²) множення в O(n log n)
        a_ntt = self._ntt(a)
        b_ntt = self._ntt(b)
        c_ntt = (a_ntt * b_ntt) % self.q
        return self._inverse_ntt(c_ntt)

    def _ntt(self, poly: np.ndarray) -> np.ndarray:
        """Number Theoretic Transform."""
        # Cooley-Tukey butterfly algorithm
        # Simplified: в реальності потрібен примітивний корінь
        n = len(poly)
        result = poly.copy()
        # ... NTT implementation
        return result

    def _inverse_ntt(self, poly: np.ndarray) -> np.ndarray:
        """Inverse NTT."""
        # ... inverse NTT implementation
        return poly

    def sample_noise(self, eta: int) -> np.ndarray:
        """
        Centered Binomial Distribution (CBD).
        Генерує "маленькі" коефіцієнти для noise.
        """
        coeffs = np.zeros(self.n, dtype=np.int64)
        for i in range(self.n):
            # Sum of eta random bits - sum of eta random bits
            a = sum(np.random.randint(0, 2) for _ in range(eta))
            b = sum(np.random.randint(0, 2) for _ in range(eta))
            coeffs[i] = (a - b) % self.q
        return coeffs


class MLKEM:
    """
    ML-KEM Key Encapsulation Mechanism.
    """

    def __init__(self, params: MLKEMParameters = MLKEM_768):
        self.params = params
        self.ring = PolynomialRing(params)

    def keygen(self) -> Tuple[np.ndarray, np.ndarray]:
        """
        Генерація ключів.
        Returns: (public_key, secret_key)
        """
        k = self.params.k
        n = self.params.n

        # 1. Генеруємо випадкову матрицю A (публічна)
        A = np.random.randint(0, self.params.q, size=(k, k, n))

        # 2. Генеруємо секретний вектор s з малими коефіцієнтами
        s = np.array([self.ring.sample_noise(self.params.eta1) for _ in range(k)])

        # 3. Генеруємо noise вектор e
        e = np.array([self.ring.sample_noise(self.params.eta1) for _ in range(k)])

        # 4. Обчислюємо публічний ключ: t = A·s + e
        t = np.zeros((k, n), dtype=np.int64)
        for i in range(k):
            for j in range(k):
                t[i] = self.ring.add(
                    t[i],
                    self.ring.multiply_ntt(A[i, j], s[j])
                )
            t[i] = self.ring.add(t[i], e[i])

        public_key = (A, t)  # В реальності серіалізуються
        secret_key = s

        return public_key, secret_key

    def encapsulate(self, public_key) -> Tuple[np.ndarray, bytes]:
        """
        Encapsulation: генерує shared secret та ciphertext.
        """
        A, t = public_key
        k = self.params.k
        n = self.params.n

        # 1. Генеруємо випадковий вектор r
        r = np.array([self.ring.sample_noise(self.params.eta1) for _ in range(k)])

        # 2. Генеруємо noise
        e1 = np.array([self.ring.sample_noise(self.params.eta2) for _ in range(k)])
        e2 = self.ring.sample_noise(self.params.eta2)

        # 3. Генеруємо випадкове повідомлення m (буде seed для shared secret)
        m = np.random.randint(0, 2, size=256)  # 256 bits

        # 4. Обчислюємо ciphertext
        # u = A^T · r + e1
        u = np.zeros((k, n), dtype=np.int64)
        for i in range(k):
            for j in range(k):
                u[i] = self.ring.add(
                    u[i],
                    self.ring.multiply_ntt(A[j, i], r[j])
                )
            u[i] = self.ring.add(u[i], e1[i])

        # v = t^T · r + e2 + encode(m)
        v = e2.copy()
        for i in range(k):
            v = self.ring.add(v, self.ring.multiply_ntt(t[i], r[i]))
        # Encode message into polynomial
        v = self.ring.add(v, self._encode_message(m))

        ciphertext = (u, v)
        shared_secret = self._derive_key(m)

        return ciphertext, shared_secret

    def decapsulate(self, ciphertext, secret_key) -> bytes:
        """
        Decapsulation: відновлює shared secret з ciphertext.
        """
        u, v = ciphertext
        s = secret_key
        k = self.params.k

        # Обчислюємо v - s^T · u
        temp = np.zeros_like(v)
        for i in range(k):
            temp = self.ring.add(temp, self.ring.multiply_ntt(s[i], u[i]))

        m_decoded = self.ring.add(v, -temp % self.params.q)
        m = self._decode_message(m_decoded)

        return self._derive_key(m)

    def _encode_message(self, m: np.ndarray) -> np.ndarray:
        """Encode 256-bit message into polynomial."""
        # Scale: 0 → 0, 1 → q/2
        return (m * (self.params.q // 2)) % self.params.q

    def _decode_message(self, poly: np.ndarray) -> np.ndarray:
        """Decode polynomial back to message."""
        threshold = self.params.q // 4
        return (poly > threshold).astype(int)

    def _derive_key(self, m: np.ndarray) -> bytes:
        """Derive shared secret from message."""
        import hashlib
        return hashlib.sha3_256(m.tobytes()).digest()

ML-DSA (Module-Lattice Digital Signature Algorithm)

Раніше відомий як Dilithium. Для цифрових підписів (замість RSA/ECDSA).

"""
ML-DSA (Dilithium) Digital Signature Implementation Concepts
"""

from dataclasses import dataclass
from typing import Tuple, Optional
import numpy as np
import hashlib

@dataclass
class MLDSAParameters:
    """Параметри ML-DSA."""
    n: int = 256
    k: int = 4      # Розмір публічного ключа
    l: int = 4      # Розмір секретного ключа
    q: int = 8380417  # Модуль
    eta: int = 2    # Noise bound для секретного ключа
    tau: int = 39   # Кількість ненульових елементів у challenge
    beta: int = 78  # ||s1||∞, ||s2||∞ ≤ eta, тому β = τ × η
    gamma1: int = 2**17  # Для hint
    gamma2: int = 95232  # (q-1)/88


class MLDSA:
    """
    ML-DSA Digital Signature Scheme.
    """

    def __init__(self, params: MLDSAParameters = MLDSAParameters()):
        self.params = params

    def keygen(self) -> Tuple[dict, dict]:
        """Генерація ключів."""
        # 1. Випадкове seed
        seed = np.random.bytes(32)

        # 2. Розширюємо seed для матриці A, секретних векторів
        rho, rho_prime, K = self._expand_seed(seed)

        # 3. Генеруємо матрицю A з seed (детермінований expansion)
        A = self._expand_matrix(rho)

        # 4. Генеруємо секретні вектори s1, s2 з малими коефіцієнтами
        s1 = self._sample_secret(rho_prime, self.params.l)
        s2 = self._sample_secret(rho_prime, self.params.k, offset=self.params.l)

        # 5. Обчислюємо t = A·s1 + s2
        t = self._matrix_vector_mult(A, s1)
        for i in range(self.params.k):
            t[i] = (t[i] + s2[i]) % self.params.q

        # 6. Power2Round для compression
        t1, t0 = self._power2round(t)

        public_key = {'rho': rho, 't1': t1}
        secret_key = {'rho': rho, 'K': K, 's1': s1, 's2': s2, 't0': t0}

        return public_key, secret_key

    def sign(self, secret_key: dict, message: bytes) -> dict:
        """
        Підпис повідомлення.
        Використовує rejection sampling для security.
        """
        rho = secret_key['rho']
        K = secret_key['K']
        s1 = secret_key['s1']
        s2 = secret_key['s2']
        t0 = secret_key['t0']

        A = self._expand_matrix(rho)

        # Хеш повідомлення
        mu = hashlib.sha3_256(message).digest()

        # Rejection sampling loop
        nonce = 0
        while True:
            # 1. Генеруємо випадковий y з рівномірного розподілу
            y = self._sample_masking(nonce)
            nonce += 1

            # 2. w = A·y
            w = self._matrix_vector_mult(A, y)

            # 3. HighBits для hint
            w1 = self._high_bits(w)

            # 4. Challenge c = H(mu || w1)
            c = self._sample_challenge(mu, w1)

            # 5. z = y + c·s1
            z = self._add_vectors(y, self._scalar_mult(c, s1))

            # 6. Rejection sampling check
            # Перевіряємо, що z не витікає інформацію про s1
            if self._check_norm(z, self.params.gamma1 - self.params.beta):
                # Додаткова перевірка для r0 = LowBits(w - c·s2)
                r = self._sub_vectors(w, self._scalar_mult(c, s2))
                r0 = self._low_bits(r)

                if self._check_norm(r0, self.params.gamma2 - self.params.beta):
                    # Compute hint
                    h = self._make_hint(r, w)
                    if self._count_ones(h) <= self.params.tau:
                        return {'z': z, 'c_tilde': self._hash_challenge(c), 'h': h}

            # Якщо не пройшло — повторюємо з новим y

    def verify(self, public_key: dict, message: bytes, signature: dict) -> bool:
        """Верифікація підпису."""
        rho = public_key['rho']
        t1 = public_key['t1']

        z = signature['z']
        c_tilde = signature['c_tilde']
        h = signature['h']

        A = self._expand_matrix(rho)
        mu = hashlib.sha3_256(message).digest()

        # Відновлюємо challenge
        c = self._recover_challenge(c_tilde)

        # Перевірка норми z
        if not self._check_norm(z, self.params.gamma1 - self.params.beta):
            return False

        # w' = A·z - c·t1·2^d
        w_approx = self._matrix_vector_mult(A, z)
        ct1 = self._scalar_mult(c, self._shift_t1(t1))
        w_approx = self._sub_vectors(w_approx, ct1)

        # Використовуємо hint для відновлення w1
        w1_prime = self._use_hint(h, w_approx)

        # Перевіряємо challenge
        c_prime = self._sample_challenge(mu, w1_prime)
        return np.array_equal(c, c_prime)

    def _expand_seed(self, seed: bytes) -> Tuple[bytes, bytes, bytes]:
        """Expand seed into multiple values using SHAKE."""
        import hashlib
        shake = hashlib.shake256(seed)
        output = shake.digest(96)
        return output[:32], output[32:64], output[64:96]

    def _sample_challenge(self, mu: bytes, w1) -> np.ndarray:
        """Sample challenge polynomial with τ non-zero coefficients."""
        # Hash mu || w1 and use to sample sparse polynomial
        h = hashlib.sha3_256(mu + self._serialize(w1)).digest()
        c = np.zeros(self.params.n, dtype=np.int64)
        # Set τ positions to ±1
        positions = np.random.choice(self.params.n, self.params.tau, replace=False)
        signs = np.random.choice([-1, 1], self.params.tau)
        c[positions] = signs
        return c

    # Additional helper methods...
    def _matrix_vector_mult(self, A, v):
        """Matrix-vector multiplication in the ring."""
        pass

    def _high_bits(self, r):
        """Extract high bits for hint."""
        pass

    def _low_bits(self, r):
        """Extract low bits."""
        pass

    def _check_norm(self, v, bound):
        """Check infinity norm."""
        pass

    def _serialize(self, obj):
        """Serialize for hashing."""
        return bytes(str(obj), 'utf-8')

SLH-DSA (Stateless Hash-Based Digital Signature Algorithm)

Раніше відомий як SPHINCS+. Hash-based підписи — максимальна консервативність.

"""
SLH-DSA (SPHINCS+) - Hash-Based Signatures
Найконсервативніший варіант: безпека базується ТІЛЬКИ на hash functions.
"""

from dataclasses import dataclass
from typing import Tuple, List
import hashlib
import numpy as np

@dataclass
class SLHDSAParameters:
    """Параметри SLH-DSA."""
    n: int = 32          # Security parameter (hash output size)
    w: int = 16          # Winternitz parameter
    h: int = 64          # Total tree height
    d: int = 8           # Layers of hypertree
    k: int = 22          # FORS trees
    a: int = 6           # FORS tree height


class WOTS:
    """
    Winternitz One-Time Signature (WOTS+).
    Базовий будівельний блок для SPHINCS+.
    """

    def __init__(self, n: int = 32, w: int = 16):
        self.n = n  # Hash output length
        self.w = w  # Winternitz parameter
        # len = ceil(8n/log2(w)) + ceil(log2(len1 * (w-1))/log2(w))
        self.len1 = int(np.ceil(8 * n / np.log2(w)))
        self.len2 = int(np.ceil(np.log2(self.len1 * (w - 1)) / np.log2(w))) + 1
        self.len = self.len1 + self.len2

    def keygen(self, seed: bytes) -> Tuple[bytes, List[bytes]]:
        """
        Генерація WOTS+ ключів.
        """
        # Secret key: len random n-byte strings
        sk = []
        for i in range(self.len):
            sk.append(self._prf(seed, i))

        # Public key: chain each sk value w-1 times
        pk = []
        for i in range(self.len):
            pk.append(self._chain(sk[i], 0, self.w - 1))

        # Compress pk to single value
        pk_root = self._hash_pk(pk)

        return pk_root, sk

    def sign(self, sk: List[bytes], message: bytes) -> List[bytes]:
        """
        WOTS+ підпис.
        """
        # Convert message to base-w representation
        msg_base_w = self._to_base_w(message, self.len1)

        # Compute checksum
        checksum = sum(self.w - 1 - x for x in msg_base_w)
        checksum_base_w = self._int_to_base_w(checksum, self.len2)

        # Full message: msg || checksum
        full_msg = msg_base_w + checksum_base_w

        # Signature: chain each sk[i] exactly msg[i] times
        sig = []
        for i in range(self.len):
            sig.append(self._chain(sk[i], 0, full_msg[i]))

        return sig

    def verify(self, pk_root: bytes, message: bytes, sig: List[bytes]) -> bool:
        """
        Верифікація WOTS+ підпису.
        """
        msg_base_w = self._to_base_w(message, self.len1)
        checksum = sum(self.w - 1 - x for x in msg_base_w)
        checksum_base_w = self._int_to_base_w(checksum, self.len2)
        full_msg = msg_base_w + checksum_base_w

        # Complete the chains
        pk_candidate = []
        for i in range(self.len):
            pk_candidate.append(self._chain(sig[i], full_msg[i], self.w - 1 - full_msg[i]))

        # Verify against public key
        return self._hash_pk(pk_candidate) == pk_root

    def _chain(self, x: bytes, start: int, steps: int) -> bytes:
        """Hash chain: apply F repeatedly."""
        result = x
        for i in range(start, start + steps):
            result = self._F(result, i)
        return result

    def _F(self, x: bytes, idx: int) -> bytes:
        """Keyed hash function."""
        return hashlib.sha256(x + idx.to_bytes(4, 'big')).digest()

    def _prf(self, seed: bytes, idx: int) -> bytes:
        """Pseudorandom function."""
        return hashlib.sha256(seed + idx.to_bytes(4, 'big')).digest()

    def _to_base_w(self, msg: bytes, out_len: int) -> List[int]:
        """Convert bytes to base-w representation."""
        bits = int.from_bytes(msg, 'big')
        result = []
        for _ in range(out_len):
            result.append(bits % self.w)
            bits //= self.w
        return result[::-1]

    def _int_to_base_w(self, x: int, out_len: int) -> List[int]:
        """Convert integer to base-w."""
        result = []
        for _ in range(out_len):
            result.append(x % self.w)
            x //= self.w
        return result[::-1]

    def _hash_pk(self, pk: List[bytes]) -> bytes:
        """Hash public key components."""
        return hashlib.sha256(b''.join(pk)).digest()


class FORS:
    """
    Forest of Random Subsets (FORS).
    Few-time signature scheme для SPHINCS+.
    """

    def __init__(self, k: int = 22, a: int = 6):
        self.k = k  # Number of trees
        self.a = a  # Tree height (2^a leaves per tree)
        self.t = 2 ** a  # Leaves per tree

    def keygen(self, seed: bytes) -> Tuple[bytes, List[List[bytes]]]:
        """Generate FORS keys."""
        sk = []
        trees = []

        for i in range(self.k):
            tree_sk = []
            leaves = []
            for j in range(self.t):
                # Secret key: random values
                sk_val = self._prf(seed, i * self.t + j)
                tree_sk.append(sk_val)
                # Leaf: hash of secret
                leaves.append(hashlib.sha256(sk_val).digest())

            sk.append(tree_sk)
            trees.append(self._build_tree(leaves))

        # Root is hash of all tree roots
        roots = [tree[0] for tree in trees]
        pk = hashlib.sha256(b''.join(roots)).digest()

        return pk, sk

    def sign(self, sk: List[List[bytes]], message: bytes) -> Tuple[List[bytes], List[List[bytes]]]:
        """
        FORS sign: reveal k secrets based on message.
        """
        indices = self._message_to_indices(message)

        revealed = []
        auth_paths = []

        for i, idx in enumerate(indices):
            # Reveal sk[i][idx]
            revealed.append(sk[i][idx])
            # Authentication path
            auth_paths.append(self._get_auth_path(i, idx))

        return revealed, auth_paths

    def _message_to_indices(self, msg: bytes) -> List[int]:
        """Convert message to k indices."""
        h = hashlib.sha256(msg).digest()
        indices = []
        bits = int.from_bytes(h, 'big')
        for _ in range(self.k):
            indices.append(bits % self.t)
            bits //= self.t
        return indices

    def _build_tree(self, leaves: List[bytes]) -> List[bytes]:
        """Build Merkle tree."""
        tree = leaves[:]
        while len(tree) > 1:
            new_level = []
            for i in range(0, len(tree), 2):
                combined = tree[i] + (tree[i+1] if i+1 < len(tree) else tree[i])
                new_level.append(hashlib.sha256(combined).digest())
            tree = new_level
        return tree

    def _get_auth_path(self, tree_idx: int, leaf_idx: int) -> List[bytes]:
        """Get authentication path for leaf."""
        # Simplified: return sibling hashes up the tree
        return []

    def _prf(self, seed: bytes, idx: int) -> bytes:
        return hashlib.sha256(seed + idx.to_bytes(4, 'big')).digest()


class SLHDSA:
    """
    SLH-DSA (SPHINCS+) Full Implementation.
    """

    def __init__(self, params: SLHDSAParameters = SLHDSAParameters()):
        self.params = params
        self.wots = WOTS(params.n, params.w)
        self.fors = FORS(params.k, params.a)

    def keygen(self, seed: bytes = None) -> Tuple[bytes, dict]:
        """Generate keypair."""
        if seed is None:
            seed = np.random.bytes(48)

        sk_seed = seed[:16]
        sk_prf = seed[16:32]
        pk_seed = seed[32:48]

        # Build hypertree
        # Root of top tree is the public key
        root = self._build_hypertree(sk_seed, pk_seed)

        public_key = pk_seed + root
        secret_key = {
            'sk_seed': sk_seed,
            'sk_prf': sk_prf,
            'pk_seed': pk_seed,
            'pk': public_key
        }

        return public_key, secret_key

    def sign(self, secret_key: dict, message: bytes) -> bytes:
        """Sign message."""
        # 1. Randomize
        opt_rand = np.random.bytes(self.params.n)
        R = self._prf(secret_key['sk_prf'], opt_rand, message)

        # 2. Compute message digest
        digest = hashlib.sha256(R + secret_key['pk'] + message).digest()

        # 3. FORS signature on digest
        fors_pk, fors_sig = self._fors_sign(digest, secret_key)

        # 4. WOTS+ signatures up the hypertree
        ht_sig = self._hypertree_sign(fors_pk, secret_key)

        # Combine
        return R + fors_sig + ht_sig

    def verify(self, public_key: bytes, message: bytes, signature: bytes) -> bool:
        """Verify signature."""
        pk_seed = public_key[:self.params.n]
        pk_root = public_key[self.params.n:]

        # Parse signature
        R = signature[:self.params.n]
        # ... parse fors_sig, ht_sig

        # Compute digest
        digest = hashlib.sha256(R + public_key + message).digest()

        # Verify FORS
        fors_pk = self._fors_verify(digest, signature)

        # Verify hypertree
        computed_root = self._hypertree_verify(fors_pk, signature)

        return computed_root == pk_root

    def _build_hypertree(self, sk_seed: bytes, pk_seed: bytes) -> bytes:
        """Build d-layer hypertree."""
        # Each layer is a tree of WOTS+ signatures
        # ...implementation
        return hashlib.sha256(sk_seed + pk_seed).digest()

    def _fors_sign(self, digest: bytes, secret_key: dict):
        """FORS signature."""
        pass

    def _hypertree_sign(self, fors_pk: bytes, secret_key: dict):
        """Sign up the hypertree."""
        pass

    def _prf(self, key: bytes, *inputs) -> bytes:
        return hashlib.sha256(key + b''.join(inputs)).digest()

Практичне використання з liboqs (Python)

"""
Практичне використання Post-Quantum криптографії через liboqs.
"""

import oqs
from typing import Tuple

class PQCryptoWrapper:
    """
    Обгортка для зручного використання PQ криптографії.
    """

    @staticmethod
    def list_available_algorithms():
        """Показати доступні алгоритми."""
        print("Key Encapsulation Mechanisms:")
        for kem in oqs.get_enabled_KEM_mechanisms():
            print(f"  - {kem}")

        print("\nSignature Schemes:")
        for sig in oqs.get_enabled_sig_mechanisms():
            print(f"  - {sig}")

    @staticmethod
    def kem_example(algorithm: str = "Kyber768") -> Tuple[bytes, bytes]:
        """
        Демонстрація Key Encapsulation.
        """
        # Створюємо KEM об'єкт
        kem = oqs.KeyEncapsulation(algorithm)

        # Генеруємо keypair (сервер)
        public_key = kem.generate_keypair()
        print(f"Public key size: {len(public_key)} bytes")
        print(f"Secret key size: {len(kem.export_secret_key())} bytes")

        # Encapsulation (клієнт)
        # Клієнт використовує public key сервера
        ciphertext, shared_secret_client = kem.encap_secret(public_key)
        print(f"Ciphertext size: {len(ciphertext)} bytes")
        print(f"Shared secret size: {len(shared_secret_client)} bytes")

        # Decapsulation (сервер)
        # Сервер використовує свій secret key
        shared_secret_server = kem.decap_secret(ciphertext)

        # Перевірка
        assert shared_secret_client == shared_secret_server
        print("Key exchange successful!")

        return shared_secret_client, ciphertext

    @staticmethod
    def signature_example(algorithm: str = "Dilithium3"):
        """
        Демонстрація цифрового підпису.
        """
        # Створюємо Signature об'єкт
        signer = oqs.Signature(algorithm)

        # Генеруємо keypair
        public_key = signer.generate_keypair()
        print(f"Public key size: {len(public_key)} bytes")
        print(f"Secret key size: {len(signer.export_secret_key())} bytes")

        # Підписуємо повідомлення
        message = b"This is a test message for post-quantum signature"
        signature = signer.sign(message)
        print(f"Signature size: {len(signature)} bytes")

        # Верифікація
        verifier = oqs.Signature(algorithm)
        is_valid = verifier.verify(message, signature, public_key)
        print(f"Signature valid: {is_valid}")

        return signature, public_key

    @staticmethod
    def benchmark_algorithms():
        """
        Порівняння продуктивності алгоритмів.
        """
        import time

        results = []

        # KEM algorithms
        kem_algs = ["Kyber512", "Kyber768", "Kyber1024"]
        for alg in kem_algs:
            kem = oqs.KeyEncapsulation(alg)

            # Keygen benchmark
            start = time.time()
            for _ in range(100):
                pk = kem.generate_keypair()
            keygen_time = (time.time() - start) / 100 * 1000

            # Encap benchmark
            start = time.time()
            for _ in range(100):
                ct, ss = kem.encap_secret(pk)
            encap_time = (time.time() - start) / 100 * 1000

            # Decap benchmark
            start = time.time()
            for _ in range(100):
                ss = kem.decap_secret(ct)
            decap_time = (time.time() - start) / 100 * 1000

            results.append({
                'algorithm': alg,
                'type': 'KEM',
                'keygen_ms': keygen_time,
                'encap_ms': encap_time,
                'decap_ms': decap_time,
                'pk_size': len(pk),
                'ct_size': len(ct)
            })

        # Signature algorithms
        sig_algs = ["Dilithium2", "Dilithium3", "Dilithium5"]
        message = b"Benchmark message"

        for alg in sig_algs:
            sig = oqs.Signature(alg)

            # Keygen
            start = time.time()
            for _ in range(100):
                pk = sig.generate_keypair()
            keygen_time = (time.time() - start) / 100 * 1000

            # Sign
            start = time.time()
            for _ in range(100):
                signature = sig.sign(message)
            sign_time = (time.time() - start) / 100 * 1000

            # Verify
            verifier = oqs.Signature(alg)
            start = time.time()
            for _ in range(100):
                verifier.verify(message, signature, pk)
            verify_time = (time.time() - start) / 100 * 1000

            results.append({
                'algorithm': alg,
                'type': 'SIG',
                'keygen_ms': keygen_time,
                'sign_ms': sign_time,
                'verify_ms': verify_time,
                'pk_size': len(pk),
                'sig_size': len(signature)
            })

        return results


class HybridCrypto:
    """
    Гібридний режим: класична + post-quantum криптографія.
    Безпечно від обох типів атак.
    """

    def __init__(self):
        from cryptography.hazmat.primitives.asymmetric import x25519
        from cryptography.hazmat.primitives import hashes
        from cryptography.hazmat.primitives.kdf.hkdf import HKDF

        self.classical_private = x25519.X25519PrivateKey.generate()
        self.classical_public = self.classical_private.public_key()

        self.pq_kem = oqs.KeyEncapsulation("Kyber768")
        self.pq_public = self.pq_kem.generate_keypair()

    def get_public_keys(self) -> dict:
        """Отримати публічні ключі."""
        return {
            'classical': self.classical_public.public_bytes_raw(),
            'post_quantum': self.pq_public
        }

    def encapsulate(self, peer_public_keys: dict) -> Tuple[dict, bytes]:
        """
        Hybrid encapsulation.
        Combines X25519 + Kyber.
        """
        from cryptography.hazmat.primitives.asymmetric import x25519
        from cryptography.hazmat.primitives.kdf.hkdf import HKDF
        from cryptography.hazmat.primitives import hashes

        # Classical key exchange
        peer_classical = x25519.X25519PublicKey.from_public_bytes(
            peer_public_keys['classical']
        )
        classical_shared = self.classical_private.exchange(peer_classical)

        # Post-quantum encapsulation
        pq_ciphertext, pq_shared = self.pq_kem.encap_secret(
            peer_public_keys['post_quantum']
        )

        # Combine shared secrets
        combined = classical_shared + pq_shared
        final_key = HKDF(
            algorithm=hashes.SHA256(),
            length=32,
            salt=None,
            info=b"hybrid-key"
        ).derive(combined)

        ciphertexts = {
            'classical': self.classical_public.public_bytes_raw(),
            'post_quantum': pq_ciphertext
        }

        return ciphertexts, final_key

    def decapsulate(self, ciphertexts: dict) -> bytes:
        """
        Hybrid decapsulation.
        """
        from cryptography.hazmat.primitives.asymmetric import x25519
        from cryptography.hazmat.primitives.kdf.hkdf import HKDF
        from cryptography.hazmat.primitives import hashes

        # Classical
        peer_classical = x25519.X25519PublicKey.from_public_bytes(
            ciphertexts['classical']
        )
        classical_shared = self.classical_private.exchange(peer_classical)

        # Post-quantum
        pq_shared = self.pq_kem.decap_secret(ciphertexts['post_quantum'])

        # Combine
        combined = classical_shared + pq_shared
        final_key = HKDF(
            algorithm=hashes.SHA256(),
            length=32,
            salt=None,
            info=b"hybrid-key"
        ).derive(combined)

        return final_key


# Демонстрація
if __name__ == "__main__":
    print("=== Post-Quantum Cryptography Demo ===\n")

    wrapper = PQCryptoWrapper()

    print("1. Key Encapsulation (Kyber768):")
    wrapper.kem_example("Kyber768")

    print("\n2. Digital Signature (Dilithium3):")
    wrapper.signature_example("Dilithium3")

    print("\n3. Hybrid Mode (X25519 + Kyber):")
    alice = HybridCrypto()
    bob = HybridCrypto()

    # Alice encapsulates to Bob
    ciphertexts, alice_key = alice.encapsulate(bob.get_public_keys())

    # Bob decapsulates
    bob_key = bob.decapsulate(ciphertexts)

    print(f"Keys match: {alice_key == bob_key}")

Порівняння алгоритмів

| Алгоритм | Тип | Public Key | Secret Key | Signature/CT | Security |

|----------|-----|------------|------------|--------------|----------|

| RSA-2048 | Classic | 256 B | 256 B | 256 B | ~112 bit |

| ECDSA P-256 | Classic | 64 B | 32 B | 64 B | ~128 bit |

| ML-KEM-768 | PQ | 1184 B | 2400 B | 1088 B | ~192 bit (PQ) |

| ML-KEM-1024 | PQ | 1568 B | 3168 B | 1568 B | ~256 bit (PQ) |

| ML-DSA-65 | PQ | 1952 B | 4032 B | 3293 B | ~192 bit (PQ) |

| ML-DSA-87 | PQ | 2592 B | 4896 B | 4595 B | ~256 bit (PQ) |

| SLH-DSA-256s | PQ | 64 B | 128 B | 29792 B | ~256 bit (PQ) |

Ключове спостереження: PQ алгоритми мають значно більші розміри ключів та підписів, але це прийнятна ціна за квантову стійкість.

Ідеї для дослідження

Для бакалавра:

• Benchmark Kyber vs RSA (швидкість, розмір)
• Інтеграція liboqs в Python/Node.js застосунок
• Демонстрація Hybrid TLS з PQ алгоритмами

Для магістра:

• PQ-secure Federated Learning протокол
• Side-channel resistance lattice криптографії
• Міграційна стратегія для enterprise систем
• Порівняння SPHINCS+ vs Dilithium для різних use cases

Для PhD:

• Нові lattice constructions з меншими ключами
• Quantum-classical hybrid protocols
• Формальна верифікація PQ схем (в Coq/Lean)
• Practical attacks на lattice-based криптографію

Висновок: міграція вже почалась

«Harvest now, decrypt later» — це не теорія. Державні актори вже збирають зашифрований трафік. NIST каже: повна міграція займе 10-15 років. Q-Day може настати через 10-15 років.

Математика проста: якщо не почати зараз — не встигнеш.

Хто розуміє post-quantum криптографію сьогодні — буде на передовій найбільшої криптографічної міграції в історії людства. Від TLS до blockchain, від IoT до державних систем — все потребує оновлення.

Для дослідників це унікальна можливість: нова область, нові стандарти, нові виклики. Якщо вас цікавить PQC для академічної роботи, фахівці SKP-Degree на skp-degree.com.ua допоможуть з реалізацією lattice-based криптографії та аналізом безпеки. Консультації доступні в Telegram: @kursovi_diplomy.

Post-quantum криптографія, Kyber, Dilithium, SPHINCS+, lattice-based криптографія, NIST FIPS 203/204/205, квантові комп'ютери, Q-Day, алгоритм Шора — ключові терміни для дипломної чи магістерської роботи з криптографії та кібербезпеки майбутнього.