Les fonctions de hachage cryptographique atteignent-elles chaque valeur possible, par exemple sont-elles surjectives?
prenez une fonction de hachage binaire couramment utilisée - par exemple, SHA-256. Comme son nom l'indique, il affiche une valeur de 256 bits.
Let être l'ensemble de toutes les valeurs binaires 256 bits possibles. est extrêmement grand, mais fini.
Let B l'ensemble de toutes les valeurs binaires. B est infini.
Let C est l'ensemble des valeurs obtenues en exécutant SHA-256 sur chaque membre de B. Évidemment, cela ne peut pas être fait dans la pratique, mais je suppose que nous pouvons encore faire l'analyse mathématique.
Ma Question: Par nécessité, C փ . Mais n' C= <!--4?
EDIT: comme l'ont souligné certaines réponses, cela dépend entièrement de la fonction has en question. Donc, si vous savez la réponse pour toute fonction de hachage, merci de le dire!
5 réponses
tout d'abord, soulignons que SHA-256 n'accepte pas toutes les chaînes binaires possibles comme entrées. Tel que défini par FIPS 180-3, SHA-256 accepte comme entrée toute séquence de bits de longueur inférieure à 2^64 bits (i.e. pas plus de 18446744073709551615 bits). C'est très courant; toutes les fonctions de hachage sont en quelque sorte limitées dans la longueur d'entrée formelle. Une raison est que la notion de sécurité est définie en ce qui concerne le coût de calcul; Il ya un seuil sur le calcul le pouvoir que tout attaquant peut rassembler. Les entrées au-delà d'une longueur donnée nécessiteraient plus que cette puissance de calcul maximale pour simplement évaluer la fonction. En bref, les cryptographes sont très méfiants vis-à-vis des infinites, parce que les infinites ont tendance à empêcher la sécurité d'être même définie, et encore moins quantifiée. Si votre jeu de données d'entrée C doit être limité aux séquences jusqu'à 2^64-1 bits.
cela dit, Voyons ce que l'on sait de la fonction de hachage surjectivity.
fonctions de hachage essayez d'émuler un oracle aléatoire, un objet conceptuel qui sélectionne les sorties au hasard sous la seule contrainte qu'il "se souvient" des entrées et sorties précédentes, et, si on lui donne une entrée déjà vue, il renvoie la même sortie qu'auparavant. Par définition, un oracle aléatoire ne peut être prouvé surjectif qu'en essayant des entrées et en épuisant l'espace de sortie. Si la sortie a taille n bits, alors on s'attend à ce qu'environ 2^(2n) entrées distinctes seront nécessaires pour épuiser l'espace de sortie de taille 2^n. n = 256, ce qui signifie que hashing about 2^512 les messages (par ex. tous les messages de 512 bits) devraient être suffisants (en moyenne). SHA-256 accepte des entrées beaucoup plus longues que 512 bits (en effet, il accepte des entrées jusqu'à 18446744073709551615 bits), donc il semble hautement plausible ce SHA-256 est surjectif.
cependant, il n'a pas été prouvé que SHA-256 est surjectif, et c'est attendu. Comme montré ci-dessus, une preuve de surjectivité pour un oracle aléatoire nécessite une énorme puissance de calcul, nettement plus que de simples attaques telles que des préimages (2^n) et les collisions (2^(n / 2)). Par conséquent, une bonne fonction de hachage "ne devrait pas" permettre à une propriété telle que la surjectivité d'être effectivement prouvée. Il serait très suspect: la sécurité de la fonction de hachage découle de la une telle intransigeance devrait s'opposer fermement à toute tentative d'analyse mathématique.
en conséquence, la surjectivité n'est pas formellement prouvée pour toute fonction de hachage décente, et même pas pour les fonctions de hachage "cassées" telles que MD4. Il est seulement "fortement suspecté" (un oracle aléatoire avec des entrées beaucoup plus long que la sortie devrait être surjectif).
Pas nécessairement. Le principe de pigeonhole indique qu'une fois qu'un hachage de plus au-delà de la taille de A a été généré qu'il y a une probabilité de collision de 1, mais il fait pas état que chaque élément de a a été généré.
Cela dépend vraiment de la fonction de hachage. Si vous utilisez cette fonction de hachage valide:
Int256 Hash (string input) {
return 0;
}
alors il est évident que C != A. Donc le "par exemple, SHA256" est une note assez importante à considérer.
pour répondre à votre question actuelle: je le crois, mais je ne fais que supposer. Wikipedia ne fournit aucune information significative à ce sujet.
Pas nécessairement. Cela dépendrait de la fonction de hachage.
Il serait sans doute idéal si la fonction de hachage surjective, mais il y a des choses qui sont habituellement plus importantes, comme une faible probabilité de collisions.
Il n'est pas toujours le cas. Cependant, la qualité requise pour un algorithme de hachage sont:
- cardinalité de B
- Répartition des hachages dans B (chaque valeur de B doit avoir la même probabilité d'être un hachage)