title: F-FCSR
text: # F-FCSR
  
  En cryptographie, F-FCSR est un algorithme de chiffrement appartenant à la famille des algorithmes de chiffrements de flux. Il est basé sur l'utilisation d'un registre à décalage à rétroaction avec retenue (FCSR), ce qui est similaire à un LFSR au détail près que les opérations sont faites avec retenue, de manière à rendre la fonction de transition non-linéaire. L'idée du chiffrement fut proposée par Thierry Berger, François Arnault et Cédric Lauradoux. F-FCSR était candidat au concours eSTREAM et fut inclus dans la liste des gagnants du concours en avril 2008. Cependant, après la mise en évidence de faiblesses cryptographiques, F-FCSR fut retiré de la liste eSTREAM en septembre 2008.
  
  ## Caractéristiques des versions
  
  | Nom | Taille du registre principal | Initialisation | Filtre | Nombre de bits à la sortie du filtre |
  | - | - | - | - | - |
  | F-FCSR-8 | 128 | 64/128 tics (dépend du vecteur d'initialisation) | Dépend de la clé | 8 |
  | F-FCSR-H | 160 | 160 tics | Statique | 8 |
  | F-FCSR-8.2 | 256 | 258 tics | Dépend de la clé | 16 |
  | F-FCSR-16 | 256 | 16 + 258 tics | Statique | 16 |
  | F-FCSR-H v.2 | 160 | 20 + 162 tics | Statique | 8 |
  
  ## Description de l'algorithme
  
  ### FCSR
  
  Il existe deux modes de connexion pour les FCSR : le mode dit de « Galois » et le mode dit de « Fibonacci ». Pour F-FCSR, on utilise le mode de Galois, puisqu'il est efficace. On introduit les notations suivantes :
  
  * q — entier de connexion du FCSR. C'est un nombre impair à valeur négative, satisfaisant les conditions suivantes :
     * $2^{|q|-1}=1\mod {q}$
     * T = (|q| − 1)/2, où 2T est la période de la séquence binaire p/q
  * p — paramètre dépendant de la clé, tel que 0 < p < |q|
  * n — taille du registre principal du FCSR. |q|, en écriture binaire, possède n + 1 bits, c'est-à-dire $2^n$ < −q < $2^{n+1}$
  * d: d = (1 − q)/2, en écriture binaire $\sum _{i=0}^{n-1}d_{i}\cdot 2^{i}$, $d_i$ = {0, 1}, $d_{n-1}$ = 1
  * M — registre principal (codé sur n bits). L'entier $m(t)=\sum _{i=0}^{n-1}m_{i}(t)\cdot 2^{i}$ représente le contenu de M.
  * C — registre de retenue (codé sur l bits), où l + 1 est le poids de Hamming de la représentation binaire de d. L'entier $c(t)=\sum _{i=0}^{l-1}c_{i}(t)\cdot 2^{i}$ représente le contenu de C.
  * (m, c) — état du FCSR (correspondant à M = m et C = c)
  
  Si (m, c) est l'état du FCSR à un moment $t_0,$ avec $m=m(t_{0})$, $c=c(t_{0})$, alors $(m_{0}(t_{0}+i))_{i\in {N}}$ est la représentation binaire de p/q, où p = m + 2c.
  
  ### Filtrage d'un bit
  
  Le filtre F est la séquence de bits (${f}_{0,}{f}_{1,...,}{f}_{n-1}$) de taille n. Un bit de sortie est obtenu en calculant : ${k}=\bigoplus _{i=0}^{n-1}{f}_{i}\cdot {m}_{i}$
  
  ### Initialisation
  
  Étant donné les faiblesses des précédentes versions de F-FCSR dues à un faible mélange initial des bits dans le registre principal, la procédure d'initialisation, pour F-FCSR-H v.2 et F-FCSR-16, se passe de la manière suivante :
  
  * On initialise le registre principal M avec la concaténation de la clé secrète K et du vecteur d'initialisation (IV) : (K, IV), on initialise le registre de retenue à 0.
  * On fait passer 16 tics d'horloge pour F-FCSR-16 et 20 pour F-FCSR-H v.2
  * On récupère, sur la sortie, 256 et 160 bits respectivement, que l'on met dans M
  * On fait passer n + 2 tics d'horloge (les bits en sortie sont jetés durant cette étape)
  
  **Exemple de FCSR**
  
  q = −347, d = 174 = $(10101110)_2,$ n = 8, l = 4.
  
  