Admin CliCours
Crypto système symétrique
Dans un cryptosystème symétrique, une même clé est employée pour le chiffrement et le déchiffrement d’un message. Cette clé est donc privée et ne doit en aucun cas être rendue publique. Par conséquent, lorsque deux entités, nommées Alice et Bob, veulent s’échanger un message, ils doivent auparavant s’échanger la clé de façon sécurisée p. ex. lors d’une rencontre en présentiel. Problème : Alice veut envoyer une lettre à Bob. Elle ne fait pas confiance au facteur qui peut ouvrir la lettre avant de la poster. Comment échanger des lettres sans que le facteur puisse accéder au contenu de la lettre ? Solution : Une méthode symétrique pour résoudre ce problème est l’achat d’une boîte avec un cadenas. Au préalable, Alice prend une boîte et un cadenas et donne un exemplaire de la clé du cadenas à Bob en toute discrétion lors d’une rencontre. Puis, Alice et Bob peuvent s’échanger des messages : l’un comme l’autre peut mettre un message dans la boîte et refermer celle-ci à l’aide du cadenas. Chacun possédant une clé, ils peuvent tous deux ouvrir le cadenas et découvrir le message que la boîte contient. Le facteur n’a pas la clé et ne peut donc pas obtenir le message contenu dans la boîte. Dans cet exemple, le cadenas représente la fonction de chiffrement et la clé du cadenas est la clé privée. Le message clair est le message mis dans la boîte et le message chiffré est la boîte contenant le message.
La cryptographie symétrique est le type de cryptographie utilisé depuis l’Antiquité. Les premiers algorithmes de substitutions monoalphabétique ou polyalphabétique consistant en des décalages de lettres sont symétriques. Dans un chiffrement par substitution monoalphabétique, chaque lettre de l’alphabet est chiffrée de la même façon p. ex. « A » est toujours chiffré en « D ». Le chiffrement d’une lettre peut différer dans un chiffrement par substitution polyalphabétique p. ex. « AA » peut être chiffré en « CD ». Commercialisée et vendue à partir de 1923, la machine à chiffrer électromécanique Enigma [Tur40] est également symétrique et consiste en une substitution polyalphabétique. Enigma fut utilisée principalement durant la Seconde Guerre Mondiale et fut cassée par Alan Turing pendant la guerre [DPT]. Les cryptosystèmes symétriques actuels sont soit par bloc, soit par flot. Un chiffrement symétrique par bloc consiste à décomposer le message à chiffrer en bloc de b bits. Chaque bloc est ensuite chiffré en suivant un mode d’opérations c-à-d suivant une procédure de traitement des blocs. Le mode d’opérations le plus simple est de chiffrer chaque bloc indépendamment des autres et de concaténer les blocs résultats : cette méthode est appelée ECB pour Electronic Code Book. Cependant, d’autres modes sont utilisés en pratique dans le but d’augmenter le niveau de sécurité p. ex. CBC pour Cipher Block Chaining [EMST78]. Un chiffrement symétrique par flot nécessite d’un générateur de nombre pseudo-aléatoire (PRNG, pour Pseudo-Random Number Generator).
Un PRNG est utilisé pour générer une suite de nombre pseudo-aléatoire. La fonction OU exclusif (ou XOR, pour eXclusive OR) est appliquée entre cette suite et les bits du message à chiffrer. Un XOR, noté _, est un opérateur logique tel que : 0 _ 0 = 0, 1 _ 0 = 1, 0 _ 1 = 1 et 1 _ 1 = 0. Le One Time Pad (OTP) est un chiffrement symétrique par flot considéré comme cryptographiquement sûr. La clé symétrique consiste en une suite de nombres aléatoires aussi grande que le message à chiffrer. Le chiffrement est la fonction XOR appliquée entre la clé symétrique et le message. Bien que ce cryptosystème soit sûr, l’échange de clé revient au même problème que d’échanger le message en clair, vu que la clé est aussi longue que le message. Le cryptosystème symétrique le plus utilisée de nos jours est l’AES [DR99] pour Advanced Encryption Standard qui est un système de chiffrement par bloc. L’AES a la structure d’un réseau de substitution-permutation. Un bloc de message de clair passant par ce type de réseau va passer dans un enchaînement de transformations, chacune correspondant soit à une substitution, soit à une permutation. Par conséquent, l’AES est une succession de plusieurs rondes, chacune composée de fonctions de substitution et de permutation. Suite à ces transformations, le message obtenu est XORé avec la clé de ronde en fin de ronde.
Usage de la cryptographie
De manière générale, les cryptosystèmes asymétriques sont plus lents que les symétriques. En revanche, la gestion des clés pour un cryptosystème asymétrique est plus facile : en effet, chaque correspondant doit posséder sa propre paire clé publique/privée. Dans un cryptosystème symétrique, chaque utilisateur doit posséder une clé privée pour chaque correspondant. De plus, l’envoi préliminaire de la clé privée (partagée entre les deux entités) doit être impérativement fait à travers un canal de communication sécurisé. Ce problème n’est pas présent pour un cryptosystème asymétrique. En effet, la clé servant au chiffrement est publique. Afin d’employer au mieux les deux types de cryptosystèmes et de profiter des avantages de chacun, il est préférable de chiffrer les messages avec un cryptosystème symétrique. La clé privée symétrique est ensuite chiffrée avec un cryptosystème asymétrique pour être envoyée au destinataire avec le message chiffré en symétrique. Cette méthode d’utilisation de la cryptographie permet d’échanger des informations de manière sécurisée p. ex. entre un client et sa banque, entre un patient et son médecin, entre les membres d’une famille,… Il en est de même quand un utilisateur se connecte et utilise un site internet ou une application sur son smartphone : les données personnelles de l’utilisateur envoyées sur le serveur du site ou de l’application sont protégées car chiffrées.
Les sites ou applications sensibles peuvent être, par exemple, d’ordre militaires, bancaires, conversationnelles, sociales, économiques ou médicales. Pour toutes ces sites ou applications, les deux entités échangeant des informations se font mutuellement confiance : en effet, chacune va avoir accès aux données en clair. Les tierces personnes, autres que les deux entités concernées, ne pourront en aucun cas avoir accès aux informations déchiffrées. Lorsqu’un utilisateur discute avec un ami à travers, p. ex. l’application WhatsApp, les deux entités se connaissent et se font mutuellement confiance. De plus, sur WhatsApp, les données sont dites « protégées avec le chiffrement de bout en bout. Cela signifie que WhatsApp et les tiers ne peuvent pas les lire » 2. Dans cet exemple, la sécurité repose exclusivement sur la capacité de chiffrement utilisé par WhatsApp. Cependant, la plupart du temps, la sécurité repose sur la confiance portée en l’application. Prenons l’exemple de l’application Samsung Health 3 installée automatiquement sur tous les smartphones Samsung. Cette application permet entre autre de calculer les calories gagnées/perdues en fonction du sport réalisé et des repas consommés dans la journée. Pour cela, dès l’inscription, l’utilisateur doit rentrer certaines informations personnelles comme son genre, sa date de naissance, sa taille, son poids et son niveau d’activité. Ensuite, chaque jour, l’utilisateur peut renseigner quel sport il a pratiqué, pendant combien de temps ainsi que tous les aliments consommés dans la journée avec leur proportion. Ainsi, l’utilisateur peut voir le nombre de calories perdues (grâce au sport) et gagnées (suite aux repas).
Analyse de la complexité algorithmique
La complexité algorithmique ou complexité 1 d’un algorithme peut être estimée dans le pire cas. Pour que cette estimation pire cas soit au plus juste, le nombre d’opérations effectuées au pire cas pendant l’algorithme doit être déterministe. Par exemple, afin de calculer précisément la complexité au pire cas d’un algorithme, celui-ci ne doit pas posséder de boucle ayant un nombre non borné d’itérations non déterministe c-à-d qui diffère d’une exécution à l’autre de l’algorithme. Parmi les schémas cités dans 3.2, seul le schéma [DGHV10] possède une boucle non bornée. Dans ce schéma, les opérations sont effectuées modulo p. La boucle est présente dans la génération de clés : des entiers doivent être échantillonnés à partir d’une distribution tant que le plus grand d’entre eux est impair et que son reste modulo p est pair. La condition étant probabiliste et non bornée, la complexité de cette boucle est difficile à quantifier. Une solution pour gérer ce problème est d’estimer le nombre d’itérations moyen en exécutant plusieurs fois le calcul. Coron et al. [CMNT11] ont créé une variante du schéma [DGHV10] avec une clé publique compressée. Cette version ne possède plus la boucle non-déterministe décrite dans ce paragraphe. Les schémas de chiffrement homomorphe possèdent donc que très rarement des boucles non bornées. Afin de pouvoir effectuer une analyse de complexité de schémas de chiffrement homomorphe au pire cas, ce type de boucle peut être éviter soit en estimant un nombre d’itérations de la boucle en moyenne, soit en modifiant le schéma afin de retirer la boucle. L’objectif est de pouvoir analyser plusieurs schémas en fonction de leurs paramètres d’entrée. Ces analyses permettront d’évaluer l’influence des paramètres d’entrée. De plus, elles faciliteront la comparaison des schémas entre eux. Dans nos travaux, la complexité est le nombre d’opérations effectuées lors d’un algorithme.
Ce nombre est déterminé sur la base de 8 opérations : addition, soustraction, multiplication, division, modulo, tirage aléatoire, arrondi et puissance. Ces opérations correspondent aux algorithmes atomiques utiles à la modélisation sauf les algorithmes de l’inverse, du produit scalaire et de décomposition binaire. En effet, la complexité de ces trois algorithmes peut être calculée avec les 8 opérations citées ci-dessus. Les complexités produites par ces opérations sont différentes si elles sont réalisées avec des entiers ou des polynômes. Par conséquent, la complexité est représentée sous la forme d’un tableau à deux dimensions : une dimension pour les 8 opérations citées et une autre dimension pour le type des objets manipulés (INT pour entiers et POLY pour polynômes). Ce tableau est appelée le tableau de la complexité ou complexity dans les algorithmes. TABLE 3.3 – Représentation de la complexité après l’analyse de l’Algorithme 6 appelé distriLWE qui retourne une distribution LWE. Chaque Atomique, Spécifique et Homomorphe basique va être lié à un algorithme d’analyse de la complexité. Ces algorithmes d’analyse ont pour objectif de mettre à jour le tableau de la complexité. La mise à jour consiste en l’incrémentation de certaines cellules en fonction de l’algorithme d’origine. A titre d’exemple, la Table 3.3 montre la représentation de la complexité de l’Algorithme 6. Une seule cellule du tableau de la complexité est incrémentée lors de l’utilisation d’un algorithme atomique à l’exception de l’inverse, du produit scalaire et la décomposition binaire. En effet, un algorithme atomique ne contient qu’une opération unitaire. Lors de l’utilisation de l’Algorithme 1 nommé add, seule une cellule de la colonne Add (pour addition) sera incrémentée.
Remerciements |
Télécharger le document complet
