Résistance aux collisionsLa résistance aux collisions est une propriété des fonctions de hachage cryptographiques : une fonction de hachage cryptographique H est résistante aux collisions s’il est difficile de trouver deux entrées qui donnent la même valeur de hachage ; c’est-à-dire deux entrées A et B de telles que : , et A ≠ B. Une fonction de hachage avec plus d’entrées que de sorties doit nécessairement générer des collisions. Considérons une fonction de hachage telle que SHA-256 qui produit une sortie de 256 bits à partir d’une entrée d’une longueur arbitraire.
Fonction de compressionvignette|Une fonction de compression unidirectionnelle typique, habituellement utilisée dans la construction Merkle-Damgård En cryptographie, une fonction de compression est une fonction à sens unique qui prend une entrée de M bits et produit à sa sortie une séquence de N bits avec N strictement inférieur à M. On doit ce terme à Ralph Merkle et Ivan Damgård qui l'ont utilisé dans le cadre de la construction de Merkle-Damgård. La sortie est ainsi « compressée » (à perte d'où le terme « sens unique ») puisque plus courte que l'entrée.
Fonction de hachage cryptographiqueUne fonction de hachage cryptographique est une fonction de hachage qui, à une donnée de taille arbitraire, associe une image de taille fixe, et dont une propriété essentielle est qu'elle est pratiquement impossible à inverser, c'est-à-dire que si l'image d'une donnée par la fonction se calcule très efficacement, le calcul inverse d'une donnée d'entrée ayant pour image une certaine valeur se révèle impossible sur le plan pratique. Pour cette raison, on dit d'une telle fonction qu'elle est à sens unique.
Attaque de collisionsEn cryptographie, une attaque de collisions est une attaque sur une fonction de hachage cryptographique qui tente de trouver deux entrées de cette fonction qui produisent le même résultat (appelé valeur de hachage), c'est-à-dire qui résultent en une collision. Dans une attaque de collisions, contrairement à une (), la valeur de hachage n'est pas précisée.
Attaque de préimageEn cryptographie, une attaque de préimage est une attaque sur une fonction de hachage cryptographique qui essaie de trouver un message qui a une valeur spécifique de hachage. Une bonne fonction de hachage cryptographique doit résister à des attaques de . Il existe deux types d'attaques de préimage : l'attaque de préimage : pour une valeur de sortie spécifiée, un attaquant tente de trouver une entrée qui produit cette valeur en sortie, c’est-à-dire, pour un donné, il tente de trouver un tel que ; l'attaque de seconde préimage : l'attaquant tente de trouver une seconde entrée qui a la même valeur de hachage qu’une entrée spécifiée ; pour un donné, il tente de trouver une deuxième préimage tel que .
Chiffrement par blocvignette|un schéma de chiffrement par bloc Le chiffrement par bloc (en anglais block cipher) est une des deux grandes catégories de chiffrements modernes en cryptographie symétrique, l'autre étant le chiffrement par flot. La principale différence vient du découpage des données en blocs de taille généralement fixe. La taille de bloc est comprise entre 32 et 512 bits. Dans le milieu des années 1990, le standard était de 64 bits. Depuis 2000 et le concours AES, le standard est de 128 bits.
Théorie de la complexité (informatique théorique)vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique.
Collision (informatique)vignette|Schéma d'une collision entre deux résultats d'une fonction de hachage En informatique, une collision désigne une situation dans laquelle deux données ont un résultat identique avec la même fonction de hachage. Les collisions sont inévitables dès lors que l'ensemble de départ (données fournies) de la fonction de hachage est d'un cardinal strictement supérieur à l'ensemble d'arrivée (empreintes). Ce problème est une déclinaison du principe des tiroirs. La conséquence de ces collisions dépend de leurs applications.
Attaque des anniversairesUne attaque des anniversaires ou attaque par le paradoxe des anniversaires est un type d’attaque en cryptanalyse qui exploite des notions mathématiques équivalentes à celles qu’utilise le paradoxe des anniversaires en théorie des probabilités. L'objet de l'attaque consiste à comparer entre elles les méthodes de chiffrement de plusieurs sources jusqu'à ce que deux d'entre elles correspondent. Cette attaque peut être utilisée pour modifier les communications entre deux personnes ou plus.
Taille de bloc (cryptographie)En cryptologie moderne, la cryptographie symétrique se divise en deux catégories : le chiffrement par bloc et le chiffrement par flot. Les chiffrements par bloc travaillent sur des blocs de bits dont la longueur est fixe. La taille de bloc se réfère au nombre de bits présents dans le bloc traité par l'algorithme. Le bloc en clair est transmis à l'algorithme de chiffrement qui va produire un bloc de même taille mais chiffré. La sortie ne peut pas être plus courte que l'entrée puisque le système doit être inversé lors du déchiffrement (contrairement aux fonctions de hachage).
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Fonction de hachageQuand il s'agit de mettre dans un tableau de taille raisonnable (typiquement résidant dans la mémoire principale de l'ordinateur) un ensemble de données de taille variable et arbitraire, on utilise une fonction de hachage pour attribuer à ces données des indices de ce tableau. Par conséquent, une fonction de hachage est une fonction qui associe des valeurs de taille fixe à des données de taille quelconque. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage, codes de hachage, résumés, signatures ou simplement hachages.
Quantum complexity theoryQuantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes. Two important quantum complexity classes are BQP and QMA.
Error correction codeIn computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code or error correcting code (ECC). The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors.
Time hierarchy theoremIn computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n2 time but not n time. The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E.
Complexité paramétréeEn algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
NIST hash function competitionThe NIST hash function competition was an open competition held by the US National Institute of Standards and Technology (NIST) to develop a new hash function called SHA-3 to complement the older SHA-1 and SHA-2. The competition was formally announced in the Federal Register on November 2, 2007. "NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process for the Advanced Encryption Standard (AES).
Code linéaireEn mathématiques, plus précisément en théorie des codes, un code linéaire est un code correcteur ayant une certaine propriété de linéarité. Plus précisément, un tel code est structuré comme un sous-espace vectoriel d'un espace vectoriel de dimension finie sur un corps fini. L'espace vectoriel fini utilisé est souvent F2n le terme usuel est alors celui de code linéaire binaire. Il est décrit par trois paramètres [n, k, δ] . n décrit la dimension de l'espace qui le contient. Cette grandeur est appelée longueur du code.
Data Encryption StandardLe Data Encryption Standard (DES, prononcer //) est un algorithme de chiffrement symétrique (chiffrement par bloc) utilisant des clés de 56 bits. Son emploi n'est plus recommandé aujourd'hui, du fait de sa lenteur à l'exécution et de son espace de clés trop petit permettant une attaque systématique en un temps raisonnable. Quand il est encore utilisé c'est généralement en Triple DES, ce qui ne fait rien pour améliorer ses performances. DES a notamment été utilisé dans le système de mots de passe UNIX.
NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
