REDOC

REDOC — симетричний блочний криптоалгоритм, розроблений в 1990 році для компанії Cryptech. Криптоалгоритм отримав найменування REDOC II. Всі операції — підстановки, перестановки, XOR виконуються з байтами, що дозволяє ефективно реалізуватися програмно. Алгоритм використовує залежні від ключа і відкритого вихідного тексту набори таблиць (S-блоків), використовуючи мінливі табличні функції. Алгоритм відрізняє використання масок, тобто чисел, одержаних із ключової таблиці. Маски використовуються для вибору таблиць конкретної функції конкретного раунду. При цьому, використовується як значення маски, так і значення даних.

REDOC II

Розробники	Майкл Вуд
Уперше оприлюднений	1990 р
Раундів	10
Тип	власний

Алгоритм

Схема алгоритму REDOC

REDOC-II являє собою десятираундову криптосистему (але висловлено припущення, що 1 — або двораундова версія є безпечною). Кожен раунд в оригінальній версії REDOC II передбачає набір маніпуляцій з 10 — байтовим блоком. Сім біт кожного байта використовуються для значень даних і восьмий біт — біт парності.

Однак, так як використовуються для шифрування тільки перші 7 біт кожного байта, алфавітниЙ простір для кожного байта від 0 до 127. Всі операції виконуються по модулю 128.

Довжина ключа в оригінальній версії REDOC II становить 10 байт. Ефективний розмір ключа становить 70 біт. Слід уточнити, що REDOC II може підтримувати довжину ключа в діапазоні від 70 до 17 920 біт.

Кожен раунд складається з шести фаз:

1. Фаза змінної перестановки,
2. Перша фаза змінного ключа XOR,
3. Друга фаза змінного ключа XOR,
4. Фаза змінного анклаву,
5. Перша фаза змінної підстановки,
6. Друга фаза змінної підстановки.

Під час кожної фази дані обробляються за допомогою таблиць.

Види таблиць

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 десятибайтних таблиць ключів і дев'ять таблиць масок обчислюються для кожного ключа за допомогою алгоритму обробки ключа. (Обчислювані, створюються при ініціалізації шифрування)

Приклад таблиці ключів
Ключ 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 з конкретним байтом із таблиці масок. Отримане значення — це номер таблиці перестановок. Всі байти даних замінюються обраною перестановкою.

Фази змінного ключа XOR

Вибирається байт даних і відповідний байт з таблиці масок, між якими здійснюється операція XOR. Отримане значення — номер таблиці ключів. (Варто нагадати, що для шифрування використовується 7 біт кожного байта. Тому отриманий номер таблиці ключів лежить в діапазоні від 0 до 127). Всі байти даних, виключаючи вибраний, піддаються операції XOR з відповідними байтами з таблиці ключів із отриманим номером.

Така операція здійснюється для всіх байтів даних.

Фази змінної підстановки

Вибирається байт даних і відповідний байт із таблиці масок, між якими здійснюється операція XOR. Отримане значення, взяте за модулем 16 — номер таблиці підстановки. Всі байти, за винятком вибраного, замінюються значеннями з таблиці підстановки з отриманим номером.

Така операція здійснюється для всіх байтів з даних.

Фази змінного анклаву

Фаза змінного анклаву

Зумовлена таблиця анклаву має п'ять рядків і 3 стовпця. Кожен запис містить число від 1 до 5. Існує 2 властивості, яким повинна відповідати таблиця анклаву:

• кожен стовпець повинен бути перестановкою чисел 1-5;
• кожен рядок має містити 3 різних значення.

Пов'язано це з тим, що обробка таблиці відбувається по рядках і наступним чином: Кожне число в таблиці анклаву означає позицію байта. Три байти, які вказані з допомогою одного рядка таблиці, що додаються (по модулю 128). Байт, зазначений у першому стовпці, замінюється отриманою сумою.

Схема обробки під-блоків за допомогою таблиць анклаву

Кожна фаза змінного анклаву використовує 4 таблиці анклаву наступним чином:

1. Розділяє на два блоки підблоку по 5 байт кожен. Підблоки називають лівою і правою половинами.
2. XOR між двома байтами з лівої половини і двома байтами з таблиці масок. Отримані 2 байта — це покажчики двох таблиць анклаву.
3. Обробка лівої половини першою таблицею анклаву, вказаної з допомогою отриманого байту.
4. Обробка отриманої лівої половини другою таблицею анклаву, вказаної з допомогою отриманого байту.
5. XOR між лівою і правою половинами.
6. XOR між двома байтами отриманої в правій половині і двома байтами з таблиці масок. Отримані два байти — покажчики двох таблиць анклаву.
7. Обробка отриманої правої половини першою таблицею анклаву, зазначеної отриманим байтом.
8. Обробка отриманої правої половини другою таблицею анклаву, зазначеної отриманим байтом.
9. XOR правої і лівої половин.
10. Конкатенація лівої половини з отриманим значенням попереднього кроку.

Надійність

Найбільш ефективним способом розкриття ключа вважається груба сила, для досягнення мети потрібно 2¹⁶⁰ операцій. Практично єдиним ефективним криптоаналізом було відкриття одного з раундів алгоритму Томасом Кузиком, але розширити розтин на подальші раунди не вдалося. З допомогою 2300 відкритих текстів був проведений криптоаналіз одного з раундів Шаміром і Біхамом, після 4 раундів були отримані 3 значення маски, проте успіхів як таких це не принесло й на даний момент алгоритм вважається криптостійким.

REDOC III

Існує також значно спрощена версія алгоритму — REDOC III, створенА Майклом Вудом. Використовується 80-бітний блок, довжина ключа мінлива, може досягати 20480 бітів. Перестановки Й підстановки виключені, всі операції над блоком і ключем засновані лише на застосуванні XOR, через це значно збільшена швидкість шифрування за рахунок стійкості до диференціального криптоаналізу. Основою алгоритму є генеровані на основі секретного ключа 256 10-байтових ключів, отримані на основі XOR 128 10-байтових ключів два 10-байтових блока маски. Для успішного відновлення обох масок алгоритму REDOC III потрібно 223 відкритих текстів. Цей алгоритм нескладний і швидкий. На 33 мегагерцовому процесорі 80386 він шифрує дані зі швидкістю 2.75 Мбіт/с. Криптографічна система REDOC II здатна шифрувати 800 кбіт/с при тактовій частоті 20 Мгц.

Алгоритм REDOC II та його спрощена версія запатентовані в США.

Примітки

1. Шнайер, Б., 2002, Раздел 13.5.
2. M.J.B. Robshaw, 1995, с. 36.
3. Cusick, Wood, 1991, с. 547.
4. Biham, Shamir, 1992, с. 19.
5. Biham, Shamir, 1992, с. 20.
6. Cusick, Wood, 1991, с. 546.

Література

• Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C.. — М.: Триумф, 2002. — 816 с. — .
• 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) —  — 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) —  — 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) [Архівовано 17 липня 2012 у Wayback Machine.]