Brevet FR3141025A1 — publié le 20240419

Procédés et dispositifs de chiffrement, de génération de trappe et de détection de motif Ce procédé de chiffrement mis en œuvre dans un système définissant une clé publique (pk), pour obtenir un chiffré (C) par chiffrement de données (m) comportant des caractères élémentaires m[i], la clé publique pk comportant : - des éléments gc,i pour tout entier i entre 1 et un entier u, les éléments gc,i étant de la forme g^(ac,i) où ac,i est un entier entre 0 et un entier p-1 et g un générateur d’un groupe G ; - des éléments hk, pour tout entier k entre 1 et un entier t, les éléments hk étant de la forme g^(1/bk) où bk est un entier entre 0 et p-1.; - le générateur g ; - une description du groupe G ; et - une description d’une fonction H à valeur dans un ensemble fini, ledit procédé comportant des étapes de : - sélection (C22) d’un entier a entre 0 et p-1 ; - calcul (C24) pour tout entier k entre 1 et une entier t, d’une valeur Ek = H(hk^(a)) ; - calcul (C26) pour tout entier i entre 1 et un entier u, d’une valeur Ci égale à gm[i],i^a, - obtention (C28) du chiffré (C), ledit chiffré étant constitué des éléments {Ek, Ci}. Fig. 4 Procédés et dispositifs de chiffrement, de génération de trappe et de détection de motif Arrière-plan de l’invention L'invention se rapporte au domaine des télécommunications. Elle concerne plus particulièrement un système de chiffrement dit « cherchable », c'est- à-dire un système permettant de détecter la présence d'un motif (en anglais « pattern ») dans un flux de données chiffré. On constate aujourd’hui que la plupart, environ 90%, des flux de données échangés sur les réseaux de télécommunication sont chiffrés. C’est par exemple le cas des requêtes HTTPS ou des requêtes DNS. Ce chiffrement empêche la supervision de ces flux de données, par exemple pour la détection d’attaques (virus, déni de service, …) ou le filtrage des contenus (contrôle parental, …). Une solution pour surveiller les données chiffrées échangées entre un fournisseur de service, décrite dans le document Lin-Shung Huang, Alex Rice, Erling Ellingsen, and Collin Jackson. Analyzing forged SSL certificates, 2014 IEEE Symposium on Security and Privacy, pages 83–97. IEEE Computer Society Press, May 2014, consiste à utiliser un serveur mandataire (ou « proxy ») qui usurpe l’identité du fournisseur de service, obtient la clé de chiffrement, déchiffre les caractères, les analyse en clair, les chiffre à nouveau et les transmet à l’utilisateur. Cette solution n’est pas satisfaisante car elle révèle les données au serveur proxy. Une autre famille de solutions cryptographiques dans laquelle se situe l’invention est appelée « chiffrement cherchable » (ou « searchable encryption » en anglais). Le chiffrement cherchable permet de détecter si un flux de données comporte un chiffré d'un motif, à condition de détenir une certaine information, appelée habituellement « trappe » et associée préalablement à ce motif. Les trois documents suivants proposent de telles solutions : [1] Justine Sherry, Chang Lan, Raluca Ada Popa, and Sylvia Ratnasamy. BlindBox: Deep Packet Inspection over Encrypted Traffic. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, SIGCOMM ’15; [2] Nicolas Desmoulins, Pierre-Alain Fouque, Cristina Onete, and Olivier Sanders. Pattern matching on encrypted streams. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018; et [3] Elie Bouscatié, Guilhem Castagnos and Olivier Sanders. Public Key Encryption with Flexible Pattern Matching. ASIACRYPT 2021. La solution décrite dans [1], basée sur un chiffrement symétrique, ne permet la détection que de motifs de taille fixe. Elle est donc très limitée et en particulier n’est pas adaptée à la détection de virus dont les tailles peuvent être très variées. Les solutions décrites dans [2] et [3] sont très complexes, notamment parce qu’elles nécessitent l’usage de courbes elliptiques à couplage (de l’anglais « pairing-friendly »). La présente invention propose un système de chiffrement cherchable remédiant à des insuffisances/inconvénients de l'état de la technique et/ou y apportant des améliorations. Objet et résumé de l’invention Ainsi, et selon un premier aspect, l’invention concerne un procédé de génération d’une trappe dans un système de chiffrement , ladite trappe étant associée à un motif w comprenant des caractères élémentaires w[1], …w[v] compris dans un alphabet complété par un caractère spécial pouvant remplacer un caractère quelconque dudit alphabet, ledit système définissant une clé secrète paramétrée par des entiers n et t et comportant : - un entier a c,i pour tout caractère c de l’alphabet et pour tout entier i entre 1 et l’entier n ; et - un entier b k pour tout entier k entre 1 et l’entier t ; le procédé comportant des étapes de : - sélection d’un entier s compris entre 1 et l’entier t ; et - calcul d’une valeur T = b s *(r 1 a w[1],1 + r 2 a w[2],2 +…+ r v a w[v],v ), r i =0 si w[i] est ledit caractère spécial et r i est égal à un entier r sinon, ladite trappe comportant les éléments s, r, et T. Corrélativement, l’invention concerne un dispositif de génération d’une trappe dans un système de chiffrement , ladite trappe étant associée à un motif w comprenant des caractères élémentaires w[1], …w[v] compris dans un alphabet complété par un caractère spécial pouvant remplacer un caractère quelconque dudit alphabet, ledit système définissant une clé secrète paramétrée par des entiers n et t et comportant : - un entier a c,i pour tout caractère c de l’alphabet et pour tout entier i entre 1 et l’entier n ; et - un entier b k pour tout entier k entre 1 et l’entier t ; le dispositif comportant: - un module de sélection d’un entier s compris entre 1 et l’entier t ; et - un module de calcul d’une valeur T = b s *(r 1 a w[1],1 + r 2 a w[2],2 +…+ r v a w[v],v ), r i =0 si w[i] est ledit caractère spécial et r i est égal à un entier r sinon, la trappe comportant les éléments s, r, et T. La trappe ainsi générée permet de détecter un motif de taille quelconque dans un flux de données par le biais de la procédure de détection décrite ultérieurement. Selon un deuxième aspect, l’invention concerne un procédé de chiffrement mis en œuvre dans un système de chiffrement définissant une clé publique, pour obtenir un chiffré par chiffrement de données m comportant au moins u caractères élémentaires m[i], la clé publique comportant : - des éléments g c,i pour tout entier i entre 1 et un entier u, les éléments g c,i étant de la forme g^(a c,i ) où a c,i est un entier entre 0 et un entier p-1 et g un générateur d’un groupe G d’ordre p; - des éléments h k , pour tout entier k entre 1 et un entier t, les éléments h k étant de la forme g^(1/b k ) où b k est un entier entre 0 et p-1 ; - le générateur g ; - une description du groupe G ; et - une description d’une fonction H à valeur dans un ensemble fini, ledit procédé comportant des étapes de : - sélection d’un entier a entre 0 et p-1 ; - calcul pour tout entier k entre 1 et t, d’une valeur E k = H(h k ^(a)) ; - calcul pour tout entier i entre 1 et u, d’une valeur C i égale à g m[i],i ^a, - obtention du chiffré, ledit chiffré étant constitué des éléments {E k , C i }. Corrélativement, l’invention concerne un dispositif de chiffrement mis en œuvre dans un système de chiffrement définissant une clé publique, le dispositif étant configuré pour obtenir un chiffré C par chiffrement de données m, comportant au moins u caractères élémentaires m[i], la clé publique comportant : - des éléments g c,i pour tout entier i entre 1 et un entier u, les éléments g c,i étant de la forme g^(a c,i ) où a c,i est un entier entre 0 et un entier p-1 et g un générateur d’un groupe G d’ordre p ; - des éléments h k , pour tout entier k entre 1 et un entier t, les éléments h k étant de la forme g^(1/b k ) où b k est un entier entre 0 et p-1.; - le générateur g d’un groupe G ; - une description du groupe G ; et - une description d’une fonction H à valeur dans un ensemble fini, ledit dispositif comportant : - un module de sélection d’un entier a entre 0 et p-1 ; - un premier module de calcul pour tout entier k entre 1 et t, d’une valeur E k = H(h k ^(a)), - un deuxième module de calcul pour tout entier i entre 1 et u, d’une valeur C i égale à g m[i],i ^a, et un module d’obtention du chiffré, ledit chiffré étant constitué des éléments {E k , C i }. Les motifs et les données sont des chaînes de caractères appartenant à un alphabet. Les caractères peuvent être de n’importe quel type. Les caractères peuvent par exemple être codés sur 2 bits, 8 bits, … Les chaînes de caractères peuvent être des séquences ADN. Très avantageusement, le procédé de chiffrement s'effectue indépendamment des motifs à détecter. Ainsi, le dispositif qui chiffre le flux de données ne tient pas compte lors du chiffrement des motifs qui seront éventuellement cherchés dans le flux, ni de la taille de ces motifs. Dans un mode de mise en œuvre particulier, le dispositif qui reçoit le flux chiffré génère les trappes associées aux motifs qui sont à détecter. Il peut effectuer la détection lui-même ou confier cette tâche à un autre dispositif à qui il communique ces trappes. Selon un troisième aspect, l’invention concerne un procédé de détection, dans un système de chiffrement, d'un motif w dans un chiffré obtenu par chiffrement de données , ledit motif w comprenant des caractères élémentaires (w[1], …w[v]) compris dans un alphabet complété par un caractère spécial pouvant remplacer un caractère quelconque dudit alphabet, le procédé comprenant des étapes de : - obtention d’une trappe associée audit motif ; - calcul d’un élément Q = C 1 ^r 1 *…*C v ^r v avec r i =0 si w[i] est ledit caractère spécial et r i = r sinon ; - calcul d’une valeur D égale à Q^(1/T), où T est un élément de ladite trappe ; - calcul d’une valeur H(D) où H est une fonction H à valeur dans un ensemble fini ; - détection que les données comportent ledit motif w si H(D) est égal à E s , où s est un entier compris dans ladite trappe. Corrélativement, l’invention concerne un dispositif de détection, dans un système de chiffrement , d'un motif w dans un chiffré obtenu par chiffrement de données, ledit motif comprenant des caractères élémentaires (w[1], …w[v]) compris dans un alphabet complété par un caractère spécial pouvant remplacer un caractère quelconque dudit alphabet, le dispositif comprenant: - un module d’obtention d’une trappe associée audit motif ; - un premier module de calcul d’un élément Q = C 1 ^r 1 *…*C v ^r v avec r i =0 si w[i] est ledit caractère spécial et r i = r sinon ; - un deuxième module de calcul d’une valeur D égale à Q^(1/T), où T est un élément de ladite trappe ; - un troisième module de calcul d’une valeur H(D) où H est une fonction H à valeur dans un ensemble fini ; - un module de détection configuré pour détecter que les données comportent ledit motif w si H(D) est égal à E s , où s est un entier compris dans ladite trappe. Dans un mode de réalisation, le chiffré est obtenu par un procédé de chiffrement tel que mentionné ci-dessus et la trappe est obtenue par un procédé de génération de trappe tel que mentionné ci-dessus. Le procédé de détection de présence d’un motif est de très faible complexité par rapport aux solutions décrites dans les documents [2] et [3] introduits précédemment, ceux-ci nécessitant l’usage de courbes elliptiques à couplage. De façon avantageuse, le dispositif de détection n’a besoin d’aucune connaissance sur les données en clair qui ont été chiffrées. Le motif peut être détecté sans déchiffrer le flux de données. De façon très avantageuse, le motif peut être recherché à une position quelconque dans le flux. Conformément à l’invention, la détection s’opère sur les w premiers caractères du chiffré. Pour décaler la position du motif à détecter, il suffit de commencer ledit motif par un nombre approprié de caractères spéciaux. L’invention vise aussi un procédé de déchiffrement d'un chiffré obtenu par chiffrement de données comportant au moins u caractères élémentaires, le chiffré étant généré conformément à un procédé de chiffrement tel que mentionné ci-dessus, le procédé de déchiffrement comprenant : - obtention d'une trappe associée à chacune des données élémentaires distinctes du flux de données, ladite trappe étant générée conformément à un procédé de génération d’une trappe tel que mentionné ci-dessus, - détection de la présence de ladite trappe, conformément au procédé de détection d'un motif tel que mentionné ci-dessus. L’invention vise aussi un système de chiffrement comprenant : - un dispositif de génération de trappe, - un dispositif de chiffrement , et - un dispositif de détection de la présence d'un motif dans un chiffré tels que mentionnés ci-dessus. La présente invention peut en particulier être utilisée pour détecter des virus (en anglais « malware »), en générant des trappes associées à ces virus. Une liste de motifs pour la détection de virus est publiée à l’adresse https://www.snort.org/. La présente invention peut également être utilisée pour effectuer un contrôle parental en générant des trappes correspondant à des mots-clés à filtrer, et en bloquant les flux qui comportent ces mots-clés. Dans un mode particulier de réalisation, les différentes étapes des procédés de génération de trappe, de chiffrement et de détection sont déterminées par des instructions de programmes d'ordinateurs ou sont implémentées par une puce en silicium qui comprend des transistors adaptés pour constituer des portes logiques d'une logique câblée non programmable. En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en œuvre dans un ordinateur contrôleur, ce programme comportant des instructions adaptées à la mise en œuvre des étapes d'un procédé tel que décrit ci-dessus. 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, une mémoire non volatile de type flash ou encore un moyen d'enregistrement magnétique, par exemple un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. D’autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent des exemples de réalisation dépourvus de tout caractère limitatif. Sur les figures : La représente un système de chiffrement chiffrable conforme à un mode particulier de réalisation; La représente les principales étapes d’un procédé de génération de clés conforme à un mode particulier de réalisation ; La représente les principales étapes d’un procédé de chiffrement conforme à un mode particulier de réalisation; La représente les principales étapes d’un procédé de génération de trappe conforme à un mode particulier de réalisation; La représente les principales étapes d’un procédé de détection de présence d’un motif conforme à un mode particulier de réalisation; La représente un dispositif de chiffrement conforme à un mode particulier de réalisation; La représente un dispositif de génération de trappe conforme à un mode particulier de réalisation; La représente un dispositif de détection de présence d’un motif conforme à un mode particulier de réalisation. A noter que l’on utilise ici une notation habituelle en cryptographie dans laquelle : - « x_i » représente « x indice i », soit « xi » ; - « g^x » représente « g puissance x », soit « gx », - le produit est schématisé par un astérisque : « * » lorsque de nombreux facteurs indexés interviennent. Une notation où l’astérisque est absente est également possible : « 2n » pour « 2 * n », - l’addition est classiquement schématisée par le signe « + » lorsque de nombreux facteurs indexés interviennent. La représente un système SYS de chiffrement cherchable conforme à l’invention. Ce système SYS permet de détecter la présence d’un motif w dans un flux de données chiffré C. Sur cette figure, un dispositif de chiffrement DC chiffre des données en clair pour générer un flux de données chiffré C et pour envoyer ce flux chiffré C à un dispositif de déchiffrement RX configuré pour déchiffrer ce flux chiffré et récupérer le flux de données en clair. Le système SYS de chiffrement est basé sur un système de cryptographie à clé publique. A cette fin il repose sur une clé secrète sk et une clé publique pk associée. On suppose qu'un dispositif KG de génération de clés est agencé pour générer la paire de clés sk, pk selon une méthode connue. Un dispositif DG de génération de trappe est configuré pour générer, pour un motif w donné, une trappe TR(w) associée à ce motif. Le dispositif DG de génération de trappe est représenté indépendant mais peut par exemple être intégré dans le dispositif de déchiffrement RX. La trappe TR(w) est destinée à être utilisée par un dispositif de détection DD pour détecter la présence du motif w dans le flux chiffré. Le dispositif de génération de trappe DG est configuré pour transmettre la ou les trappes qu'elle a générées au dispositif de détection DD. Le système SYS de chiffrement comprend ainsi le dispositif de génération de trappe DG, le dispositif de chiffrement DC, et le dispositif de détection DD. Dans le mode de réalisation décrit ici, le système de chiffrement SYS utilise un groupe G d’ordre p. Ce groupe peut être quelconque, mais dans la suite de la description, il peut s’agir notamment d’un groupe de points d’une courbe elliptique, ou d’un sous-groupe multiplicatif d’un corps fini. Par la suite, les données sont traitées comme des chaînes de caractères. Ces caractères appartiennent à un alphabet S. La représente les principales étapes K10 à K28 pouvant être mises en œuvre par le dispositif KG de génération de clés conforme à un mode particulier de réalisation. La clé secrète est paramétrée par des entiers n et t. Le procédé de génération de clés comporte une première étape K10 de sélection des paramètres du système, ces paramètres comprenant : n : un nombre maximal de caractères pouvant être chiffrés par le procédé de chiffrement ; t : un entier ; p : un nombre premier ; G : un groupe d’ordre p ; g : un élément de G qui n’est pas l’élément neutre, appelé générateur ; H : une fonction H prenant en entrée n’importe quelle chaîne de bits et à valeur dans un ensemble fini D. En pratique, on pourra par exemple utiliser n’importe quelle fonction de hachage cryptographique, telle que SHA-256 ou SHA-3. Au cours d’une étape K20, le procédé de génération de clés génère une paire de clés {pk, sk} comportant une clé secrète sk et une clé publique associée pk. Au cours d’une étape K22, pour tout caractère c de l’alphabet S et pour tout entier i entre 1 et n, le procédé de génération de clés sélectionne un entier a c,i entre 0 et p-1 et calcule g c,i = g^(a c,i ) Au cours d’une étape K24, pour tout entier k entre 1 et t, le procédé sélectionne un entier b k entre 0 et p-1 et calcule h k = g^(1/b k ). Au cours d’une étape K26, le procédé définit la clé publique pk du système cryptographique comme l’ensemble constitué : - des éléments g c,i , h k et g ; - de la description du groupe G ; et - de la description de la fonction H. On note pk = {g c,i , h k , g, G, H} Au cours d’une étape K28, le procédé définit la clé secrète sk du système cryptographique comme l’ensemble constitué: - des entiers a c,i et b k ; - ou de toute information qui permet de les retrouver. On note sk = {a c,i , b k , g, G, H} De façon connue, la clé publique pk est supposée connue de tous les dispositifs du système SYS, notamment par le dispositif de chiffrement DC. La clé secrète sk est connue du dispositif de génération de trappe DT et du dispositif de déchiffrement RX. La représente les principales étapes C22 à C28 d’un procédé de chiffrement conforme à un mode particulier de réalisation. La procédé de chiffrement permet de chiffrer n’importe quelle chaîne de caractères m = m[1], m[2], …, m[u] dans lequel la taille u de cette chaîne est inférieure ou égale à la taille n maximum des données pouvant être chiffrées et déchiffrées par le système SYS. Les caractères m[i], quel que soit i, sont des éléments de l’alphabet S. Ce procédé de chiffrement utilise la clé publique pk = {g c,i , h k , g, G, H} pour chiffrer les données. Au cours d’une étape C22, le procédé de chiffrement sélectionne un entier a entre 0 et p-1. Au cours d’une étape C24, le procédé de chiffrement calcule, pour tout entier k entre 1 et t, E k = H(h k ^(a)). On rappelle ici que la fonction H prend en entrée n’importe quelle chaîne de bits et à valeur dans un ensemble fini D. Au cours d’une étape C26, le procédé de chiffrement calcule, pour tout entier i entre 1 et u, C i = g m[i],i ^a. Au cours d’une étape C28, le procédé de chiffrement obtient le chiffré C constitué de tous les éléments E k et C i. On note C = {E k , C i }. On note que ce chiffré comporte t+u éléments avec : - t : entier choisi faisant partie des paramètres du système ; et - u : taille des données à chiffrer. Dans le mode de réalisation décrit ici, le procédé de chiffrement est mis en œuvre par le dispositif de chiffrement DC et le dispositif de chiffrement DC envoie le chiffré C au dispositif de déchiffrement RX. La représente les principales étapes T22 à T26 d’un procédé de génération de trappe conforme à un mode particulier de réalisation. Le procédé de génération de trappe permet de générer une trappe pour n’importe quel motif w = w[1], w[2], …, w[v] dans lequel la taille v du motif est inférieure ou égale à la taille n maximum des données pouvant être chiffrés et déchiffrés par le système SYS, et w[i], quel que soit i, un élément de l’alphabet S ou un caractère spécial « * ». Ce procédé utilise la clé secrète sk = {a c,i , b k , g, G, H} Au cours d’une étape T22, le procédé de génération de trappe sélectionne un entier s entre 1 et t. Au cours d’une étape T24, le procédé de génération de trappe sélectionne un entier r entre 1 et p-1 et calcule T = b s *(r 1 a w[1],1 + r 2 a w[2],2 +…+ r v a w[v],v ), où : - r i =0 si w[i] est le caractère spécial «* » et - r i = r sinon. Dans un mode particulier de réalisation r = 1 pour toutes les trappes. Au cours d’une étape T26, le procédé de génération obtient la trappe TR(w) pour le motif w, avec TR(w) = {s, r, T}. On note que r n’a pas besoin d’être secret. Dans le mode de réalisation décrit ici, le procédé de génération de trappe est mis en œuvre par le dispositif de déchiffrement RX. Dans le mode de réalisation décrit ici, le dispositif de déchiffrement RX envoie la trappe TR(w) au dispositif DD de détection de présence d’un motif. La représente les principales étapes D22 à D32 d’un procédé de détection de présence d’un motif conforme à un mode particulier de réalisation. Le procédé de détection de présence d’un motif permet de tester si le motif w = w[1], w[2], …, w[v] correspond à v éléments des données m en clair qui ont été chiffrées pour générer le chiffré C = {E k , C i }, k étant compris entre 1 et t, i étant compris entre 1 et u. Ce procédé utilise : - l’alphabet S ; - l’entier t - la taille u de la chaîne de caractères en clair avant chiffrement - la longueur v du motif w - le chiffré C = {E k , C i } ; - la trappe TR(w) = {s, r, T} associée à ce motif w ; et - la fonction H. Dans le mode de réalisation décrit ici, ce procédé de détection comporte les étapes D22 à D32 suivantes. Au cours d’une étape D22, le procédé de détection calcule un élément Q = C 1 ^r 1 *…*C v ^r v avec : - r i =0 si w[i] est le caractère spécial « * » et - r i = r sinon. Au cours d’une étape D24, le procédé de détection calcule un élément D = Q^(1/T). Au cours d’une étape D26, le procédé de détection calcule H(D). Au cours d’une étape D28, le procédé de détection compare H(D) avec E s , s étant le premier élément de la trappe TR(w) et E s , l’élément de rang s du chiffré C. Si H(D) = E s , le procédé de détection détermine ou détecte (étape D30) que les données m, chiffrées en C, comportent le motif w. Sinon le procédé de détection détermine (étape D32) que les données m, chiffrées en C, ne comportent pas le motif w. Cette détection est effectuée sans déchiffrer le chiffré C. Nous apportons ci-après la preuve de la validité du chiffrement présenté ci-avant. Si un motif w = w[1],…,w[v] est présent dans des données m = m[1],…,m[u], alors w[i] = m[i] pour tout i entre 1 et v tel que w[i] est différent du caractère spécial « * ». Désignons par J l’ensemble de tels i. Alors, l’élément Q calculé à l’étape D22 est exactement le produit des C i ^r pour i appartenant à J. Comme Ci = g m[i],i ^a = g^(a*a m[i],i ) = g^(a * a w[i],i ), ce produit est exactement g^(a * r * A), où A est la somme des a w[i],i pour i appartenant à J. Ainsi Q^(1/T) permet de simplifier cette somme et donne exactement g^(a/b s ). En calculant l’image par H de cette dernière valeur on retombe exactement sur E s . A l’inverse, si le motif diffère, ne serait-ce que sur une unique position, de la suite de caractères chiffré, on peut prouver que la probabilité de retomber sur E s est d’au plus 1 /p, ce qui est négligeable en pratique. En effet, p peut être choisi par exemple proche de 2 256 . L’invention vise aussi un procédé de déchiffrement d'un chiffré obtenu par chiffrement de données comportant au moins u caractères élémentaires, le chiffré étant généré conformément à un procédé de chiffrement tel que décrit précédemment, le procédé de déchiffrement comprenant : - obtention d'une trappe associée à chacune des données élémentaires distinctes du flux de données, ladite trappe étant générée conformément à un procédé de génération d’une trappe tel que décrit précédemment, - détection de la présence de cette trappe, conformément au procédé de détection d'un motif tel que décrit précédemment. Un dispositif DG de génération de trappe dans un système de chiffrement, selon un exemple de réalisation va maintenant être décrit en relation avec la . Ce dispositif DG est un équipement informatique, tel un ordinateur. Le dispositif DG de génération de trappe comprend : - une unité de traitement ou processeur 601, ou "CPU" (de l'anglais "Central Processing Unit"), destinée à charger des instructions en mémoire, à les exécuter, à effectuer des opérations ; - un ensemble de mémoires, dont une mémoire volatile 602, ou "RAM" (pour "Random Access Memory") utilisée pour exécuter des instructions de code, stocker des variables, etc., et une mémoire de stockage 603 de type « EEPROM » (de anglais « Electrically Erasable Programmable Read Only Memory »). En particulier, la mémoire de stockage 603 est agencée pour mémoriser un module logiciel de génération de trappe qui comprend des instructions de code pour mettre en œuvre les étapes du procédé de génération de trappe tel que décrit précédemment. La mémoire de stockage 603 est également agencée pour mémoriser dans une zone sécurisée la clé secrète sk du système de chiffrement. Le dispositif DG de génération de trappe comprend également : - un module MT22 pour sélectionner un entier s compris entre 1 et t ; - un module MT24 de calcul d’une valeur T = b s *(r 1 a w[1],1 + r 2 a w[2],2 +…+ r v a w[v],v ), r i =0 si w[i] est ledit caractère spécial et r i est égal à un entier r sinon, et - un module RES pour restituer la trappe comportant les éléments s, r, et T. Un dispositif DC de chiffrement, selon un exemple de réalisation va maintenant être décrit en relation avec la . Ce dispositif DC de chiffrement est un équipement informatique, tel un ordinateur. Il comprend : - une unité de traitement ou processeur 701 , ou CPU, destinée à charger des instructions en mémoire, à les exécuter, à effectuer des opérations ; - un ensemble de mémoires, dont une mémoire volatile 702, ou RAM utilisée pour exécuter des instructions de code, stocker des variables, etc., et une mémoire de stockage 703 de type EEPROM. En particulier, la mémoire de stockage 703 est agencée pour mémoriser un module logiciel de chiffrement qui comprend des instructions de code pour mettre en œuvre les étapes du procédé de chiffrement tel que décrit précédemment. La mémoire 703 est également agencée pour mémoriser la clé publique pk du système de chiffrement. Le dispositif DC de chiffrement comprend également : - un module MC22 de sélection d’un entier a entre 0 et p-1 ; - un premier module MC24 de calcul pour tout entier k entre 1 et une entier t, d’une valeur E k = H(h k ^(a)) - un deuxième module MC26 de calcul pour tout entier i entre 1 et un entier u, d’une valeur C i égale à g m[i],i ^a, et un module MC28 d’obtention du chiffré, ledit chiffré étant constitué des éléments {E k , C i }. Un dispositif DD de détection de présence d’un motif, selon un exemple de réalisation va maintenant être décrit en relation avec la . Ce dispositif DD est un équipement informatique, tel un ordinateur. Il comprend : - une unité de traitement ou processeur 801, ou CPU, destinée à charger des instructions en mémoire, à les exécuter, à effectuer des opérations ; - un ensemble de mémoires, dont une mémoire volatile 802, ou RAM utilisée pour exécuter des instructions de code, stocker des variables, etc., et une mémoire de stockage 803 de type EEPROM. En particulier, la mémoire de stockage 803 est agencée pour mémoriser un module logiciel de détection d'un motif dans un flux qui comprend des instructions de code pour mettre en œuvre les étapes du procédé de détection de motif tel que décrit précédemment. Le dispositif DD de détection de présence d’un motif comprend également : - un module MD20 d’obtention d’une trappe TR(w) associée audit motif ; - un premier module MD22 de calcul d’un élément Q = C 1 ^r 1 *…*C v ^r v avec r i =0 si w[i] est ledit caractère spécial et r i = r sinon ; - un deuxième module MD24 de calcul d’une valeur D égale à Q^(1/T), où T est un élément de ladite trappe ; - un troisième module MD26 de calcul d’une valeur H(D) où H est une fonction H à valeur dans un ensemble fini ; - un module MD30 de détection configuré pour détecter que les données (m) comportent ledit motif (w) si H(D) est égal à E s , où s est un entier compris dans ladite trappe. Procédé de génération d’une trappe (TR(w)) dans un système de chiffrement , ladite trappe (TR(w)) étant associée à un motif w comprenant des caractères élémentaires w[1, …w[v compris dans un alphabet (S) complété par un caractère spécial pouvant remplacer un caractère quelconque dudit alphabet, ledit système définissant une clé secrète (sk) paramétrée par des entiers n et t et comportant : - un entier a c,i pour tout caractère c de l’alphabet (S) et pour tout entier i entre 1 et l’entier n ; et - un entier b k pour tout entier k entre 1 et l’entier t ; le procédé comportant des étapes de : - sélection (T22) d’un entier s compris entre 1 et l’entier t ; et - calcul (T24) d’une valeur T = b s *(r 1 a w[1],1 + r 2 a w[2],2 +…+ r v a w[v],v ), r i =0 si w[i] est ledit caractère spécial et r i est égal à un entier r sinon, ladite trappe comportant les éléments s, r, et T. Procédé de chiffrement mis en œuvre dans un système de chiffrement définissant une clé publique (pk), pour obtenir un chiffré (C) par chiffrement de données (m) comportant au moins u caractères élémentaires m[i, la clé publique pk comportant : - des éléments g c,i pour tout entier i entre 1 et un entier u, les éléments g c,i étant de la forme g^(a c,i ) où a c,i est un entier entre 0 et un entier p-1 et g un générateur d’un groupe G d’ordre p ; - des éléments h k , pour tout entier k entre 1 et un entier t, les éléments h k étant de la forme g^(1/b k ) où b k est un entier entre 0 et p-1.; - le générateur g ; - une description du groupe G ; et - une description d’une fonction H à valeur dans un ensemble fini, ledit procédé comportant des étapes de : - sélection (C22) d’un entier a entre 0 et p-1 ; - calcul (C24) pour tout entier k entre 1 et t, d’une valeur E k = H(h k ^(a)) ; - calcul (C26) pour tout entier i entre 1 et u, d’une valeur C i égale à g m[i],i ^a, - obtention (C28) du chiffré (C), ledit chiffré étant constitué des éléments {E k , C i }. Procédé de détection, dans un système de chiffrement , d'un motif (w) dans un chiffré (C) obtenu par chiffrement de données (m), ledit motif (w) comprenant des caractères élémentaires (w[1, …w[v) compris dans un alphabet (S) complété par un caractère spécial pouvant remplacer un caractère quelconque dudit alphabet, le procédé comprenant des étapes de : - obtention (D20) d’une trappe (TR(w)) associée audit motif ; - calcul (D22) d’un élément Q = C 1 ^r 1 *…*C v ^r v avec r i =0 si w[i] est ledit caractère spécial et r i = r sinon ; - calcul (D24) d’une valeur D égale à Q^(1/T), où T est un élément de ladite trappe ; - calcul (D26) d’une valeur H(D) où H est une fonction H à valeur dans un ensemble fini ; - détection (D30) que les données (m) comportent ledit motif (w) si H(D) est égal à E s , où s est un entier compris dans ladite trappe. Dispositif (DG) de génération d’une trappe (TR(w)) dans un système de chiffrement , ladite trappe (TR(w)) étant associée à un motif (w) comprenant des caractères élémentaires (w[1, …w[v) compris dans un alphabet (S) complété par un caractère spécial pouvant remplacer un caractère quelconque dudit alphabet, ledit système définissant une clé secrète (sk) paramétrée par des entiers n et t et comportant : - un entier a c,i pour tout caractère c de l’alphabet (S) et pour tout entier i entre 1 et l’entier n ; et - un entier b k pour tout entier k entre 1 et l’entier t ; le dispositif (DG) comportant: - un module (MT22) de sélection d’un entier s compris entre 1 et t ; et - un module (MT24) de calcul d’une valeur T = b s *(r 1 a w[1],1 + r 2 a w[2],2 +…+ r v a w[v],v ), r i =0 si w[i] est ledit caractère spécial et r i est égal à un entier r sinon, ladite trappe (TR(w)) comportant les éléments s, r, et T. Programme d’ordinateur pour un dispositif de génération d’une trappe dans un système de chiffrement , comprenant des instructions de code de programme destinées à commander l'exécution des étapes du procédé de génération d’une trappe selon la revendication 1, lorsque le programme est exécuté sur ledit dispositif. Dispositif (DC) de chiffrement mis en œuvre dans un système de chiffrement définissant une clé publique (pk), le dispositif étant configuré pour obtenir un chiffré (C) par chiffrement de données (m), comportant au moins u caractères élémentaires m[i, la clé publique (pk) comportant : - des éléments g c,i pour tout entier i entre 1 et un entier u, les éléments g c,i étant de la forme g^(a c,i ) où a c,i est un entier entre 0 et un entier p-1 et g un générateur d’un groupe G d’ordre p ; - des éléments h k , pour tout entier k entre 1 et un entier t, les éléments h k étant de la forme g^(1/b k ) où b k est un entier entre 0 et p-1.; - le générateur g d’un groupe G ; - une description du groupe G ; et - une description d’une fonction H à valeur dans un ensemble fini, ledit dispositif comportant : - un module (MC22) de sélection d’un entier a entre 0 et p-1 ; - un premier module (MC24) de calcul pour tout entier k entre 1 et t, d’une valeur E k = H(h k ^(a)) - un deuxième module (MC26) de calcul pour tout entier i entre 1 et u, d’une valeur C i égale à g m[i],i ^a, et un module (MC28) d’obtention du chiffré, ledit chiffré étant constitué des éléments {E k , C i }. Programme pour un dispositif de chiffrement, comprenant des instructions de code de programme destinées à commander l'exécution des étapes du procédé de chiffrement selon la revendication 2, lorsque le programme est exécuté sur ledit dispositif. Dispositif (DD) de détection, dans un système de chiffrement, de présence d'un motif (w) dans un chiffré (C) obtenu par chiffrement de données (m), ledit motif (w) comprenant des caractères élémentaires (w[1, …w[v) compris dans un alphabet (S) complété par un caractère spécial pouvant remplacer un caractère quelconque dudit alphabet, le dispositif comprenant : - un module (MD20) d’obtention d’une trappe (TR(w)) associée audit motif ; - un premier module (MD22) de calcul d’un élément Q = C 1 ^r 1 *…*C v ^r v avec r i =0 si w[i] est ledit caractère spécial et r i = r sinon ; - un deuxième module (MD24) de calcul d’une valeur D égale à Q^(1/T), où T est un élément de ladite trappe ; - un troisième module (MD26) de calcul d’une valeur H(D) où H est une fonction H à valeur dans un ensemble fini ; - un module (MD30) de détection configuré pour détecter que les données (m) comportent ledit motif (w) si H(D) est égal à E s , où s est un entier compris dans ladite trappe. Programme pour un dispositif de détection de présence d'un motif dans un chiffré, comprenant des instructions de code de programme destinées à commander l'exécution des étapes du procédé de détection de présence d'un motif dans un chiffré selon la revendication 3, lorsque le programme est exécuté sur ledit dispositif. Procédé de déchiffrement d'un chiffré (C) obtenu par chiffrement de données (m) comportant au moins u caractères élémentaires m[i, le chiffré étant généré conformément au procédé de chiffrement selon la revendication 2, le procédé de déchiffrement comprenant : - obtention d'une trappe associée à chacune des données élémentaires distinctes du flux de données, ladite trappe étant générée conformément au procédé de génération de trappe selon la revendication 1 , - détection de la présence de ladite trappe, conformément au procédé de détection d'un motif selon la revendication 3. Système de chiffrement comprenant : - un dispositif (DG) de génération de trappe selon la revendication 4, - un dispositif (DC) de chiffrement selon la revendication 6, et - un dispositif (DD) de détection de présence d'un motif dans un chiffré selon la revendication 8.