DESX

DESX
Создатель:	Рональд Ривест
Создан:	1984
Размер ключа:	184 бит
Размер блока:	64 бит
Число раундов:	16
Тип:	Сеть Фейстеля

DESX — симметричный алгоритм шифрования, разработанный на основе блочного шифра DES (Data Encryption Standard). Данный алгоритм использует метод отбеливания ключа с целью усиления устойчивости к атакам на основе полного перебора.

История

Исходный алгоритм DES был утвержден в качестве стандарта в 1977 и имел длину ключа 56 бит (<math>2^{56}</math> возможных ключей). Алгоритм подвергался критике из-за того что вычислительные мощности для полного перебора ключей были доступны крупным организациям и правительствам, в частности Агентству Национальный Безопасности США. Для увеличения длины ключа алгоритма DES без его существенной переработки криптоаналитиком Рональдом Ривестом из компании RSA был предложен алгоритм DESX в 1984 г. Повышенная стойкость алгоритма была формально продемонстрирована Джо Килиан и Филипом Роугвей в 1996 г.

Описание

Суть алгоритма состоит в том, что перед выполнением однократного DES и после него на данные операцией XOR накладываются различные 64-битные фрагменты ключа:

<math>\mbox{DES-X(}M) = K_2 \oplus \mbox{DES}_K (M \oplus K_1)</math>

Таким образом, длина ключа увеличивается до 56 + 2 × 64 = 184 бит.

DESX полностью совместим с алгоритмом DES в случае, если К₁ = К₂ = 0. Авторы алгоритма дают ряд несложных рекомендаций, позволяющих использовать переменный размер ключа шифрования, предварительно применив к нему хэширование алгоритмом SHA-1. Кроме того, авторы алгоритма допускают использование 120-битного ключа шифрования, при этом К₁ устанавливается равным К₂. Существует вариант DESX, также разработанный компанией RSA, со 120-битным ключом, состоящим из К и К₁, а значение К₂ является функцией всех 16 байтов ключа шифрования. Известен еще один вариант алгоритма DESX, в котором вместо обеих операций XOR выполняется сложение по модулю <math>2^{64}</math>.

Скорость алгоритма DESX приблизительно равна скорости DES.

DESX достаточно стоек, имеет аппаратную реализацию и широко используется.

Реализация DESX включена в криптографические библиотеки BSAFE компании RSA Security с конца 80х годов.

Криптостойкость

Хотя длина ключа алгоритма DESX — 184 бита, эффективная длина ключа составляет 56 + 64 — 1 — log₂(M) = 119 — log₂(M) = ~119 бит, где М — число известных пар открытый текст/шифротекст. Более того длина ключа падает до 88 бит при <math>2^{32}</math> известных открытых текстах и при использовании атаки на основе адаптивно подобранного открытого текста. Поэтому некоторые реализации используют ключ К₂ как одностороннюю функцию от К₁ и К.

DESX также увеличивает стойкость DES к дифференциальному и линейному криптоанализу, хотя улучшение не столь значительное, чем в случае атаки на основе полного перебора ключей. Для успешной атаки на алгоритм DESX дифференциальный криптоанализ потребует <math>2^{61}</math> известных открытых текстов (<math>2^{47}</math> для DES), а линейный криптоанализ — <math>2^{60}</math> текстов(<math>2^{43}</math> для DES).

Ссылки

• Joe Kilian and Phillip Rogaway, [www.cs.ucdavis.edu/~rogaway/papers/desx.pdf How to protect DES against exhaustive key search] (PDF), Advances in Cryptology — Crypto '96, Springer-Verlag (1996), pp. 252—267.
• Phillip Rogaway, [www.cs.ucdavis.edu/~rogaway/papers/cryptobytes.ps The security of DESX] (PostScript)
• A. Biryukov and D. Wagner, Advanced Slide Attacks, Eurocrypt 2000, Springer-Verlag (2000), pp.589-606

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

– Душенька… а меня то.
Соня, Наташа, Петя, Анна Михайловна, Вера, старый граф, обнимали его; и люди и горничные, наполнив комнаты, приговаривали и ахали.
Петя повис на его ногах. – А меня то! – кричал он. Наташа, после того, как она, пригнув его к себе, расцеловала всё его лицо, отскочила от него и держась за полу его венгерки, прыгала как коза всё на одном месте и пронзительно визжала.
Со всех сторон были блестящие слезами радости, любящие глаза, со всех сторон были губы, искавшие поцелуя.
Соня красная, как кумач, тоже держалась за его руку и вся сияла в блаженном взгляде, устремленном в его глаза, которых она ждала. Соне минуло уже 16 лет, и она была очень красива, особенно в эту минуту счастливого, восторженного оживления. Она смотрела на него, не спуская глаз, улыбаясь и задерживая дыхание. Он благодарно взглянул на нее; но всё еще ждал и искал кого то. Старая графиня еще не выходила. И вот послышались шаги в дверях. Шаги такие быстрые, что это не могли быть шаги его матери.
Но это была она в новом, незнакомом еще ему, сшитом без него платье. Все оставили его, и он побежал к ней. Когда они сошлись, она упала на его грудь рыдая. Она не могла поднять лица и только прижимала его к холодным снуркам его венгерки. Денисов, никем не замеченный, войдя в комнату, стоял тут же и, глядя на них, тер себе глаза.
– Василий Денисов, друг вашего сына, – сказал он, рекомендуясь графу, вопросительно смотревшему на него.
– Милости прошу. Знаю, знаю, – сказал граф, целуя и обнимая Денисова. – Николушка писал… Наташа, Вера, вот он Денисов.
Те же счастливые, восторженные лица обратились на мохнатую фигуру Денисова и окружили его.
– Голубчик, Денисов! – визгнула Наташа, не помнившая себя от восторга, подскочила к нему, обняла и поцеловала его. Все смутились поступком Наташи. Денисов тоже покраснел, но улыбнулся и взяв руку Наташи, поцеловал ее.
Денисова отвели в приготовленную для него комнату, а Ростовы все собрались в диванную около Николушки.
Старая графиня, не выпуская его руки, которую она всякую минуту целовала, сидела с ним рядом; остальные, столпившись вокруг них, ловили каждое его движенье, слово, взгляд, и не спускали с него восторженно влюбленных глаз. Брат и сестры спорили и перехватывали места друг у друга поближе к нему, и дрались за то, кому принести ему чай, платок, трубку.
Ростов был очень счастлив любовью, которую ему выказывали; но первая минута его встречи была так блаженна, что теперешнего его счастия ему казалось мало, и он всё ждал чего то еще, и еще, и еще.
На другое утро приезжие спали с дороги до 10 го часа.
В предшествующей комнате валялись сабли, сумки, ташки, раскрытые чемоданы, грязные сапоги. Вычищенные две пары со шпорами были только что поставлены у стенки. Слуги приносили умывальники, горячую воду для бритья и вычищенные платья. Пахло табаком и мужчинами.
– Гей, Г'ишка, т'убку! – крикнул хриплый голос Васьки Денисова. – Ростов, вставай!
Ростов, протирая слипавшиеся глаза, поднял спутанную голову с жаркой подушки.
– А что поздно? – Поздно, 10 й час, – отвечал Наташин голос, и в соседней комнате послышалось шуршанье крахмаленных платьев, шопот и смех девичьих голосов, и в чуть растворенную дверь мелькнуло что то голубое, ленты, черные волоса и веселые лица. Это была Наташа с Соней и Петей, которые пришли наведаться, не встал ли.