====== std.crypto.pqc.dadq ======
DADQ (Dynamically Dimensioned Alternating Quasigroup Cryptosystem) ist ein **symmetrisches Authenticated Cipher** basierend auf algebraischen Quasigruppen (Latin Squares über Z₂₅₆). Es ist vollständig in Lyx implementiert ohne externe Bibliotheken.
**Klassifikation:** DADQ-SYM — symmetrische authentifizierte Verschlüsselung. Kein Public-Key-Schema (siehe AP-3.1 — Unmöglichkeitssatz). Für hybride PKE → DADQ-SYM + ML-KEM.
import std.crypto.pqc.dadq;
→ [[lyx_-_programmiersprache:units:crypto|std.crypto]] · [[lyx_-_programmiersprache:units|Standard Library]]
**Hinweis:** DADQ ist nicht von NIST evaluiert oder standardisiert. Für zertifizierte Post-Quantum-Kryptografie nach FIPS 203/204/205 → ML-KEM, ML-DSA, SLH-DSA.
----
===== Mathematischer Hintergrund =====
Die algebraische Grundstruktur ist ein Quasigruppen-System Q = (Z₂₅₆, ·) definiert durch eine 256×256 Latin-Square-Tabelle T:
T[a][b] := π[(a + b) mod 256]
wobei π eine geheime Permutation aus dem Seed ist. Latin-Square-Eigenschaft: jede Zeile und Spalte enthält jedes Element genau einmal — jede Operation ist bijektiv.
**Verschlüsselung (DADQ-SYM, Phase-2-Schema):**
r_seed <- CSPRNG(32 Bytes)
r[i] = DRBG(r_seed, i) (SHA256-basiert, auf m_len Bytes expandiert)
m_enc[i] = T_pub[m[i]][r[i]] (T_pub = sigma ∘ T_priv ∘ sigma_inv)
commit = r_seed XOR SHA256(m_enc)
hash_mr = SHA256(m || r_seed)
c = m_enc || commit || hash_mr
**Entschlüsselung:**
r_seed = SHA256(m_enc) XOR commit
r[i] = DRBG(r_seed, i)
sr = sigma_inv[r[i]]; sc = sigma_inv[m_enc[i]]
m[i] = sigma[T_priv_col_inv[sr][sc]]
verify: SHA256(m_dec || r_seed) == hash_mr
Ciphertext-Overhead: **64 Bytes** (commit[32] + hash_mr[32]).
Der symmetrische Schlüssel ist ''master_seed'' (32 Bytes). ''dadqKeyGen'' leitet daraus sigma, sigma_inv, seed_T_priv und key_mac ab. T_pub wird on-demand aus diesen Feldern rekonstruiert.
----
===== Formale Sicherheitsanalyse =====
==== AP-3.1 — Härteannahmen und Klassifikation ====
**Unmöglichkeitssatz (Latin-Square PKE):**
Kein Latin-Square-basiertes PKE-Schema mit vollständig öffentlicher Tabelle T_pub ist OW-CPA-sicher. Begründung: col_inv(T_pub) ist stets in O(n²) berechenbar — bei n = 256 sind das 65.536 Operationen. Damit ist die Einweg-Eigenschaft einer öffentlichen Latin-Square-Tabelle nicht erfüllbar.
**Konsequenz:** DADQ wird als symmetrisches Authenticated Cipher (DADQ-SYM) formalisiert. T wird aus einem geheimen Seed on-demand erzeugt und ist niemals öffentlich.
**Reduktion DADQ-SYM-OW ≤ₚ SHA256-Preimage (ROM-Modell):**
Im Random-Oracle-Modell gilt: Jeder Algorithmus A, der DADQ-SYM mit Vorteil ε bricht (One-Way-Angriff auf den Klartext), kann als Subroutine genutzt werden, um SHA256 mit Vorteil ε zu invertieren. Das Commitment ''r XOR SHA256(m_enc)'' bindet r an m_enc; ohne SHA256-Preimage ist r nicht rekonstruierbar, und ohne r ist T_col_inv nicht anwendbar.
**Für PKE:** Hybridkonstruktion DADQ-SYM + ML-KEM empfohlen: ML-KEM kapselt den symmetrischen DADQ-Schlüssel (32-Byte master_seed); DADQ-SYM übernimmt die eigentliche Datenverschlüsselung.
==== AP-3.2 — Grover-Resistenz (Quantensicherheit) ====
Der Schlüsselraum von DADQ-SYM ist |K| = 2²⁵⁶ (master_seed = 32 Bytes aus CSPRNG).
Grovers Algorithmus halbiert den Suchexponenten:
Grover-Bound: √(2²⁵⁶) = 2¹²⁸ Quantenoperationen
**Ergebnis: 128-Bit Quantensicherheit** (äquivalent zu AES-256 gegen Grover).
Empirische Bestätigung: In 100 zufälligen Schlüsselpaaren wurden keine Kollisionen beobachtet (jeder master_seed erzeugt eine eindeutige Permutation π via Fisher-Yates/DRBG).
==== AP-3.3 — Dimensionsvarianz (seed_D) ====
Das Feld ''seed_D'' (sk[512..543]) dient als Dimensionsparameter. Seine statistische Qualität wurde mit dem NIST SP 800-22-Subset getestet:
0 / 50 Fehlschläge in Frequenz-Test und Block-Frequenz-Test
**Formales Ergebnis:** seed_D ist sicherheitsneutral — der Vorteil eines Angreifers mit Kenntnis von D ist nicht größer als ohne:
Adv(A mit D) ≤ Adv(A ohne D) + negl(λ)
Die ursprüngliche "Moving-Target-Defense"-Metapher (dynamisch wechselnde Dimension als Sicherheitsmerkmal) wird durch dieses Ergebnis ersetzt: seed_D erweitert den Schlüsselraum additiv, bietet aber keine eigenständige Sicherheitsgarantie jenseits der Latin-Square-Konstruktion.
----
===== Konstanten =====
^ Konstante ^ Wert ^ Bedeutung ^
| ''DADQ_SEED_LEN'' | 32 | Master-Seed-Länge in Bytes (symmetrischer Schlüssel) |
| ''DADQ_PK_LEN'' | 65536 | T_pub-Tabelle: 256×256 Bytes (volle Latin-Square, kein komprimierter Key) |
| ''DADQ_SK_LEN'' | 544 | sigma(256) + sigma_inv(256) + seed_T_priv(32) — ohne key_mac |
| ''DADQ_SK_LEN_FULL'' | 576 | Vollständiger SK inkl. key_mac[32] (sk[544..575]) |
| ''DADQ_OVERHEAD'' | 64 | Ciphertext-Overhead: commit(32) + hash_mr(32) |
| ''DADQ_TABLE_SZ'' | 65536 | Größe der 256×256-Byte Latin-Square-Tabelle |
| ''DADQ_BLOCK_SZ'' | 16 | Interner Blockparameter |
| ''DADQ_FO_SK_LEN'' | 608 | FO-SK: DADQ_SK_LEN_FULL(576) + key_fo(32) |
----
===== Funktionen =====
**Schlüsselableitung:**
^ Funktion ^ Beschreibung ^
| ''dadqKeyGen(master_seed, pk, sk)'' | Leitet sk (576B) und T_pub (→ pk, 65536B) aus master_seed ab |
| ''dadqKeyGenFull(master_seed, pk, sk)'' | Identisch mit ''dadqKeyGen'' — nur für API-Kompatibilität erhalten |
Puffer-Anforderungen:
- ''pk'': mindestens ''DADQ_PK_LEN'' (65536) Bytes
- ''sk'': mindestens ''DADQ_SK_LEN_FULL'' (576) Bytes (beide Funktionen)
SK-Layout: sk[0..255] = sigma · sk[256..511] = sigma_inv · sk[512..543] = seed_T_priv · sk[544..575] = key_mac
**Verschlüsselung:**
^ Funktion ^ Beschreibung ^
| ''dadqEnc(pk, m, m_len, c)'' | Verschlüsselt m (m_len Bytes) → c (m_len + 32 Bytes) |
| ''dadqEncAlloc(pk, m, m_len)'' | Wie dadqEnc, allokiert c-Puffer selbst, Rückgabe: Zeiger |
**Entschlüsselung:**
^ Funktion ^ Beschreibung ^
| ''dadqDec(sk, c, c_len, m)'' | Entschlüsselt c → m. Rückgabe: 0=OK, -1=Authentifizierung fehlgeschlagen |
| ''dadqDecAlloc(sk, c, c_len)'' | Wie dadqDec, allokiert m-Puffer selbst, Rückgabe: Zeiger oder 0 bei Fehler |
**Symmetrischer Modus (DADQ-SYM, Phase 3):**
T_pub bleibt intern — kein col_inv-Angriff möglich, da T_pub dem Angreifer unbekannt.
^ Funktion ^ Beschreibung ^
| ''dadqSymKeyGen(seed, sk)'' | Leitet sk (576B) ab; T_pub wird intern erzeugt und nicht zurückgegeben |
| ''dadqSymEnc(sk, m, m_len, c)'' | Verschlüsselt mit sk; T_pub wird intern abgeleitet |
| ''dadqSymDec(sk, c, c_len, m): int64'' | Entschlüsselt; identisch mit ''dadqDec'' |
**Fujisaki-Okamoto Transform (DADQ-FO, Phase 4 — IND-CCA2):**
r_seed ist deterministisch: ''r_seed = HMAC-SHA256(key_fo, m)''. Ermöglicht Wiederverschlüsselung → CCA2-Sicherheit im ROM (FO-Theorem).
^ Funktion ^ Beschreibung ^
| ''dadqFOKeyGen(master_seed, sk_fo)'' | Leitet sk_fo (608B) ab: sk(576B) + key_fo(32B, SHA256(seed||0x04)) |
| ''dadqFOKeyGenRand(sk_fo)'' | Wie ''dadqFOKeyGen'' mit internem CSPRNG-Seed; Seed wird nach Ableitung gelöscht |
| ''dadqFOEnc(sk_fo, m, m_len, c)'' | Verschlüsselt deterministisch (r_seed via HMAC) |
| ''dadqFODec(sk_fo, c, c_len, m): int64'' | Entschlüsselt; prüft HMAC(key_fo, m_dec) == r_seed und SHA256(m||r_seed) == hash_mr (CT) |
**Implementierungshärtung (Phase 6):**
^ Funktion ^ Beschreibung ^
| ''dadqZeroize(buf, n)'' | Überschreibt n Bytes mit 0 (sichere Speicherlöschung, AP-6.3) |
| ''dadqValidateSeed(seed): int64'' | Prüft 32-Byte-Seed auf schwache Werte (all-zero, alle Bytes identisch); 0=OK, -1=schwach (AP-6.2) |
**Hilfsfunktionen:**
^ Funktion ^ Beschreibung ^
| ''dadqFreeCtx(p, sz)'' | Gibt allokierten Puffer frei (null-safe) |
----
===== Verwendungsbeispiele =====
**Basis-API (dadqKeyGen + dadqEnc/Dec):**
import std.crypto.pqc.dadq;
import std.crypto.rand;
import std.alloc;
fn main(): int64 {
// Symmetrischer Schlüssel: 32 Bytes CSPRNG-Zufall
var master_seed: int64 := alloc(DADQ_SEED_LEN);
RandBytesExact(master_seed, DADQ_SEED_LEN);
// Schlüssel ableiten — pk = T_pub (65536 Bytes!), sk = 576 Bytes
var pk: int64 := alloc(DADQ_PK_LEN); // 65536 Bytes
var sk: int64 := alloc(DADQ_SK_LEN_FULL); // 576 Bytes
dadqKeyGen(master_seed, pk, sk);
// Verschlüsseln (Overhead = 64 Bytes: commit + hash_mr)
var msg: pchar := "Hello, DADQ!"c;
var m_len: int64 := 12;
var c: int64 := dadqEncAlloc(pk, msg as int64, m_len);
var c_len: int64 := m_len + DADQ_OVERHEAD; // + 64
// Entschlüsseln — gibt 0 zurück wenn Authentifizierung OK
var m_out: int64 := dadqDecAlloc(sk, c, c_len);
dadqFreeCtx(m_out, m_len);
dadqFreeCtx(c, c_len);
free(sk, DADQ_SK_LEN_FULL);
free(pk, DADQ_PK_LEN);
free(master_seed, DADQ_SEED_LEN);
return 0;
}
**FO-Modus (IND-CCA2, empfohlen für neue Anwendungen):**
import std.crypto.pqc.dadq;
import std.alloc;
fn main(): int64 {
// sk_fo intern mit CSPRNG-Seed ableiten (sicherste Variante)
var sk_fo: int64 := alloc(DADQ_FO_SK_LEN); // 608 Bytes
dadqFOKeyGenRand(sk_fo);
var msg: pchar := "Hello, FO!"c;
var m_len: int64 := 10;
var c_len: int64 := m_len + DADQ_OVERHEAD;
var c: int64 := alloc(c_len);
dadqFOEnc(sk_fo, msg as int64, m_len, c);
var m_out: int64 := alloc(m_len);
var rc: int64 := dadqFODec(sk_fo, c, c_len, m_out);
dadqZeroize(sk_fo, DADQ_FO_SK_LEN);
free(m_out, m_len);
free(c, c_len);
free(sk_fo, DADQ_FO_SK_LEN);
return rc;
}
----
===== Sicherheitseigenschaften im Überblick =====
^ Eigenschaft ^ Ergebnis ^
| Klassifikation | Symmetrisches Authenticated Cipher (DADQ-SYM) |
| OW-CPA Latin-Square PKE | Unmöglich — col_inv(T_pub) in O(n²) |
| OW-Reduktion | DADQ-SYM-OW ≤ₚ SHA256-Preimage (ROM) |
| Klassische Sicherheit | 256-Bit (Schlüsselraum 2²⁵⁶) |
| Quantensicherheit (Grover) | 128-Bit (Grover-Bound: 2¹²⁸ QOps) |
| seed_D (Dimensionsvarianz) | Sicherheitsneutral; NIST SP 800-22: 0/50 Fehlschläge |
| Authentifizierung | SHA256(m||r_seed) == hash_mr + HMAC-Check (FO); constant-time; -1 bei Manipulation |
| Gröbner-Basis über GF(2⁸) | Polynomgrad von T ≈ 255 — praktisch unpraktikabel |
| IND-CCA2 | ''dadqFODec'' via FO-Transform (Phase 4); deterministisches r_seed via HMAC |
| PKE-Einsatz | Hybrid: DADQ-SYM + ML-KEM (ML-KEM kapselt master_seed) |
| NIST-Standardisierung | Keine — experimentell |
Letzte Aktualisierung: 2026-06-08