Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
достаточно взять в среднем порядка блоков, где N — общее число блоков, которые теоретически могут встретиться в открытом тексте. Применительно к алгоритмам DES и ГОСТ, которые оперируют с двоичными векторами длины
64, это означает, что в среднем, уже среди 232 блоков открытого текста, будут встречаться повторяющиеся. Следует отметить, что при шифровании осмысленных текстов на естественных языках повторения будут появляться еще чаще, поскольку в осмысленных текстах в силу используемой лексики и грамматических правил встречаются далеко не все сочетания букв и знаков алфавита.
232
ьлочные системы шифрования
К блочным шифрам, используемым в режиме простой замены, могут быть применены и некоторые методы анализа шифров простой замены в обычных алфавитах. В частности, при достаточно большой длине шифртекста можно применять методы анализа, использующие статистические характеристики открытых текстов. Например, вычисляя частоты появления блоков в шифрованном тексте и проводя опробование часто повторяющихся блоков, начиная с наиболее вероятных сочетаний знаков в открытом тексте, можно составить словарь соответствия между блоками открытого и шифрованного текстов. Далее, развивая текст по смыслу с учетом избыточности открытых текстов, найденные блоки открытого текста можно дополнять соседними блоками. При этом одновременно восстанавливается открытый текст и дополняется словарь соответствия. Этот метод эффективен, когда наблюдается стандартность переписки. Например, всегда стандартны заголовки деловых бумаг, юридических и прочих документов.
Еще одна слабость блочных шифров в режиме простой замены при шифровании осмысленных текстов связана с тем фактом, что в открытом тексте могут появляться не все сочетания знаков, что проявляется в фактическом сокращение числа используемых соответствий между блоками открытого и шифрованного текстов. Однако эта слабость легко устранима, если перед шифрованием применить к открытому текст) процедуру сжатия информации, например использовать стан дартные алгоритмы архивации данных.
Следующим моментом, на который следует обрати внимание, является проблема последнего неполного блок* данных при шифровании текстов, длины которых не кратнь размеру блока. При использовании блочного шифра этот неполный блок должен быть каким-либо образом дополнен д( стандартной длины. Если при этом алгоритм дополнения вы бран неудачно, например, блок дополняется одними нулями то при определении соответствующего блока открытого тек ста у криптоаналитика появляются дополнительные возмож
23
Ілава 8
ности. Эта проблема может показаться надуманной, поскольку относится только к последнему блоку сообщения. Однако именно в конце сообщения обычно ставится подпись и, следовательно, появляются подходы к определению по шифртек-сту авторства собщения.
Отдельно остановимся на методах анализа криптографических алгоритмов, основанных на принципе многократного использования блочных шифров. Р. Меркль и М. Хеллман [Мег, Неї] на примере DES показали, как, используя метод встречи посередине, можно вскрыть схему двукратного шифрования.
Рассмотрим метод вскрытия блочного шифра при использовании двойного шифрования в общем случае.
Предположим, что известны блок M открытого текста и соответствующий ему блок С шифрованного текста. Алгоритм вскрытия неизвестных ключей кх и к2 состоит из двух этапов.
На первом этапе перебираются все возможные варианты ключа к . Для каждого варианта к ключа к вычисляются значения ADR(k) = Ek(M), после чего значения к помещаются в память по адресу ADR(k).
На втором этапе опробуются возможные варианты ключа к2. Для опробуемого варианта к’ ключа к2 вычисляются значения ADR(k') = Dk'(C) и производится обращение в память по адресу ADR(V). Если по этому адресу памяти записи отсутствуют, то происходит переход к опробованию следующего варианта к' ключа к2. Если же по адресу ADR(V) в памяти хранится ключ к, то образуется допустимая пара ключей (?,&'), удовлетворяющая равенству С = Ek,(Ek(M)).
234
Ьлочные системы шифрования
Заметим, что в ячейку памяти с номером ADR(k') могут
попасть несколько вариантов ключа к (для этот память необходимо соответствующим образом организовать). Для каждого из них пара (к,к') является допустимым ключом.
Несложно заметить, что для реализации данного алгоритма требуется 2\К\ опробований и столько же операций
обращения к памяти, где | АГ| — общее число ключей шифра.
Таким образом, вместо JATj2 операций, требуемых при полном переборе ключей, затраты метода встречи посередине составляют порядка 4|ЛТ| операций (операции опробования и обращения к памяти для простоты считают приблизительно равносильными по сложности). Заметим, что такой резкий эффект снижения трудоемкости достигается за счет использования большой (и специальным образом организованной) памяти.
В заключение отметим, что помимо перебора ключей и метода встречи посередине, при исследованиях блочных шифров успешно применяются методы линейного и дифференциального анализа.