Раздел: Документация
0 ... 87 88 89 90 91 92 93 ... 169 стичь структурной эквивалентности процедур за- и расшифрования, они отличаются друг от друга только последовательностью использования ключевых элементов; - использование ключа относительно небольшого размера и выработка из него массива ключевых элементов для шагов преобразования с помощью процедуры «развертывания» ключа. Комбинированием простых шифрующих преобразований в линейную цепочку можно создать вполне надежный составной шифр. Однако для достижения приемлемой стойкости такого шифра потребовалось бы использовать весьма большое количество элементарных преобразований. Эта схема построения криптографических алгоритмов не получила сколько-нибудь заметного распространения, потому что была предложена другая схема, имеющая лучшие показатели сложность/трудоемкость преобразования. Более высокая эффективность достигается в ней использованием следующего общего принципа. Если есть система обработки данных, составленная из относительно простых блоков преобразований, то, в общем случае, ее сложность намного выше, если структура этой системы отлична от линейной и содержит ветвления и циклы. Вспомните, что в алгоритме с сильно разветвленной структурой разобраться намного сложнее, чем в линейном алгоритме. Другой пример, из теории автоматического регулирования: системы преобразования аналогового сигнала, содержащие петли обратной связи и параллельные ветви, на порядок сложнее анализировать, чем цепи, составленные из тех же самых динамических звеньев, но имеющие линейную структуру. Таким образом, усложнить шифрующее преобразование при фиксированном количестве элементарных шагов можно, если сделать его структуру нелинейной. Рассмотрим, как достигнуть этой цели на практике. Вспомним, что ключевые данные могут комбинироваться с шифруемыми данными в преобразованиях двух типов: заменах и функциональных операциях. Оказывается, что второй способ использования ключевой информации предпочтительнее. Вместо того, чтобы делить входы вектора замены между блоком шифруемых данных и ключевым элементом, оказалось выгоднее скомбинировать данные с ключом посредством подходящей бинарной операции, а затем подвергнуть результат замене. Предположим, например, что мы преобразуем 32-битовый блок данных, используя 32-битовый ключ и несколько узлов замены с 4-битовым входом. Если использовать для комбинирования ключа и данных узлы замены, то нам необходимо будет использовать 16 узлов замены 4 бита на 2 бита, на вход каждого узла замены будут подаваться 272 два бита шифруемых данных и два бита ключа. При этом каждый выходной бит такого узла будет зависеть ровно от двух битов данных и от двух битов ключа. Если же мы подвергнем преобразованию замены побитовую сумму по модулю 2 ключа с данными, то нам необходимо будет использовать 8 узлов замены 4 бита на 4 бита, и каждый выходной бит узла замен будет зависеть уже от четырех битов ключа и от четырех битов данных. Тем самым в этом преобразовании может быть достигнута большая степень перемешивания и рассеивания. В результате сказанного выше, в практических шифрах для комбинирования шифруемых данных и ключа почти повсеместно используются бинарные операции аддитивного и,реже, мультипликативного типа. В этом случае преобразование осуществляется по следующему уравнению: Ti+1 = Ti 0 Ki Бинарная операция использованная для модификации шифруемого блока, должна обладать свойством, необходимым для операции наложения гаммы, в частности, должна существовать обратная ей операция - такая, что для любых блоков данных Т и К допустимого размера должно выполняться следующее условие: (Т ° К) • К = Т Сложность преобразования существенно повысится, если комбинировать с данными не непосредственно ключевой код, а код, выработанный из ключа и зависящий от данных. В этом случае преобразование осуществляется по следующему уравнению: Ti+1 = Ti ° f(Ti,Ki) На самом деле понятно, что с математической точки зрения данная запись мало отличается от наиболее общей формы записи преобразования: Ti + l = F(Ti,Ki) , (*) однако, в отличие от последней, она содержит некоторые указания на возможный способ своей реализации. Ее важная особенность заключается в том, что от функции преобразования f из первого уравнения уже не требуется обратимость, как от функции F из уравнения (*), от нее требуется только как можно большая сложность плюс выполнение некоторых дополнительных условий, которые в сильно упрощенном виде могут быть сформулированы как отсутствие потерь информации при ее вычислении. Дело в том, что при создании шифрующего преобразования общего вида бывает 273 Павел ЛомвшнДвниэЛьсШрвйй необходимо примирить два противоречащих друг другу требования. Преобразование должно быть обратимым - иначе расшифрование будет невозможным; преобразование должно быть достаточно сложным и нелинейным - в противном случае оно не может претендовать на то, чтобы являться подлинно шифрующим преобразованием. Понятно, почему указанные требования противоречат друг другу -выполнение обратного преобразования есть не что иное, как решение уравнения прямого преобразования относительно одного из его аргументов; однако, если уравнение нелинейное, то не существует общих методов его решения. Обратимость преобразования означает, что должна существовать эффективно вычислимая функция g(Ti+l,Ki), обладающая следующим свойством: f(Ti,Ki) = g(Tl+l,"KJ.) = g(Ti f(Ti,Ki),Ki) (**) для любых допустимых блоков данных Ti и Обратное преобразование выполняется в соответствии со следующим уравнением: Ti =g(Ti + l,Ki) В общем случае сконструировать пару функций преобразования (f и g), удовлетворяющих уравнению и являющихся при этом сложными и нелинейными, достаточно трудно. Тем не менее это возможно, если «отделить» требование сложности функций f и g от требования выполнения условия (**). Это легко можно сделать, если использовать операцию «°» модификации шифруемого блока, которая оставляет неизменным значение некоторой функции от преобразуемого блока данных. II » J(Ti) = J(Ti 0 Г1) = J(Ti+l) для любых блоков данных Ti, подходящего размера. Понятно, что в этом случае и обратная ей операциятакже обладает указанным свойством: J(Ti+l • П) = J(Ti) 274 0 ... 87 88 89 90 91 92 93 ... 169
|
