| dbo:abstract
|
- Kolize je v matematice situace, kdy pro různé vstupní hodnoty funkce přiřazuje stejné výstupní hodnoty. Kolize je nežádoucí například u hašovací funkce nebo u kryptografické hašovací funkce, kde v informatice způsobuje potíže, které je nutné dále řešit. (cs)
- Στην επιστήμη των υπολογιστών, σύγκρουση (αγγλικά: collision ή clash) είναι μια κατάσταση που παρουσιάζεται όταν δύο συμβολοσειρές (strings) έχουν την ίδια τιμή (hash value) κατακερματισμού, , ψηφιακό αποτύπωμα ή την κρυπτογραφική σύνοψη. Σε αυτή την περίπτωση οι τιμές ονομάζονται «συνώνυμες». Οι συμβολοσειρές μπορεί να είναι οσοδήποτε μικρές (π.χ. 1 byte) ή μεγάλες (π.χ. αρχείο πολλών GB) και ονομάζονται «κλειδιά». Είναι δηλαδή κατάσταση που συμβαίνει σε εφαρμογές της πληροφορικής που αφορούν την διαχείριση των δεδομένων και την ασφάλεια των υπολογιστών. Τομείς τόσο σημαντικοί ώστε η αποφυγή του συμβάντος της σύγρουσης να αποτελεί από μόνο του ένα θεμελιώδες πεδίο μελέτης. Οι συγκρούσεις είναι αναπόφευκτες όταν πρέπει τα στοιχεία ενός μεγάλου συνόλου (όπως τα ονόματα ενός τηλεφωνικού καταλόγου) να κωδικοποιηθούν, δηλαδή να αντιστοιχιστούν σε μικρές συμβολοσειρές (strings). Επειδή η αντιστοίχιση γίνεται αυτόματα με συναρτήσεις ή αλγόριθμους το πρόβλημα είναι η επιλογή ή η κατασκευή του κατάλληλου αλγόριθμου που να ελαχιστοποιεί τις συγκρούσεις, σε όσο το δυνατό μικρότερο μέγεθος κωδικοποίησης (συμβολοσειρας σε bits ή bytes). Για παράδειγμα η αντιστοίχιση ενός μικρού αριθμού ονομάτων (π.χ. λιγότερα από 20) σε κωδικούς του ενός byte (8bits), δηλαδή η απόδοση σε κάθε όνομα ενός κωδικού μεταξύ 0 και 255 με μηχανικό τρόπο (αυτόματα) και με την μικρότερη πιθανότητα οι κωδικοί δύο ή περισσοτέρων ονομάτων να συμπίπτουν (σύγκρουση ή collision). Φυσικά αν τα ονόματα ήταν περισσότερα από 256 η αντιστοίχιση αποτυγχάνει λόγω αναπόφευκτης σύγκρουσης. (el)
- In computer science, a hash collision or clash is when two pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. Although hash algorithms have been created with the intent of being collision resistant, they can still sometimes map different data to the same hash (by virtue of the pigeonhole principle). Malicious users can take advantage of this to mimic, access, or alter data. Due to the possible negative applications of hash collisions in data management and computer security (in particular, cryptographic hash functions), collision avoidance has become an important topic in computer security. (en)
- En informática, una colisión de hash es una situación que se produce cuando dos entradas distintas a una función de hash producen la misma salida. Es matemáticamente imposible que una función de hash carezca de colisiones, ya que el número potencial de posibles entradas es mayor que el número de salidas que puede producir un hash. Sin embargo, las colisiones se producen más frecuentemente en los malos algoritmos. En ciertas aplicaciones especializadas con un relativamente pequeño número de entradas que son conocidas de antemano es posible construir una , que se asegura que todas las entradas tengan una salida diferente. Pero en una función en la cual se puede introducir datos de longitud arbitraria y que devuelve un hash de tamaño fijo (como MD5), siempre habrá colisiones, debido a que un hash dado puede pertenecer a un infinito número de entradas. (es)
- 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. Si les empreintes ont été calculées afin d'identifier des données similaires, telles des chaînes d'ADN, alors les fonctions de hachage seront conçues de telle sorte à maximiser la probabilité des collisions entre des données presque identiques. À l'opposé, si l'objectif est de contrôler l'intégrité des données, tel un fichier que l'on a transféré et dont on veut être sûr qu'aucun bit n'ait été altéré lors du transfert, les fonctions de hachage devront minimiser la probabilité des collisions entre des données presque identiques. Dans la pratique, les collisions sont en général indésirables. Toute collision dans une table de hachage augmente le coût moyen de recherche d'une donnée dans la table. Lorsque les empreintes sont utilisées pour détecter des fichiers doublons, une collision peut entraîner la suppression définitive d'un fichier si le système ne compare pas les deux fichiers avant de supprimer ce qu'il pense être le doublon. Les collisions représentent également une menace pour la sécurité informatique dans certains systèmes. Il en résulte une recherche importante dans la conception d'algorithmes minimisant le nombre de collisions et/ou rendant plus difficile leur génération. (fr)
- 計算機科学には全く限らず、ハッシュ関数のような種類の関数を使うような場面で、衝突(英: collision)とは、2つの異なるデータからハッシュ関数などで生成したハッシュ値など（チェックサム・フィンガープリント・メッセージダイジェストなど）の値が同じ値（シノニム）になることである。 (ja)
- In crittografia, una collisione hash è una situazione che avviene quando due diversi input producono lo stesso output tramite una funzione hash. Potenzialmente, la maggior parte delle funzioni hash danno luogo a collisioni, ma con una buona funzione hash esse avvengono molto raramente (e sono molto difficili da trovare). In certe applicazioni specifiche, in cui si ha un numero relativamente piccolo di input, è possibile costruire una che mappa tutti i diversi input in differenti output. Invece, una funzione che prende in ingresso input di lunghezza arbitraria e ritorna un hash di misura fissa (come l'MD5), deve avere necessariamente delle collisioni, perché il numero di possibili output è finito a fronte di un numero infinito di possibili input. (it)
- 해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다. 해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시 충돌이 자주 발생하지 않도록 구성되어야 한다.암호학적 해시 함수의 경우 해시 함수의 안전성을 깨뜨리는 충돌 공격이 가능할 수 있기 때문에 의도적인 해시 충돌을 만드는 것이 어렵도록 만들어야 한다. (ko)
- Kolizja funkcji skrótu H to taka para różnych wiadomości m1, m2, że mają one taką samą wartość skrótu, tj. H(m1) = H(m2). Ponieważ funkcja skrótu zwraca skończenie wiele wartości, a przestrzeń argumentów jest nieskończona (w przypadku funkcji akceptujących dowolnie długie argumenty), lub przynajmniej znacznie większa od przestrzeni wyników, dla każdej funkcji skrótu istnieją kolizje. W wielu zastosowaniach zależy nam na tym, żeby nie była znana żadna kolizja funkcji skrótu.Jest to jednak bardzo silne wymaganie, i często zależy nam na słabszej właściwości funkcji (od silniejszych do słabszych właściwości):
* niemożliwość łatwego generowania nowych kolizji
* niemożliwość znalezienia, dla danego m1 takiego m2, że H(m1) = H(m2), czyli second preimage resistance
* niemożliwość znalezienia, dla danego h takiego m że H(m) = h, czyli preimage resistance (pl)
- Колли́зия хеш-фу́нкции — два различных входных блока данных и для хеш-функции таких, что Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму. В некоторых частных случаях, когда множество различных входных данных конечно, можно задать инъективную хеш-функцию, по определению не имеющую коллизий. Однако для хеш-функций, принимающих вход переменной длины и возвращающих хеш постоянной длины (таких как MD5), коллизии обязаны существовать, поскольку хотя бы для одного значения хеш-функции соответствующее ему множество входных данных (полный прообраз) будет бесконечно — и любые два набора данных из этого множества образуют коллизию. (ru)
- Колізією хеш-функції називаються два різних вхідних блоки даних і таких, що Колізії існують для більшості хеш-функцій, але для «хороших» хеш-функцій частота їх виникнення близька до теоретичного мінімуму. В деяких окремих випадках, коли множина різних вхідних даних є скінченною, можна задати ін'єктивну хеш-функцію, за визначенням без колізій. Однак, для хеш-функцій, які приймають вхідні дані змінної довжини і повертають хеш постійної довжини (таких як MD5), колізії обов'язково будуть існувати, оскільки хоча б для одного значення хеш-функції відповідна йому вхідна множина значень буде безкінечною — і будь-які два значення з цієї множини утворюють колізію. (uk)
- 在计算机科学中，碰撞或冲突是指两个不同的元素具有相同的哈希值、校验和，数字指纹时发生的情况。当数据量足够多（例如将所有可能的人名和计算机文件名映射到一段字符上）时，碰撞是不可避免的。这仅仅是鸽巢原理的一个实例。 碰撞的影响依程序而异。当散列函数和数字指纹用于标识相似数据时，程序被设计成尽可能增加相似但不同的数据发生碰撞的可能性；校验和则不同，要求尽可能使得相似的数据输出不同，而不考虑不同数据输出相同的情况。 (zh)
|
| rdfs:comment
|
- Kolize je v matematice situace, kdy pro různé vstupní hodnoty funkce přiřazuje stejné výstupní hodnoty. Kolize je nežádoucí například u hašovací funkce nebo u kryptografické hašovací funkce, kde v informatice způsobuje potíže, které je nutné dále řešit. (cs)
- 計算機科学には全く限らず、ハッシュ関数のような種類の関数を使うような場面で、衝突(英: collision)とは、2つの異なるデータからハッシュ関数などで生成したハッシュ値など（チェックサム・フィンガープリント・メッセージダイジェストなど）の値が同じ値（シノニム）になることである。 (ja)
- In crittografia, una collisione hash è una situazione che avviene quando due diversi input producono lo stesso output tramite una funzione hash. Potenzialmente, la maggior parte delle funzioni hash danno luogo a collisioni, ma con una buona funzione hash esse avvengono molto raramente (e sono molto difficili da trovare). In certe applicazioni specifiche, in cui si ha un numero relativamente piccolo di input, è possibile costruire una che mappa tutti i diversi input in differenti output. Invece, una funzione che prende in ingresso input di lunghezza arbitraria e ritorna un hash di misura fissa (come l'MD5), deve avere necessariamente delle collisioni, perché il numero di possibili output è finito a fronte di un numero infinito di possibili input. (it)
- 해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다. 해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시 충돌이 자주 발생하지 않도록 구성되어야 한다.암호학적 해시 함수의 경우 해시 함수의 안전성을 깨뜨리는 충돌 공격이 가능할 수 있기 때문에 의도적인 해시 충돌을 만드는 것이 어렵도록 만들어야 한다. (ko)
- Колли́зия хеш-фу́нкции — два различных входных блока данных и для хеш-функции таких, что Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму. В некоторых частных случаях, когда множество различных входных данных конечно, можно задать инъективную хеш-функцию, по определению не имеющую коллизий. Однако для хеш-функций, принимающих вход переменной длины и возвращающих хеш постоянной длины (таких как MD5), коллизии обязаны существовать, поскольку хотя бы для одного значения хеш-функции соответствующее ему множество входных данных (полный прообраз) будет бесконечно — и любые два набора данных из этого множества образуют коллизию. (ru)
- Колізією хеш-функції називаються два різних вхідних блоки даних і таких, що Колізії існують для більшості хеш-функцій, але для «хороших» хеш-функцій частота їх виникнення близька до теоретичного мінімуму. В деяких окремих випадках, коли множина різних вхідних даних є скінченною, можна задати ін'єктивну хеш-функцію, за визначенням без колізій. Однак, для хеш-функцій, які приймають вхідні дані змінної довжини і повертають хеш постійної довжини (таких як MD5), колізії обов'язково будуть існувати, оскільки хоча б для одного значення хеш-функції відповідна йому вхідна множина значень буде безкінечною — і будь-які два значення з цієї множини утворюють колізію. (uk)
- 在计算机科学中，碰撞或冲突是指两个不同的元素具有相同的哈希值、校验和，数字指纹时发生的情况。当数据量足够多（例如将所有可能的人名和计算机文件名映射到一段字符上）时，碰撞是不可避免的。这仅仅是鸽巢原理的一个实例。 碰撞的影响依程序而异。当散列函数和数字指纹用于标识相似数据时，程序被设计成尽可能增加相似但不同的数据发生碰撞的可能性；校验和则不同，要求尽可能使得相似的数据输出不同，而不考虑不同数据输出相同的情况。 (zh)
- Στην επιστήμη των υπολογιστών, σύγκρουση (αγγλικά: collision ή clash) είναι μια κατάσταση που παρουσιάζεται όταν δύο συμβολοσειρές (strings) έχουν την ίδια τιμή (hash value) κατακερματισμού, , ψηφιακό αποτύπωμα ή την κρυπτογραφική σύνοψη. Σε αυτή την περίπτωση οι τιμές ονομάζονται «συνώνυμες». Οι συμβολοσειρές μπορεί να είναι οσοδήποτε μικρές (π.χ. 1 byte) ή μεγάλες (π.χ. αρχείο πολλών GB) και ονομάζονται «κλειδιά». (el)
- In computer science, a hash collision or clash is when two pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. Although hash algorithms have been created with the intent of being collision resistant, they can still sometimes map different data to the same hash (by virtue of the pigeonhole principle). Malicious users can take advantage of this to mimic, access, or alter data. (en)
- En informática, una colisión de hash es una situación que se produce cuando dos entradas distintas a una función de hash producen la misma salida. Es matemáticamente imposible que una función de hash carezca de colisiones, ya que el número potencial de posibles entradas es mayor que el número de salidas que puede producir un hash. Sin embargo, las colisiones se producen más frecuentemente en los malos algoritmos. En ciertas aplicaciones especializadas con un relativamente pequeño número de entradas que son conocidas de antemano es posible construir una , que se asegura que todas las entradas tengan una salida diferente. Pero en una función en la cual se puede introducir datos de longitud arbitraria y que devuelve un hash de tamaño fijo (como MD5), siempre habrá colisiones, debido a que un (es)
- 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. (fr)
- Kolizja funkcji skrótu H to taka para różnych wiadomości m1, m2, że mają one taką samą wartość skrótu, tj. H(m1) = H(m2). Ponieważ funkcja skrótu zwraca skończenie wiele wartości, a przestrzeń argumentów jest nieskończona (w przypadku funkcji akceptujących dowolnie długie argumenty), lub przynajmniej znacznie większa od przestrzeni wyników, dla każdej funkcji skrótu istnieją kolizje. (pl)
|
