rijndael (1085220), страница 5
Текст из файла (страница 5)
3.2.3 Построение линейного приближения.
Как только была собрана информация о линейных приближениях для S-блока, мы можем начать построение линейных приближений полного шифра. Это достигается путем связывания соответствующих линейных приближений S-блоков. Построение линейного приближения, содержащего биты открытого текста и биты входа последнего раунда, дает возможность напасть на шифр, извлекая биты подключа последнего раунда. Рассмотрим детально построение линейного приближения для нашего криптоалгоритма.
В нашем построении мы будем использовать два линейных приближения S-блока.
Пусть и будут теперь суммой входа и суммой выхода нашей системы, имеющих длину 32 бит. Записывать их значения будем в виде 8 шестнадцатиричных цифр. Зададим значение для равное [09 09 09 09], которое соответствует линейной комбинации бит входной последовательности
и по которому требуется определить значение для .
По аналогии с дифференциальным криптоанализом, подробно исследуем действие каждого преобразования на приближение. Обозначения для них оставим прежние.
Для начала возьмем преобразование AddRoundKey(), чтобы узнать влияние ключа. До преобразования X и — это последовательности бит состояния и ключа раунда i, соответственно. Тогда на выходе преобразования мы получаем последовательность и линейное приближение
Далее эта последовательность X' поступает на вход нелинейного преобразования SB, на котором мы стараемся выбрать такие линейные приближения S-блока, чтобы их можно было бы соединить между раундами. Этот выбор непосредственно влияет на вероятность и отклонение конечного приближения всего шифра. В нашем случае выберем линейное приближение S-блока . После преобразования получаем последовательность X'' и линейное приближение
или
Полученная комбинация выполняется с вероятностью
Преобразование SR работает как перестановка индексов нашего приближения и в итоге получаем последовательность X''' и линейное приближение (из-за симметричности оно остается прежним), вероятность которого не изменяется
В преобразование MC следует подробно исследовать зависимость каждого бита на выходе от бит на входе преобразования. Снова (как и в дифференциальном анализе) рассмотрим только первые два байта и состояния S. Тогда состояние S равняется
или более подробно
В нашем случае нужно получить выражение, зависящее от бит , , и . Для этого рассмотрим линейную комбинацию бит .
В итоге, после преобразования получаем последовательность X'''' и линейное приближение, вероятность которого по прежнему не изменяется
Далее снова следует преобразование AddRoundKey(), которое добавит к нашему приближению сумму определенных бит ключа первого раунда. И пусть — последовательность бит состояния после этого преобразования. В результате, мы получаем линейное приближение первого раунда
где
вероятность которого равна , а отклонение e=+1/32.
Проделав те же операции для второго раунда, получим линейное приближение первых двух раундов, которое и требовалось построить
где
Вероятность полученного приближения равна
а отклонение равно e=+1/32.
Следует заметить, что мы получили линейное приближение с одинаковыми суммой входа и суммой выхода . В результате, если исключить сумму бит ключа с правой стороны приближения, то полученное выражение
должно выполняться с вероятностью , если сумма , или с вероятностью , если сумма . Но в любом случае эффективность приближения будет равна |e|=1/32.
3.2.4 Извлечение бит подключа последнего раунда.
Если обнаружено линейное приближение R-1 раундов с достаточно большой вероятностью для шифра с числом раундов R, то можно напасть на шифр, извлекая биты подключа последнего раунда. В нашем случае, возможно извлечь биты из подключа последнего раунда. Этот процесс основывается на частичном расшифровании последнего раунда шифртекста. Те позиции подключа , которые были бы вовлечены в приближение на последнем раунде, называются целевым частичным подключем.
В нашем случае, в целевой частичный подключ входят биты с 4 по 7, с 12 по 15, с 20 по 23 и с 28 по 31. Соответственно, нам нужно перебрать все возможных значения подключа
Для каждого значения подключа мы выберем случайных открытых текстов X. Далее для каждого такого текста получим шифртекст на неизвестном ключе K (предполагаем, что нам заранее были известен набор пар открытого текста и шифртекста), и произведем его частичное расшифрование на текущем ключе-кандидате. Подставим значения бит в наше линейное приближение и проверим выполняется ли оно. Если результат верный (то есть приближение выполняется), то увеличиваем счет ключа-кандидата. В конце подсчитываем вероятность p выполнения приближения и эффективность |e| для каждого значения подключа.
Ниже приведена часть результата нашей атаки.
| |e| | |
| F A 1 9 | 0.01209 |
| F A 1 A | 0.00659 |
| F A 1 B | 0.00854 |
| F A 1 C | 0.00940 |
| F A 1 D | 0.00146 |
| F A 1 E | 0.00964 |
| F A 1 F | 0.00024 |
| F A 2 0 | 0.00610 |
| F A 2 1 | 0.01025 |
| F A 2 2 | 0.00452 |
| F A 2 3 | 0.03040 |
| F A 2 4 | 0.00354 |
| F A 2 5 | 0.00745 |
| F A 2 6 | 0.00488 |
| F A 2 7 | 0.01282 |
| F A 2 8 | 0.02075 |
| F A 2 9 | 0.00842 |
| F A 2 A | 0.01599 |
| F A 2 B | 0.00476 |
| F A 2 C | 0.01575 |
| F A 2 D | 0.00403 |
Как видно из результатов, полученная эффективность очень близка к ожидаемой (1/32=0.03125). В итоге мы получили 16 бит ключа третьего раунда из 32 возможных (знак x означает неизвестные биты)
3.2.5 Восстановление исходного ключа.
Для восстановления исходного ключа воспользуемся теми же выражениями, которые использовались в дифференциальном криптоанализе. С их помощью мы получим 16 бит исходного ключа K. Мы можем это сделать, так как подстановка SB[] действует на 2 полубайта независимо, а в операции Å эти полубайты так же не зависят друг от друга.
В следующих выражениях под обозначением k понимается младший полубайт байта ключа.
Так как мы знаем значения младших полубайтов ключа , то можем получить сначала подключи и , а затем и , то есть ключ .
Подобным образом мы находим ключ и собственно исходный ключ K.
K=[xB xE x5 x6]
Оставшиеся 16 бит найдем простым перебором.
K=[2B 7E 15 16]
3.2.6 Эффективность криптоанализа.
Всего был использован одно линейное приближение. Для него число вариантов подключей равнялось . Для каждого подключа было проанализировано пар открытых текстов. То есть всего было произведенно зашифрований.
Для отсавшихся 16 бит ключа перебирались вариантов, то есть было произведенно зашифрований, что значительно меньше числа шифрований для восстановления первых 16 бит ключа. Следовательно, этим перебором можно пренебречь.
Откуда следует, что линейный криптоанализ оказался на 3 порядка эффективнее, чем метод полного перебора, и наша криптосистема оказалась нестойкой к данному методу криптоанализа.
3.2.7 Программная реализация.
Исходный код на языке C++ для линейного криптоанализа приведен в Приложении 3.
4. Криптосистема как генератор псевдослучайных последовательностей.
Чтобы получить генератор псевдослучайных последовательностей, будем использовать нашу криптосистему в режиме сцепления блоков. Это значит, что она функционирует по следующей схеме
Начальная инициализация последовательности задается значением и ключом K. Последовательность строится начиная со значения .
Для тестирования зададим следующие значения и ключом K=[2B 7E 15 16].
4.1 Введение.
Статистический тест формулируется для проверки определенной нулевой гипотезы о том, что проверяемая последовательность является случайной. С этой нулевой гипотезой связана альтернативная гипотеза о том, что последовательность неслучайна. Для каждого применяемого теста получают заключение о принятии или отклонении нулевой гипотезы, основываясь на сформированной исследуемым генератором последовательности.
Для каждого теста должна быть выбрана подходящая статистика случайности для принятия или отклонения нулевой гипотезы. Согласно предположению о случайности, такая статистика имеет распределение возможных значений. Теоретическое эталонное распределение этой статистики для нулевой гипотезы определяется математическими методами. Из этого эталонного распределения определяется критическое значение. Во время проведения теста вычисляется значение тестовой статистики. Это значение сравнивается с критическим значением. Если значение тестовой статистики превышает критическое значение, нулевая гипотеза для случайности отклоняется. В противном случае нулевая гипотеза принимается.
Проверка статистической гипотезы — процедура генерации заключения, которая имеет два возможных результата — или принять (данные случайны), или принять (данные неслучайны).
Если данные на самом деле случайны, то заключение об отклонении нулевой гипотезы (т. е. что данные неслучайны) будет приниматься крайне редко. Это заключение называется ошибкой первого рода. Если данные неслучайны, то заключение о принятии нулевой гипотезы (т. е. что данные случайны) называется ошибкой второго рода. Заключения о принятии , когда данные действительно случайны, и отклонении , когда данные неслучайны, являются правильными.
Вероятность ошибки 1-го рода называется уровнем значимости теста. Эта вероятность может быть установлена до испытания и обозначается как a. Для теста a суть вероятность того, что тест укажет на неслучайность последовательности, тогда как на самом деле она является случайной. То есть на то, что последовательность имеет неслучайные свойства, даже если ее произвел хороший генератор.
Вероятность ошибки 2-го рода обозначается как b. Для теста b есть вероятность того, что тест укажет на случайность последовательности, тогда как это не так; т. е. плохой генератор произвел последовательность, которая, как кажется, имеет случайные свойства. В отличие от a, b не является фиксированным значением; b могут принимать множество различных значений, потому что существует бесконечное число ситуаций, когда поток данных может быть неслучаен, и каждая из них выдает различные b. Вычисление ошибки 2-го рода является более сложным из-за множества возможных типов неслучайности.
Одной из основных целей нижеописанных тестов является минимизация вероятности ошибки 2-го рода, иначе говоря, минимизация вероятности принятия последовательности, произведенной плохим генератором, за последовательность, произведенную хорошим генератором. Вероятности a и b связаны друг с другом и с длиной n проверяемой последовательности: если два из этих значений определены, третье определяется автоматически. На практике обычно выбирают размер n и значение для a (вероятности ошибки 1-го рода). Тогда критическая точка для данной статистики выбирается так, чтобы получить наименьшее значение b (вероятность ошибки 2-го рода).
4.2 Общее описание набора тестов Руководства НИСТ.
Каждый тест основан на вычислении значения тестовой статистики, которое является функцией данных. Если значение тестовой статистики есть S, a t — критическое значение, то вероятность ошибки 1-го рода и 2-го рода есть соответственно
Тестовая статистика использует вычисление значения P-value, которое констатирует силу доказательства против нулевой гипотезы, иначе говоря, P-value есть вероятность того, что совершенный генератор случайных чисел произвел бы последовательность менее случайную, чем исследуемая, для типа неслучайности, проверяемого тестом. Если P-value для теста равно 1, то последовательность абсолютно случайна. P-value, равное 0, указывает, что последовательность абсолютно неслучайна. Для теста следует выбрать уровень значимости a. Если значение P-value больше или равно a, то принимается нулевая гипотеза, т. е. последовательность кажется случайной. Если значение P-value меньше a, то нулевая гипотеза отклоняется, то есть последовательность кажется неслучайной. Параметр a обозначает вероятность ошибки 1-го рода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
