Procédé, système et dispositif de génération d'une séquence de données pseudo aléatoire.

Domaine technique de l'invention L'invention se rapporte au domaine du chiffrement/déchiffrement et concerne un système et un procédé de génération d'une séquence de données pseudo aléatoire.

L'invention trouve une application très avantageuse en ce qu'elle permet de créer des suites de bits destinées au chiffrement symétrique, pour lequel les chiffrement et déchiffrement utilisent une même clé secrète. D'une part, l'invention s'inscrit dans le cadre d'un procédé de chiffrement à flot qui consiste à additionner bit à bit un message avec une séquence de données pseudo aléatoire de même longueur. D'autre part, elle s'inscrit dans le cadre d'un procédé dans lequel l'opération de chiffrement et l'opération de déchiffrement sont identiques. On notera que, le chiffrement symétrique est employé couramment dans tous les types de communications, telles que les communications mobiles (GSM, UMTS...), l'internet (SSL...), les cartes à puce (cartes bancaires), etc.

Arrière-plan de l'invention

La technique de chiffrement symétrique la plus élémentaire est le chiffrement à flot consistant à additionner bit à bit le message clair avec une suite aléatoire de même longueur. Cette technique pose le problème essentiel et difficile de la génération de longues suites pseudo-aléatoires.

La méthode la plus répandue de chiffrement à flot consiste à utiliser une suite pseudo-aléatoire générée de manière indépendante du message à chiffrer en faisant appel, dans un but d'économie matérielle, à des registres à décalage à rétroaction linéaire.

L'inconvénient majeur des registres à décalage à rétroaction linéaire est leur linéarité. En effet, la connaissance d'un nombre de bits de sortie du registre égal à la longueur du registre ainsi que du polynôme de rétroaction associé au registre permet de connaître les bits de sortie ainsi que tous les états ultérieurs du registre.

Aussi, afin de "casser" la linéarité des registres à décalage à rétroaction linéaire, il est d'usage de combiner la sortie de plusieurs registres, ainsi, éventuellement, que leur état interne, à l'aide par exemple d'une fonction booléenne non linéaire. La figure 5 montre un tel générateur 121 appelé « shrinking generator » décrit dans la demande de brevet européen EP 0 619 659 comportant un premier registre à décalage à rétroaction linéaire 123a, un second registre à décalage à rétroaction linéaire 123b, et un moyen 125 pour sélectionner la sortie du générateur 121. A chaque décalage, les deux registres 123a et 123b sont décalés simultanément, et la sortie du dispositif 121 est égale à la sortie du deuxième registre 123b si la sortie du premier registre 123a est « 1 », sinon aucun bit n'est sorti.

Le shrinking generator permet de combiner non seulement les sorties de deux registres à décalage à rétroaction linéaire mais aussi, plus généralement, tout couple de suites de bits. Le shrinking generator fait partie d'une classe de procédés de chiffrement à flot, dans lesquels un registre à décalage à rétroaction linéaire en contrôle un autre. L'idée est de faire varier le nombre de décalages, d'une part, entre les différents registres employés et, d'autre part, entre deux bits consécutifs, afin de casser la linéarité des registres.

Une variante du shrinking generator, appelée « self-shrinking generator », repose sur le même principe, mais à partir, cette fois d'un seul registre. Les bits de sortie du registre sont lus deux à deux, et Ie

premier bit contrôle la sortie du second de sorte que la sortie du système est le second bit si le premier est « 1 », et aucun bit n'est sorti sinon.

Les inconvénients de l'emploi de registres à décalage à rétroaction linéaire seuls sont nombreux. Le principal est la faiblesse due à la linéarité du dispositif. Lorsque des registres sont combinés par une fonction booléenne, là aussi des inconvénients apparaissent. Au niveau matériel, ils proviennent de la complexité de l'implémentation de la fonction. De plus, cette fonction est fixée, et il est possible de l'attaquer.

Par ailleurs, lorsque la rétroaction des registres à décalages intervenant dans un générateur de suites pseudo-aléatoires est régulière ou facilement prédictible, le générateur est alors vulnérable aux attaques algébriques.

D'autre part, des méthodes statistiques ont mis en évidence certaines faiblesses du « shrinking generator». En particulier, dans le shrinking generator, le nombre de décalages effectués par les deux registres entre deux bits de sortie varie, mais a la même valeur pour les deux registres.

Objet et résumé de l'invention L'invention concerne un procédé de génération d'une séquence de données pseudo aléatoire à partir d'un flux de données initial comportant les étapes suivantes :

-définir un ensemble de mots de code formant un code préfixe complet,

-définir un ensemble de mots de sortie, -définir une fonction de désynchronisation associant à tout mot de code dudit code préfixe complet un mot de sortie dudit ensemble de mots de sortie,

-décomposer le flux de données initial en une suite de mots codée conformément audit code préfixe complet,

-associer les mots de ladite suite de mots codée aux mots de sortie correspondants conformément à ladite fonction de désynchronisation pour former ladite séquence de données pseudo aléatoire.

Ainsi, l'utilisation de codes préfixes complets permet une décomposition unique du flux de données initial et peut être facilement effectuée par un automate fini. De plus, ce procédé est simple à réaliser, et il utilise une fonction permettant de désynchroniser le flux de données initial pour générer une séquence de données pseudo aléatoire. En effet, l'utilisation d'un code préfixe complet et d'un "composant de désynchronisation" permet d'empêcher ou de rendre pratiquement inefficace les attaques algébriques tout en produisant un nombre minimum garanti de bits. En revanche, on notera que même si un shrinking generator est utilisé comme composant de désynchronisation dans un générateur de suites pseudo-aléatoires, le débit minimum assuré est pratiquement nul.

Avantageusement, ladite fonction de désynchronisation est une fonction paramétrée dépendant d'un paramètre prédéterminé dont la valeur est modifiable au cours de la génération de la séquence de données pseudo aléatoire. Le fait que la désynchronisation dépende d'un paramètre d'initialisation modifiable permet d'améliorer la complexité de la relation entre le flux de données initial et la séquence de données pseudo aléatoire augmentant la difficulté de prédiction de la séquence de données pseudo aléatoire. Selon une particularité de l'invention, ledit ensemble de mots de sortie comporte pour tout mot de sortie un mot de sortie complémentaire. Ceci permet d'équilibrer, pour une longueur de mot de sortie donnée, par exemple le nombre de « 0 » et de « 1 » dans l'ensemble de mots de sortie.

De préférence, les mots de code dudit code préfixe complet ont une longueur limitée par une borne supérieure h, et ledit code est tel que si un mot de sortie quelconque x est de même longueur qu'un autre mot de sortie y, alors le nombre d'antécédents par ladite fonction de désynchronisation du mot de sortie x est le même que le nombre d'antécédents par ladite fonction de désynchronisation du mot de sortie y.

Ceci garantit un débit minimum qui ne dépende pas des propriétés particulières du flux de données initial tout en permettant à la séquence de données pseudo aléatoire de présenter des bonnes propriétés statistiques. En particulier, ceci permet d'assurer que le poids de Hamming de la séquence de données pseudo aléatoire générée en sortie ne fournisse aucune information sur la séquence de données initiale. Autrement dit les bits ayant la valeur « 0 » et les bits ayant la valeur « 1 » dans la séquence de sortie contiennent la même quantité d'informations sur la séquence de données initiale.

Avantageusement, les mots dudit code préfixe complet ont une longueur limitée par une borne inférieure m, et il existe une longueur supérieure / de mots dudit code préfixe complet telle que pour toute longueur k inférieure ou égale à la longueur supérieure /, le code préfixe complet contient 2'" ^™1 mots de longueur k.

Ceci améliore encore davantage les propriétés statistiques en permettant à la séquence de données pseudo aléatoire d'avoir une distribution de probabilité optimale.

Selon un premier mode de réalisation, le procédé est caractérisé en ce que :

-le code préfixe complet est défini par un ensemble C ₁ de mots de code ayant la forme suivante ;

C ={θl"O;O ≤ w < /ι-2}u{lO"l;O < « < /î-2}u{θl" ^"I }u{lO' ^M } , avec h ≥ 2 ; -l'ensemble de mots de sortie est défini par des mots de l'ensemble binaire £, = {0,1} ;

-le paramètre prédéterminé u de la fonction de désynchronisation paramétrée est un vecteur u = (u _o ,...,u _h _ _] ) dont les composantes appartiennent à l'ensemble {0,1} ; et

-la fonction de désynchronisation paramétrée f _u est définie de la manière suivante : f _u (0f O)=U _n pour 0 < n ≤ h-2, f _u (l(Tl)≈Un® 1 pour 0 < n ≤ h-2,

f _u (Id ^1'1 )= Uh-i ⁽ B l. Ce mode de réalisation est peu coûteux à réaliser et peut être avantageusement utilisé pour implémenter un chiffrement de type matériel. De plus, le rapport entre le nombre de bits sortis (c'est-à-dire le nombre de bits de la séquence de données pseudo aléatoire) et le nombre de bits d'entrée (c'est-à-dire le nombre de bits du flux de données initial) est strictement supérieur à 1/3 et le nombre minimum garanti de bits sortis sur une entrée de longueur h est 1.

Selon un autre mode de réalisation, le procédé est caractérisé en ce que : -le code préfixe complet est défini par un ensemble G de mots de code composés de deux octets de la forme suivante C ₂ = {w,w ₂ ;w, e {θ,lf,i = 1,2/; -l'ensemble de mots de sortie est défini par des mots de l'ensemble

-le paramètre prédéterminé v de la fonction de désynchronisation paramétrée est un vecteur v = (v _o ,...,v _g ,v ₉ ) dont les composantes appartiennent à l'ensemble {θ,l}, les valeurs des huit premières composantes v _G ,...,v _g étant invariantes et Ia valeur de la dernière composante % étant variable ; et

-la fonction de désynchronisation paramétrée f _v -. C ₂ → associe à tout mot de la forme W ₁ W ₂ :

- le mot Wi si l'une des conditions suivantes est vérifiée : o 4 < wt(w, θ w ₂ ) < 8 et v _wl(u , _ιφwj) = b , wt étant le poids de Hamming, b étant un élément prédéterminé de {θ,l}, o 0 ≤ Wt(W ₁ φ w ₂ ) < 4 et v _M , _{H . _iθH . _{2 )} ≠ b , o wt{w _x θ w, ) = 4 , V ₉ = 1 , 4 < Wt(W ₁ φ W ₂ φ e) ≤ 8 et V ₄ = b , e étant un mot de {θ,l} ⁸ de poids de Hamming impair, o wt(w _x ® W ₂ ) = 4 , V ₉ = 1 , 0 ≤ wt(w _x φ w ₂ φ e) < 4 et v ₄ ≠ h , - le mot W ₂ si l'une des conditions suivantes est vérifiée : o 4 < wt(w _x φ w ₂ ) ≤ 8 et v _w/(Wiθtf2) ≠ b , o 0 < Wt(W ₁ θ W ₂ ) < 4 et v _{w/(Wi φM} , ₂ , = b , o wt(w, θ W ₂ ) = 4 , V ₉ = 1 , 4 < wt(w _x φ W ₂ ® e) ≤ 8 et V ₄ ≠ ô , o Wt(M^ ₁ θ w ₂ ) = 4 , v ₉ = 1 , 0 < Wt(Vt^ ₁ θ w ₂ θ e) < 4 et v ₄ = è , et - le mot vide f si Wt(W ₁ θ w ₂ ) = 4 et v ₉ = 0 .

Cet autre mode de réalisation peut être avantageusement utilisé pour un chiffrement de type logiciel. De plus, le rapport entre le nombre d'octets sortis et le nombre d'octets d'entrée est strictement supérieur à 1/3 et le nombre minimum garanti d'octets sortis sur une entrée de longueur h octets est 1.

L'invention vise aussi un générateur d'une séquence de données pseudo aléatoire à partir d'un flux de données initial, caractérisé en ce qu'il comporte une mémoire et une unité de traitement, ladite mémoire stockant un ensemble de mots de code formant un code préfixe complet et un ensemble de mots de sortie, ladite unité de traitement étant apte à lire et à décomposer le flux de données initial en une suite de mots codée conformément audit code préfixe complet et à associer les mots de ladite suite de mots codée aux mots de sortie correspondants

conformément à une fonction de désynchronisation pour générer ladite séquence de données pseudo aléatoire.

Ainsi, ce générateur permet de générer une séquence de données pseudo aléatoire ayant un débit minimum qui ne dépende pas des propriétés particulières du flux de données initial. De plus, ce générateur est facile à implémenter tout en étant efficace et peu coûteux.

Avantageusement, le générateur comporte en outre un moyen de paramétrage destiné à rendre ladite fonction de désynchronisation dépendante d'un paramètre prédéterminé et à modifier la valeur dudit paramètre prédéterminé au cours de la génération de la séquence de données pseudo aléatoire.

Ainsi, le fait de ne pas connaître la valeur du paramètre d'initialisation ni à quel instant elle a été modifiée augmente la difficulté de prédiction de la séquence de données pseudo aléatoire. L'invention vise aussi un dispositif de chiffrement/déchiffrement comportant une porte logique «ou-exclusif » et un générateur selon les caractéristiques ci-dessus.

Ce dispositif permet de combiner de manière simple chaque bit de la séquence de données pseudo aléatoire avec un bit correspondant d'une séquence de données d'un message à chiffrer par une addition modulo 2 pour former une séquence de données chiffrée présentant une grande complexité linéaire.

L'invention vise aussi un système sécurisé comportant au moins deux entités connectées via un réseau, chacune desdites au moins deux entités comporte un dispositif de chiffrement/déchiffrement selon les caractéristiques ci-dessus.

Ainsi, Ie système sécurisé comporte une structure simple à réaliser tout en ayant un mécanisme intrinsèquement complexe.

Brève description des dessins

D'autres particularités et avantages de l'invention ressortiront à la lecture de la description faite, ci-après, à titre indicatif mais non limitatif, en référence aux dessins annexés, sur lesquels : -la figure 1 illustre très schématiquement un procédé de génération d'une séquence de données pseudo aléatoire, selon l'invention ;

-les figures 2A et 2B montrent de manière schématique deux exemples d'automates finis permettant de décomposer un flux de données initial en une suite de mots codée selon l'invention ;

-les figures 3A et 3B illustrent des exemples schématiques d'un générateur d'une séquence de données pseudo aléatoire, selon l'invention ;

-la figure 4 montre un système sécurisé comportant des générateurs selon les figures 3A ou 3B ; et

-la figure 5 est une vue schématique d'un générateur selon l'art antérieur.

Description détaillée de modes de réalisation Conformément à l'invention, la figure 1 illustre un exemple schématique d'un procédé de génération d'une séquence de données pseudo aléatoire 1 à partir d'un flux de données initial 3.

On appelle, dans tout ce qui suit, un "mot" (ou un motif) _/ toute suite finie de lettres d'un alphabet quelconque, par exemple l'alphabet de l'ensemble binaire composé uniquement de 0 et de 1. Chaque mot comporte alors une longueur donnée. Par exemple, 0, 11, 000, 1010, 00111 sont des mots de longueurs respectives 1, 2, 3, 4 et 5. Par ailleurs, un mot "vide" noté ε est un mot de longueur nulle (c'est-à-dire, ne contenant aucune lettre).

Le flux de données initial 3 correspond à une séquence de données ayant une forte "complexité linéaire". A titre d'exemple, le flux de données initial 3 peut être engendré par un moyen de production initial 23

(voir figure 3A) comportant un registre à décalage à rétroaction linéaire de période maximale.

En effet, toute suite périodique peut être générée par une infinité de registres à décalage à rétroaction linéaire. Parmi ces registres, il en existe un qui est plus court que tous les autres. La longueur de ce plus court registre est appelé "complexité linéaire" du flux. Si la complexité linéaire de la séquence de données initiale est L ₁ alors il est possible par un algorithme de Berlekamp-Massey de reconstruire l'état initial du registre (et en fait toute la séquence) à partir d'une sous-suite de la séquence de données initiale de longueur 2L

Ainsi, afin de générer une séquence de données pseudo aléatoire en toute sécurité, il est recommandé que le flux de données initial 3 présente une forte complexité linéaire. En effet, actuellement, le meilleur algorithme connu, peut reconstituer le flux de données initial 3 en moins de 2 ⁸⁰ opérations si la complexité linéaire L de ce flux de données initial est inférieure à 160. Par conséquent, il est avantageux de prendre un flux de données initial 3 ayant une complexité linéaire L supérieure ou égale à 160.

Conformément à l'invention, on définit un ensemble de mots de code 5a formant un "code préfixe complet" 5.

On désigne par le terme générique "code" tout ensemble de mots sur un alphabet déterminé. On considère alors les propriétés de ce code relativement à l'alphabet en question.

Soit A un alphabet quelconque fixé. On considère à présent les mots composés de lettres de A, et on désigne par C un code sur A. Alors: 1) un mot x est dit "préfixe" du mot w s'il existe / tel que w=xy, cette notation signifiant que x est concaténé avec /. Si dans le code C ₁ aucun

mot du code n'est préfixe d'un autre mot du code, alors on dit que C est un "code préfixe";

2) on dit qu'un mot w esï codé par C si le mot w est la concaténation de mots de C, autrement dit, si on peut écrire avec les mots W ₁ , W ₂ ,..., w _n dans C ; alors, si pour tout mot w, il existe un mot w'tel que ww' soit codé par C ₁ on dit que C est "complet". On peut montrer que le code C est complet si, et seulement si, pour tout mot w, il existe un mot w' et un mot de code u appartenant à Ctel que /y est préfixe du mot ww', c'est-à-dire qu'il existe un mot w\ un mot de code u appartenant à Cet un mot u' tels que ww' est égal à uu'.

On dit que C est un code préfixe complet si C est à la fois un code préfixe et un code complet.

En outre, on définit un ensemble 7 de mots de sortie 7a désigné par £, tel que £est contenu dans l'union de {O,l} ^k et {ε}, et une fonction de désynchronisation / associant à tout mot de code 5a du code préfixe complet 5 un mot de sortie 7a de l'ensemble 7 de mots de sortie.

A titre d'exemple, l'ensemble 7 des mots de sortie est l'ensemble £={ε,0,l} ou £={0,1} ou E= l'union ûe{ε}et{0,l} ^8k {dNez k ≥ \ c'est-à-dire, des multiples d'octets). En particulier, afin d'équilibrer, pour une longueur de mots de sortie donnée, le nombre de « 0 » et de « 1 » dans l'ensemble de mots de sortie, il est avantageux de choisir un ensemble 7 de mots de sortie qui comporte pour tout mot de sortie 7a noté s un mot de sortie 7a complémentaire noté s .

Par ailleurs, la fonction de désynchronisation / est une opération de base (par exemple une addition bit à bit modulo 2) dont l'évaluation est peu coûteuse à réaliser.

Ainsi, Ie procédé de Ia présente invention prend en entrée un code C préfixe complet 5, un ensemble E de mots de sortie 7, et une fonction de désynchronisation / .

En outre, le procédé selon l'invention comporte une opération de décomposition 10 décomposant le flux de données initial 3 en une suite de mots codée 11 conformément audit code préfixe complet 5. En effet, l'utilisation d'un code préfixe complet 5 permet de décomposer le flux de données initial 3 de manière unique.

Avantageusement, le code préfixe complet 5 est reconnaissable par un automate fini qui, étant donné un mot W ₁ détermine si w est ou non dans le code préfixe complet 5.

En effet, les figures 2A et 2B montrent de manière schématique deux exemples d'automates finis 13a et 13b permettant de décomposer un flux de données initial 3 en une suite de mots codée 11. Un automate fini comporte un ensemble de nœuds ou d'états 15 reliés par des chemins ou flèches 17 de sorte que tout mot d'un code préfixe complet 5 peut être défini par un ensemble de chemins 17 entre un état 15 initial noté /et un état 15 final noté F. Ainsi, lorsqu'un bit est lu, on suit le chemin 17 correspondant à la valeur du bit et quand on arrive dans l'état final F ₁ on sait que l'on vient de terminer la lecture d'un mot du code préfixe complet 5 et on peut se repositionner dans l'état initial /pour lire le mot suivant.

L'exemple de la figure 2A permet de reconnaître les mots de code d'un code préfixe complet 5 défini par £={10 ^* 1, 01 ^* 0}, où 10 ^* 1 (respectivement 01 ^* 0) désigne l'ensemble des mots de la forme 10*1 (respectivement 01*0) avec k un nombre entier. On notera que 10 ⁰ I correspond au mot 11 et 01 ⁰ O correspond au mot 00. Ainsi, cet automate fini 13a permet de décomposer le flux de données initial 3 en une suite de mots codée 11 comportant des mots de la forme 10...01, 01...10, 11, et 00.

Par ailleurs, l'exemple de la figure 2B permet de reconnaître des mots de code ayant une longueur limitée par une borne supérieure h d'un code préfixe complet 5 défini par le code C=(IO^ ¹ , Ql^lO*!, 01*0, k≤h}.

En outre, le procédé selon l'invention comporte une opération d'association 20 associant les mots de la suite de mots codée 11 aux mots de sortie 7a correspondants conformément à la fonction de désynchronisation / afin de former la séquence de données pseudo aléatoire 1.

Ainsi, la mise en application du mécanisme de la présente invention concerne la décomposition 10 d'une suite d'entrée (c'est-à-dire, le flux de données initial 3) à la volée en une suite 11 de mots du code préfixe complet 5. A chaque fois qu'un mot du code préfixe complet 5 est reconnu, l'image de ce mot par la fonction de désynchronisation / produit un mot en sortie. Ce mécanisme est répété jusqu'à ce que le dernier bit de la suite d'entrée du flux de données initial 3 soit atteint ou lorsqu'une condition d'arrêt déterminée par l'utilisateur est vérifiée.

On notera que dans le cadre d'applications cryptographiques, on peut avantageusement conserver tout ou partie des données du mécanisme (code 5, fonction / ) comme données secrètes du système cryptographique.

Avantageusement, la fonction de désynchronisation / est une fonction paramétrée dépendant d'un paramètre prédéterminé dont la valeur peut être modifiée au cours de la génération de la séquence de données pseudo aléatoire 1. Cette fonction paramétrée est alors de la forme v,x κ> / _v (x) qui associe à tout vecteur binaire v de longueur m, c'est-à-dire, tout élément v de {θ,l}"' , et tout mot x du code C préfixe complet 5 un élément de l'ensemble £ de mots de sortie 7. Dans ce cas, le procédé selon l'Invention prend en entrée le flux de données initial 3 et un vecteur binaire v. Le choix de ce vecteur v peut résulter d'une opération (non-linéaire) appliquée à un vecteur d'initialisation. Bien entendu, Ie vecteur v peut prendre une valeur prédéterminée (par exemple v est le vecteur nul). Avantageusement, le

vecteur v peut être modifié au cours du déroulement du procédé et ainsi dépendre de la génération de la séquence de données pseudo aléatoire 1.

Ainsi, ce paramètre permet d'améliorer la complexité de la relation entre le flux de données initial 3 et la séquence de données pseudo aléatoire 1 augmentant la difficulté de prédiction de cette séquence de données pseudo aléatoire 1.

En outre, afin de garantir un débit minimum qui ne dépende pas des propriétés particulières du flux de données initial 3, il est avantageux que les mots de code du code préfixe complet 5 présentent une longueur limitée par une borne supérieure h et tel que si un mot de sortie quelconque Si est de même longueur qu'un autre mot de sortie s _2/ alors le nombre d'antécédents par la fonction de désynchronïsation / du mot de sortie S ₁ est le même que le nombre d'antécédents par la même fonction / du mot de sortie s, _? . Autrement dit, le code préfixe complet 5 comprend les propriétés avantageuses suivantes :

- il existe un entier /? tel que tous les mots du code C préfixe complet 5 ont une longueur inférieure ou égale à h ; et

- pour tout entier k, pour toute paire (Sj ₁ Sj) de l'ensemble E\{ε}, les nombres d'éléments de longueur k respectivement dans les ensembles f; ¹ { si} et /;' { s ₂ } sont égaux.

De plus, ceci permet d'assurer que le poids de Hamming (c'est- à-dire le nombre de bits de valeur « 1 ») de la séquence de données pseudo aléatoire 1 générée en sortie ne fournisse aucune information sur la séquence de données initiale 3. Autrement dit les bits ayant la valeur

« 0 » et les bits ayant la valeur « i » dans la séquence pseudo aléatoire 1 de sortie contiennent la même quantité d'informations sur la séquence de données initiale 3.

Avantageusement, les mots du code préfixe complet 5 ont une longueur limitée par une borne inférieure m et il existe une longueur supérieure / de mots dudit code préfixe complet telle que pour toute longueur k inférieure ou égale à cette longueur supérieure /, le code préfixe complet contient 2 ^flM mots de longueur k. Autrement dit, la fonction d'association f _v vérifie la propriété suivante : il existe un entier

/77 tel que tous les mots du code C ^* considéré ont une longueur supérieure ou égale à m, et de plus, il existe un entier / ≥ m tel que pour tout entier k supérieur ou égal à m et inférieur ou égal à /, le code C\{f ^~ \ε)} contient exactement 2 ^nM mots de longueur k.

Ainsi, avec une distribution uniforme sur le flux de données initial 3, le débit moyen est de l'ordre V , . En particulier, pour un bit donné de la séquence de données pseudo aléatoire, la probabilité que le mot de code ayant généré ce bit soit de longueur k et inversement proportionnel à k, et cela quel que soit le bit donné (0 ou 1). Ce choix de distribution de probabilité est optimal au regard des propriétés statistiques que doit satisfaire la séquence de données pseudo aléatoire 1.

A titre d'exemple et selon un premier mode de réalisation particulier de l'invention, on considère un code préfixe complet défini par un ensemble C ₁ = {orθ;θ ≤ « ≤ λ- 2}u{io ^λ i;θ < « < λ - JUIIO'" ¹ }(Où u désigne l'union), h étant un nombre entier fixé (h ≥ 2), et un ensemble de mots de sortie défini par des mots de l'ensemble binaire E ₁ ={θ,l}.

Par ailleurs, on définit un vecteur w = (« ₀ ,...,w _A _,) dont les composantes appartiennent à l'ensemble {0,1} . La fonction paramétrée f _u est définie de Ia manière suivante ; f _u (0f O)=U _n pour 0 < n ≤ h~2, f _u (1 ⁽ Tl)=U _n θ 1 pour 0 < n < h-2, (φ désigne une addition modulû 2)

Selon ce mode de réalisation, on lit le flux de données initial 3 bit par bit et pour tout mot x du code Q ₁ la valeur f _u (x) est calculée avec la connaissance du premier bit du mot x et de la valeur n (pour les mots de la forme bb"b ) ou de la valeur fixée h-1 (pour les mots de la forme

U^ ).

Afin de décrire le mécanisme de ce premier mode de réalisation, on note f _u (b,n) = f _u φb "b) = b®u _n avec 0 < n ≤ h~2 et f _u (b,h~\) = f _u φb ^h'x ) = b®u _h ^ . Par ailleurs, on dispose d'un drapeau "fïag" qui est initialisé avec la valeur 0 et prend la valeur 1 uniquement après la reconnaissance d'un mot du code Q. La valeur du drapeau est réinitialisée après chaque reconnaissance de mot. Pour chaque reconnaissance de mot, le premier bit du mot en cours est stocké de manière temporaire dans la variable c et la longueur du mot est mise à jour dans la variable "lengtH\ La valeur du bit de sortie est stockée dans la variable s.

Ainsi, ce premier mode de réalisation comporte la répétition du mécanisme suivant :

- flag±-O ; length <-0 - Lire le bit suivant b dans la suite Sdu flux de données initial 3

- c<-b

- Faire : o Lire le bit suivant b dans la suite S o Si b = c alors flagt- 1, sinon length=length+\ Tant qye {flag = 0) et length< h - 1

- . f/cφu _kιψiπ = f _u (cJength)

Ce mode de réalisation est peu coûteux à réaliser et peut être avantageusement utilisé pour ïmplémβnter un chiffrement avec des circuits électroniques de type matériel. De plus, le débit moyen, c'est-à-

dire le rapport entre le nombre de bits sortis (le nombre de bits de la séquence de données pseudo aléatoire 1) et le nombre de bits d'entrée (le nombre de bits du flux de données initial 3) est strictement supérieur à 1/3. De plus, le nombre minimum garanti de bits sortis sur une entrée de longueur h est 1.

Selon un deuxième mode de réalisation particulier de l'invention, le code préfixe complet 5 est défini par un ensemble C ₂ de mots de code composés de deux octets de la forme suivante C ₂ et l'ensemble de mots de sortie est défini par des mots de l'ensemble E ₂ = {θ,l} ⁸ u{ε}.

Par ailleurs, on définit un vecteur v = (v _o ,...,v ₈ ,v ₉ ) dont les composantes appartiennent à l'ensemble {θ,l}, les valeurs des huit premières composantes v _o ,...,v ₈ étant invariantes et la valeur de la dernière composante v ₉ étant variable. En outre, la fonction paramétrée f _v : C ₂ → {ε}u{θ,lf associe à tout mot de la forme WiW ₂ :

- le mot W ₁ si l'une des conditions suivantes est vérifiée : o 4 < Wt(W ₁ θ w ₂ ) < 8 et v _M/(M|θMθ = è , fr étant le poids de

Hamming, Jetant un élément prédéterminé de {θ,l}, o 0 ≤ Wi(W ₁ φ w ₂ ) < 4 et v _M , _{(H φ} ^ ≠ b , o Wt(W ₁ φ W ₂ ) = 4 , V ₉ = 1 , 4 < Wt(W ₎ φ w, θ e) ≤ 8 et v ₄ = b , e étant un mot de {θ,l} ⁸ de poids de Hamming impair, o Wt(W ₁ θ W ₂ ) = 4 , V ₉ = 1 , 0 < wt(w\ φ w ₂ φ e) < 4 et v ₄ ≠ b ,

- Ie mot W ₂ si l'une des conditions suivantes est vérifiée : o 4 < Wf(W ₁ θ w ₂ ) < 8 et v _{u liι@Kj :} ≠ b ,

G O ≤ Wt(W ₁ Q w ₂ ) K 4 et v _v ^e^ ≈ b , o Wi(M-, l w, ) = 4 , v _v = 1 , 4 < wt(W ₎ φ W ₂ φ e) ≤ 8 et v ₄ ≠ b ,

o Wt(W ₁ θ W ₂ ) = 4 , V ₉ = 1 , 0 < Wl(W _x θ W ₂ φ e) < 4 et V ₄ = 6 , et

- le mot vide £si w?(w, θ w ₂ ) = 4 et v ₉ = O .

Pour décrire le mécanisme de ce deuxième mode de réalisation, on fixe un entier /7 tel que h > \ et on dispose d'un drapeau "flag" qui est initialisé avec la valeur 0 et prend la valeur 1 uniquement après la reconnaissance d'un mot du code Q. Pour chaque reconnaissance de mot, le dernier octet lu est stocké de manière temporaire dans la variable c et la longueur du mot est mise à jour dans la variable "length". La valeur de l'octet de sortie est stockée dans la variable 5. La concaténation de deux octets w _x et w ₂ est notée w _x \ w ₂ .

Ainsi, ce deuxième mode de réalisation comporte la répétition du mécanisme suivant :

- flag <r- O ; length ^- O

- v ₉ <- 0 - Lire l'octet suivant octôans la suite 5

- Faire : o Lire l'octet suivant oct dans la suite 5 o S) s ≠ ε alors flag<r- 1, sinon :

• c<- oct

^« length = length +1

* Si length=h-3 , alors v ₉ <- 1

Tant que (flag = 0) - Sortir s .

Ce deuxième mode de réalisation peut être avantageusement utilisé pour un chiffrement de type logiciel. De plus, le débit moyen c'est- à-dire le rapport entre Ie nombre d'octets sortis et Ie nombre d'octets

d'entrée est strictement supérieur à 1/3 et le nombre minimum garanti d'octets sortis sur une entrée de longueur h octets est 1.

La figure 3A illustre un exemple très schématique d'un générateur 21 d'une séquence de données pseudo aléatoire 1. Le générateur 21 comporte un moyen de production initial 23 comprenant au moins un registre à décalage à rétroaction linéaire de période maximale engendrant le flux de données initial 3. Dans une suite de période maximale T, on sait que tous les mots ou motifs de longueur k (où T=^-I) apparaissent au moins une fois. Un registre à décalage à rétroaction linéaire est un tableau de bits de longueur finie (le registre) muni d'une combinaison linéaire, représentée par un polynôme appelé polynôme de rétroaction. A chaque décalage, le bit d'indice le plus élevé est sorti, tous les autres bits sont décalés d'un indice, et le bit d'indice le plus faible prend la valeur de la combinaison linéaire avant le décalage. Avantageusement, le polynôme de rétroaction peut par exemple être un polynôme primitif correspondant à un registre à décalage à rétroaction linéaire produisant une suite de période maximale, ou bien un polynôme de la forme Q = (χ ² + l)P , avec P un polynôme primitif.

En outre, le générateur 21 comporte une mémoire 25 et une unité de traitement 27. La mémoire 25 est destinée à stocker un ensemble de mots de code formant un code préfixe complet 5 et un ensemble de mots de sortie 7.

L'unité de traitement 27 est destinée à lire et à décomposer le flux de données initial 3 en une suite de mots codée 11 conformément au code préfixe complet 5 et à associer les mots de cette suite de mots codée il aux mots de sortie correspondants conformément à une fonction de désynchronisation / pour générer Ia séquence de données pseudo aléatoire. La fonction de désynchronïsation / associe à tout mot de code du code préfixe complet 5 un mot de sortie de l'ensemble de mots de sortie 7.

On notera que les opérations de décomposition 10 et d'association 20 peuvent être réalisées de manière simultanée par l'unité de traitement 27. Ainsi, l'unité de traitement 27 lit le flux de données initial 3 bit par bit et chaque fois qu'un mot du code préfixe complet 5 est trouvé, il calcul l'image de ce mot par la fonction de désynchronisation 9.

Ainsi, ce générateur est facile à mettre en œuvre et comporte des moyens de décomposition (mémoire 25 et unité de traitement 27) qui décomposent le flux d'entrée de données initial 3 de manière unique et des moyens de désynchronisation (mémoire 25 et unité de traitement 27) permettant d'engendrer une séquence de données pseudo aléatoire ayant un débit minimum qui ne dépende pas des propriétés particulières du flux de données initial 3.

La figure 3B illustre un autre exemple d'un générateur 21 d'une séquence de données pseudo aléatoire 1 qui se distingue de celui de la figure 3A par le fait qu'il comporte en outre un moyen de paramétrage 29. Ce moyen de paramétrage 29 est destiné à rendre la fonction de désynchronisation f dépendante d'un paramètre prédéterminé et à modifier la valeur de ce paramètre au cours de la génération de la séquence de données pseudo aléatoire 1. La figure 4 montre un système sécurisé 30 comportant aux moins deux entités connectées entre elles via un réseau de communication 35 de type Internet, GSM, UMTS, WiFi, UltraWideBand, etc.

L'exemple de cette figure montre une première entité 33a connectée via le réseau de communication 35 à une seconde entité 33b.

La première entité 33a (respectivement la seconde entité 33b) comporte un premier terminal 37a (respectivement un second terminal

37b), un premier dispositif de chiffrement/déchiffrement 39a

(respectivement un second dispositif de chiffrement/déchiffrement 39b) et un premier modem 41a (respectivement un second modem 41b), les

modems 41a et 41b pouvant être tout dispositif permettant de s'interfacer au réseau de communication 35.

Chacun des premier et second dispositifs de chiffrement/déchiffrement 39a, 39b comporte un générateur 21 d'une séquence de données pseudo aléatoire 1 tel que décrit précédemment et une porte logique «ou-exclusif » 43.

Chaque dispositif de chiffrement/déchiffrement 39a, 39b est destiné à faire un chiffrement ou un déchiffrement à flot qui consiste à chiffrer ou déchiffrer un message bit après bit. Selon cet exemple, le premier dispositif de chiffrement/déchiffrement 39a fait une opération de chiffrement. Ainsi, la séquence de données pseudo aléatoire 1 appelée suite chiffrante, est combinée par la porte ou-exclusif 43 avec chaque bit de position correspondante d'un message en clair 45 envoyé par le premier terminal 37a pour obtenir un texte chiffré 47 qui est ensuite envoyé par le premier modem 41a à la seconde entité 33b. Ainsi, l'opération de chiffrement consiste à ajouter bit à bit une suite chiffrante 1 au texte clair du message

45 pour obtenir le texte chiffré 47.

Le second dispositif de chiffrement/déchiffrement 39b fait une opération de déchiffrement qui consiste à ajouter bit à bit cette même suite chiffrante 1 au texte chiffré 47 envoyé par la première entité 33a pour reformer le message au texte clair 45. Ainsi, les opérations de chiffrement et de déchiffrement sont identiques.