REDOC

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

REDOC III
Создатель:	Майкл Вуд
Размер ключа:	Переменный, до 2560 байт (20480 бит)
Размер блока:	80 бит
Число раундов:	10
Тип:	собственный

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

Алгоритм

REDOC-II представляет собой десятираундовую криптосистему (но высказано предположение, что 1- или двухраундовая версия является безопасной). Каждый раунд предусматривает набор сложных манипуляций с 10 байтовым блоком.

Оригинальная длина ключа составляет 10 байт. Однако, так как используются для шифрования только первые 7 бит, эффективный размер ключа составляет 70 бит. Следует уточнить, что REDOC II может поддерживать длину ключа в диапазоне от 70 до 17 920 бит. Текущая версия использует 140-битный ключ.

Каждый раунд состоит из шести фаз:

1. Первая переменная подстановка,
2. Вторая переменная подстановка,
3. Первый переменный ключ XOR,
4. Переменный анклав,
5. Второй переменный ключ XOR,
6. Переменная перестановка.

Во время каждой фазы данные обрабатываются с помощью таблиц.

Виды таблиц

1. 16 предопределенных подстановочных таблиц, которые используются в фазах переменной подстановки. (Фиксированы)
2. 128 предопределенных таблиц перестановок, используемые фазами переменной перестановки. (Фиксированы)
3. 128 предопределенных таблиц анклава, используемые фазами переменного анклава. (Фиксированы)
4. Кроме того, 128 десятибайтных таблиц ключей и девять таблиц масок вычисляются для каждого ключа с помощью алгоритма обработки ключа. (Вычислимые)

Описание фаз

Фазы переменного ключа XOR

В каждой фазе переменного ключа XOR осуществляется операция XOR между значением определенного байта в данных с определенным байтом в таблице масок. Итоговое значение – номер таблицы. Все байты данных, исключая выбранный байт, подвергаются операции XOR с соответствующим байтом из выбранной таблицы ключей.

Фазы переменной подстановки

В каждой фазе переменной подстановки осуществляется операция XOR между значением конкретного байта из таблицы данных и конкретным байтом в таблице масок. Номер таблицы — это полученное значение, взятое по модулю 16. Все байты, за исключением выбранного, заменяются значениями из выбранной подстановочной таблицы.

Фазы переменной перестановки

В каждой фазе переменной перестановки выбирается одна таблица путем добавления всех десяти байтов данным (по модулю 128) и результат подвергается операции XOR с конкретным байтом из таблицы масок. Полученное значение — это номер таблицы. Все байты данных переставляются выбранной перестановкой.

Фазы переменного анклава

Предопределенная таблица анклава имеет пять строк и 3 столбца. Каждая запись содержит число от 1 до 5. Существует 2 свойства, которым таблица анклава должна удовлетворять:

• каждый столбец должен быть перестановкой чисел 1—5;
• каждая строка должна содержать 3 различных значения.

Каждая фаза переменного анклава использует 4 таблицы анклава следующим образом:

1. Разделяет блоки на два под-блока по 5 байт каждый. Под-блоки называют левой и правой половинами.
2. XOR двух отдельных байтов из правой половины (в первом круге: первые 2 байта) с двумя отдельными байтами масок. Получившиеся 2 байта — это указатели двух таблиц анклава.
3. Обработка левой половины первой таблицей анклава указанной с помощью двух байтов.
4. Обработка полученной левой половины второй таблицей анклава указанной с помощью двух байтов.
5. XOR двух отдельных байтов в полученной левой половине (в первом круге: первые 2 байта) с двумя отдельными байтами масок. Полученные два байта — указатели двух таблиц анклава.
6. XOR левой и правой половин.
7. Обработка полученной правой половины первой таблицей анклава указанной с помощью двух байт.
8. Обработка полученной правой половины второй таблицей анклава указанной с помощью двух байт.
9. XOR правой и левой половин

Таблицы анклава связана с под-блоками следующим образом:

1. Каждая запись в таблице — это индекс байта в полублоке.
2. Добавление значения в 3 байта указывает на номер в первой строке таблицы и хранит результат в байтах, указывающий на первый столбец этой строки.
3. Добавление к полученному значению трех байтов указывает на номер во второй строке таблицы и хранит результат в байтах, указывающий на первый столбец в строке.
4. Аналогично добавление в соответствии с третьей, четвертой и пятой строкой.

Важное свойство таблиц анклав состоит в том, что они являются линейными операциями в терминах сложения и могут быть смоделированы матрично-векторным произведением. При изменении только одного верхнего входного бита, только один верхний выходной бит будет изменён. Кроме того, линейное изменение таблицы верхних выходных битов верхними входными битами однозначно определяет использование таблицы анклава. Это свойство как раз используется в фазе переменного анклава. Левая половина входных данных с двумя байтами правой половины влияют на выбор таблицы анклава, используемой в этой фазе. Однако 3 бита правой половины не влияют на выбор таблицы анклава (в первой фазе это 8, 9 и 10 байты) и это изменение верхних выходных битов – линейная функция от изменения верхних битов этими поступающими байтами. Следует отметить, что хотя мы делаем XOR правой и левой половин последним шагом в фазе переменного анклава, мы получаем симметричное изменение обоих половин и, следовательно, четное число измененных верхних битов.

Надежность

Наиболее эффективным способом вскрытия ключа считается грубая сила, для достижения цели потребуется 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 и его упрощенная версия запатентованы в США.

Литература

• Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C.. — М.: Триумф, 2002. — 816 с. — ISBN 5-89392-055-4.
• M.J.B. Robshaw. [friedo.szm.com/krypto/rsa/tr-601.pdf Block Ciphers. RSA Laboratories Technical Report TR-601] // 2-е изд. — 1995. — 1 августа.</span>
• Ken Shirriff, Differential Cryptanalysis of REDOC-III, [www.righto.com/papers/redoc.ps (PS)]

Отрывок, характеризующий REDOC

– Андрей Севастьяныч, – сказал Ростов, – ведь мы их сомнем…
– Лихая бы штука, – сказал ротмистр, – а в самом деле…
Ростов, не дослушав его, толкнул лошадь, выскакал вперед эскадрона, и не успел он еще скомандовать движение, как весь эскадрон, испытывавший то же, что и он, тронулся за ним. Ростов сам не знал, как и почему он это сделал. Все это он сделал, как он делал на охоте, не думая, не соображая. Он видел, что драгуны близко, что они скачут, расстроены; он знал, что они не выдержат, он знал, что была только одна минута, которая не воротится, ежели он упустит ее. Пули так возбудительно визжали и свистели вокруг него, лошадь так горячо просилась вперед, что он не мог выдержать. Он тронул лошадь, скомандовал и в то же мгновение, услыхав за собой звук топота своего развернутого эскадрона, на полных рысях, стал спускаться к драгунам под гору. Едва они сошли под гору, как невольно их аллюр рыси перешел в галоп, становившийся все быстрее и быстрее по мере того, как они приближались к своим уланам и скакавшим за ними французским драгунам. Драгуны были близко. Передние, увидав гусар, стали поворачивать назад, задние приостанавливаться. С чувством, с которым он несся наперерез волку, Ростов, выпустив во весь мах своего донца, скакал наперерез расстроенным рядам французских драгун. Один улан остановился, один пеший припал к земле, чтобы его не раздавили, одна лошадь без седока замешалась с гусарами. Почти все французские драгуны скакали назад. Ростов, выбрав себе одного из них на серой лошади, пустился за ним. По дороге он налетел на куст; добрая лошадь перенесла его через него, и, едва справясь на седле, Николай увидал, что он через несколько мгновений догонит того неприятеля, которого он выбрал своей целью. Француз этот, вероятно, офицер – по его мундиру, согнувшись, скакал на своей серой лошади, саблей подгоняя ее. Через мгновенье лошадь Ростова ударила грудью в зад лошади офицера, чуть не сбила ее с ног, и в то же мгновенье Ростов, сам не зная зачем, поднял саблю и ударил ею по французу.
В то же мгновение, как он сделал это, все оживление Ростова вдруг исчезло. Офицер упал не столько от удара саблей, который только слегка разрезал ему руку выше локтя, сколько от толчка лошади и от страха. Ростов, сдержав лошадь, отыскивал глазами своего врага, чтобы увидать, кого он победил. Драгунский французский офицер одной ногой прыгал на земле, другой зацепился в стремени. Он, испуганно щурясь, как будто ожидая всякую секунду нового удара, сморщившись, с выражением ужаса взглянул снизу вверх на Ростова. Лицо его, бледное и забрызганное грязью, белокурое, молодое, с дырочкой на подбородке и светлыми голубыми глазами, было самое не для поля сражения, не вражеское лицо, а самое простое комнатное лицо. Еще прежде, чем Ростов решил, что он с ним будет делать, офицер закричал: «Je me rends!» [Сдаюсь!] Он, торопясь, хотел и не мог выпутать из стремени ногу и, не спуская испуганных голубых глаз, смотрел на Ростова. Подскочившие гусары выпростали ему ногу и посадили его на седло. Гусары с разных сторон возились с драгунами: один был ранен, но, с лицом в крови, не давал своей лошади; другой, обняв гусара, сидел на крупе его лошади; третий взлеаал, поддерживаемый гусаром, на его лошадь. Впереди бежала, стреляя, французская пехота. Гусары торопливо поскакали назад с своими пленными. Ростов скакал назад с другими, испытывая какое то неприятное чувство, сжимавшее ему сердце. Что то неясное, запутанное, чего он никак не мог объяснить себе, открылось ему взятием в плен этого офицера и тем ударом, который он нанес ему.
Граф Остерман Толстой встретил возвращавшихся гусар, подозвал Ростова, благодарил его и сказал, что он представит государю о его молодецком поступке и будет просить для него Георгиевский крест. Когда Ростова потребовали к графу Остерману, он, вспомнив о том, что атака его была начата без приказанья, был вполне убежден, что начальник требует его для того, чтобы наказать его за самовольный поступок. Поэтому лестные слова Остермана и обещание награды должны бы были тем радостнее поразить Ростова; но все то же неприятное, неясное чувство нравственно тошнило ему. «Да что бишь меня мучает? – спросил он себя, отъезжая от генерала. – Ильин? Нет, он цел. Осрамился я чем нибудь? Нет. Все не то! – Что то другое мучило его, как раскаяние. – Да, да, этот французский офицер с дырочкой. И я хорошо помню, как рука моя остановилась, когда я поднял ее».
Ростов увидал отвозимых пленных и поскакал за ними, чтобы посмотреть своего француза с дырочкой на подбородке. Он в своем странном мундире сидел на заводной гусарской лошади и беспокойно оглядывался вокруг себя. Рана его на руке была почти не рана. Он притворно улыбнулся Ростову и помахал ему рукой, в виде приветствия. Ростову все так же было неловко и чего то совестно.
Весь этот и следующий день друзья и товарищи Ростова замечали, что он не скучен, не сердит, но молчалив, задумчив и сосредоточен. Он неохотно пил, старался оставаться один и о чем то все думал.
Ростов все думал об этом своем блестящем подвиге, который, к удивлению его, приобрел ему Георгиевский крест и даже сделал ему репутацию храбреца, – и никак не мог понять чего то. «Так и они еще больше нашего боятся! – думал он. – Так только то и есть всего, то, что называется геройством? И разве я это делал для отечества? И в чем он виноват с своей дырочкой и голубыми глазами? А как он испугался! Он думал, что я убью его. За что ж мне убивать его? У меня рука дрогнула. А мне дали Георгиевский крест. Ничего, ничего не понимаю!»
Но пока Николай перерабатывал в себе эти вопросы и все таки не дал себе ясного отчета в том, что так смутило его, колесо счастья по службе, как это часто бывает, повернулось в его пользу. Его выдвинули вперед после Островненского дела, дали ему батальон гусаров и, когда нужно было употребить храброго офицера, давали ему поручения.


Получив известие о болезни Наташи, графиня, еще не совсем здоровая и слабая, с Петей и со всем домом приехала в Москву, и все семейство Ростовых перебралось от Марьи Дмитриевны в свой дом и совсем поселилось в Москве.
Болезнь Наташи была так серьезна, что, к счастию ее и к счастию родных, мысль о всем том, что было причиной ее болезни, ее поступок и разрыв с женихом перешли на второй план. Она была так больна, что нельзя было думать о том, насколько она была виновата во всем случившемся, тогда как она не ела, не спала, заметно худела, кашляла и была, как давали чувствовать доктора, в опасности. Надо было думать только о том, чтобы помочь ей. Доктора ездили к Наташе и отдельно и консилиумами, говорили много по французски, по немецки и по латыни, осуждали один другого, прописывали самые разнообразные лекарства от всех им известных болезней; но ни одному из них не приходила в голову та простая мысль, что им не может быть известна та болезнь, которой страдала Наташа, как не может быть известна ни одна болезнь, которой одержим живой человек: ибо каждый живой человек имеет свои особенности и всегда имеет особенную и свою новую, сложную, неизвестную медицине болезнь, не болезнь легких, печени, кожи, сердца, нервов и т. д., записанных в медицине, но болезнь, состоящую из одного из бесчисленных соединений в страданиях этих органов. Эта простая мысль не могла приходить докторам (так же, как не может прийти колдуну мысль, что он не может колдовать) потому, что их дело жизни состояло в том, чтобы лечить, потому, что за то они получали деньги, и потому, что на это дело они потратили лучшие годы своей жизни. Но главное – мысль эта не могла прийти докторам потому, что они видели, что они несомненно полезны, и были действительно полезны для всех домашних Ростовых. Они были полезны не потому, что заставляли проглатывать больную большей частью вредные вещества (вред этот был мало чувствителен, потому что вредные вещества давались в малом количестве), но они полезны, необходимы, неизбежны были (причина – почему всегда есть и будут мнимые излечители, ворожеи, гомеопаты и аллопаты) потому, что они удовлетворяли нравственной потребности больной и людей, любящих больную. Они удовлетворяли той вечной человеческой потребности надежды на облегчение, потребности сочувствия и деятельности, которые испытывает человек во время страдания. Они удовлетворяли той вечной, человеческой – заметной в ребенке в самой первобытной форме – потребности потереть то место, которое ушиблено. Ребенок убьется и тотчас же бежит в руки матери, няньки для того, чтобы ему поцеловали и потерли больное место, и ему делается легче, когда больное место потрут или поцелуют. Ребенок не верит, чтобы у сильнейших и мудрейших его не было средств помочь его боли. И надежда на облегчение и выражение сочувствия в то время, как мать трет его шишку, утешают его. Доктора для Наташи были полезны тем, что они целовали и терли бобо, уверяя, что сейчас пройдет, ежели кучер съездит в арбатскую аптеку и возьмет на рубль семь гривен порошков и пилюль в хорошенькой коробочке и ежели порошки эти непременно через два часа, никак не больше и не меньше, будет в отварной воде принимать больная.