Раздел: Документация
0 ... 84 85 86 87 88 89 90 ... 169 только криптоанализ, усложняется и сам алгоритм шифрования - вот почему неразумно увеличивать его сверх необходимого. Как мы увидим в следующем выпуске, для шифров очень распространенной на сегодняшний день архитектуры, называемой «сбалансированная сеть Файстеля» - balanced Feistel network, условием эффективной реализации в виде программы для ЭВМ является равенство половинного размера блока криптоалгоритма величине машинного слова. Именно поэтому реализация отечественного стандарта шифрования - алгоритма ГОСТ 28147-89, шифра с 64-битовым размером блока, - для 32-битовых процессоров Intel х86 существенно эффективнее реализации этого же алгоритма для 16-битовых процессоров той же серии (естественно, сравнение производилось на одном и том же компьютере). В настоящее времяколичествов ми- ре - 32-битовые и по этой причине выбирать размер блока для упомянутой архитектуры шифров больше 64 бит совершенно бессмысленно, а с точки зрения эффективности реализации - вредно. Хотя для блочных шифров с достаточно большим размером блока провести исчер-нывающий статистический анализ в общем случае невозможно, тем не анализируяданные, легко чие одинаковых блоков в исходных данных, что позволяет выявить стабильные паттерны, имеющиеся в них. Предположим, например, что целиком шифруется магнитный диск с информацией. На таком диске все незанятое пространство обычно заполнено фиксированными кодами, записанными туда при его форматировании. После шифрования на месте этого кода получатся одинаковые блокичто позволит злоумышленнику отличить незанятое пространство диска от пространства, заполненного полезными данными. Иногда это бывает неприемлемым, поэтому передданных их очень лезно сжимать архиваторами, что существенно снижает избыточность данных и уменьшает вероятность встретить повторяющиеся блоки. В тех случаях, когда данные имеют физическую привязку - как в приведенном примере с шифрованием- их рекомендуется рандомизировать - модифицировать с использованием случайных или псевдослучайных. Каким же условиям должен удовлетворять стойкий блочный шифр? Эти условия сформулировал Шеннон в ряде своих основополагающих работ по теории Такой шифр должен обладать свойствами перемешивания и рассеивания: , — рассеивание: это свойство шифра, при котором одни символ (бит) исходного текста влияет на несколько символов (битов) 263 текста, оптимально - на все символы в пределах одного блока. Если данное условие выполняется, то при шифровании двух блоков данных с минимальными отличиями между ними должны получаться совершенно непохожие друг на друга блоки шифротекста. Точно такая же картина должна иметь место и для зависимости шифротекста от ключа один символ (бит) ключа должен влиять на несколько символов (битов) шифротекста; — перемешивание: это свойство шифра скрывать зависимости между символами исходного текста и шифротекста. Если шифр достаточно хорошо «перемешивает» биты исходного текста, то соответствующий шифротекст не содержит никаких статистических, и, тем более, функциональных закономерностей - опять же для стороннего наблюдателя, обладающего лишь ограниченными вычислительными ресурсами. Если шифр обладает обоими указанными свойствами в достаточной степени, то любые изменения в блоке открытых данных приводят к тому, что с точки зрения наблюдателя все символы (биты) в зашифрованном блоке получат новые значения, равновероятные в области их определения и независимые друг от друга. Так, если шифр оперирует информацией, представленной в двоичной форме, то инвертирование даже одного бита в блоке исходных данных приведет к тому, что все биты в соответствующем блоке шифрованных данных с вероятностью 1/2 независимо друг от друга также поменяют свое значение. Такой шифр невозможно вскрыть способом, менее затратным с точки зрения количества необходимых операций, чем полный перебор по множеству возможных значений ключа. Данное условие является обязательным для шифра рассматриваемого типа, претендующего на то, чтобы считаться хорошим. Архитектура блочных шифров Можно выделить следующие группы простых шифров. Шифр перестановок Заключается в перестановках структурных элементов шифруемого блока данных - битов, символов, цифр. Шифр замен Заключается в замене одних значений на другие по индексной таблице, замене подвергаются группы элементов шифруемого блока - битов или символов. 264 Шифр функциональных преобразований Заключается в выполнении сдвигов, логических и арифметических операций над элементами данных. Ниже дана подробная характеристика каждого из упомянутых типов преобразований. Шифры перестановок чрезвычайно просто реализуются аппа-ратно - разводкой проводников на плате или в кристалле, при этом совсем не требуется каких-либо дополнительных затрат, так как проводники, связывающие регистры аппаратуры, так или иначе присутствуют в схеме. В то же самое время эти преобразования очень неэффективно реализуются программно на процессорах общего назначения. Как правило, вычислительные затраты составляют не менее двух машинных команд на каждый двоичный разряд в модифицируемом блоке, если только в перестановках нет согласованности. Этой причиной, в частности, объясняется тот факт, что многие шифры, широко использующие операции данного типа, имеют при прочих равных условиях существенно менее эффективные реализации по сравнению с шифрами, их не использующими. Например, американский стандарт шифрования криптоалгоритм DES при вдвое меньшем количестве шагов в цикле шифрования по сравнению с российским стандартом (16 против 32) имеет примерно вдвое более медленную оптимальную реализацию для процессоров mtelx86. Общие виды замен аппаратно реализуются с помощью запоминающих устройств, программно - индексированным чтением из оперативной памяти, что, по сути, одно и то же: замена для элемента данных х берется из вектора или узла замен V, являющегося массивом заменяющих значений, индексированным заменяемым элементом данных: х заменяется на у = V [х]. Программно такая операция реализуется за одну команду, не считая операции загрузки индекса в соответствующий регистр. Размер памяти, необходимый для хранения вектора заменяющих, определяется следующим соотношением: V = 2X-Y , где Х и Y - размеры заменяемого и заменяющего блоков в битах соответственно, размер вектора замен V также получается в битах. Из приведенной формулы видно, что он растет экспоненциально с ростом размера заменяемого блока. В силу этого выполнение подстановки в масштабах всего шифруемого блока невозможно - потребо- 265 0 ... 84 85 86 87 88 89 90 ... 169
|
