Implementazione di Kyber in Dart — xkyber_cryptoImplementazione di Kyber in Dart — xkyber_crypto

Riepilogo

Documentazione dell'implementazione di Kyber (ML-KEM-512) in Dart/Flutter realizzata durante la fase di apprendimento dell'algoritmo. Il repository xkyber_crypto implementa lo schema IND-CCA2 completo seguendo la specifica FIPS 203, includendo NTT, Compress/Decompress, CBD e il FO transform.

Archiviato a novembre 2025 dopo aver concluso che la gestione sicura della crittografia post-quantistica in Dart è impraticabile senza garanzie di tempo costante a livello di VM.

Struttura dell'Implementazione

lib/
├── params.dart           # Parametri dello schema (KYBER_K, N, Q, η, ecc.)
├── fq.dart               # Operazioni aritmetiche modulo Q
├── reduce.dart           # Riduzione di Barrett e Montgomery
├── ntt.dart              # NTT diretto e inverso con zeta precalcolati
├── poly.dart             # Polinomi: serializzazione, compressione, CBD, uniform
├── polyvec.dart          # Vettori di polinomi
├── gen_matrix.dart       # Generazione della matrice A del problema Module-LWE
├── indcpa.dart           # Schema IND-CPA sottostante
├── kem.dart              # FO transform: IND-CCA2 KEM
├── shake.dart            # SHAKE128 (Keccak) da zero
├── verify.dart           # Confronto in tempo costante e cmov
├── constant_time_comparison.dart  # Wrapper di confronto costante
├── randombytes.dart      # Generazione di entropia (Random.secure)
├── noise_generator.dart  # Rumore deterministico (non usato nel KEM principale)
├── kyber_kem.dart        # API pubblica di incapsulamento/disincapsulamento
├── kyber_keypair.dart    # Generazione della coppia di chiavi
└── xkyber_symmetric.dart # Cifratura simmetrica AES-GCM con la chiave condivisa

Estratti di Codice

Parametri dello Schema (params.dart)

L'implementazione usa ML-KEM-512 (NIST level 1, k=2):

const int KYBER_K = 2;
const int KYBER_N = 256;
const int KYBER_Q = 3329;
const int KYBER_ETA = 2;

Le dimensioni di chiavi e ciphertext derivano da questi parametri:

const int KYBER_PUBLICKEYBYTES = 800;   // pk compresso + seed
const int KYBER_SECRETKEYBYTES = 1632;   // sk completo
const int KYBER_CIPHERTEXTBYTES = 768;   // ct completo

Ogni polinomio di 256 coefficienti viene codificato in 12 bit per coefficiente (384 byte), e la versione compressa usa 3 bit (128 byte).

Riduzioni: Barrett e Montgomery (reduce.dart)

Kyber richiede riduzioni modulari efficienti. L'implementazione include entrambi i metodi:

int barrettReduce(int a) {
  const int v = 20159;  // floor((1<<26 + KYBER_Q/2) / KYBER_Q)
  int t = ((a * v) >> 26);
  int r = a - t * KYBER_Q;
  return r;
}

int montgomeryReduce(int a) {
  int t = (a * KYBER_QINV) % 65536;  // R = 2^16
  int r = (a + t * KYBER_Q) ~/ 65536;
  if (r >= KYBER_Q) { r -= KYBER_Q; }
  return r;
}

Confronto con FIPS 203: La specifica definisce montgomeryReduce come operazione costante in tempo. In Dart, ~/ 65536 è una divisione intera che la VM di Dart potrebbe ottimizzare a shift di bit, ma non c'è garanzia. Il compilatore JIT può riordinare le operazioni e rompere il tempo costante.

NTT (ntt.dart)

La NTT è il cuore computazionale di Kyber. Implementazione iterativa in-place con 128 zeta precalcolati:

void _nttInPlace(List<int> poly) {
  int len, start, j, k;
  int t, zeta;
  k = 1;
  for (len = 128; len >= 2; len >>= 1) {
    for (start = 0; start < 256; start = j + len) {
      zeta = zetasUfficiali[k];
      k++;
      for (j = start; j < start + len; j++) {
        // ... butterfly con Montgomery reduction
      }
    }
  }
}

Gli zeta sono la radice primitiva 256-esima dell'unità nel campo modulo 3329, precalcolati come valori in dominio Montgomery:

final List<int> zetasUfficiali = <int>[
  2285, 340, 1017, 1352, 203, 1441, 2048, 360, ...
];

Confronto con FIPS 203: L'accesso a zetasUfficiali[k] con k++ per iterazione è sequenziale e prevedibile. Tuttavia, l'implementazione in C di riferimento usa puntatori e accesso diretto alla memoria. In Dart, l'accesso a List<int> implica bounds checking e possibili gc write barrier che la VM introduce senza controllo del programmatore.

Polinomi: Compress/Decompress (poly.dart)

Compress riduce da 12 bit a 3 bit per coefficiente:

Uint8List polycompress(Poly a) {
  for (int i = 0; i < KYBER_N; i += 8) {
    int t0 = (((t.coeffs[i] << 3) + (KYBER_Q >> 1)) ~/ KYBER_Q) & 0x7;
  }
}

Decompress inverte l'operazione:

a.coeffs[i + 0] = (d0 * KYBER_Q + 4) >> 3;

CBD — Centered Binomial Distribution (poly.dart)

Il rumore viene generato mediante la distribuzione binomiale centrata con η=2:

void cbd(Poly r, Uint8List buf) {
  for (int i = 0; i < KYBER_N ~/ 8; i++) {
    int t = buf[2 * i] | (buf[2 * i + 1] << 8);
    for (int j = 0; j < 8; j++) {
      int aj = (t >> j) & 1;
      int bj = (t >> (j + 8)) & 1;
      r.coeffs[8 * i + j] = aj - bj;
    }
  }
}

Confronto con FIPS 203: CBD implica un ciclo con shift di bit. Dart VM non garantisce che il ciclo for venga eseguito senza interruzioni del GC, senza riordinamento da JIT, senza branch misprediction nel processore.

FO Transform: IND-CCA2 KEM (kem.dart)

int cryptokemdec(Uint8List ss, Uint8List c, Uint8List sk) {
  indcpaenc(cprime, mprime, pk, coinsPrime);
  int fail = verify(c, cprime) ? 0 : 1;
  if (fail == 0) {
    ssInput.setRange(0, KYBER_SYMBYTES, kprime);
  } else {
    ssInput.setRange(0, KYBER_SYMBYTES, z);
  }
}

Confronto con FIPS 203: Il FO transform è il punto più critico per attacchi di timing. Il confronto verify(c, cprime) deve essere costante in tempo. Tuttavia, la VM di Dart non garantisce che il ciclo r |= a[i] ^ b[i] venga compilato senza ramificazioni dipendenti dai dati.

SHAKE128 da Zero (shake.dart)

void _keccakf() {
  for (int round = 0; round < 24; round++) {
    // Theta, Rho, Pi, Chi, Iota
  }
}

Confronto con FIPS 203: Le prestazioni in Dart sono significativamente inferiori rispetto a C ottimizzato. Nei benchmark, l'implementazione Dart può essere 10-50x più lenta del riferimento in C.

Differenze con l'Implementazione di Riferimento (pq-crystals/C)

Conclusione

L'implementazione è funzionalmente corretta: tutti i vettori di test passano, l'incapsulamento e il disincapsulamento producono segreti condivisi coincidenti. Tuttavia, la correttezza funzionale non implica sicurezza crittografica in presenza di un attaccante in grado di misurare tempi di esecuzione, accessi alla cache o consumo energetico.

L'archiviazione del repository riflette la conclusione che, nell'ecosistema Dart/Flutter attuale, non è possibile garantire le proprietà di tempo costante che Kyber richiede per essere sicuro in un ambiente avversariale reale.