Алгоритм блочного шифрування
Назва: REDOC II
Розробник: Майкл Вуд
Створений: 1990 р
Опублікований: 1990 р
Розмір ключа: від 70 до 17 920 біт, ефективний: 70 біт
Розмір блоку: 70 біт
Число раундів: 10
Тип: власний

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

АлгоритмРедагувати

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

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

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

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

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

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

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

Види таблицьРедагувати

1) 16 зумовлених символів таблиць, які використовуються в фазах змінної підстановки. (Фіксовані)

2) 128 зумовлених таблиць перестановок, використовувані фазами змінної перестановки. (Фіксовані)

3) 128 зумовлених таблиць анклаву, використані фазами змінного анклаву. (Фіксовані)

4) Крім того, 128 десятибайтних таблиць ключів і дев'ять таблиць масок обчислюються для кожного ключа за допомогою алгоритму обробки ключа. (Обчислювані, створюються при ініціалізації шифрування)[3][4]

Опис фазРедагувати

Фази змінної перестановкиРедагувати

У кожній фазі змінної перестановки складаються всі десять байт даних (по модулю 128), і результат піддається операції XOR з конкретним байтом із таблиці масок. Отримане значення — це номер таблиці перестановок. Всі байти даних замінюються обраною перестановкою[4].

Фази змінного ключа XORРедагувати

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

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

Фази змінної підстановкиРедагувати

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

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

Фази змінного анклавуРедагувати

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

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

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

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

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

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

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

ПриміткиРедагувати

  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 с. — 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)