Научная литература
booksshare.net -> Добавить материал -> Криптография -> Алферов А.П. -> "Основы криптографии Учебное пособие" -> 60

Основы криптографии Учебное пособие - Алферов А.П.

Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие — М.: Гелиос АРВ, 2002. — 480 c.
ISBN 5-85438-025-0
Скачать (прямая ссылка): osnovikriptografii2005.djvu
Предыдущая << 1 .. 54 55 56 57 58 59 < 60 > 61 62 63 64 65 66 .. 126 >> Следующая


достаточно взять в среднем порядка блоков, где 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|ЛТ| операций (операции опробования и обращения к памяти для простоты считают приблизительно равносильными по сложности). Заметим, что такой резкий эффект снижения трудоемкости достигается за счет использования большой (и специальным образом организованной) памяти.

В заключение отметим, что помимо перебора ключей и метода встречи посередине, при исследованиях блочных шифров успешно применяются методы линейного и дифференциального анализа.
Предыдущая << 1 .. 54 55 56 57 58 59 < 60 > 61 62 63 64 65 66 .. 126 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed