Кpиптогpафия от папиpуса до компьютеpа



Шифры взбивания и стандарт DES


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

s=L*t

где L - невырожденная матрица случайного линейного преобразования бит, или, что то же самое, детерминант L не равен нулю. И хотя расшифровывание в этом случае придется осуществлять решением систем линейных уравнений, но каждый бит шифровки начинает уже зависеть от каждого бита текста. Шифры на основе этого преобразования называют скрамблерами или взбивалками за то, что они взбивают текст сообщения, как повара омлет. К сожалению, доля невырожденных матриц с увеличением их размера стремительно убывает. Детерминант матрицы L, как и ее элементы, может быть равен либо 0, либо 1. Если det(L)=0, то матрица вырождена. Поскольку известно, что для матрицы, составленной из квадратных подматриц А, В, С и D, имеем:

     ¦А В¦
     ¦   ¦ =det(A)det(B)-det(C)-det(D)
     ¦C D¦

и, обозначив через Pn вероятность равенства единице детерминанта случайной матрицы размером 2**n, получаем следующее рекуррентное выражение:

P(n+1)=2*Pn*Рn*(1-Pn*Pn).

Так как P1=0.5, то увеличение n влечет быстрое убывание невырожденных матриц среди случайных.
     Для того, чтобы матрица L была невырожденной, случайной и при расшифровании не нужно было производить много вычислений, американскими криптографами был предложен алгоритм, легший в основу стандартного криптографического преобразования DES. Суть его одного шага можно описать следующей схемой.
     Входной блок данных делится пополам на левую L' и правую R' части. После этого формируется выходной массив так, что его левая часть L" представлена правой частью R' входного, а правая R" формируется как сумма L' и R' операцией XOR. Далее, выходной массив шифруется перестановкой с заменой. Можно убедиться, что все проведенные операции могут быть обращены и расшифровывание осуществляется за число операций, линейно зависящее от размера блока. В то же самое время, после нескольких таких взбиваний можно считать, что каждый бит выходного блока шифровки может зависеть от каждого бита сообщения.
     Система шифрования DES была разработана IBM под именем Lucifer и предложена со своими корректировками Национальным Бюро Стандартов США в 1976 году как стандарт шифрования. В ней применен ключ из 56 бит. Следует отметить, что в стандарте DES применены перестановки лишь специального типа, что наводило критиков этого стандарта на мысль, что АНБ хорошо знало их теорию и могло для взлома воспользоваться заранее известными слабыми местами. Однако принцип этого шифрования прошел самую широкую апробацию и ему посвящено множество публикаций. Нарекания вызывали лишь выбранные короткими длины блока в 64 бита и ключа в 56 бит, что недостаточно для таких задач, как национальная безопасность. Свое развитие DES получил в ГОСТ 28147-89, который увеличил длину ключа до 256 бит и допустил произвольные перестановки. В заключение приведем программу, демонстрирующую эффект взбивания на блоке в 64 байта. С увеличением числа взбиваний порча единственного бита в шифровке делает нечитаемой половину текста, что обусловлено побайтовой перестановкой. Если бы перестановка была побитовая, то весь текст от ошибки в единственном бите перестал бы читаться.

    




Содержание  Назад  Вперед