Implémentation de Kyber en Dart — xkyber_cryptoImplémentation de Kyber en Dart — xkyber_crypto

Résumé

Documentation de l'implémentation de Kyber (ML-KEM-512) en Dart/Flutter réalisée pendant la phase d'apprentissage de l'algorithme. Le dépôt xkyber_crypto implémente le schéma IND-CCA2 complet en suivant la spécification FIPS 203, incluant NTT, Compress/Decompress, CBD et le FO transform.

Archivé en novembre 2025 après avoir conclu que la gestion sécurisée de la cryptographie post-quantique en Dart est irréalisable sans garanties de temps constant au niveau de la VM.

Structure de l'Implémentation

lib/
├── params.dart           # Paramètres du schéma (KYBER_K, N, Q, η, etc.)
├── fq.dart               # Opérations arithmétiques modulo Q
├── reduce.dart           # Réduction de Barrett et Montgomery
├── ntt.dart              # NTT direct et inverse avec zetas précalculés
├── poly.dart             # Polynômes : sérialisation, compression, CBD, uniform
├── polyvec.dart          # Vecteurs de polynômes
├── gen_matrix.dart       # Génération de la matrice A du problème Module-LWE
├── indcpa.dart           # Schéma IND-CPA sous-jacent
├── kem.dart              # FO transform : KEM IND-CCA2
├── shake.dart            # SHAKE128 (Keccak) à partir de zéro
├── verify.dart           # Comparaison en temps constant et cmov
├── constant_time_comparison.dart  # Wrapper de comparaison constante
├── randombytes.dart      # Génération d'entropie (Random.secure)
├── noise_generator.dart  # Bruit déterministe (non utilisé dans le KEM principal)
├── kyber_kem.dart        # API publique d'encapsulation/désencapsulation
├── kyber_keypair.dart    # Génération de paire de clés
└── xkyber_symmetric.dart # Chiffrement symétrique AES-GCM avec la clé partagée

Extraits de Code

Paramètres du Schéma (params.dart)

L'implémentation utilise 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;

Les tailles de clés et de ciphertext sont dérivées de ces paramètres :

const int KYBER_PUBLICKEYBYTES = 800;   // pk compressé + graine
const int KYBER_SECRETKEYBYTES = 1632;   // sk complet
const int KYBER_CIPHERTEXTBYTES = 768;   // ct complet

Chaque polynôme de 256 coefficients est codé en 12 bits par coefficient (384 bytes), et la version compressée utilise 3 bits (128 bytes).

Réductions : Barrett et Montgomery (reduce.dart)

Kyber nécessite des réductions modulaires efficaces. L'implémentation inclut les deux méthodes :

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;
}

Contraste avec FIPS 203 : La spécification définit montgomeryReduce comme une opération constante dans le temps. En Dart, ~/ 65536 est une division entière que la VM de Dart pourrait optimiser en décalage de bits, mais il n'y a aucune garantie. Le compilateur JIT peut réordonner les opérations et briser le temps constant.

NTT (ntt.dart)

La NTT est le cœur computationnel de Kyber. Implémentation itérative in-place avec 128 zetas précalculés :

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 = zetasOfficiel[k];
      k++;
      for (j = start; j < start + len; j++) {
        // ... butterfly avec réduction de Montgomery
      }
    }
  }
}

Les zetas sont la racine primitive 256-ième de l'unité dans le corps modulo 3329, précalculés comme valeurs dans le domaine Montgomery :

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

Contraste avec FIPS 203 : L'accès à zetasOfficiel[k] avec k++ par itération est séquentiel et prévisible. Cependant, l'implémentation en C de référence utilise des pointeurs et un accès direct à la mémoire. En Dart, l'accès à List<int> implique une vérification de bornes et une éventuelle barrière d'écriture GC que la VM introduit sans contrôle du programmeur.

Polynômes : Compress/Decompress (poly.dart)

Compress réduit de 12 bits à 3 bits par coefficient :

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 inverse l'opération :

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

CBD — Centered Binomial Distribution (poly.dart)

Le bruit est généré par la distribution binomiale centrée avec η=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;
    }
  }
}

Contraste avec FIPS 203 : CBD implique une boucle avec décalage de bits. Dart VM ne garantit pas que la boucle for s'exécute sans interruptions du GC, sans réordonnancement par le JIT, sans branch misprediction dans le processeur.

FO Transform : KEM IND-CCA2 (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);
  }
}

Contraste avec FIPS 203 : Le FO transform est le point le plus critique pour les attaques de temporisation. La comparaison verify(c, cprime) doit être constante dans le temps. Cependant, la VM de Dart ne garantit pas que la boucle r |= a[i] ^ b[i] se compile sans branchements dépendant des données.

SHAKE128 à partir de Zéro (shake.dart)

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

Contraste avec FIPS 203 : Les performances en Dart sont significativement inférieures à celles du C optimisé. Dans les benchmarks, l'implémentation Dart peut être 10-50× plus lente que la référence en C.

Différences avec l'Implémentation de Référence (pq-crystals/C)

Conclusion

L'implémentation est fonctionnellement correcte : tous les vecteurs de test passent, l'encapsulation et la désencapsulation produisent des secrets partagés correspondants. Cependant, la correction fonctionnelle n'implique pas la sécurité cryptographique en présence d'un attaquant capable de mesurer les temps d'exécution, les accès au cache ou la consommation d'énergie.

L'archivage du dépôt reflète la conclusion que, dans l'écosystème Dart/Flutter actuel, il n'est pas possible de garantir les propriétés de temps constant que Kyber nécessite pour être sécurisé dans un environnement adversarial réel.