MD2

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
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]

Зноски

[ред. | ред. код]
  1. ↑ а б Kaufman, Perlman та Speciner, 2002, Hashes and Message Digests.
  2. ↑ RFC 6149
  3. ↑ RFC Errata Report » RFC Editor.
  4. ↑ MD2.py. Github Gist (англ.).
  5. ↑ RFC 1319
  6. ↑ How is the MD2 hash function S-table constructed from Pi?. Cryptography Stack Exchange. Stack Exchange. 2 серпня 2014. Процитовано 23 травня 2021.
  7. ↑ https://urchin.earth.li/~twic/md2.py
  8. ↑ MD2 — PyCryptodome 3.190b1 documentation. pycryptodome.readthedocs.io.
  9. ↑ js-md2. npm (англ.). 8 лютого 2017.
  10. ↑ MD2 (Oracle Fusion Middleware Crypto FIPS Java API Reference). docs.oracle.com.
  11. ↑ md2 package - github.com/htruong/go-md2 - Go Packages. pkg.go.dev.
  12. ↑ 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= (довідка)

Література

[ред. | ред. код]

Посилання

[ред. | ред. код]


Замок Це незавершена стаття з криптографії.
Ви можете допомогти проєкту, виправивши або дописавши її.
Отримано з https://uk.wikipedia.org/w/index.php?title=MD2&oldid=42430331