| dbo:abstract
|
- Merkleova-Damgårdova konstrukce je pojem z oboru kryptografie, kterým se označuje konkrétní způsob vytváření kryptografických hašovacích funkcí z vhodných jednosměrných kompresních funkcí. Jedná se o způsob poměrně oblíbený, kterým vznikly mimo jiné hašovací funkce MD5, SHA1 a SHA2. Způsob popsal ve své dizertační práci v roce 1979. Sám Ralph Merkle a nezávisle na něm dokázali, že při vhodném použití výplně a při jednosměrné kompresní funkci je kolizím odolná i vzniklá kryptografická hašovací funkce. (cs)
- Merkles Meta-Verfahren (auch Merkle-Damgård-Konstruktion) ist eine Methode zur Konstruktion von kryptographischen Hash-Funktionen, die auf Arbeiten von Ralph Merkle und zurückgeht. Gegeben ist eine Kompressionsfunktion , die eine Bit lange Eingabe auf eine Bit lange Ausgabe abbildet. Sie ist kollisionssicher, das heißt, es ist nicht mit realistischem Aufwand möglich, zwei verschiedene Eingaben zu finden, die auf die gleiche Ausgabe abgebildet werden. Durch die Anwendung von Merkles Meta-Verfahren ergibt sich daraus eine kollisionssichere Hash-Funktion , die beliebig lange Nachrichten auf einen Hashwert von Bit abbildet. (de)
- La construction de Merkle-Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de taille quelconque tout en produisant une sortie de taille fixe, et en satisfaisant les contraintes de sécurité liées à la cryptographie :
* résistance aux collisions (difficulté de trouver deux messages distincts qui produisent la même empreinte)
* résistance aux attaques sur les préimages (difficulté de trouver un message à partir de son empreinte, difficulté de forger un deuxième message produisant la même empreinte que le premier) La construction de Merkle-Damgård emploie une fonction de compression avec une entrée et une sortie de taille fixe, et divise le message à hacher en blocs de taille fixe. Les blocs sont ensuite envoyés les uns après les autres dans la fonction de compression. Le résultat de chaque compression est ensuite transmis au bloc suivant selon plusieurs schémas :
* Miyaguchi-Preneel
* Matyas-Meyer-Oseas
* Davies-Meyer Le premier bloc utilise un vecteur d'initialisation constant puisque aucun autre bloc ne le précède. La construction de Merkle-Damgård produit un hachage résistant aux collisions pour autant que la fonction de compression utilisée soit également résistante aux collisions. De la qualité de la fonction de compression dépendra la résistance de l'algorithme à la cryptanalyse. Le principe de Merkle-Damgård est utilisé notamment dans MD5 et SHA-1.
* Portail de la cryptologie (fr)
- In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA-1 and SHA-2. The Merkle–Damgård construction was described in Ralph Merkle's Ph.D. thesis in 1979. Ralph Merkle and Ivan Damgård independently proved that the structure is sound: that is, if an appropriate padding scheme is used and the compression function is collision-resistant, then the hash function will also be collision-resistant. The Merkle–Damgård hash function first applies an function to create an input whose size is a multiple of a fixed number (e.g. 512 or 1024) — this is because compression functions cannot handle inputs of arbitrary size. The hash function then breaks the result into blocks of fixed size, and processes them one at a time with the compression function, each time combining a block of the input with the output of the previous round. In order to make the construction secure, Merkle and Damgård proposed that messages be padded with a padding that encodes the length of the original message. This is called length padding or Merkle–Damgård strengthening. In the diagram, the one-way compression function is denoted by f, and transforms two fixed length inputs to an output of the same size as one of the inputs. The algorithm starts with an initial value, the initialization vector (IV). The IV is a fixed value (algorithm or implementation specific). For each message block, the compression (or compacting) function f takes the result so far, combines it with the message block, and produces an intermediate result. The last block is padded with zeros as needed and bits representing the length of the entire message are appended. (See below for a detailed length padding example.) To harden the hash further, the last result is then sometimes fed through a finalisation function. The finalisation function can have several purposes such as compressing a bigger internal state (the last result) into a smaller output hash size or to guarantee a better mixing and avalanche effect on the bits in the hash sum. The finalisation function is often built by using the compression function. (Note that in some documents a different terminology is used: the act of length padding is called "finalisation".) (en)
- In crittografia, la costruzione di Merkle-Damgård è un metodo per costruire delle funzioni crittografiche di hash utilizzando delle funzioni a compressione a senso unico.Questa particolare costruzione è stata utilizzata nell'implementazione di molti algoritmi di hash, come ad esempio MD5, SHA1 e . La costruzione Merkle–Damgård venne descritta nella tesi di dottorato di Ralph Merkle nel 1979.Ralph Merkle e provarono che se viene utilizzato un appropriato schema di e la funzione di compressione è resistente alle collisioni, allora anche la funzione di hash sarà resistente alle collisioni. La funzione di hash Merkle-Damgård applica, inizialmente, una funzione a riempimento per creare un input la cui dimensione è un numero fisso (esempio: 512 o 1024). Questo avviene perché le funzioni di compressione non sono in grado di gestire input di dimensioni arbitrarie. La funzione di hash, successivamente, suddivide il risultato in blocchi di dimensioni fisse e li processa uno alla volta con la funzione di compressione, ogni volta combinando l'input con l'output del blocco precedente. Per fare in modo che la costruzione risultasse sicura, Merkle e Damgård proposero di riempire i messaggi con un padding che codificasse la lunghezza del messaggio originario. Questo passaggio viene chiamato lunghezza di padding o rafforzamento di Merkle–Damgård. Schema che raffigura la costruzione Merkle–Damgård Nel modello, la funzione di compressione unidirezionale è denominata , essa si occupa di trasformare due input di lunghezza fissa in un output della stessa dimensione degli input di partenza. L'algoritmo parte con un valore iniziale fisso, denominato vettore di inizializzazione (VI). Per ogni blocco del messaggio, la funzione di compressione prende il risultato fino ad ora ottenuto e lo combina con il suddetto messaggio producendo un risultato intermedio. L'ultimo blocco, infine, è riempito con degli "zero" e con dei bit che rappresentano la lunghezza dell'intero messaggio. Per rafforzare l'hash ulteriormente, il risultato finale viene, in alcuni casi, alimentato attraverso una funzione di finalizzazione. La funzione di finalizzazione può avere molteplici scopi, come ad esempio la compressione di uno stato interno più grande (l'ultimo risultato) in un output più piccolo o per garantire un effetto di mescolamento migliore nei bit della somma di hash. La funzione di finalizzazione è spesso costruita usando la funzione di compressione. (it)
- Будова Меркла-Демґарда або геш-функція Меркла-Демґарда — це метод будови стійкої до колізій криптографічної геш-функції зі стійкої до колізій однобічної функції стискання.:145 Цей підхід використовується багатьма розповсюдженими алгоритмами такими як MD5, SHA1 і SHA2. Будова Меркла-Демґарда була описана в Ph.D. тезах Ралфа Меркла в 1979. Ральф Меркле і незалежно довели, що якщо використати прийнятну схему доповнення і стійку до колізій функцію стискання, тоді геш-функція також буде стійкою до колізій. Геш-функція Меркла-Демґарда спочатку застосовує отримуючи вихід довжини кратної до певного числа (наприклад 512 або 1024) — бо функція стискання не може обробити вхідні дані довільного розміру. Тоді геш-функція розбиває вхідні дані на блоки умовленого розміру і обробляє їх по одному функцією стискання, щоразу використовуючи блок на вході і блок утворений попереднім раундом.:146 З метою зробити будову безпечною, Меркл і Демґард запропонували, щоб повідомлення доповнювались доповненням, яке б кодувало довжину початкового повідомлення. Це називається довжинне доповнення (англ. length padding) або підсилення Меркла-Демґарда (англ. Merkle–Damgård strengthening). На діаграмі, однобічна функція стискання позначена як f, і перетворює вхід певної довжини на вихід тої ж довжини. Алгоритм стартує з ініціалізаційним вектором, ініціалізаційний вектор (IV). IV це фіксоване значення (специфічне алгоритму або реалізації). Для кожного блоку повідомлення, функція стискання f бере поточний результат і поєднує його з наступним блоком повідомлення, утворюючи проміжний результат. Останній блок доповнюється нулями і бітами, що представляють загальну довжину доданого повідомлення. (Нижче наведений приклад довжинного додавання в подробицях.) Для зміцнення геш-функції, результат пропускають через завершальну функцію. Завершальна функція може мати декілька цілей таких як додаткове стискання, краще змішування та лавиновий ефект на бітах геш-суми. Завершальна функція часто будується із використанням функції стискання[джерело?] (Зауважте, що в деяких паперах довжинне доповнення називають «завершенням».). (uk)
- Структура Меркла — Дамгора (англ. Merkle–Damgård construction, MD) — метод построения криптографических хеш-функций, предусматривающий разбиение входных сообщений произвольной длины на блоки фиксированной длины и работающий с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего прохода. Впервые описана в 1979 году в докторской диссертации Ральфа Меркла. Меркл и независимо показали: если функция сжатия устойчива к коллизиям, то и хеш-функция будет также устойчива — чтобы доказать устойчивость структуры, сообщение дополняется блоком, который кодирует длину первоначального сообщения (упрочнение Меркла — Дамгора). Структура предусматривает вектор инициализации — фиксированное значение, которое зависит от реализации алгоритма, и которое применяется к первому проходу — применению функции сжатия к нему и первому блоку сообщения. Результат каждого прохода передаётся на следующий вход и очередному блоку сообщения; последний блок дополняется нулями, если необходимо, также, добавляется блок с информацией о длине целого сообщения. Для упрочнения хеша последний результат иногда пропускают через функцию финализации (англ. finalisation function), которая может использоваться также для уменьшения размера выходного хеша сжатием результата последнего применения в хеш меньшего размера или чтобы гарантировать лучшее смешивание битов и усилить влияние небольшого изменения входного сообщения на хеш (обеспечить лавинный эффект). Функция финализации часто строится с использованием функции сжатия. Основные алгоритмы, реализующие структуру Меркла — Дамгора — MD5, SHA-1, семейство SHA-2. (ru)
|
| rdfs:comment
|
- Merkleova-Damgårdova konstrukce je pojem z oboru kryptografie, kterým se označuje konkrétní způsob vytváření kryptografických hašovacích funkcí z vhodných jednosměrných kompresních funkcí. Jedná se o způsob poměrně oblíbený, kterým vznikly mimo jiné hašovací funkce MD5, SHA1 a SHA2. Způsob popsal ve své dizertační práci v roce 1979. Sám Ralph Merkle a nezávisle na něm dokázali, že při vhodném použití výplně a při jednosměrné kompresní funkci je kolizím odolná i vzniklá kryptografická hašovací funkce. (cs)
- Merkles Meta-Verfahren (auch Merkle-Damgård-Konstruktion) ist eine Methode zur Konstruktion von kryptographischen Hash-Funktionen, die auf Arbeiten von Ralph Merkle und zurückgeht. Gegeben ist eine Kompressionsfunktion , die eine Bit lange Eingabe auf eine Bit lange Ausgabe abbildet. Sie ist kollisionssicher, das heißt, es ist nicht mit realistischem Aufwand möglich, zwei verschiedene Eingaben zu finden, die auf die gleiche Ausgabe abgebildet werden. Durch die Anwendung von Merkles Meta-Verfahren ergibt sich daraus eine kollisionssichere Hash-Funktion , die beliebig lange Nachrichten auf einen Hashwert von Bit abbildet. (de)
- In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA-1 and SHA-2. (en)
- La construction de Merkle-Damgård est une construction algorithmique qui permet de résoudre le problème du hachage cryptographique en acceptant un message de taille quelconque tout en produisant une sortie de taille fixe, et en satisfaisant les contraintes de sécurité liées à la cryptographie :
* résistance aux collisions (difficulté de trouver deux messages distincts qui produisent la même empreinte)
* résistance aux attaques sur les préimages (difficulté de trouver un message à partir de son empreinte, difficulté de forger un deuxième message produisant la même empreinte que le premier) (fr)
- In crittografia, la costruzione di Merkle-Damgård è un metodo per costruire delle funzioni crittografiche di hash utilizzando delle funzioni a compressione a senso unico.Questa particolare costruzione è stata utilizzata nell'implementazione di molti algoritmi di hash, come ad esempio MD5, SHA1 e . La costruzione Merkle–Damgård venne descritta nella tesi di dottorato di Ralph Merkle nel 1979.Ralph Merkle e provarono che se viene utilizzato un appropriato schema di e la funzione di compressione è resistente alle collisioni, allora anche la funzione di hash sarà resistente alle collisioni. (it)
- Будова Меркла-Демґарда або геш-функція Меркла-Демґарда — це метод будови стійкої до колізій криптографічної геш-функції зі стійкої до колізій однобічної функції стискання.:145 Цей підхід використовується багатьма розповсюдженими алгоритмами такими як MD5, SHA1 і SHA2. Будова Меркла-Демґарда була описана в Ph.D. тезах Ралфа Меркла в 1979. Ральф Меркле і незалежно довели, що якщо використати прийнятну схему доповнення і стійку до колізій функцію стискання, тоді геш-функція також буде стійкою до колізій. (uk)
- Структура Меркла — Дамгора (англ. Merkle–Damgård construction, MD) — метод построения криптографических хеш-функций, предусматривающий разбиение входных сообщений произвольной длины на блоки фиксированной длины и работающий с ними по очереди с помощью функции сжатия, каждый раз принимая входной блок с выходным от предыдущего прохода. Основные алгоритмы, реализующие структуру Меркла — Дамгора — MD5, SHA-1, семейство SHA-2. (ru)
|
