REDOC
REDOC — симетричний блочний криптоалгоритм, розроблений Майклом Вудом в 1990 році для компанії Cryptech. Криптоалгоритм отримав найменування REDOC II. Всі операції — підстановки, перестановки, XOR виконуються з байтами, що дозволяє ефективно реалізуватися програмно. Алгоритм використовує залежні від ключа і відкритого вихідного тексту набори таблиць (S-блоків), використовуючи мінливі табличні функції. Алгоритм відрізняє використання масок, тобто чисел, одержаних із ключової таблиці. Маски використовуються для вибору таблиць конкретної функції конкретного раунду. При цьому, використовується як значення маски, так і значення даних[1].
| Алгоритм блокового шифрування | |
|---|---|
| Назва: | REDOC II |
| Розробник: | Майкл Вуд |
| Створений: | 1990 р |
| Опублікований: | 1990 р |
| Розмір ключа: | від 70 до 17 920 біт, ефективний: 70 біт |
| Розмір блоку: | 70 біт |
| Число раундів: | 10 |
| Тип: | власний |
Алгоритм
REDOC-II являє собою десятираундову криптосистему (але висловлено припущення, що 1 — або двораундова версія є безпечною)[2]. Кожен раунд в оригінальній версії REDOC II передбачає набір маніпуляцій з 10 — байтовим блоком. Сім біт кожного байта використовуються для значень даних і восьмий біт — біт парності.
Однак, так як використовуються для шифрування тільки перші 7 біт кожного байта, алфавітниЙ простір для кожного байта від 0 до 127. Всі операції виконуються по модулю 128[3].
Довжина ключа в оригінальній версії REDOC II становить 10 байт. Ефективний розмір ключа становить 70 біт. Слід уточнити, що REDOC II може підтримувати довжину ключа в діапазоні від 70 до 17 920 біт[3].
Кожен раунд складається з шести фаз:
- Фаза змінної перестановки,
- Перша фаза змінного ключа XOR,
- Друга фаза змінного ключа XOR,
- Фаза змінного анклаву,
- Перша фаза змінної підстановки,
- Друга фаза змінної підстановки.
Під час кожної фази дані обробляються за допомогою таблиць[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
Вибирається байт даних і відповідний байт з таблиці масок, між якими здійснюється операція XOR. Отримане значення — номер таблиці ключів. (Варто нагадати, що для шифрування використовується 7 біт кожного байта. Тому отриманий номер таблиці ключів лежить в діапазоні від 0 до 127). Всі байти даних, виключаючи вибраний, піддаються операції XOR з відповідними байтами з таблиці ключів із отриманим номером.
Така операція здійснюється для всіх байтів даних.[4]
Фази змінної підстановки
Вибирається байт даних і відповідний байт із таблиці масок, між якими здійснюється операція XOR. Отримане значення, взяте за модулем 16 — номер таблиці підстановки. Всі байти, за винятком вибраного, замінюються значеннями з таблиці підстановки з отриманим номером.
Така операція здійснюється для всіх байтів з даних[4].
Фази змінного анклаву
Зумовлена таблиця анклаву має п'ять рядків і 3 стовпця. Кожен запис містить число від 1 до 5. Існує 2 властивості, яким повинна відповідати таблиця анклаву:
- кожен стовпець повинен бути перестановкою чисел 1-5;
- кожен рядок має містити 3 різних значення[4].
Пов'язано це з тим, що обробка таблиці відбувається по рядках і наступним чином: Кожне число в таблиці анклаву означає позицію байта. Три байти, які вказані з допомогою одного рядка таблиці, що додаються (по модулю 128). Байт, зазначений у першому стовпці, замінюється отриманою сумою.[3]
Кожна фаза змінного анклаву використовує 4 таблиці анклаву наступним чином:
- Розділяє на два блоки підблоку по 5 байт кожен. Підблоки називають лівою і правою половинами.
- XOR між двома байтами з лівої половини і двома байтами з таблиці масок. Отримані 2 байта — це покажчики двох таблиць анклаву.
- Обробка лівої половини першою таблицею анклаву, вказаної з допомогою отриманого байту.
- Обробка отриманої лівої половини другою таблицею анклаву, вказаної з допомогою отриманого байту.
- XOR між лівою і правою половинами.
- XOR між двома байтами отриманої в правій половині і двома байтами з таблиці масок. Отримані два байти — покажчики двох таблиць анклаву.
- Обробка отриманої правої половини першою таблицею анклаву, зазначеної отриманим байтом.
- Обробка отриманої правої половини другою таблицею анклаву, зазначеної отриманим байтом.
- XOR правої і лівої половин.
- Конкатенація лівої половини з отриманим значенням попереднього кроку[5].
Надійність
Найбільш ефективним способом розкриття ключа вважається груба сила, для досягнення мети потрібно 2160 операцій. Практично єдиним ефективним криптоаналізом було відкриття одного з раундів алгоритму Томасом Кузиком, але розширити розтин на подальші раунди не вдалося. З допомогою 2300 відкритих текстів був проведений криптоаналіз одного з раундів Шаміром і Біхамом, після 4 раундів були отримані 3 значення маски, проте успіхів як таких це не принесло й на даний момент алгоритм вважається криптостійким[1].
REDOC III
Існує також значно спрощена версія алгоритму — 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].
Примітки
- Шнайер, Б., 2002, Раздел 13.5.
- M.J.B. Robshaw, 1995, с. 36.
- Cusick, Wood, 1991, с. 547.
- Biham, Shamir, 1992, с. 19.
- Biham, Shamir, 1992, с. 20.
- Cusick, Wood, 1991, с. 546.
Література
- Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C.. — М.: Триумф, 2002. — 816 с. — ISBN 5-89392-055-4.
- Cusick T. W., Wood M. C. The Redoc II Cryptosystem // Advances in Cryptology — CRYPTO ’90: 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings / A. J. Menezes, S. A. Vanstone — Springer Berlin Heidelberg, 1991. — P. 546—563. — (Lecture Notes in Computer Science; Vol. 537) — ISBN 978-3-540-54508-8 — ISSN 0302-9743 — doi:10.1007/3-540-38424-3_38
- Biham E., Shamir A. Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer // Advances in Cryptology — CRYPTO'91: 11th Annual International Cryptology Conference, Santa Barbara, California, USA, 1991, Proceedings / J. Feigenbaum — Springer Science+Business Media, 1992. — P. 156—171. — 484 p. — (Lecture Notes in Computer Science; Vol. 576) — ISBN 978-3-540-55188-1 — ISSN 0302-9743 — doi:10.1007/3-540-46766-1
- M.J.B. Robshaw. Block Ciphers. RSA Laboratories Technical Report TR-601 // 2-е изд. — 1995. — 1 августа.
- Ken Shirriff, Differential Криптоаналіз of REDOC-III, (PS)