Лабораторная работа № 2.2
Тема: Криптоанализ потоковых симметричных шифров.
Цель: Ознакомиться с принципом взлома криптосистемы, основанной на использовании регистра сдвига с линейной обратной связью.
Задание:
1. Изучить основные теоретические положения касательно криптоанализа шифра на базе РСЛОС по известным длине регистра и битам шифрованной последовательности.
2. Определить вид ассоциированного многочлена РСЛОС, основываясь на заданной согласно варианту последовательности бит шифротекста. Длину регистра принять равною 
.
Структура отчета
1. Титульный лист.
2. Тема и цель работы.
3. Задание и, если есть, номер варианта.
4. Краткие теоретические сведения.
5. Ход работы с включением расчетов, программных кодов и результатов работы программ.
6. Выводы.
Теоретические сведения
Стойкость шифрования
При проектировании криптографических систем нужно иметь абсолютно точное представление о том, какие именно свойства стойкости обеспечивает тот или иной примитив и как защитить разрабатываемые схемы от всех возможных атак.
Существуют три вида стойкости:
- теоретико-информационная или абсолютная стойкость;
- семантическая стойкость;
- полиномиальная стойкость.
Обсудим каждый из них поочередно.
Теоретико-информационная стойкость. Криптосхема называется абсолютно стойкой (обладает теоретико-информационной стойкостью), если нападающий с неограниченными вычислительными возможностями не сможет извлечь никакой информации об открытом тексте, используя данный шифротекст. Теоретически ключ такой системы равен по длине самому сообщению, причем никакой ключ нельзя использовать дважды. Очевидно, абсолютно стойкую систему невозможно создать.
Семантическая стойкость. Семантическая стойкость похожа на теоретико-информационную, но здесь предполагается, что атакующий обладает полиномиальными вычислительными возможностями. Говоря формально, все что нападающий может вычислить за полиномиальное время о данном открытом тексте по данному шифротексту, он может узнать и без шифротекста. Другими словами, обладание шифротекстом никак не помогает извлечь информацию о сообщении.
Полиномиальная стойкость. Неприятность, связанная с семантической стойкостью, заключается в том, что очень трудно проверить, обладает ли конкретная схема этим свойством. Полиномиальная стойкость, иногда называемая неразличимостью шифрования, является несравненно более просто проверяемым свойством.
Система, обладающая полиномиальной стойкостью, семантически стойка. Следовательно, чтобы проверить криптосистему на семантическую стойкость, достаточно продемонстрировать ее полиномиальную криптостойкость.
Будем говорить, что система обладает свойством неразличимости шифрования, или полиномиальной стойкостью, если никакой атакующий, сгенерировав два открытых текста 
и получив от интересующего абонента два шифротекста 
не сможет определить, которому открытому тексту соответствует который шифротекст с вероятностью, превышающей 50%.
Теперь следует ввести различные модели атак. Существует три основных модели:
- пассивная атака, или атака с выбором открытого текста, СРА (от англ. chosen plaintext attack);
- атака с выбором шифротекста, ССА1 (от англ. chosen ciphertext attack);
- адаптивная атака с выбором шифротекста, ССА2 (от англ. adaptive chosen ciphertext attack).
Пассивная атака. Пассивная атака – очень слабая форма атаки. Злоумышленнику разрешается просматривать различные шифрованные сообщения. Кроме того, ему открыт доступ к «черному ящику», осуществляющему шифрование, но не расшифровывание. Таким образом, пассивная атака – простейшая модель нападения на криптосистему, поскольку она предусматривает открытый доступ к функции шифрования.
Атака с выбором шифротекста. Атака с выбором шифротекста, которую часто называют атакой «обеденного перерыва», представляет собой несколько более сильную модель нападения. Здесь злоумышленнику предоставлен доступ к расшифровывающему «черному ящику» (функции дешифрования). Он может предлагать «ящику» расшифровать некоторое число шифротекстов по его выбору, пока абонент, на которго напралена атака не контролирует «ящик» (вышел на «обеденный перерыв»). После этого, спустя некоторое время, злоумышленнику дают тестовый шифротекст и предлагают дешифровать его или восстановить какую-нибудь информацию о подлежащем открытом тексте собственными силами, не прибегая к помощи «черного ящика».
Адаптивная атака с выбором шифротекста. Адаптивная атака с выбором шифротекста – наиболее сильная форма атаки. В этом случае злоумышленнику можно пользоваться расшифровывающим прибором длярасшифровывания любого шифротекста
по ее выбору, кроме тестового. Принято считать, что любая вновь предлагаемая криптосистема с открытым ключом должна обладать полиномиальной стойкостью по отношению к адаптивной атаке с выбором шифротекста.
Алгоритм шифрования называют стойким, если он семантически стоек в отношении адаптивной атаки с выбором шифротекста. Однако легче проверить, что данная криптосистема удовлетворяет следующему определению. Алгоритм шифрования называют стойким, если он полиномиально стоек в отношении адаптивной атаки с выбором шифротекста.
При пассивном нападении полиномиально стойкая система обязана быть семантически стойкой.
Криптоанализ системы основанной на РСЛОС
Стандартный способ генерирования потока битов основан на использовании регистра сдвига с обратной связью. Это микросхема с ячейками памяти, в каждой из которых записан один бит информации. Множество таких ячеек и образует регистр. На каждом шаге содержимое нескольких заранее определенных ячеек, которые называются отводами пропускается через функцию обратной связи.
А ее значение записывается в самую левую ячейку регистра, сдвигая все остальные его биты на одну позицию вправо. Самый крайний справа, «вытолкнутый» из регистра, бит — выход регистра сдвига на данном шаге (рис. 1).
Рис. 1. Регистр сдвига с обратной связью
По причинам, о которых мы будем говорить позже, в качестве функций обратной связи желательно брать нелинейные функции. Однако это сложно осуществитьна практике, и поэтому пользуются регистром сдвига с линейной обратной связью или, сокращенно, РСЛОС, функция обратной связи в котором линейна. Этот регистр устроен так же, как и общий, описанный выше. Но в качестве функции обратной связи берется логическая операция XOR исключающего ИЛИ.
На языке математики работу регистра длины 
можно описать следующим образом. Задается последовательность битов 
, в которой на отводах стоят единицы, а в остальных ячейках — нули.
Допустим, что в начальном положении в регистре записана последовательность 
. На выходе регистра получается последовательность 
, где при 
Заметим, что если в начальном состоянии регистра во всех его ячейках стояли нули, то и на выходе мы будем получать сплошные нули.
Если же стартовая последовательность была нетривиальной, то генерируемая последовательность, в конечном счете, окажется периодической.
Действительно, число возможных последовательностей длины конечно, и меняя их на каждом шагу, мы волей-неволей получим одну из уже встречавшихся. После этого, ввиду детерминированности процесса, мы получим периодичность. Напомним, что периодом последовательности называется наименьшее натуральное число 
, при котором для всех достаточно больших значений параметра 
выполняется равенство 
.
Нетрудно подсчитать, что существует 2 
-1 разных ненулевых начальных состояний регистра. Поэтому максимум, на что можно рассчитывать, это на то, что регистр сдвига с линейной обратной связью при любом ненулевом начальном положении будет генерировать последовательность битов периода 2 -1. Свойства выдаваемой РСЛОС последовательности тесно связаны со свойствами двоичного многочлена
,
ассоциированного с этим регистром. Его ненулевые коэффициенты называются отводами, как и соответствующие ячейки регистра, поставляющие значения аргументов функции обратной связи. На рис. 2 изображен РСЛОС, ассоциированный с многочленом 
, а на рис. 3 – с многочленом 
.
Рис. 2. Регистр сдвига с линейной обратной связью для ассоциированного многочлена
Свойства последовательности битов, генерируемой РСЛОС зависят от ассоциированного многочлена:
1. Если старший коэффициент ассоциированного многочлена 
, то периодичность генерируемой последовательности может проявиться не сразу.
2. Если 
= 1, то соответствующая последовательность называется неособой. Она будет периодичной с самого начала, т.е. равенство 
выполнено для всех , а не только для достаточно больших.
Рис. 3. Регистр сдвига с линейной обратной связью для ассоциированного многочлена
Наиболее интересны неособые последовательности, соответствующие многочленам со следующими дополнительным свойством: когда 
неприводим, при любом ненулевом начальном состоянии регистра период генерируемой последовательности равен наименьшему числу , при котором многочлен делит 1 
. Как следствие, период последовательности будет делить число 2 -1.
В качестве примера рассмотрим РСЛОС с ассоциированным многочленом . Генерируемая последовательность в этом случае имеет вид
Допустим, что перед началом процесса в регистре записана последовательность [0,0,1], тогда период генерируемого потока битов будет равен 7, и мы получаем последовательность, представленную в табл. 1.
Поскольку внутреннее состояние на седьмом шаге вернулось к исходному, то начиная со следующего шага мы будем получать повторения.
Мы не будем здесь обсуждать существующие алгоритмы, генерирующие примитивные многочлены. Ограничимся лишь небольшим списком таких многочленов с малым числом отводов. Очевидно, что чем меньше отводов в многочлене, тем быстрее работает соответствующий регистр сдвига.
Хотя РСЛОС быстро генерирует поток битов, исходя из ключа малого размера, особенно при аппаратной реализации, они плохо подходят для целей криптографии ввиду их линейности, собственно, именно того свойства, которое придает им высокую эффективность в аппаратных средствах.
Таблица 1. Пример генерируемой последовательности бит
Обосновывая слабую криптостойкость линейных регистров, покажем, что зная длину регистра и 21 последовательных битов, вышедших из РСЛОС, можно вычислить весь генерируемый поток. Заметим, что для этого нам достаточно определить значения отводов, т. е. набор 
коэффициентов ассоциированного многочлена, поскольку стартовое состояние регистра 
можно взять из известной нам последовательности сгенерированных битов. Такие данные можно получить с помощью атаки с известным открытым текстом, когда мы получаем шифрограмму, соответствующую известной нам части исходного сообщения. Напомним, что функция обратной связи в этой ситуации — просто сложение значений отводов по модулю 2, действующая по формуле
.
Используя это соотношение для 
, получим систему линейных уравнений с неизвестными 
, которые нам и нужно определить. В матричной форме эта система выглядит следующим образом:
.
Предположим, что мы перехватили последовательность битов
1,1,1,1,0,1,0,1,1,0,0,1,0,0,0,...,
созданную 4-битовым РСЛОС.
Предыдущая система уравнений примет вид:
.
Подставляя в нее элементы перехваченной последовательности получим:
.
Получим систему уравнений:
.
Решим систему по модулю 2 и найдем:
Тогда многочлен, ассоциированный с РСЛОС, равен 
. Можно сделать вывод, что поточный шифр, основанный на единственном РСЛОС, беззащитен перед атаками с известным открытым текстом.
Мерой криптографического качества последовательности бит служит понятие линейной сложности последовательности.
Линейной сложностью бесконечной последовательности битов
называется величина 
равная
- 0, если S — последовательность нулей,
- 
, если S нельзя получить с помощью какого-нибудь РСЛОС,
- длине наименьшего РСЛОС, выдающего последовательность s в остальных случаях.
Поскольку бесконечную последовательность битов просмотреть невозможно, ограничиваются ее первыми п элементами, обозначая эту часть как 
. Имеют место следующие свойства.
- Длялюбого 
выполнено неравенство 
.
- Если последовательность s периодична и ее период равен , то 
.
- 
Ожидаемая линейная сложность случайной двоичной последовательности (именно ее мы и хотели бы видеть в качестве потока ключей) должна быть больше, чем 
. С другой стороны, РСЛОС длины выдает последовательность, чья линейная сложность удовлетворяет соотношению: 
для всех 
. Таким образом, линейный регистр генерирует потоки битов слишком далекие от случайных.
Как мы видели, зная длину РСЛОС и генерируемую им последовательность битов, можно вычислить ассоциированный с регистром многочлен. Для определения длины регистра используется ряд линейных сложностей, т.е. последовательность 
. Кроме того, существует эффективный алгоритм Берлекэмпа - Мэсси, вычисляющий ряд линейных сложностей 
для данной конечной последовательности .
Следовательно, при генерировании потока ключей регистром сдвига с линейной обратной связью длины , атакующий, получив не более 21 последовательных битов этого потока, может раскрыть регистр полностью и самостоятельно производить бегущий ключ любой нужной ему длины. Поэтому возникает необходимость найти нелинейный способ эксплуатации РСЛОС, при котором генерируемая последовательность обладает высокой линейной сложностью.
Контрольные вопросы
1. Нарисуйте схему регистра сдвига с обратной связью.
2. Что такое отвод?
3. Что такое период последовательности?
4. Дайте определение ассоциированному многочлену.
5. Опишите свойства последовательности, генерируемой РСЛОС, зависящие от ассоциированного многочлена.
6. Что такое неособая последовательность?
7. Что такое линейная сложность?
8. Каким образом можно определить значение ассоциированного многочлена РСЛОС по заданной последовательности шифротекста?
9. Чем определяется стойкость системы основанной, на использовании РСЛОС.
10. Как повысить криптостойкость потоковой криптосистемы?
11. Что такое криптостойкость?
12. Какие виды стойкости существуют?
13. Какие виды атак на криптосистему вам известны?
Варианты заданий
| № варианта | Значения последовательности шифротекста | |