А. М. Курилкина таганрогский государственный радиотехнический университет распараллеливание криптоаналитического метода "разделяй и побеждай"для каскадных шифров вданном доклад

Вид материалаДоклад
Подобный материал:

УДК 004.056:378(06) Проблемы информационной безопасности в системе высшей школы


Л.К. БАБЕНКО, А.М. КУРИЛКИНА

Таганрогский государственный радиотехнический университет


РАСПАРАЛЛЕЛИВАНИЕ КРИПТОАНАЛИТИЧЕСКОГО МЕТОДА “РАЗДЕЛЯЙ И ПОБЕЖДАЙ”ДЛЯ КАСКАДНЫХ ШИФРОВ


В данном докладе предлагается параллельный алгоритм метода “разделяй и побеждай”.


Для получения более надёжных шифров используют каскадно уже известные шифры с различными не зависимыми ключами [1]. При таком шифровании ключ всегда можно разделить на две не зависимые части, а при криптоанализе воспользоваться известным методом “разделяй и побеждай”.

Пусть, например, текст шифруется сначала алгоритмом и ключом , где , а затем, для большей надежности, ещё раз алгоритмом и ключом , где , причем и различны и не зависимы. Ключ системы представляет собой вектор , где .

Предположим, что существует критерий g, позволяющий при известных и проверять правильность первой компоненты в ключе . То есть для любого функция , если такой, что , и , если . Если известные открытые и шифрованные тексты достаточно длинные, то достаточно часто существует единственный ключ k такой, что [2].

Тогда метод “разделяй и побеждай” предлагает в начале опробовать элемен­ты множества , отбраковывая варианты по критерию g . Отсюда определится - первая компонента вектора . Затем, используя уравнение относительно неизвестного парамет­ра , опробовать варианты .

Основная проблема при применении метода “разделяй и побеждай” состоит в нахождении критерия g, который зависит от конкретных преобразований шифра [3].

Пусть и - трудоемкости вычисления функций и соответственно на фиксированном наборе переменных. Тогда в среднем трудоемкость данного метода . Следовательно, трудоемкость метода “разделяй и побеждай” значительно меньше полного перебора , но все же требует значительной затраты времени. Чтобы сократить временные затраты предлагается использовать следующий параллельный алгоритм:

1. Распределяем перебор значений ключа по всем процессам.

Перебирая значения ключа, проверяем условие:

если , тогда , где .

2. Распределяем перебор значений ключа по всем процессам.

Перебирая значения ключа проверяем условие:

если , то, где .

Так как количество вариантов ключей намного больше количества процессов, то можно считать, что общий объем вычислений распределяется между процессами равномерно.

Тогда трудоемкость одного процесса будет примерно , а ускорение при работе данного метода будет не менее чем . Данный подход можно распространять и на другие методы криптоанализа, особенно на те, в которых производится частичный перебор. Это делает их более эффективными, что позволяет получать более точные оценки стойкости шифров.

Список литературы
  1. Брюс Шнайер. Прикладная криптография: Протоколы, алгоритмы, исходные тексты на языке Си. М.:ТРИУМФ:2002. С.401-413.
  2. Грушо А.А., Применко Э.А., Тимонина Е.Е. Анализ и синтез криптоалгоритмов.: Курс лекций: Йошкар-Ола, 2000.
  3. Colic J. Intrinsic Statistical Weakness of Keystream generators//Advances in Cryptology- ASIACRYPT’94, Lecture Notes in Computer Science, Springer-Verlag, 1995,v.917, c. 91-103.




ISBN 5-7262-0557-Х. XII Всероссийская научно-практическая конференция