Методы проверки чисел на простоту
ЛАБОРАТОРНАЯ РАБОТА №7.
ГЕНЕРАЦИЯ ПРОСТЫХ ЧИСЕЛ, ИСПОЛЬЗУЕМЫХ В
КРИПТОАЛГОРИТМАХ С ОТКРЫТЫМ КЛЮЧОМ
Использование простых чисел в алгоритме RSA
Для аутентификации (определения подлинности) сообщений (файлов) в сетях ЭВМ используются алгоритмы с открытым ключом.
Один из самых известных алгоритмов с открытым ключом – алгоритм RSA.
Пусть h(x) – хеш–функция сообщения х. В качестве подписи используется число
M = [h(x)] ^ e (mod N),
где h(x) – хеш–функция сообщения x;
N = p*q, p, q – простые числа;
e – показатель степени, такой что
(e, f (N)) = 1,
где f(N) = (p–1)*(q–1) – функция Эйлера от модуля N.
Подписывающая сторона вычисляет такое d, что:
de = 1(mod f(N)).
Число d является не секретным и передаётся проверяющей стороне. Проверяющая сторона при проверке подписи проверяет условие:
h(x) = M^d (mod N).
Отметим, что процедура симметрична относительно e и d. Здесь секретный ключ подписывающего: числа p, q, e; открытый ключ проверяющего подпись – пара чисел N, d.
Для того, чтобы описанная схема была достаточно стойкой от подделки, числа p и q должны быть случайными большими простыми числами и иметь в своей двоичной записи несколько сотен бит.
Проблема генерации многоразрядных случайных простых чисел представляет собой весьма важную задачу, поскольку от выбранного алгоритма генерации существенно зависят такие параметры криптосхемы, как время работы (на этапе настройки программы – создания образца подписи) и стойкость, т.е. устойчивость к подделке подписи.
Если пренебречь требованием случайности, предъявляемым к генерируемым простым числам (то есть выбирать их из какого – то фиксированного множества чисел), то нарушителю для вскрытия схемы достаточно перебрать это множество чисел и найти то, которое делит модуль N без остатка.
Если в результате генерации хотя бы одно из чисел p или q окажется не простым, то и вся система подписи окажется неработоспособной: может найтись такой реальный подлинный документ, проверка подписи которого не подтвердит его подлинность.
Методы проверки чисел на простоту
Рассмотрим методы проверки чисел на простоту.
Задача проверки простоты чисел имеет давнюю историю. Так, например, проверка простоты чисел Ферма
Fk = 2^2^k+1, k = 1, 2, …
связана с возможностью построения циркулем и линейкой правильных многоугольников. Для криптографических целей требуется проверять очень большие случайные числа. Простейшим методом проверки простоты натурального числа N является метод пробных делений: для d=2, 3, 4 … мы проверяем выполнение условия (d, N)>1. (Здесь (d, N) – наибольший общий делитель чисел d и N) . Число операций, требуемых для этого метода, имеет порядок корня из N.
Поэтому уже для чисел порядка 10^30–10^40 он неприменим.
По существу, этот метод не только проверяет простоту, но и находит нетривиальный делитель в случае составного N.
Отметим ещё алгоритмы Румели и Адлемана (давшего букву А в названии RSA), проверяющие простоту N за
O((log N)^(c*log log log N))
шагов для некоторой константы c. Перечисленные выше тесты дают 100% гарантию простоты числа N, то есть, если какой – либо тест на выходе объявляет число N простым, то это можно считать строгим математическим доказательством простоты N. Однако эти тесты практически не используются ввиду значительного времени их работы.
В отличие от таких “детерминированных“ тестов существуют ещё “вероятностные“ тесты проверки простоты. Для исследуемого числа проверяется выполнение некоторых, связанных со случайными числами, условий. Если какое– либо из этих условий не выполнено, то N – составное число. Если же все условия выполнены, то с некоторой вероятностью можно утверждать, что N – простое число. Эта вероятность тем ближе к 1, чем большее количество случайных чисел мы проверим.
Обычно эти условия основаны на малой теореме Ферма, утверждающей, что для любого положительного числа b, не превосходящего некоторого простого числа p :
b^(p–1) = 1(mod p).
Например, 2^6 = 64 = 63+1 = 1(mod 7). Если требуется определить, является ли целое число r простым, то можно выбрать любое положительное целое число b, меньшее r, и проверить, выполнено ли равенство
b^(r–1) = 1(mod r).
Если равенство не выполнено, то на основании теоремы Ферма можно быть совершенно уверенным, что r – не простое число. Если же равенство выполнено, то можно лишь предполагать, что r – простое число и поэтому назвать его “псевдопростым по основанию b“. Вероятность P (x) того, что составное число x окажется псевдопростым по случайному основанию, убывает с ростом x.
К сожалению, существуют так называемые числа Кармайкла – такие составные числа, которые обладают свойством:
b^(r–1) = 1(mod r) для всех b из интервала [1, r],
которые взаимно просты с r.
Примером числа Кармайкла является число 561 = 3*11*17.
Применение теста Ферма к таким числам с большой вероятностью даст положительный результат, то есть этот тест объявит такие числа простыми. До сих пор неизвестно, конечно или бесконечно множество чисел Кармайкла. Однако тест Ферма можно существенно усилить.
Дадим определение строго псевдопростого числа. Пусть N – нечётное число, N–1 = d*2^s, d – нечётно. Число N называется строго псевдопростым в базе a, если a^ d = 1(modN) или
a^(d*2^r) = - 1(mod N) при некотором r, 0<r<s.
Вероятностный тест на простоту, основанный на проверках на строгую псевдопростоту по случайным базам называют тестом Селфриджа. Аналогов чисел Кармайкла (т.е. чисел, строго псевдопростых по всем базам, не превышающим самого числа) в этом случае нет.
Поскольку тесты, основанные на теореме Ферма, требуют значительного времени для вычислений, на практике проверяемое число делят вначале на маленькие простые числа. Если проверяемое число разделилось на одно из них, то оно заведомо не простое, если же нет, то тогда применяют один из описанных выше вероятностных тестов.
Классический результат теории чисел – теорема Чебышева – показывает, что доля положительных целых чисел, меньших некоторого целого m и являющихся простыми, близка к 1/(ln m). Например, доля целых чисел, меньших 10^100 и являющихся простыми, близка к 1/(ln10^100) = 1/230. Поскольку 90% этих чисел лежат между 10^99 и 10^100, то доля простых чисел в этом диапазоне также составляет около 1/230.
Поэтому, если наугад выбрать число с 99–ю значащими десятичными цифрами, т.е. в диапазоне от 10^99 до 10^100, то оно окажется простым с вероятностью около 1/230.
Таким образом, если мы выберем случайно большое целое положительное нечётное число x и будем последовательно проверять на простоту числа x, x+1, x+2, … , то в среднем мы впервые встретим простое число на шаге с номером ln x.