Розробники | Майкл Вуд |
---|---|
Уперше оприлюднений | 1990 р |
Раундів | 10 |
Тип | власний |
REDOC — симетричний блочний криптоалгоритм, розроблений Майклом Вудом в 1990 році для компанії Cryptech. Криптоалгоритм отримав найменування REDOC II. Всі операції — підстановки, перестановки, XOR виконуються з байтами, що дозволяє ефективно реалізуватися програмно. Алгоритм використовує залежні від ключа і відкритого вихідного тексту набори таблиць (S-блоків), використовуючи мінливі табличні функції. Алгоритм відрізняє використання масок, тобто чисел, одержаних із ключової таблиці. Маски використовуються для вибору таблиць конкретної функції конкретного раунду. При цьому, використовується як значення маски, так і значення даних[1].
REDOC-II являє собою десятираундову криптосистему (але висловлено припущення, що 1 — або двораундова версія є безпечною)[2]. Кожен раунд в оригінальній версії REDOC II передбачає набір маніпуляцій з 10 — байтовим блоком. Сім біт кожного байта використовуються для значень даних і восьмий біт — біт парності.
Однак, так як використовуються для шифрування тільки перші 7 біт кожного байта, алфавітниЙ простір для кожного байта від 0 до 127. Всі операції виконуються по модулю 128[3].
Довжина ключа в оригінальній версії REDOC II становить 10 байт. Ефективний розмір ключа становить 70 біт. Слід уточнити, що REDOC II може підтримувати довжину ключа в діапазоні від 70 до 17 920 біт[3].
Кожен раунд складається з шести фаз:
Під час кожної фази дані обробляються за допомогою таблиць[4].
1) 16 зумовлених символів таблиць, які використовуються в фазах змінної підстановки. (Фіксовані)
Приклад таблиці підстановки | |||||||
---|---|---|---|---|---|---|---|
Original | = | Sub 0 | Sub 1 | Sub 4 | Sub 10 | Sub 14 | Sub15 |
Value | |||||||
0 | = | 90 | 47 | 25 | 66 | 73 | 0 |
1 | = | 46 | 89 | 51 | 13 | 36 | 52 |
2 | = | 66 | 87 | 103 | 31 | 107 | 44 |
3 | = | 21 | 20 | 116 | 7 | 43 | 83 |
… | = | ||||||
126 | = | 24 | 14 | 105 | 114 | 77 | 6 |
127 | = | 122 | 62 | 11 | 63 | 49 | 79 |
2) 128 зумовлених таблиць перестановок, використовувані фазами змінної перестановки. (Фіксовані)
Приклад таблиці перестановок | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Original | = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Перестановка 1 | = | 1 | 6 | 7 | 9 | 10 | 2 | 5 | 8 | 3 | 4 |
Перестановка 2 | = | 10 | 4 | 8 | 3 | 1 | 7 | 2 | 9 | 5 | 6 |
Перестановка 3 | = | 1 | 6 | 4 | 9 | 8 | 5 | 10 | 2 | 3 | 7 |
… | = | ||||||||||
Перестановка 86 | = | 9 | 7 | 2 | 6 | 5 | 8 | 3 | 10 | 1 | 4 |
Перестановка 87 | = | 5 | 3 | 8 | 1 | 9 | 7 | 10 | 2 | 4 | 6 |
… | = | ||||||||||
Перестановка 126 | = | 9 | 8 | 3 | 7 | 1 | 10 | 5 | 6 | 2 | 4 |
Перестановка 127 | = | 7 | 8 | 5 | 10 | 9 | 3 | 4 | 2 | 1 | 6 |
3) 128 зумовлених таблиць анклаву, використані фазами змінного анклаву. (Фіксовані)
Приклад таблиці анклаву | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a | b | c | d | ||||||||||||
Entry 0: | 5 | 2 | 3 | 3 | 5 | 2 | 5 | 4 | 2 | 5 | 4 | 2 | |||
4 | 3 | 1 | 1 | 3 | 5 | 4 | 3 | 1 | 2 | 5 | 1 | ||||
2 | 5 | 4 | 2 | 4 | 1 | 1 | 5 | 3 | 1 | 3 | 5 | ||||
1 | 4 | 5 | 4 | 1 | 4 | 3 | 2 | 5 | 3 | 2 | 4 | ||||
3 | 1 | 2 | 4 | 2 | 3 | 2 | 1 | 4 | 4 | 1 | 3 | ||||
Entry 1: | 3 | 1 | 2 | 3 | 2 | 5 | 4 | 2 | 1 | 4 | 2 | 3 | |||
4 | 3 | 1 | 5 | 1 | 4 | 3 | 4 | 5 | 5 | 3 | 1 | ||||
2 | 5 | 4 | 2 | 4 | 3 | 5 | 1 | 4 | 2 | 1 | 5 | ||||
5 | 2 | 3 | 4 | 3 | 1 | 1 | 3 | 2 | 3 | 5 | 4 | ||||
1 | 4 | 5 | 1 | 5 | 2 | 2 | 5 | 3 | 1 | 4 | 2 | ||||
… | |||||||||||||||
Entry 31: | 2 | 4 | 1 | 2 | 4 | 3 | 1 | 5 | 3 | 4 | 1 | 5 | |||
3 | 5 | 4 | 4 | 1 | 2 | 2 | 4 | 1 | 3 | 5 | 2 | ||||
5 | 1 | 3 | 3 | 5 | 4 | 4 | 3 | 2 | 1 | 4 | 3 | ||||
1 | 2 | 5 | 5 | 2 | 1 | 5 | 2 | 4 | 2 | 3 | 4 | ||||
4 | 3 | 2 | 1 | 3 | 5 | 3 | 1 | 5 | 5 | 2 | 1 |
4) Крім того, 128 десятибайтних таблиць ключів і дев'ять таблиць масок обчислюються для кожного ключа за допомогою алгоритму обробки ключа. (Обчислювані, створюються при ініціалізації шифрування)[3][4]
Приклад таблиці ключів | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Ключ 0 | = | 0 | 34 | 5 | 63 | 9 | 73 | 74 | 107 | 109 | 33 |
Ключ 1 | = | 10 | 62 | 48 | 85 | 32 | 101 | 8 | 0 | 63 | 56 |
Ключ 2 | = | 26 | 59 | 75 | 97 | 33 | 80 | 8 | 6 | 73 | 26 |
… | = | ||||||||||
Ключ 107 | = | 36 | 123 | 45 | 10 | 55 | 59 | 109 | 45 | 98 | 24 |
… | = | ||||||||||
Ключ 118 | = | 95 | 25 | 48 | 47 | 1 | 20 | 117 | 55 | 19 | 67 |
… | = | ||||||||||
Ключ 126 | = | 62 | 110 | 70 | 27 | 124 | 31 | 119 | 97 | 9 | 2 |
Ключ 127 | = | 11 | 54 | 25 | 87 | 107 | 73 | 4 | 118 | 62 | 34 |
Приклад таблиці масок | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Маска 1 | = | 48 | 2 | 121 | 18 | 60 | 105 | 33 | 50 | 11 | 60 |
Маска 2 | = | 26 | 78 | 24 | 72 | 69 | 13 | 77 | 43 | 9 | 99 |
Маска 3 | = | 64 | 113 | 72 | 61 | 37 | 13 | 49 | 71 | 24 | 60 |
Маска 4 | = | 104 | 62 | 69 | 87 | 18 | 31 | 102 | 101 | 32 | 125 |
У кожній фазі змінної перестановки складаються всі десять байт даних (по модулю 128), і результат піддається операції XOR з конкретним байтом із таблиці масок. Отримане значення — це номер таблиці перестановок. Всі байти даних замінюються обраною перестановкою[4].
Вибирається байт даних і відповідний байт з таблиці масок, між якими здійснюється операція XOR. Отримане значення — номер таблиці ключів. (Варто нагадати, що для шифрування використовується 7 біт кожного байта. Тому отриманий номер таблиці ключів лежить в діапазоні від 0 до 127). Всі байти даних, виключаючи вибраний, піддаються операції XOR з відповідними байтами з таблиці ключів із отриманим номером.
Така операція здійснюється для всіх байтів даних.[4]
Вибирається байт даних і відповідний байт із таблиці масок, між якими здійснюється операція XOR. Отримане значення, взяте за модулем 16 — номер таблиці підстановки. Всі байти, за винятком вибраного, замінюються значеннями з таблиці підстановки з отриманим номером.
Така операція здійснюється для всіх байтів з даних[4].
Зумовлена таблиця анклаву має п'ять рядків і 3 стовпця. Кожен запис містить число від 1 до 5. Існує 2 властивості, яким повинна відповідати таблиця анклаву:
Пов'язано це з тим, що обробка таблиці відбувається по рядках і наступним чином: Кожне число в таблиці анклаву означає позицію байта. Три байти, які вказані з допомогою одного рядка таблиці, що додаються (по модулю 128). Байт, зазначений у першому стовпці, замінюється отриманою сумою.[3]
Кожна фаза змінного анклаву використовує 4 таблиці анклаву наступним чином:
Найбільш ефективним способом розкриття ключа вважається груба сила, для досягнення мети потрібно 2160 операцій. Практично єдиним ефективним криптоаналізом було відкриття одного з раундів алгоритму Томасом Кузиком, але розширити розтин на подальші раунди не вдалося. З допомогою 2300 відкритих текстів був проведений криптоаналіз одного з раундів Шаміром і Біхамом, після 4 раундів були отримані 3 значення маски, проте успіхів як таких це не принесло й на даний момент алгоритм вважається криптостійким[1].
Існує також значно спрощена версія алгоритму — REDOC III, створенА Майклом Вудом. Використовується 80-бітний блок, довжина ключа мінлива, може досягати 20480 бітів. Перестановки Й підстановки виключені, всі операції над блоком і ключем засновані лише на застосуванні XOR, через це значно збільшена швидкість шифрування за рахунок стійкості до диференціального криптоаналізу. Основою алгоритму є генеровані на основі секретного ключа 256 10-байтових ключів, отримані на основі XOR 128 10-байтових ключів два 10-байтових блока маски. Для успішного відновлення обох масок алгоритму REDOC III потрібно 223 відкритих текстів. Цей алгоритм нескладний і швидкий. На 33 мегагерцовому процесорі 80386 він шифрує дані зі швидкістю 2.75 Мбіт/с[1]. Криптографічна система REDOC II здатна шифрувати 800 кбіт/с при тактовій частоті 20 Мгц.[6]
Алгоритм REDOC II та його спрощена версія запатентовані в США[1].