Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Résistance aux collisions
Résumé
La 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. Comme la fonction doit générer une des 2256 sorties pour chaque membre d’un ensemble beaucoup plus vaste d’entrées, le principe des tiroirs garantit que certaines entrées auront la même valeur de hachage. La résistance aux collisions ne signifie pas qu’il n'y a pas de collisions, mais seulement que les collisions sont difficiles à trouver.
Le paradoxe des anniversaires illustre la limite supérieure de la résistance aux collisions : si une fonction de hachage produit N bits de sortie, un attaquant qui teste 2N/2 (ou ) opérations de hachage sur des entrées aléatoires est susceptible de trouver deux sorties identiques. S’il existe une méthode plus facile que cette attaque par force brute pour trouver deux sorties identiques, la fonction de hachage est considérée comme inadéquate pour servir de fonction de hachage cryptographique.
Les fonctions de hachage cryptographiques sont généralement conçues pour être résistantes aux collisions. Cependant, de nombreuses fonctions de hachage que l'on croyait résistantes aux collisions ont été cassées. Par exemple, on connaît maintenant des techniques plus efficaces que la force brute pour trouver des collisions pour les fonctions de hachage MD5 et SHA-1. D'un autre côté, il existe des preuves mathématiques que, pour certaines fonctions de hachage, la recherche de collisions est au moins aussi difficile que certains problèmes mathématiques difficiles comme la factorisation ou le logarithme discret. On dit que ces fonctions ont été prouvées sûres.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (34)
Personnes associées (9)
Unités associées (1)
Concepts associés (9)
Cryptographie
thumb|La machine de Lorenz utilisée par les nazis durant la Seconde Guerre mondiale pour chiffrer les communications militaires de haut niveau entre Berlin et les quartiers-généraux des différentes armées. La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés. Elle se distingue de la stéganographie qui fait passer inaperçu un message dans un autre message alors que la cryptographie rend un message supposément inintelligible à autre que qui de droit.
Paradoxe des anniversaires
Le paradoxe des anniversaires résulte de l'estimation probabiliste du nombre de personnes que l'on doit réunir pour avoir au moins une chance sur deux que deux personnes de ce groupe aient leur anniversaire le même jour. Il se trouve que ce nombre est 23, ce qui choque un peu l'intuition. À partir d'un groupe de 57 personnes, la probabilité est supérieure à . Il s'agit d'un paradoxe non pas dans le sens de contradiction logique, mais dans le sens où c'est une vérité mathématique qui contredit l'intuition : la plupart des gens estiment que cette probabilité est très inférieure à .
Attaque de collisions
En 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.
Cours associés (3)
CH-310: Dynamics and kinetics
The course covers the principles of chemical kinetics, including differential rate laws, derivation of exact and approximate integral rate laws for common elementary and composite reactions, fundament
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
PHYS-702: Advanced Quantum Field Theory
The course builds on the course QFT1 and QFT2 and develops in parallel to the course on Gauge Theories and the SM.
Séances de cours associées (34)
La cinétique des collisions : théorie et applications
Couvre la théorie et les applications de la cinétique de collision dans la compréhension des interactions moléculaires.
Cryptographie appliquée: fonctions de hachage
Explore les fonctions de hachage et leur rôle crucial dans la cryptographie, les signatures numériques et la technologie blockchain.
Hashing: Les bases et la sécurité
Examine les aspects fondamentaux et sécuritaires du hachage dans la représentation et la vérification des données.