В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа + 0 1 0 0 1 1 1 0 1 0 1 0 0 0 . 0 1 Рис. 11.1. Сложение и умно- жение по модулю 2 11.4 Большие простые числа Некоторые криптографические алгоритмы используют очень большие простые числа. Говоря об “очень больших числах”, мы имеем в виду числа с многими сотнями разрядов. Но не стоит беспокоиться — вам не придется работать с такими числами вручную. Для этого существуют компьютеры. Чтобы компьютер смог оперировать такими большими числами, требует- ся библиотека арифметических операций многократной точности (multipreci- sion library). Мы не можем использовать числа с плавающей запятой, потому что у них нет нескольких сотен разрядов точности. Мы не можем исполь- зовать и обычные целые числа, поскольку в большинстве языков програм- мирования значения целочисленных типов ограничены примерно десятком разрядов. Лишь некоторые языки программирования обладают встроенной поддержкой целых чисел с произвольной точностью. Написание функций для выполнения вычислений над большими целыми числами — весьма интересное занятие. Более подробно об этом можно прочитать в книге Кнута [54, раз- дел 4.3]. Тем не менее реализация библиотеки арифметических операций мно- гократной точности требует намного больше работы, чем кажется на первый взгляд. Нам нужно не только получить правильный ответ, но и вычислить его настолько быстро, насколько это возможно. Существует довольно много особых случаев, рассмотрение которых требует крайне тщательного подхода. Поэтому рекомендуем оставить время для более важных вещей и загрузить из Internet одну из многочисленных бесплатных библиотек или же воспользо- ваться языком наподобие Python, который обладает встроенной поддержкой больших целых чисел. Для реализации криптографических систем с открытым ключом нам по- надобятся простые числа в 2000-4000 бит длиной. Базовый метод генерации таких больших простых чисел удивительно прост: взять случайное число и проверить, не является ли оно простым. Существует много хороших ал- горитмов, позволяющих определить, является число простым или нет. Су- ществует также масса простых чисел. В окружении числа n приблизительно одно из каждых ln n чисел является простым. (Натуральный логарифм n , или ln n — одна из стандартных функций, встречающихся на любом инже- 11.4. Большие простые числа 221 нерном калькуляторе. Проиллюстрировать, насколько медленно возрастает значение натурального логарифма больших чисел, можно на следующем при- мере: натуральный логарифм числа 2 k немного меньше, чем 0 , 7 · k .) Число длиной в 2000 бит находится в диапазоне от 2 1999 до 2 2000 . В этом диапа- зоне примерно одно из каждых 1386 чисел является простым. Кроме того, б´ольшую часть чисел этого диапазона сразу же можно откинуть как состав- ные, например четные числа. Ниже приведен пример генерации больших простых чисел. функция GenerateLargePrime вход: l Нижняя граница диапазона, в котором должно находиться простое число. u Верхняя граница диапазона, в котором должно находиться простое число. выход: p Простое число в диапазоне l, . . . , u . Проверим корректность задания диапазона. assert 2 < l ≤ u Подсчитаем максимальное количество попыток. r ← 100 ( b log 2 u c + 1) repeat r ← r − 1 assert r > 0 Выберем в заданном интервале случайное число n . n ∈ R l, . . . , u Продолжим попытки до тех пор, пока не найдем простое число. until isPrime ( n ) return n Оператор ∈ R используется для обозначения случайного выбора числа из заданного множества. Разумеется, для выполнения этой операции понадобит- ся генератор псевдослучайных чисел. Описанный алгоритм достаточно прост. Вначале мы проверяем, что ин- тервал задан корректно. Случаи l ≤ 2 и l ≥ u не представляют для нас интереса и влекут за собой массу проблем. Обратите внимание на граничное условие: случай l = 2 не допускается 3 . Затем мы подсчитываем, какое ко- личество попыток нужно совершить, чтобы найти простое число. Существу- ют интервалы, которые не содержат простых чисел. Например, в интервале 3 Алгоритм Рабина–Миллера, который мы будем применять позднее, не слишком хо- рошо работает, когда на его вход подается число 2. Это не страшно — мы и так зна- ем, что 2 является простым числом, поэтому генерировать его с помощью функции GenerateLargePrime нет никакой нужды. |