- •Содержание
- •Введение
- •1.1. Общая система секретной связи (по К. Шеннону)
- •1.1.1. Основные криптографические термины
- •1.1.2. Модель системы секретной связи К.Шеннона
- •1.2. Подходы к оценке надежности реальных криптосистем
- •1.2.2. Метод сведения к общей алгоритмической проблеме
- •Глава 2. ОБЩИЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ АНАЛИЗА ОСНОВНЫХ ТИПОВ ШИФРОВ
- •2.1. Элементарные шифры
- •2.2. Основные типы шифров
- •2.2.1 Потоковые шифры. Последовательность выбора шифрпреобразований
- •2.2.2. Качество гаммы
- •2.2.3. Периодичность гаммы
- •2.2.4. Блочные шифры
- •2.2.5. Алгоритмические проблемы, связанные со стойкостью основных типов шифров
- •Глава 3. ТЕСТИРОВАНИЕ УЗЛОВ КРИПТОСХЕМ КАК МЕТОД КОМПРОМЕТАЦИИ ШИФРОВ
- •3.1. Компрометация шифров
- •3.2. Задача тестирования линейной рекуррентной составляющей криптоузла
- •3.3. Задача восстановления параметров искаженной линейной рекурренты
- •3.3.1. Представление элементов рекурренты через элементы начального заполнения
- •3.3.2. Производные соотношения
- •3.3.4. Качественная характеристика задачи восстановления параметров линейной искаженной рекурренты
- •Глава 4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ
- •4.1. Нелинейность булевой функции
- •4.2. Критерии распространения и корреляционная иммунность
- •4.3. Устойчивые булевы отображения
- •Глава 5. ОСОБЕННОСТИ ПРИМЕНЕНИЯ АЛГОРИТМА ГОСТ 28147-89
- •5.1. Криптоэквивалентная схема алгоритма ГОСТ 28147-89
- •5.2. Влияние блока подстановки на последовательности выходов итераций
- •5.2.1 Расшифрование в режиме простой замены
- •5.2.2. Возможность ослабления шифра за счет структуры сеансового ключа
- •5.3. Замечания о режимах шифрования и имитовставки
- •Глава 6. ВЫБОР ДОЛГОВРЕМЕННОГО КЛЮЧА АЛГОРИТМА ГОСТ 28147-89
- •6.1. Область сильных ключей
- •6.1.1. Достаточность условия равновероятности псевдогаммы для выбора сильного блока подстановки
- •6.2. Контроль долговременного ключа алгоритма ГОСТ 28147-89
- •6.2.1. Угроза внедрения слабых параметров
- •6.2.2. Подход к выявлению слабых долговременных ключей
- •6.2.3. Свойства теста
- •6.2.4. Тестирование долговременного ключа
- •Глава 7. ЭЛЕМЕНТЫ ТЕОРИИ СРАВНЕНИЙ
- •7.1.1. Расширенный алгоритм Эвклида
- •7.2. Модульная арифметика
- •7.2.1. Функция Эйлера и малая теорема Ферма
- •7.3. Сравнения первой степени от одного неизвестного
- •7.3.1. Китайская теорема об остатках
- •7.3.2. Степенные сравнения по простому модулю
- •Глава 8. ВЫЧИСЛЕНИЕ КВАДРАТНОГО КОРНЯ В ПРОСТОМ ПОЛЕ
- •8.1.1. Символ Лежандра
- •8.1.2. Символ Якоби
- •8.2. Алгоритм нахождения квадратного корня в простом поле
- •9.1. Построение криптосистемы RSA. Идея цифровой подписи
- •9.2. Смешанные криптосистемы. Протокол Диффи-Хэллмана ключевого обмена
- •9.3. Цифровая подпись Эль-Гамаля
- •9.3.1. Криптосистема Эль-Гамаля
- •9.3.2. Механизм цифровой подписи Эль-Гамаля
- •9.3.3. Ослабление подписи Эль-Гамаля вследствие некорректной реализации схемы
- •9.3.4. Варианты цифровой подписи типа Эль-Гамаля
- •10.1 Обозначения и постановка задачи
- •10.2. Построение корней из единицы в поле
- •10.3. Алгоритм дискретного логарифмирования
- •10.3.1. Пример вычисления дискретного логарифма
- •10.4. Фальсификация подписи Эль-Гамаля в специальном случае выбора первообразного элемента и характеристики поля
- •10.4.1. Слабые параметры в подписи Эль-Гамаля
- •Глава 11. МЕТОДЫ ФАКТОРИЗАЦИИ ПОЛЛАРДА
- •11.2.1. Оценка вероятности выбора критической пары
- •11.2.2. Оптимизация выбора критической пары
- •Глава 12. НЕКОТОРЫЕ СЛУЧАИ ОСЛАБЛЕНИЯ КРИПТОСИСТЕМЫ RSA
- •12.1. Атаки на RSA, не использующие факторизацию модуля
- •12.2. Атаки на RSA, использующие факторизацию модуля
- •12.2.1. Алгоритм факторизации Диксона
- •Глава 13. ТЕСТ ФЕРМА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ
- •13.1. Решето Эратосфена и критерий Вильсона
- •13.2. Тест на основе малой теоремы Ферма
- •13.2.1. Основные свойства псевдопростых чисел
- •13.2.2. Свойства чисел Кармайкла
- •13.2.3. (n-1) - критерий Люка
- •13.2.3. Понятие о последовательностях Люка. (n+1) - критерий Люка
- •Глава 14. ТЕСТЫ СОЛОВЕЯ-ШТРАССЕНА И РАБИНА-МИЛЛЕРА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ
- •14.1. Тест Соловея-Штрассена
- •14.1.1. Эйлеровы псевдопростые числа
- •14.2. Тест Рабина-Миллера
- •14.2.1. Сильно псевдопростые числа
- •Глава 15. ПОСТРОЕНИЕ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ
- •15.1. Детерминированный тест, основанный на обобщенном критерии Люка
- •15.1.1. Теорема Поклингтона
- •15.1.2. Обобщение критерия Люка
- •15.2. Детерминированный тест, основанный на теореме Димитко
- •Глава 16. ВЫБОР ПАРАМЕТРОВ КРИПТОСИСТЕМЫ RSA
- •16.1. Общие требования к выбору параметров
- •16.2. Метод Гордона построения сильно простых чисел
- •16.3. Пример построения сильно простого числа
- •Глава 17. ОБЩИЕ СВЕДЕНИЯ ОБ ИНОСТРАННЫХ КРИПТОСРЕДСТВАХ
- •17.1. Аппаратные криптосредства
- •17.2. Основные принципы построения систем управления ключами
- •17.2.1. Ключевые системы потоковых шифров
- •17.3. Блочные шифры в смешанных криптосистемах
- •17.3.2. Смешанная криптосистема на основе алгоритмов RSA и IDEA
- •ЗАКЛЮЧЕНИЕ
- •ЛИТЕРАТУРА
178 Глава 14. ТЕСТЫ СОЛОВЕЯ-ШТРАССЕНА И РАБИНА-МИЛЛЕРА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ
Это можно сделать, исходя из утверждения, аналогичного тому, которое мы рассматривали при анализе свойств псевдопростых чисел. Интересно, что
эйлеровы псевдопростые являются псевдопростыми числами. |
|||||||||
Теорема [16]. Пусть n - нечетное составное число. Тогда: |
|||||||||
а) если n - эйлерово псевдопростое по основанию a, то оно псевдопростое |
|||||||||
по основанию a; |
|
|
|
|
|
|
|
|
|
б) |
если n - эйлерово псевдопростое по основаниям a и b, то n - эйлерово |
||||||||
псевдопростое по основаниям ab и ab−1(modn); |
|
||||||||
|
|
|
|
|
(n−1) 2 |
a |
|
||
в) |
множество |
|
En = a Zn |
: a |
|
= |
|
(mod n) является подгруппой |
|
|
|
|
|||||||
|
|
|
|
|
|
n |
|
||
группы |
F ={a Z |
n |
: an−1 =1(mod n)}; |
|
|
|
|
||
|
n |
|
|
|
|
|
|
|
г) если n не является эйлеровым псевдопростым по основанию a, хотя бы для одного числа a, то En ≤ (1 2)Zn* .
Действительно, свойства а), б) и в) следуют из мультипликативности символа Якоби и того факта, что его значение равно ±1.
Докажем г): En ≤ Fn ≤ (1 2)Zn* .
Таким образом, при повторении теста Соловея-Штрассена k раз,
вероятность неотбраковки составного числа ≤ (12)k .
14.2. Тест Рабина-Миллера
Еще более эффективным тестом является тест Рабина-Миллера, в котором используется критерий, в конечном счете основанный на факте, что для простого модуля квадратными корнями из единицы являются лишь числа ±1,
а для составного нечетного модуля n =uv , (u,v)=1, число таких корней больше двух.
Тест Рабина-Миллера 179
Пусть n - нечетное натуральное число. Тогда можно записать где t - нечетное и s ≥1.
Если число n - простое, то an−1 =1(n), при (a,n)=1. Поэтому квадратные корни из единицы имеют вид: a(n−1)2 = ±1(n), где показатель равен
Это означает, что в ряду вычетов по модулю n чисел at , a2t ,Ka2s −1 t либо появится −1(n), либо все они сравнимы с единицей, т.е. at =1(n).
Если n - составное, то возможны и другие случаи.
Основанный на данном замечании тест Рабина-Миллера заключается в следующем:
1) псевдослучайно выбираем вычет a {2,K,n −1}, проверяем условие
(a,n)=1. Если условие не |
выполнено, значит, n |
- составное и работа |
закончена; |
|
|
2) вычисляем at (mod n). |
Если at = ±1(mod n), |
то не исключено, что |
число n - простое и необходимо перейти на начало, чтобы повторить тест для другого основания;
3) вычисляем последовательно вычеты чисел a2t ,Ka2s −1 t по модулю n,
пока не появится (−1), либо не исчерпается список;
4)если (−1) обнаружена в списке, то не исключено, что число n - простое
инеобходимо перейти на начало, чтобы повторить тест для другого основания;
5)если ни одно число из списка не сравнимо с (−1), то число n - составное
инеобходимо закончить работу.
Как и для ранее рассмотренных тестов, существуют составные числа n, которые для соответствующих оснований a проходят тест.
180 Глава 14. ТЕСТЫ СОЛОВЕЯ-ШТРАССЕНА И РАБИНА-МИЛЛЕРА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ
14.2.1. Сильно псевдопростые числа
Назовем число n = 2s t +1, где s ≥1, t - нечетно, сильно псевдопростым по основанию a >1, если выполняется одно из двух условий: at = ±1(n), либо в
последовательности a2t ,Ka2s −1 t существует число, сравнимое с –1 по модулю n.
Оказывается, можно показать, что для любого a >1 существует бесконечно много сильно псевдопростых чисел n по основанию a. Пример: a =7 , n = 25; a=5, n=781.
Можно доказать следующие основные свойства сильно псевдопростых чисел [15]:
1)число n сильно псевдопростое по основанию a является эйлеровым псевдопростым по тому же основанию;
2)если нечетное составное число n является сильно псевдопростым по основанию a, то общее количество оснований, по которому это число является
сильно псевдопростым, не превышает (n −1)4 .
Таким образом, при повторении теста Рабина-Миллера k раз вероятность неотбраковки составного числа ≤ (14)k .
Оказывается, количество повторений теста, достаточное для практических
приложений, можно ограничить величиной 2log22 n .
Интересно отметить, что простоту небольших простых чисел можно проверять, используя несколько заранее указанных оснований.
Примеры [16]: если n<1373653 - сильно псевдопростое по основаниям 2 и 3, то n - простое; если n<341550071728321 - сильно псевдопростое по основаниям 2, 3, 5, 7, 11, 13, 17, то n - простое.