rijndael (1085219), страница 5
Текст из файла (страница 5)
В итоге мы получили 16 бит ключа третьегораунда K3 из 32 возможных (знак x означает неизвестные биты)K3 = [xF xA x2 x3].3.2.5 Восстановление исходного ключа.Для восстановления исходного ключа воспользуемся теми же выражениями,которые использовались в дифференциальном криптоанализе. С их помощьюмы получим 16 бит исходного ключа K.
Мы можем это сделать, так как22подстановка SB[] действует на 2 полубайта независимо, а в операции ⊕ этиполубайты так же не зависят друг от друга.В следующих выражениях под обозначением k понимается младший полубайт байта ключа.k4 = k0 ⊕ S(k3 ) ⊕ 1k5 = k1 ⊕ S(k2 )k6 = k2 ⊕ k4k7 = k3 ⊕ k5k8 = k4 ⊕ S(k7 ) ⊕ 2k9 = k5 ⊕ S(k6 )k10 = k6 ⊕ k8k11 = k7 ⊕ k9k12 = k8 ⊕ S(k11 ) ⊕ 4k13 = k9 ⊕ S(k10 )k14 = k10 ⊕ k12k15 = k11 ⊕ k13Так как мы знаем значения младших полубайтов ключа K3 = [k12 k13 k14 k15 ],то можем получить сначала подключи k10 и k11 , а затем k8 и k9 , то есть ключK2 .k10 = k12 ⊕ k14 = F ⊕ 2 = Dk11 = k13 ⊕ k15 = A ⊕ 3 = 9k8 = S(k11 ) ⊕ k12 ⊕ 4 = S(9) ⊕ F ⊕ 4 = F ⊕ F ⊕ 4 = 4k9 = S(k10 ) ⊕ k13 = S(D) ⊕ A = 7 ⊕ A = DПодобным образом мы находим ключ K1 и собственно исходный ключ K.K = [xB xE x5 x6]Оставшиеся 16 бит найдем простым перебором.K = [2B 7E 15 16]3.2.6 Эффективность криптоанализа.Всего был использован одно линейное приближение.
Для него число вариантов подключей равнялось 216 . Для каждого подключа было проанализировано213 пар открытых текстов. То есть всего было произведенно 229 зашифрований.Для отсавшихся 16 бит ключа перебирались 216 вариантов, то есть былопроизведенно 216 зашифрований, что значительно меньше числа шифрованийдля восстановления первых 16 бит ключа. Следовательно, этим переборомможно пренебречь.Откуда следует, что линейный криптоанализ оказался на 3 порядка эффективнее, чем метод полного перебора, и наша криптосистема оказаласьнестойкой к данному методу криптоанализа.3.2.7 Программная реализация.Исходный код на языке C++ для линейного криптоанализа приведен в Приложении 3.234 Криптосистема как генератор псевдослучайныхпоследовательностей.Чтобы получить генератор псевдослучайных последовательностей, будем использовать нашу криптосистему в режиме сцепления блоков.
Это значит, чтоона функционирует по следующей схемеXi = f (Xi−1 , K),i > 1.Начальная инициализация последовательности задается значением X0 и ключом K. Последовательность строится начиная со значения X1 .Для тестирования зададим следующие значения X0 = [00 00 00 00] иключом K = [2B 7E 15 16].4.1Введение.Статистический тест формулируется для проверки определенной нулевой гипотезы H0 о том, что проверяемая последовательность является случайной.С этой нулевой гипотезой связана альтернативная гипотеза H1 о том, чтопоследовательность неслучайна.
Для каждого применяемого теста получаютзаключение о принятии или отклонении нулевой гипотезы, основываясь насформированной исследуемым генератором последовательности.Для каждого теста должна быть выбрана подходящая статистика случайности для принятия или отклонения нулевой гипотезы. Согласно предположению о случайности, такая статистика имеет распределение возможныхзначений. Теоретическое эталонное распределение этой статистики для нулевой гипотезы определяется математическими методами.
Из этого эталонногораспределения определяется критическое значение. Во время проведения теста вычисляется значение тестовой статистики. Это значение сравнивается скритическим значением. Если значение тестовой статистики превышает критическое значение, нулевая гипотеза для случайности отклоняется.
В противном случае нулевая гипотеза принимается.Проверка статистической гипотезы — процедура генерации заключения,которая имеет два возможных результата — или принять H0 (данные случайны), или принять H1 (данные неслучайны).Если данные на самом деле случайны, то заключение об отклонении нулевой гипотезы (т. е. что данные неслучайны) будет приниматься крайне редко.Это заключение называется ошибкой первого рода. Если данные неслучайны, то заключение о принятии нулевой гипотезы (т. е. что данные случайны)называется ошибкой второго рода. Заключения о принятии H0 , когда данные действительно случайны, и отклонении H0 , когда данные неслучайны,являются правильными.Вероятность ошибки 1-го рода называется уровнем значимости теста.
Этавероятность может быть установлена до испытания и обозначается как α.Для теста α суть вероятность того, что тест укажет на неслучайность последовательности, тогда как на самом деле она является случайной. То естьна то, что последовательность имеет неслучайные свойства, даже если еепроизвел хороший генератор.Вероятность ошибки 2-го рода обозначается как β. Для теста β есть вероятность того, что тест укажет на случайность последовательности, тогда24как это не так; т. е.
плохой генератор произвел последовательность, которая,как кажется, имеет случайные свойства. В отличие от α, β не является фиксированным значением; β могут принимать множество различных значений,потому что существует бесконечное число ситуаций, когда поток данныхможет быть неслучаен, и каждая из них выдает различные β. Вычислениеошибки 2-го рода является более сложным из-за множества возможных типовнеслучайности.Одной из основных целей нижеописанных тестов является минимизациявероятности ошибки 2-го рода, иначе говоря, минимизация вероятности принятия последовательности, произведенной плохим генератором, за последовательность, произведенную хорошим генератором.
Вероятности α и β связаныдруг с другом и с длиной n проверяемой последовательности: если два изэтих значений определены, третье определяется автоматически. На практикеобычно выбирают размер n и значение для α (вероятности ошибки 1-го рода). Тогда критическая точка для данной статистики выбирается так, чтобыполучить наименьшее значение β (вероятность ошибки 2-го рода).4.2Общее описание набора тестов Руководства НИСТ.Каждый тест основан на вычислении значения тестовой статистики, котороеявляется функцией данных. Если значение тестовой статистики есть S, at — критическое значение, то вероятность ошибки 1-го рода и 2-го рода естьсоответственноP (S > t|H0 истинна) = P (отклонить H0 |H0 истинна),P (S < t|H0 ложна) = P (принять H0 |H0 ложна).Тестовая статистика использует вычисление значения P-value, котороеконстатирует силу доказательства против нулевой гипотезы, иначе говоря,P-value есть вероятность того, что совершенный генератор случайных чисел произвел бы последовательность менее случайную, чем исследуемая, длятипа неслучайности, проверяемого тестом.
Если P-value для теста равно 1,то последовательность абсолютно случайна. P-value, равное 0, указывает,что последовательность абсолютно неслучайна. Для теста следует выбратьуровень значимости α. Если значение P-value больше или равно α, то принимается нулевая гипотеза, т. е. последовательность кажется случайной.
Еслизначение P-value меньше α, то нулевая гипотеза отклоняется, то есть последовательность кажется неслучайной. Параметр α обозначает вероятностьошибки 1-го рода.Выберем α равным 0.01, которое говорит о том, что из 100 случайныхпоследовательностей не прошла бы тест лишь одна. При P-value > 0.01последовательность рассматривается как случайная с доверительностью 99%.При P-value < 0.01 последовательность рассматривается как неслучайная сдоверительностью 99%.Итак, оценка статистических испытаний основана на проверке гипотезы ослучайности исследуемой последовательности нулей единиц.
Ниже приведеналгоритм, позволяющий оценить конкретную двоичную последовательность.Постановка гипотезы. Предполагаем, что последовательность является случайной.25Вычисление тестовой статистики. Проводим непосредственное тестирование последовательности на битном уровне.Вычисление P-value. P-value ∈ [0; 1].Сравнение P-value с α. Задаем α, где α = 0.01. Если P-value > α, то тестыпройдены.Далее приведен список и общие характеристики (определяемы дефект)каждого статистического теста НИСТ.1. Частотный тест. Слишком много нулей или единиц.2.
Частотный тест в подпоследовательностях. Слишком много нулей илиединиц в подпоследовательностях.3. Проверка “дырок”. Большое (малое) число подпоследовательностей нулей и единиц свидетельствует, что колебание потока бит слишком быстрое (медленное).4.
Проверка “дырок” в подпоследовательностях. Отклонения в распределении подпоследовательностей единиц.5. Проверка рангов матриц. Отклонение распределения рангов матрицот соответствующего распределения для истинно случайной последовательности, связанное с периодичностью подпоследовательностей.6. Спектральный тест. Периодические свойства последовательности.7. Проверка непересекающихся шаблонов.
Непериодические шаблоны встречаются слишком часто.8. Проверка пересекающихся шаблонов. Слишком часто встречаются mбитные последовательности единиц.9. Универсальный статистический тест Маурера. Сжимаемость (регулярность) последовательности.10. Сжатие при помощи алгоритма Лемпела-Зива. Большая сжимаемость,чем истинно случайная последовательность.11. Линейная сложность. Отклонение от распределения линейной сложности для конечной длины (под)строки.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
