MD2
Загальні | |
---|---|
Уперше оприлюднений | 2008 |
Серія | MD2, MD4, MD5, MD6 |
Деталі | |
Розмір даджеста | 128 біт |
Раундів | 18 |
MD2 (англ. Message Digest Algorithm) — хеш-функція, розроблена Рональдом Ріверстом (RSA Laboratories) в 1989 році і описана RFC 1319 (оновлено від RFC 1115). Розмір хешу — 128 біт (16 байт). Всі операції алгоритму виконуються з октетами (байтами)[1].
Хоча алгоритм все ще повністю не було зламано, в 2011 IETF змінило його статус на "історичний" і натомість рекомендує використовувати SHA-256 чи інші сильні алгоритми[2].
Опис алгоритму
Спочатку повідомлення доповнюють так, щоб його довжина в байтах була кратна 16. Для цього додають до кінця повідомлення (від 1 до 16-ти) байтів кожен з яких містить значення . Повідомлення матиме довжину , таку що . позначатиме доповнене повідомлення.
На другому кроці додають чексуму , використовуючи "випадкову" перестановку з 256 байт, побудовану з цифр числа Пі, . Для цього робиться наступне:
для і := від 0 до 15: C[i] := 0 L := 0 для і := від 0 до N/16-1: // для кожного блоку по 16 байт для j від 0 до 15: c := M[i*16+j] // символ в блоці L := C[j] := C[j] xor S[c xor L] // оновлюємо чексуму
В описі цього кроку RFC містить помилку (виправлену в Errata 555[3]), замість L = C[j] = C[j] xor S[c xor L]
там роблять присвоєння L = C[j] = S[c xor L]
, тому якщо реалізовувати точно як в RFC, вивід хеш-функції не буде відповідати деяким тестовим прикладам з RFC (`abcdefghijklmnopqrstuvwxyz` і довшим)[4].
16 байтів чексуми додаються до повідомлення , нова довжина повідомлення
На третьому кроці виділяється і обнуляється буфер для дайджесту повідомлення з 48 байтів.
На четвертому кроці виконується хешування повідомлення блок за блоком. Використовується таке саме значення перестановки як на кроці 2.
для і := від 0 до N'/16-1: // для кожного блоку по 16 байт для j від 0 до 15: X[16+j] := M[i*16+j] X[32+j] := X[16+j] xor X[j] t := 0 для j := від 0 до 17: // 18 раундів хешування для k := від 0 до 47: t := X[k] := X[k] xor S[t] t := t + j mod 256
На останньому кроці повертають перших 16 байтів вмісту буфера X.
Приклад реалізації на Python
def MD2(data): ''' >>> MD2(b'') '8350e5a3e24c153df2275c9f80692773' >>> MD2(b'a') '32ec01ec4a6dac72c0ab96fb34c0b5d1' >>> MD2(b'abc') 'da853b0d3f88d99b30283a69e6ded6bb' >>> MD2(b'message digest') 'ab4f496bfb2a530b219ff33031fe06b0' >>> MD2(b'abcdefghijklmnopqrstuvwxyz') '4e8ddff3650292ab5a4108c3aa47940b' >>> MD2(b'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789') 'da33def2a42df13975352846c30338cd' >>> MD2(b'12345678901234567890123456789012345678901234567890123456789012345678901234567890') 'd5976f79d83d3a0dc9806c3c66f3efd8' ''' M = list(data) # Крок 1. Доповнення i = 16 - (len(M) % 16) M = M + [i] * i N = len(M) # Крок 2. Додавання чексуми C = [0] * 16 L = 0 for i in range(N//16): for j in range(16): c = M[i*16 + j] L = C[j] = C[j]^S[c ^ L] M = M + C N = len(M) # Крок 3. Ініціалізація буфера MD X = [0] * 48 # Крок 4. обробка повідомлення 16-байтовими блоками for i in range(N//16): for j in range(16): X[16+j] = M[i*16+j] X[32+j] = X[16+j]^X[j] t = 0 for j in range(18): for k in range(48): t = X[k]^S[t] X[k] = t t = (t + j) % 256 # Крок 5. Вивід return ''.join(f'{x:02x}' for x in X[:16]) S = [ 41, 46, 67, 201, 162, 216, 124, 1, 61, 54, 84, 161, 236, 240, 6, 19, 98, 167, 5, 243, 192, 199, 115, 140, 152, 147, 43, 217, 188, 76, 130, 202, 30, 155, 87, 60, 253, 212, 224, 22, 103, 66, 111, 24, 138, 23, 229, 18, 190, 78, 196, 214, 218, 158, 222, 73, 160, 251, 245, 142, 187, 47, 238, 122, 169, 104, 121, 145, 21, 178, 7, 63, 148, 194, 16, 137, 11, 34, 95, 33, 128, 127, 93, 154, 90, 144, 50, 39, 53, 62, 204, 231, 191, 247, 151, 3, 255, 25, 48, 179, 72, 165, 181, 209, 215, 94, 146, 42, 172, 86, 170, 198, 79, 184, 56, 210, 150, 164, 125, 182, 118, 252, 107, 226, 156, 116, 4, 241, 69, 157, 112, 89, 100, 113, 135, 32, 134, 91, 207, 101, 230, 45, 168, 2, 27, 96, 37, 173, 174, 176, 185, 246, 28, 70, 97, 105, 52, 64, 126, 15, 85, 71, 163, 35, 221, 81, 175, 58, 195, 92, 249, 206, 186, 197, 234, 38, 44, 83, 13, 110, 133, 40, 132, 9, 211, 223, 205, 244, 65, 129, 77, 82, 106, 220, 55, 200, 108, 193, 171, 250, 36, 225, 123, 8, 12, 189, 177, 74, 120, 136, 149, 139, 227, 99, 232, 109, 233, 203, 213, 254, 59, 0, 29, 57, 242, 239, 183, 14, 102, 88, 208, 228, 166, 119, 114, 248, 235, 117, 75, 10, 49, 68, 80, 180, 143, 237, 31, 26, 219, 153, 141, 51, 159, 17, 131, 20 ]
Перестановка S
Масив з 256 байтів S - це S-таблиця. Її побудовано перемішуванням цілих чисел від 0 до 255 використовуючи варіант алгоритму Дарстенфельда[en] в якому генератор псевдовипадкових чисел використовує цифри десяткового представлення Пі[5][6] (див. число "нічого не сховав у рукаві"[en]).
Цей розділ потребує доповнення. |
Реалізації
В RFC 1319 дається еталонна реалізація на С, крім цього існують реалізації на Python[7][8], JavaScript[9], Java, [10]Go[11]та іншими мовами програмування.
Безпека
Функція демонструє лавиновий ефект, зміна лише одного символа змінює кожен байт в хеші. Наприклад в наступних двох хешах червоним кольором показано половинку байта що не змінилась:
MD2('wikipedia') = 'e01ebd633170ac3210b4c25e941b3417' MD2('wikipedib') = 'b2451ac2a2691e485a30519caf8c0512'
Хеш має розмір 128 біт, тому для того аби знайти повідомлення яке хешується в найгіршому випадку треба перебрати варіантів. Знайдені вразливості, які дозволяють скоротити кількість варіантів до [12]
Цей розділ потребує доповнення. |
Історія
Після винайдення асиметричної криптографії й алгоритму RSA, постала проблема того що RSA занадто повільний для того аби підписувати довгі повідомлення. Безпечна криптографічна хеш-функція могла б значно підвищити зручність цифрового підпису, тому були створені функції MD та MD2. MD, на відміну від MD2 не була опублікована, і використовувалась в додатках безпечної електронної пошти від RSA Security.[1]
Зноски
- ↑ а б Kaufman, Perlman та Speciner, 2002, Hashes and Message Digests.
- ↑ RFC 6149
- ↑ RFC Errata Report » RFC Editor.
- ↑ MD2.py. Github Gist (англ.).
- ↑ RFC 1319
- ↑ How is the MD2 hash function S-table constructed from Pi?. Cryptography Stack Exchange. Stack Exchange. 2 серпня 2014. Процитовано 23 травня 2021.
- ↑ https://urchin.earth.li/~twic/md2.py
- ↑ MD2 — PyCryptodome 3.190b1 documentation. pycryptodome.readthedocs.io.
- ↑ js-md2. npm (англ.). 8 лютого 2017.
- ↑ MD2 (Oracle Fusion Middleware Crypto FIPS Java API Reference). docs.oracle.com.
- ↑ md2 package - github.com/htruong/go-md2 - Go Packages. pkg.go.dev.
- ↑ Muller, Frédéric (2004). The MD2 Hash Function Is Not One-Way. Advances in Cryptology - ASIACRYPT 2004: 214—229. doi:https://doi.org/10.1007/978-3-540-30539-2_16.
{{cite journal}}
: Перевірте значення|doi=
(довідка)
Література
- Kaufman, Charlie; Perlman, Radia; Speciner, Mike (2002). Network security: private communication in a public world (вид. 2.). Upper Saddle River, NJ London: Prentice Hall PTR. ISBN 0130460192.
Посилання
- RFC 1319
- RFC 1115
- RFC 6149
- п
- о
- р
розтягування ключів[en]
- HKDF[en]
- KDF1/KDF2
повідомлення
шифрування
- CCM[en]
- ChaCha20-Poly1305[en]
- CWC[en]
- EAX[en]
- GCM
- IAPM[en]
- OCB[en]
некриптографічні[en]
функції
- Adler-32[en]
- CRC
- FNV[en]
- Алгоритм Луна
- Колізійна
- Знаходження першовзору
- «Днів народження»
- Грубою силою
- Райдужна таблиця
- Сторонніми каналами
- Розширення довжини[en]
- Лавиновий ефект
- Колізія геш-функції
- Будова Меркла-Демґарда
- Функція губки
- HAIFA construction[en]
- Hash-based cryptography[en]
- Дерево Меркла
- Автентифікація повідомлень
- Доказ виконаної роботи
- Сіль
- Перець
Портал «Програмування» |
Це незавершена стаття з криптографії. Ви можете допомогти проєкту, виправивши або дописавши її. |