Titre de l'invention

Générateur et procédé de génération de fonction pseudoaléatoire à clé secrète

Domaine technique de l'invention

L'invention se rapporte au domaine de génération de fonctions pseudo-aléatoires pour lesquels il existe une preuve qui relie leur sécurité à la complexité des meilleures attaques pour des schémas très simples à analyser. En particulier, l'invention relève du domaine de la cryptographie symétrique, et se rapporte à un procédé de chiffrement par blocs.

En particulier, l'invention trouve une application très avantageuse en ce qu'elle permet un chiffrement/déchiffrement symétrique présentant un grand degré de sécurité et assurant une implémentation simple et efficace en matériel et en logiciel. On notera que, le chiffrement symétrique est employé couramment dans tous les types de communications, telles que les communications mobiles, l'Internet, les cartes à puce, etc.

Arrière-plan de l'invention En cryptographie symétrique, l'émetteur et le destinataire d'un échange de données chiffrées doivent partager préalablement à tout échange la connaissance d'une clé secrète K. Des algorithmes de chiffrement et de déchiffrement paramétrés par la clé K permettent respectivement à l'émetteur de transformer un message en clair en un cryptogramme et au destinataire de recouvrer le message clair à partir du cryptogramme.

Le chiffrement par blocs constitue avec le chiffrement à flot l'une des deux principales méthodes de chiffrement symétrique. A la clé secrète K, un algorithme de chiffrement par blocs associe une fonction de chiffrement, c'est-à-dire, une transformation bijective E _κ de l'ensemble

{0,l} ⁿ des mots de n bits, également appelés blocs. Pour chiffrer un message clair M de longueur quelconque, on peut enchaîner les appels à la fonction E _κ selon différents modes opératoires.

Il existe de nombreux algorithmes de chiffrement par blocs connus, par exemple le « Data Encryption Standard » (DES), « l'Advanced Encryption Standard » (AES), MISTY, RC6, IDEA, etc. Mathématiquement, ces algorithmes de chiffrement par blocs constituent des générateurs de permutations pseudo-aléatoires, c'est-à-dire qu'à une clé relativement courte ils associent une permutation de l'ensemble des blocs de n bits de telle sorte que si la clé est choisie aléatoirement, la permutation obtenue est difficile à distinguer d'une permutation vraiment aléatoire.

Une notion voisine de celle de générateur de permutations pseudo-aléatoires est celle de générateur de fonctions pseudo-aléatoires de n bits vers m bits (où m est un entier égal ou non à ri) difficiles à distinguer de fonctions de n bits vers m bits parfaitement aléatoire. Un générateur de fonctions pseudo-aléatoires peut être utilisé selon divers modes opératoires pour la construction d'algorithmes cryptographiques et notamment d'algorithmes de chiffrement par blocs, d'authentification de message, ou de chiffrement à flot. Les algorithmes de chiffrement par blocs existants les plus utilisés et reconnus, comme I ¹ AES et le DES, opèrent sur des clés constituées d'un mot binaire relativement court et ne possédant aucune structure particulière. Ainsi par exemple, les clés secrètes du DES sont constituées de mots de longueur 56 bits, celles de l'AES de mots de longueur 128, 192 ou 256 bits. Il existe quelques rares algorithmes par blocs opérant sur des clés possédant une structure particulière qui utilise 8 permutations secrètes de l'ensemble {0,..,255} des octets, mais il n'existe pas d'argument mathématique permettant de fonder une plus grande confiance dans la sécurité de ces algorithmes que dans ceux dont la clé est constituée de mots de longueur suffisante, par exemple 128 bits.

On considère habituellement que pour qu'un algorithme par blocs (ou plus généralement un générateur de fonctions ou de permutations pseudo-aléatoires) soit sûr, il doit être impossible, compte tenu de la limitation des ressources de calcul susceptibles d'être disponibles dans les années ou décennies à venir, à un adversaire disposant d'un nombre arbitraire N d'accès "en boîte noire" aux fonctions de chiffrement et/ou de déchiffrement associées à une clé secrète inconnue K, de réaliser l'un des types d'attaque suivants : -reconstituer la clé secrète K; -plus généralement, prédire un nouveau couple de messages clair-chiffré (X,Y) satisfaisant Y = E _K (X) distincts des N couples de messages clair- chiffrés (Xi ₁ Y ₁ ) résultant des N accès de l'adversaire aux fonctions de chiffrement et/ou de déchiffrement; -plus généralement encore, distinguer avec une probabilité de succès non négligeable une fonction E _κ associée à une clé K aléatoire d'une permutation parfaitement aléatoire de l'ensemble {0, 1} ⁿ des blocs de n bits, ce au moyen d'un algorithme de test utilisant le résultat des N accès en boîte noire à la fonction et/ou à son inverse. Ceci constitue la définition la plus générale de la sécurité d'un algorithme dans le sens où se prémunir contre ce type d'attaque assure une sécurité absolue de l'algorithme d'un point de vue mathématique (i.e. hors attaques par canaux cachés, etc.).

Il est généralement admis que les ressources de calcul susceptibles d'être mises en œuvre, actuellement ou dans les années à venir, par tout adversaire (y compris une coalition de millions d'internautes) sont strictement inférieures à 2 ⁸⁰ opérations élémentaires.

Actuellement, en cryptographie à clé publique, on parle de "preuves de sécurité", de "preuves partielles de sécurité" ou de "preuves de sécurité réductionnistes" d'un schéma lorsque l'on a pu ramener de façon prouvée la sécurité de ce schéma à la résolution d'un problème réputé difficile. Les problèmes les plus classiques réputés difficiles que l'on utilise à ce jour en cryptographie à clé publique sont le problème de la

factorisation d'entiers et le problème du logarithme discret sur divers groupes finis.

Par opposition à la situation dans le domaine de la cryptographie à clé publique, la sécurité des algorithmes par blocs connus, y compris ceux qui sont considérés comme les plus sûrs comme AES, repose dans l'état actuel des connaissances sur des bases très empiriques. Pour aucun algorithme par blocs connu on ne dispose d'arguments mathématiques permettant d'établir une borne inférieure sur la complexité d'attaques de l'un des types décrits ci-dessus. Les principaux types d'arguments sur lesquels se fonde la confiance que l'on peut avoir dans la sécurité des algorithmes considérés comme les plus sûrs sont les suivants :

-absence d'attaque connue de complexité inférieure au niveau de sécurité souhaité, par exemple de complexité inférieure à 2 ⁸⁰ ou à 2 ^|K| , où \K\ est la longueur des clés de l'algorithme exprimée en bits;

-résistance prouvable à des méthodes particulières d'attaque, par exemple résistance à la cryptanalyse différentielle et la cryptanalyse linéaire;

-enfin, dans le cas de certains algorithmes comme DES, l'existence de preuves de résistance au type d'attaque le plus général mentionné ci- dessus dans le modèle de sécurité dit de Luby et Rackoff dans lequel l'on remplace certaines composantes de l'algorithme réel (par exemple les fonctions dépendant de la clé utilisées aux différents tours) par des fonctions idéales parfaitement aléatoires. Bien que ce type de preuve ne fournisse pas de borne inférieure sur la complexité d'attaques contre l'algorithme réel, il peut être considéré comme une assurance que la structure générale de l'algorithme (par exemple l'emploi du schéma dit de Feistel dans le cas du DES) ne présente pas de défaut de faiblesse intrinsèque. En particulier, il est décrit dans le document "Efficient

Symmetric-Key Ciphers Based on an NP-Complete Subproblerri ¹ de Matt

Blaze, un algorithme de chiffrement à clé secrète. Cet algorithme est construit à partir de plusieurs schémas de Feistel F ₁ imbriqués en couches. Chaque schéma de Feistel F, associe à n, bits d'entrée n, bits de sortie en un nombre de tours identique qui est égal à 4 pour chaque schéma de Feistel F, imbriqué. Or cet algorithme a été cryptanalysé par une attaque portée sur le schéma de Feistel appartenant à la couche supérieure de l'imbrication.

Il a été démontré dans les documents "Generic Attacks on Feistel Schemes ^*1 et "Security of Random Feistel Schemes with 5 or more Rounds" de J. Patarin que pour éviter cette attaque, il est nécessaire que le Schéma de Feistel de la couche supérieure de l'imbrication associe à n, bits d'entrée n, bits de sortie en au moins 6 tours. Plus particulièrement, ce document ("Security of Random Feistel Schemes with 5 or more Rounds") décrit une attaque sur les schémas de Feistel à 5 tours en 2 ^nι opérations, ce qui pour le cas de schémas de Feistel à 64 bits d'entrée donne une attaque en 2 ⁶⁴ <2 ⁸⁰ . Ainsi, il faut au moins 6 tours.

Cependant, même en prenant un nombre de tours égal à 6 pour le schéma de Feistel appartenant à la couche supérieure, il n'y a pas la garantie que ce type d'algorithme reste résistant à de futures attaques. En outre, en prenant ce même nombre de tours pour les schémas de Feistel appartenant à des couches inférieures, il pourrait toujours exister des attaques sur ces schémas, détruisant alors la sécurité de l'ensemble de l'algorithme.

Ainsi, aucune des méthodes connues de chiffrement à l'aide d'un algorithme par blocs (et plus généralement aucun algorithme de génération de fonctions ou permutations pseudo-aléatoires) ne concilie les deux conditions suivantes :

1 °) l'existence d'arguments mathématiques permettant d'étayer la conjecture que même lorsque l'on utilise l'algorithme au-delà de la distance d'unicité définie par Shannon, il n'existe aucune attaque

réalisable en moins de 2 ^e opérations, où c est un nombre suffisamment grand pour assurer une sécurité forte de l'algorithme (par exemple supérieur ou égal à 80).

2°) l'existence d'implémentations logicielles de rapidité proche de celle des algorithmes par blocs actuellement les plus utilisés, comme I ¹ AES ou le DES nécessitant des ressources de calcul (temps, mémoire, etc.) réalistes.

Objet et résumé de l'invention La présente invention concerne un procédé de génération de fonction pseudo-aléatoire à clé secrète K d'un bloc d'entrée de m bits vers un bloc de sortie de n bits utilisant un nombre déterminé α de schémas cryptographiques φi(mi,ni),..., φ,(m _ι ,n,),..., φa(m _a ,n _a ) imbriqués en couches selon une structure récursive, chaque schéma cryptographique courant φ,(m,,n _ι ) associant à m, bits d'entrée n, bits de sortie en un nombre de tours r,, chaque tour utilisant une fonction élémentaire interne f ^ή construite à partir de t, schémas cryptographiques φ _l+1 (m _l+1l n _l+1 ) de n _l+1 bits vers m, ₊₁ bits, avec n _l+1 < n,, m _l+1 < m, et t, ≥ 1, chaque schéma cryptographique φ,(m,,n,) définissant un nombre minimal d'opérations compim,, n,, r, ), dépendant dudit nombre de tours r,, nécessaire pour le distinguer d'une fonction aléatoires associant à m, bits d'entrée n, bits de sortie, pour chaque schéma cryptographique φ,(m,,ni) ledit nombre de tours r, étant choisi de sorte que ledit nombre d'opérations comp^m,, n,, r, ) qui lui est associé soit supérieur ou égal à un nombre prédéterminé 2 ^e , c étant un nombre entier.

Ainsi, en modulant le nombre de tours, on apporte une preuve de sécurité pour chacun des schémas cryptographiques et donc pour l'ensemble du procédé de génération de fonction pseudo-aléatoire. Ainsi, les meilleures attaques connues pour distinguer chaque schéma cryptographique d'une fonction aléatoire nécessitent un nombre d'étapes

de calcul supérieur ou égal au nombre prédéterminé 2 ^e qui peut être choisi très grand.

Avantageusement, ledit nombre déterminé a de schémas cryptographiques est choisi tel que les fonctions élémentaires A^ les plus internes constituant les schémas cryptographiques φa(m _a ,n _a ) de la couche la plus interne soient des fonctions aléatoires définissant une taille minimale de ladite clé secrète.

Ainsi, le procédé de génération de fonction pseudo-aléatoire présente une grande efficacité avec une clé secrète de taille raisonnable. Avantageusement, ledit nombre prédéterminé 2 ^e est égal à 2 ⁸⁰ .

Ainsi, le procédé de génération de fonction pseudo-aléatoire ne peut pas être distingué d'une fonction aléatoire associant à m bits d'entrée n bits de sortie en moins de 2 ⁸⁰ étapes de calcul, ce qui est le standard de sécurité actuel. Selon une particularité de la présente invention, lesdits schémas cryptographiques φ ₁ (mi,ni),..., φ,(m,,n,) φa(m _a ,Ha) correspondent à des schémas de permutations cryptographiques TJi(D ₁ ),..., π,(n,), ... ,IJa (Ha), chaque permutation cryptographique IJ ₁ (H ₁ ) implémentant une permutation des blocs de n, bits. Ainsi, le procédé de génération de fonction pseudo-aléatoire peut être implémenté à l'aide de schémas de permutation cryptographiques qui sont plus nombreux et mieux étudiés que les schémas cryptographiques réalisant des fonctions non bijectives. Ainsi, le procédé de génération de fonction pseudo-aléatoire peut être utilisé pour réaliser un chiffrement à clé secrète de manière simple et sécurisé.

Avantageusement, lesdits schémas de permutations cryptographiques π,(ni), ..., π,(n,), ... ,IJa (Ha) correspondent à des schémas de Feistel symétriques F ₁ (H ₁ ), ..., F ₁ (H ₁ ), ... , F _a (n _a ).

Ainsi, le procédé de génération de fonction pseudo-aléatoire peut-être implémenté de façon très efficace, les schémas de Feistel étant bien étudiés et simples à réaliser.

Pour chaque schéma de Feistel symétrique F ₁ (H ₁ ) ledit nombre de tours r, dépend du nombre de bits n, et dudit nombre entier c selon une inéquation définie par r, > 2c/n,+4.

Ainsi, le procédé de génération de fonction pseudo-aléatoire ne peut pas être distingué d'une permutation aléatoire des blocs de n bits à l'aide des attaques connues. L'invention vise aussi un procédé de chiffrement pseudoaléatoire à clé secrète K d'un bloc d'entrée de m bits vers un bloc de sortie de n bits utilisant le procédé de génération de fonction pseudo-aléatoire selon l'une quelconque des caractéristiques ci-dessus.

L'invention vise aussi un générateur de fonction pseudo- aléatoire à clé secrète K d'un bloc d'entrée de m bits vers un bloc de sortie de n bits utilisant un nombre déterminé <x de schémas cryptographiques

φi(m _1t ni),..., φ,(m,,n _t ),..., φ _a (m _a ,n _a ) imbriqués en couches selon une structure récursive, chaque schéma cryptographique courant φ,(/77,,n,J associant à m, bits d'entrée n, bits de sortie en un nombre de tours r,, chaque tour utilisant une fonction élémentaire interne f ^ή construite à partir de tι schémas cryptographiques φ _l+1 (m _l+ i,n _l+1 ) de n,+i bits vers m,+i bits, avec n _l+1 < n _h m,+i < m, et t, ≥ 1 , chaque schéma cryptographique φ,(m,,n,) définissant un nombre minimal d'opérations comp(m _h n _h r, ), dépendant dudit nombre de tours r,, nécessaire pour le distinguer d'une fonction aléatoires associant à m, bits d'entrée n, bits de sortie, le générateur comportant des moyens de calculs pour calculer, pour chaque schéma cryptographique φ,(m _h n,), ledit nombre de tours r, de sorte que ledit nombre d'opérations comp(m _h n _h r, ) qui lui est associé soit supérieur ou égal à un nombre prédéterminé 2 ^e , c étant un nombre entier.

L'invention vise aussi un dispositif de chiffrement pseudoaléatoire à clé secrète K d'un bloc d'entrée de m bits vers un bloc de sortie de n bits, le dispositif comportant un générateur de fonction pseudoaléatoire selon les caractéristiques ci-dessus. L'invention vise aussi un programme d'ordinateur téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par un microprocesseur, le programme comprenant des instructions de codes pour l'exécution des étapes du procédé de génération de fonctions pseudo aléatoire selon au moins l'une quelconque des caractéristiques ci-dessus, lorsqu'il est exécuté sur un ordinateur.

L'invention également un programme d'ordinateur téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par un microprocesseur, le programme comprenant des instructions de codes pour l'exécution des étapes du procédé de chiffrement selon les caractéristiques ci-dessus, lorsqu'il est exécuté sur un ordinateur.

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 de manière schématique un générateur de fonctions pseudo-aléatoire, selon l'invention ; -la figure 2 illustre de manière schématique un algorithme pour générer une fonction de m bits vers n bits, selon l'invention ; et

-les figures 3A à 3C illustrent de manière schématique un mode de réalisation, selon l'invention.

Description détaillée de modes de réalisation

Conformément à l'invention, la figure 1 est une figure schématique d'un générateur 1 de fonctions pseudo-aléatoire à clé secrète

K d'un bloc d'entrée 3 de m bits vers un bloc de sortie 5 de n bits. Ce générateur 1 utilise des primitives ou schémas cryptographiques φ,(m,,n,) de m, bits à n, bits.

En effet, le générateur 1 de fonction pseudo-aléatoire comporte des moyens de traitement de données ou de calcul 7 qui construisent un nombre déterminé ex de schémas cryptographiques φ _} (mi,rii),..., φι(m,,n,),..., φa(m _a ,n _a ) imbriqués en couches selon une structure récursive. Le premier schéma cryptographique est celui de la couche la plus externe et le dernier schéma cryptographique

φa(m _a ,n _a ) est celui de la couche la plus interne. Chaque schéma cryptographique courant φ,(m,,ni) associe à m, bits d'entrée n, bits de sortie en un nombre de tours r,, chaque tour utilisant une fonction élémentaire interne f'K Chaque fonction élémentaire interne f> est construite à partir de t, schémas cryptographiques φ _l+1 (m _l+1l n _l+1 ) de n, ₊₁ bits vers m, ₊ i bits, avec n _l+1 < n,, m, ₊ i < m, et t, ≥ 1.

Chaque schéma cryptographique φ,(m,,n,) est caractérisé par un nombre minimal d'opérations comp(m _h n,, r, ) nécessaire pour le distinguer d'une fonction aléatoires associant à /V ₁ bits d'entrée n, bits de sortie.

Ce nombre minimal d'opérations comp{m _h n,, r, ) est une fonction dite « de complexité » qui dépend du nombre de tours r, et éventuellement des paramètres m, et n, intervenant dans la construction des schémas cryptographique. Cette fonction de complexité est représentative de la complexité des attaques génériques (c'est-à-dire, les attaques permettant de distinguer le schéma cryptographique d'une fonction réellement aléatoires lorsque les fonctions élémentaires sont aléatoires).

Pour chaque schéma cryptographique φ^m,,/!,), les moyens de calcul 7 déterminent le nombre de tours r, nécessaire pour que le nombre minimal d'opérations comp(m _h n _tl r, ) qui lui est associé soit supérieur ou égal à un nombre prédéterminé 2 ^e , c étant un nombre entier. Selon le standard de sécurité actuel on peut choisir le nombre prédéterminé 2 ^e égal

- ₎ 80

Ainsi, le générateur 1 de la présente invention permet de générer une fonction pseudo-aléatoire de telle sorte qu'un adversaire dont la puissance de calcul est limitée à 2 ^e opérations est incapable de distinguer une fonction générée par ce générateur 1 et une clé aléatoire d'une permutation réellement aléatoire. Ceci peut être prouvé au moyen d'une preuve de sécurité qui s'appuie sur l'étude de la sécurité des "briques" intermédiaires utilisées, à savoir : -des théorèmes concernant la sécurité dite inconditionnelle de ces briques, c'est-à-dire des bornes de sécurité valables pour un attaquant ayant une puissance de calcul illimitée ;

-des conjectures, étayées par plusieurs années de recherche de la communauté cryptographique, sur la complexité des meilleures attaques possibles sur les briques utilisées (appelées "attaques génériques" car elles s'appliquent à des schémas où les fonctions élémentaires f° ^} sont des fonctions réellement aléatoires).

En outre, les moyens de calcul sont adaptés pour calculer le nombre déterminé ex de schémas cryptographiques de sorte que les fonctions élémentaires /^ les plus internes constituant les schémas cryptographiques φa(m _a ,n _a ) de la couche la plus interne soient des fonctions aléatoires définissant une taille minimale de la clé secrète K.

Avantageusement, les schémas cryptographiques

0J(IrI ₁₁ D ₁ ),..., φ,(m _h n _t ) φa(m _a ,n _a ) peuvent être bijectives et correspondre en particulier à des schémas de permutations

cryptographiques rTj(ni), ..., π,(n,), ... ,π _a (n _a ) qui sont très nombreux et bien étudiés. Chaque permutation cryptographique π,(nj implémente une permutation des blocs de n, bits.

En particulier, les permutations cryptographiques FI ₁ (Di), • • -, HiCnJ, ... ,IJ _a Cn a) peuvent correspondre à des schémas de Feistel symétriques F ₁ (IIi), ..., F ₁ (H ₁ ), ... , F _a (n _a ) qui sont simple à réaliser.

Dans ce cas, pour chaque schéma de Feistel symétrique F,(nJ le nombre de tours r, dépend du nombre de bits n, et du nombre entier c selon une inéquation définie par r, ≥ 2c/n,+4. Ainsi, en modulant selon l'invention, pour chaque schéma de Feistel

Fi, le nombre de tours nécessaire en apportant une preuve de sécurité pour chacun de ces schémas, on apporte une preuve de sécurité pour l'ensemble du procédé de génération.

La figure 2 illustre un algorithme pour générer une fonction de m bits vers n bits ou une permutation de n bits résistant à tout attaquant possédant une capacité de calculs inférieure ou égale à 2 ^e , ou c vaut par exemple 80.

Dans une première étape El, on construit cette fonction ou permutation à partir d'un certain schéma cryptographique φ ₁ Cm^n ₁ ) ou IJiCn ₁ ) (par exemple un schéma de Feistel), avec Hi ₁ =Im et D ₁ =Ii en fixant le nombre de tour ri utilisé tel que COmPCr ₁ ) = 2 ^e . Cela nécessite ri fonctions ou permutations élémentaires f ^1} .

Dans une deuxième étape E2, chacune de ces fonctions ou permutations élémentaires / ^i; va être à son tour implémentée à l'aide de U ₁ schémas cryptographiques 0 ₂ Cm^n ₂ ) ou IJ ₂ (D ₂ ) (qui peut être identique ou différent de celui de la première l'étape) en fixant le nombre de tours r ₂ utilisés tel que Comp(r ₂ ) = ¥. La construction nécessite alors ri fois ti fois r ₂ fonctions ou permuations élémentaires f* ²⁾ .

On peut ainsi continuer récursivement le procédé jusqu'à une étape E3 où les fonctions ou permutations élémentaires de la primitive cryptographique interne seront réellement aléatoires et constitueront la clé

/Cdu procédé de génération. Généralement, il existe un nombre e d'étapes qui minimisera la taille de la clé secrète.

Le générateur de fonctions de m bits vers n bits ou de permutations de n bits pseudo-aléatoires ainsi obtenu possède alors une sécurité prouvée contre tout adversaire possédant une capacité de calculs inférieure ou égale à 2 ^e dans le sens ou parvenir à attaquer le générateur 1 reviendrait à améliorer les attaques génériques sur les primitives utilisées, ce qui est très improbable. De plus, ce générateur est très pratique à utiliser car très efficace et possède une taille de clé raisonnable.

Dans le cas où l'on obtient une permutation, elle peut-être utilisée selon les modes opératoires habituels des chiffrements par blocs. Dans le cas où l'on obtient une fonction, elle peut être utilisée selon certains modes particuliers comme le mode compteur pour réaliser du chiffrement à flot ou le mode CBC MAC pour réaliser une authentification de messages.

Les constructions cryptographiques intermédiaires utilisées pour obtenir la génération d'une fonction aléatoire sont potentiellement nombreuses.

A titre d'exemple, on peut utiliser les schémas de Feistel décrits par exemple par Michael Luby et Charles Rackoff dans le document « How to Construct Pseudorandom Permutations from Pseudorandom Functions », SIAM J. Comput 17(2): 373-386 (1988). Les meilleures attaques conjecturées contre ces schémas de Feistel ont été décrites par Jacques Patarin dans le document « Generic Attacks on Feistel Schemes ». On notera qu'un schéma de Feistel est une bijection paire. Ainsi, lorsqu'on emboîte les schémas de Feistel, les schémas sont construits avec des bijections paires.

Par ailleurs, il est plus simple de distinguer un schéma de

Feistel d'une fonction aléatoire que d'une bijection. Il est aussi plus simple de distinguer un schéma de Feistel d'une bijection que d'une bijection paire. En effet, plus on essaie de distinguer un schéma de Feistel d'un ensemble grand, plus c'est simple.

En fait, quel que soit le nombre de tours du schéma de Feistel, il est toujours possible de le distinguer d'une fonction aléatoire avec 2 ⁿ opérations et d'une bijection en 2 ²ⁿ opérations (ce qui est indépendant du nombre de tours). Ce n'est que lorsqu'on essaie de le distinguer d'une bijection paire que le nombre d'opérations nécessaires augmente avec le nombre de tours du schéma de Feistel.

Les schémas de Feistel possèdent également des variantes dites généralisés ou dissymétriques.

Ainsi, pour un schéma de Feistel généralisés on peut utiliser des briques qui sont soit des fonctions aléatoires, soit des bijections aléatoires, soit des bijections paires aléatoires, typiquement cela concerne le schéma de Feistel le plus interne dans l'imbrication.

Typiquement, les schémas de Feistel n'utilisant comme brique que des bijections paires, sont des schémas de Feistel de niveau supérieur par rapport au schéma de Feistel le plus interne.

Pour les schémas de Feistel asymétriques, le texte en clair est divisé en deux blocs de taille différente, plus particulièrement, cela peut concerner le schéma de Feistel de niveau inférieur.

Par ailleurs, pour les schémas de Feistel symétriques, le texte en clair est divisé en deux blocs de taille identique. En particulier, cela concerne les schémas de Feistel de niveau supérieur.

En outre, pour les constructions cryptographiques intermédiaires, on peut aussi créer une fonction de n bits vers n bits à partir de deux permutations aléatoires P, et P _j de n bits vers n bits en calculant le ou exclusif « XOR » bit à bit de la sortie des deux

permutations (P, XOR P ₃ ). Des preuves de sécurité inconditionnelles existent aussi pour cette construction (par exemple, dans le document de Jacques Patarin « On Linear Systems of Equations with Distinct Variables and Small Block Size », ICISC 2005: 299-32). On peut aussi utiliser les schémas dits « de Benes » qui permettent d'obtenir des fonctions de 2n bits vers 2n bits à partir de fonctions aléatoires de n bits vers n bits. Des preuves de sécurité inconditionnelles existent aussi pour ces schémas.

Ainsi, il est possible de réaliser la présente invention selon plusieurs modes de réalisation.

En effet, les figures 3A à 3C illustrent un mode de réalisation pour la génération d'une fonction pseudo-aléatoire parmi les nombreux exemples possibles, selon l'invention.

On utilise pour cet exemple des schémas de Feistel F,(n,) symétriques à r, tours et la construction P, XOR P _j pour obtenir une permutation pseudo-aléatoire IJj ₂₈ de 128 bits vers 128 bits, avec une sécurité en 2 ⁸⁰ opérations.

Les figures 3A à 3C décrivent les différentes étapes de la construction en partant de l'étape la plus externe (figure 3A) vers l'étape la plus interne (figure 3C).

Ainsi, l'étape de la figure 3A est constituée d'un schéma de

Feistel à r _? tours, où n est déterminé par le critère de sécurité suivant : les meilleures attaques conjecturées sur un schéma de Feistel à r _? tours ont une complexité en 2f ^rl'4)n opérations, où n est la moitié du nombre de bits des blocs chiffrés.

Si l'on veut que cette complexité soit supérieure à 2 ⁸⁰ , il faut prendre r _? = 6. En se contentant de cette seule étape, on a besoin pour la clé de 6 fonctions élémentaires (aléatoires et indépendantes) f/ ^υ ,..., f/ ^1J de 64 bits vers 64 bits, donc la taille totale de la clé est 6x64x2 ⁶⁴ bits, ce qui est trop grand pour être utilisé en pratique.

Alors, on cherche à obtenir les 6 fonctions de 64 bits vers 64 bits à partir d'une seconde étape (figure 3B). Pour cela, on utilise la construction P, XOR P ₁ , appliquée à deux schémas de Feistel à r ₂ tours de 64 bits vers 64 bits. Les 6 fonctions élémentaires fi ⁽¹⁾ ,..., f/ ^1J ainsi obtenues seront utilisées pour construire le schéma de Feistel de l'étape décrite précédemment. Le même critère qu'auparavant montre qu'il faut utiliser r ₂ = 7 tours pour obtenir des permutations de 64 bits vers 64 bits non distinguables de permutations aléatoires en moins de 2 ⁸⁰ calculs. Chacune des 6 fonctions élémentaires f/ ^1J ,..., f/ ^1J nécessaires pour construire le schéma de Feistel de l'étage supérieur requiert 2x7 fonctions élémentaires de 32 bits vers 32 bits, donc la taille totale de la clé à cette étape est 6x(2x7)x32x2 ³² bits. Par souci de simplification, la figure 3B illustre la construction de la fonction élémentaires f/ ^υ de l'étape supérieur (figure 3A) à partir des 14 fonctions élémentaires fij ²⁾ ,..., Bien entendu, on peut continuer cette construction jusqu'à ce que la brique de base de la construction soit constituée de fonctions élémentaires de 1 bit vers 1 bit. Cependant il existe un nombre d'étapes pour lequel la taille de la clé est minimale.

En effet, pour les paramètres (taille de blocs de 128 bits, niveau de sécurité de 2 ⁸⁰ opérations), le nombre d'étapes optimal est de 4 (figure 3C). Par souci de simplification, la figure 3C illustre la construction de la fonction élémentaires fij ³⁾ de l'étape supérieur (non représentée) à partir des 28 fonctions élémentaires fij ⁴⁾ ,..., fi4,2 ⁽⁴⁾ .

Dans ce cas, le nombre de tours des schémas de Feistel à utiliser est respectivement n = 6, r ₂ = 7, r ₃ = 9 et r ₄ = 14. Les fonctions de base nécessaires sont alors des fonctions de 8 bits vers 8 bits et la taille de la clé est donnée par 6x(2x7)x(2x9)x(2xl4)x8x2 ⁸ bits, soit 10,8 Mo, ce qui est tout à fait à la portée des capacités mémoire des ordinateurs personnels actuels.

L'invention vise aussi un programme d'ordinateur téléchargeable depuis un réseau de communication comprenant des instructions de codes de programme pour l'exécution des étapes du procédé de génération et/ou du procédé de chiffrement selon l'invention lorsqu'il est exécuté sur un ordinateur. Ce programme d'ordinateur peut être stocké sur un support lisible par ordinateur.

Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable.

L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus. Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy dise) ou un disque dur.