Модели шифров и открытых текстов

Базовым при использовании блочных шифров является режим простой замены. В связи с этим рассмотрим ряд вопросов, связанных с эксплуатацией блочных шифров в этом режиме и влияющих на их криптографическую стойкость.

Серьезным недостатком режима простой замены является то, что зашифрование одинаковых блоков исходного текста дает идентичные блоки шифртекста. В результате криптоаналитик лишь на основе шифрованных данных может делать выводы о свойствах исходного текста. Примером таких выводов может служить определение факта рассылки писем с одинаковым содержанием в несколько адресов. Если некоторые блоки открытого текста повторились, то во всех зашифрованных сообщениях, независимо от используемых ключей, на одинаковых местах будут встречаться повторяющиеся блоки шифрованных текстов.

Другой пример — передача ключей в зашифрованном виде по линиям связи. Повторение блоков в одном шифрованном тексте показывает, что часть битов в передаваемом ключе повторились и что в дальнейшем трудоемкость перебора ключей при их тотальном опробовании может быть сокращена за счет учета повторений.

Показательно, что при случайном выборе блоков открытого текста их повторение является не столь уж редким событием. Напомним известный парадокс "дней рождений", который заключается в том, что если имеется выборка объема, сравнимого с , из множества из N элементов, то вероятность того, что в ней окажутся два одинаковых элемента, сравнима с 1/2. Этот парадокс показывает, что при случай­ном выборе блоков открытого текста для получения повтора достаточно взять в среднем порядка блоков, где N — общее число блоков, которые теоретически могут встретиться в открытом тексте. Применительно к алгоритмам DES и ГОСТ, которые оперируют с двоичными векторами длины 64, это означает, что в среднем, уже среди 232 блоков открытого текста, будут встречаться повторяющиеся. Следует отметить, что при шифровании осмысленных текстов на естественных языках повторения будут появляться еще чаще, поскольку в осмысленных текстах в силу используемой лексики и грамматических правил встречаются далеко не все сочетания букв и знаков алфавита.

К блочным шифрам, используемым в режиме простой замены, могут быть применены и некоторые методы анализа шифров простой замены в обычных алфавитах. В частности, при достаточно большой длине шифртекста можно применять методы анализа, использующие статистические характеристики открытых текстов. Например, вычисляя частоты появления блоков в шифрованном тексте и проводя опробование часто повторяющихся блоков, начиная с наиболее вероятных сочетаний знаков в открытом тексте, можно составить словарь соответствия между блоками открытого и шифрованного текстов. Далее, развивая текст по смыслу с учетом избыточности открытых текстов, найденные блоки открытого текста можно дополнять соседними блоками. При этом одновременно восстанавливается открытый текст и дополняется словарь соответствия. Этот метод эффективен, когда наблюдается стандартность переписки. Например, всегда стандартны заголовки деловых бумаг, юридических и прочих документов.

Еще одна слабость блочных шифров в режиме простой замены при шифровании осмысленных текстов связана с тем фактом, что в открытом тексте могут появляться не все сочетания знаков, что проявляется в фактическом сокращении числа используемых соответствий между блоками открытого и шифрованного текстов. Однако эта слабость легко устранима, если перед шифрованием применить к открытому тексту процедуру сжатия информации, например использовать стандартные алгоритмы архивации данных.

Следующим моментом, на который следует обратить внимание, является проблема последнего неполного блока данных при шифровании текстов, длины которых не кратны размеру блока. При использовании блочного шифра этот неполный блок должен быть каким-либо образом дополнен до стандартной длины. Если при этом алгоритм дополнения выбран неудачно, например, блок дополняется одними нулями, то при определении соответствующего блока открытого текста у криптоаналитика появляются дополнительные возможности. Эта проблема может показаться надуманной, поскольку относится только к последнему блоку сообщения. Однако именно в конце сообщения обычно ставится подпись и, следовательно, появляются подходы к определению по шифртексту авторства сообщения.

Отдельно остановимся на методах анализа криптографических алгоритмов, основанных на принципе многократного использования блочных шифров. Р.Меркль и М.Хеллман на примере DES показали, как, используя метод встречи посередине, можно вскрыть схему двукратного шифрования.

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

Предположим, что известны блок М открытого текста и соответствующий ему блок С шифрованного текста. Алгоритм вскрытия неизвестных ключей k1 и k2 состоит из двух этапов.

На первом этапе перебираются все возможные варианты ключа k. Для каждого варианта k ключа k вычисляются значения ADR(k) = Ek(M), после чего значения k помещаются в память по адресу ADR(k).

На втором этапе опробуются возможные варианты ключа k2. Для опробуемого варианта k' ключа k2 вычисляются значения ADR(k') = Dk'(C) и производится обращение в память по адресу ADR(k'). Если по этому адресу памяти записи отсутствуют, то происходит переход к опробованию следующего варианта k' ключа k2. Если же по адресу ADR(k') в памяти хранится ключ k, то образуется допустимая пара ключей (k, k'), удовлетворяющая равенству С = Еk',(Еk(М)).

Заметим, что в ячейку памяти с номером ADR(k') могут попасть несколько вариантов ключа k (для этого память необходимо соответствующим образом организовать). Для каждого из них пара (k,k') является допустимым ключом.

Несложно заметить, что для реализации данного алго­ритма требуется 2|К| опробований и столько же операций обращения к памяти, где |К| — общее число ключей шифра.

Таким образом, вместо |К|2 операций, требуемых при полном переборе ключей, затраты метода встречи посередине составляют порядка 4|К| операций (операции опробования и обращения к памяти для простоты считают приблизительно равносильными по сложности). Заметим, что такой резкий эффект снижения трудоемкости достигается за счет использования большой (и специальным образом организованной) памяти.

В заключение отметим, что помимо перебора ключей и метода встречи посередине, при исследованиях блочных шифров успешно применяются методы линейного и дифференциального анализа.

Идея метода линейного анализа состоит в линеаризации уравнений шифрования, то есть замене сложных преобразований, описывающих алгоритм шифрования, их приближениями в классе линейных функций. Под приближением в классе линейных функций (или линейным аналогом) понимается линейная функция, значения которой для достаточно большого числа наборов аргументов совпадают со значениями данной функции шифрования. Чем выше вероятность совпадения значений линейного аналога со значениями функции шифрования при случайном и равновероятном выборе аргументов, тем лучше качество аналога.

Таким образом, линейный анализ сводит задачу определения ключей к решению системы линейных уравнений, в которой правые части уравнений известны с некоторой вероятностью. Из общих принципов математической статистики вытекает, что если распределение значений правых частей уравнений системы отлично от равномерного распределения, и имеется достаточно большое число уравнений, то решение такой системы линейных уравнений может быть найдено статистическими методами.

Блочные шифры строятся, как правило, по итеративному принципу. Поэтому даже использование на каждой итерации функций, не имеющих хороших аналогов, не гарантирует отсутствия аналогов в результирующем преобразовании. Проблема построения блочных шифров, для которых удается доказать отсутствие линейных аналогов, является весьма сложной задачей современной прикладной криптографии.

Методы дифференциального (или иначе, разностного) анализа строятся в предположении, что криптоаналитик имеет для анализа несколько текстов, зашифрованных на одном ключе, и дополнительно предполагается известной информация о том, как различаются между собой открытые тексты (при этом сами открытые тексты могут быть неизвестны). В этом случае криптоаналитик получает информацию о том, как заданные отличия в открытых текстах проявляются в шифртекстах, или, другими словами, как разность аргументов шифрующего преобразования отражается на изменении его значений. Поскольку шифрующее преобразование однознач­но определяется ключом, то информация о зависимостях между разностями значений аргументов и разностями соответствующих значений функции шифрования может быть использована при построении алгебраических и статистических методов вскрытия ключей алгоритма шифрования.

Заметим, что аналогичная ситуация возникает в случае, когда криптоаналитику удается получить результат зашифрования некоторого сообщения на разных ключах с дополнительной информацией о различиях использованных ключей. В ряде работ некоторые разновидности такого подхода, получившие общее название метода дифференциальных искажений, применялись для вскрытия ключей криптографических алгоритмов, использовавшихся для защиты информации в платежных системах на основе интеллектуальных карт.

ЗАКЛЮЧЕНИЕ

В данном реферате я привел общее понятие криптоанализа, попытался дать описание общего способа построения блочных шифров, рассмотрел методы криптоанализа, используемые для блочных шифров.

В заключение необходимо сказать, что при практическом использовании блочных шифров, помимо чисто криптографических проблем, необходимо учитывать особенности конкретной системы криптографической защиты информации, ее функции и условия эксплуатации. Эти факторы определяют выбор режима шифрования и условий, в которых необходимо оценивать надежность построенной системы защиты.

Основными достоинствами режима простой замены являются простота реализации и тот факт, что изменения одного блока шифртекста вызывают изменения только в одном блоке открытого текста. К недостаткам этого режима, помимо упомянутых выше, можно отнести также неустойчивость системы защиты перед модификацией сообщения, заключающуюся в перестановке блоков шифртекста. Такое нарушение целостности данных может оказаться незамеченным, поскольку при расшифровании каждого блока будет получен осмысленный результат. В особенности это замечание касается передачи формализованных сообщений.

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

Для практического использования блочных шифров можно предложить модификацию режима простой замены, заключающуюся в замене части битов блоков открытого текста их порядковыми номерами в сообщении. Такой подход несколько снижает скорость передачи информации, поскольку часть блока перестает нести содержательную информацию. Но, с другой стороны, при такой модификации одинаковые блоки открытого текста вследствие различия их порядковых номеров будут представлены различными блоками шифрованного текста.

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

Однако оборотная сторона эффекта нераспространения искажений состоит в том, что появляется возможность целенаправленной модификации шифртекста и открытого текста с точностью до конкретного разряда. Кроме того, необходимо обеспечить уникальность гаммы, что требует для всех сообщений уникальных синхропосылок (иначе возможны повторения используемой гаммы).

Чаще блочные шифры используются в режиме шифрования с обратной связью, когда очередной блок шифртекста зависит не только от ключа, но и от предшествующих блоков шифртекста. Гаммирование с обратной связью устойчиво к перестановкам блоков шифрованного текста и к целенаправленным модификациям шифртекста. В таких системах отсутствует проблема последнего неполного блока данных и одновременно снимается острота проблемы обеспечения уникальности синхропосылки.

СПИСОК ЛИТЕРАТУРЫ

1.      Основы криптографии. Учебное пособие. / А.П. Алферов – М.: Гелиос-АРВ, 2007. – 480 с.

2.      Бабаш А.В., Шанкин Г.П. Криптография. – М.: СОЛОН-Р, 2009. – 512 с.

3.      Винокуров, А.В. Как устроен блочный шифр? / Андрей Винокуров // Вопросы криптографии. – М., - 2000. - №34. – С.19-21.

4.      NETCODE ЗАО [Электронный ресурс]. –  М.: NETCODE ЗАО, 2008. – . – Режим доступа: http://www.netcode.ru, свободный. – Загл. с экрана.

5.      CRYPTO-GRAPHY ЗАО [Электронный ресурс]. –  М.: CRYPTO-GRAPHY ЗАО, 2007. – . – Режим доступа: http://crypto-graphy.ru/, свободный. – Загл. с экрана.

3