<< Предыдущая

стр. 32
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

7.3.4. Покажите, что схему шифрования RSA с простым модулем
N = Р очень легко взломать.

7.3.5. Объясните, почему при передаче большого числа данных наи­
более приемлемый способ заключается в том, что сначала с
помош;ью криптосистемы с открытым ключом передается се­
кретный ключ, а потом с его помош;ью шифруются основные
данные симметричным алгоритмом.

7.3.6. Формальным рассуждением покажите, что вскрытие шифру-
юш;его алгоритма Рабина эквивалентно разложению на мно­
жители натуральных чисел.

7.3.7. Исследуйте различные леммы в этой главе и предположите,
что оракулы дают верный ответ лишь с некоторой вероятно-
208 Глава 7. Основные алгоритмы шифрования с открытым ключом

стью, например, верный ответ — один из десяти. Измените
формулировки лемм и докажите получившиеся утверждения
в соответствии с новыми предположениями. В каких леммах
вы можете «увеличить» вероятность и получить редукцию,
которая работает с высокой вероятностью, даже если ора­
кул выдает верные ответы с низкой вероятностью?
ГЛАВА 8
ТЕСТЫ НА
ПРОСТОТУ
И ФАКТОРИЗАЦИЯ

Ц е л и главы
• Объяснить основные тесты на простоту.
• Подробно описать чах:то использу€|мый тест на простоту, а имен­
но, тест Миллера-Рабина.
• Рассказать о различных алгоритмах факторизации.
• Показать, как работает самый удачный алгоритм разложения
на множители: метод решета в числовом поле.


8.1 • Простые числа
Простые числа необходимы для почти всех алгоритмов шифрования
с открытым ключом, например,
- В RSA или криптосистеме Рабина нам нужны простые числа
р и q для определения открытого ключа N = р - q.
- В Эль-Гамаль необходимо простое число р и простое q^ деля­
щее р —1.
˜ В варианте Эль-Гамаль, используюш.ем эллиптические кривые,
требуется эллиптическая кривая над конечным полем, порядок
которой делится на большое простое число q.
Мы увидим, что тестирование чисел на простоту можно выпол­
нить с помоп1;ью очень простого и эффективного алгоритма, допус­
кающего, однако, вероятностную ошибку. Итерируя этот алгоритм,
можно уменьшить вероятность ошибки до любой требуемой величины.
Некоторые из более сложных тестов выдают сертификат, про­
верив который третья сторона может убедиться в том, что про­
веряемое число действительно простое. Одно из очевидных требо­
ваний, предъявляемых к такому сертификату, состоит в том, что
его должно быть легче проверить, чем получить Проверку чисел
Глава 8. Тесты на простоту и факторизация

на простоту с помощью сертификатов называют алгоритмом до­
казательства простоты^ а соответствующий сертификат — до­
казательством простоты. Надо сказать, что основной алгоритм,
использующийся в криптографии, выдает сертификаты того, что
данное число является составным, но не сертификаты простоты.
Перед обсуждением алгоритмов обратим внимание на некото­
рые эвристические свойства простых чисел. Знаменитый результат,
сформулированный Гауссом в начале XIX века в виде гипотезы по­
сле долгих численных экспериментов, сейчас носит название закона
распределения простых чисел:

Теорема 8.1. (Закон распределения простых чисел.) Функция
7г(Х), вычисляющая количество простых чисел, не превосходящих
X, имеет следующую аппроксимацию:



Этот факт говорит о том, что простые числа встречаются до­
вольно часто, например, количество простых чисел, меньших 2^^^,
приблизительно равно 2^^^. Кроме того, с помощью закона распре­
деления можно вычислять вероятность простоты выбранного на­
угад числа. Вероятность случайным образом выбранного числа р
оказаться простым равна j ^ . Отсюда вытекает, что взятое наугад
число, состоящее из 512 двоичных знаков, будет простым с веро­
ятностью ^ j ^ ^ j ^ . Это означает, что в среднем нам нужно
просмотреть 177 случайных чисел порядка 2^^^, чтобы найти одно
простое.

8.1.1. Пробное деление
Наивный способ проверки числа р на простоту состоит в пробном
делении. По существу, мы пытаемся разделить число р на все числа,
начиная с 2 и кончая ^/р. Если результат деления — целое число, то
р — составное, и мы в качестве бесплатного приложения получим
один из делителей числа р, что тоже неплохо. Если же не удастся раз­
делить нацело р ни на какое из упомянутых чисел, то оно является
простым. Таким образом, пробное деление обладает тем преимуще­
ством (в сравнении с более сложными тестами на простоту), что в
результате работы такого алгоритма мы либо докажем простоту
числа р, либо найдем его нетривиальный делитель.
Однако пробное деление — очень громоздкая стратегия! В са­
мом плохом случае, когда р действительно простое, нам потребуется
8.1. Простые числа

^Jp шагов, т. е. метод имеет экспоненциальную сложность. Другой
недостаток алгоритма состоит в том, что он не дает никакого лег­
кого способа проверки простоты найденного числа j9, оставляя един­
ственную возможность убедить кого-либо в верности результата —
повторение всего алгоритма. Простой способ проверки отсутствия
простоты, конечно, есть: мы нашли нетривиальный делитель, поэто­
му р^ля доказательства того, что р — составное число, достаточно
проверить его делимость на указанный множитель.
Несмотря на свои недостатки, метод пробного деления хорош
для поиска небольших простых чисел. Существует способ и частич­
ного перебора, когда не проверяются на простоту заведомо состав­
ные числа. Например, никакое четное число, большее 2, не может
быть простым, любое число с суммой цифр, кратной 3, делится на 3
и т. д. Кроме того, в качестве гипотетических делителей достаточ­
но брать лишь простые числа.

8.1.2. Тест Ферма
Наиболее развитые вероятностные алгоритмы проверки чисел на
простоту основаны на теореме, обратной малой теореме Ферма. На­
помним, что если G — мультипликативная группа порядка # G , то
ввиду теоремы Лагранжа а^^ = 1 для любого элемента а ^ G. Сле­
довательно, если О = (Z/7VZ)* — мультипликативная группа кольца
вычетов по модулю Л/", т. е. группа порядка (^(iV), то А^ЛЯ любого ее
элемента а имеет место равенство
а^(^) = 1 (modTV).
Значит, если п — р — простое (случай малой теоремы Ферма), то
а^-1 = 1 (modp).
Итак, при простом N равенство
а^-^ = 1 (modiV)
выполнено всегда, а вот для составных N его истинность маловеро­
ятна.
Поскольку вычисление а^˜^ (modiV) довольно быстрая опера­
ция, у нас возникает быстрый тест, проверяюш;ий, является ли дан­
ное число составным. Его называют тестом Ферма по основанию а.
Заметим, что тест Ферма может лишь убедить нас в том, что число
N имеет делители, но не в состоянии доказать его простоту. Дей­
ствительно, рассмотрим составное число iV = 11 • 13 = 341, а осно­
вание в тесте Ферма выберем равным 2. Тогда 2^^^ = 1 mod 341, в
Глава 8. Тесты на простоту и факторизация

то время как число 341 не простое. В этом случае говорят, что N —
псевдопростое число (в смысле Ферма) по основанию 2. Суш;ествует
бесконечно много псевдопростых чисел по фиксированному основа­
нию, хотя они встречаются реже, чем простые. Можно показать,
что для составного N вероятность неравенства
а^-1 ^ 1 (modTV).
больше 1/2. Подводя итог сказанному, выпишем алгоритм теста
Ферма.

for (i=0; i<k; i++)
{ выбрать a из [2,...,n-l];
b = a'^ln-l} mod n;
if (b!=l)
{ напечатать (составное, a);
exit;
}
}
напечатать «правдоподобно простое»
Если на выходе этого алгоритма напечатано «составное, а», то
мы с определенностью можем заявить, что число п не является про­
стым, и что а свидетельствует об этом факте, т. е. чтобы убедиться
в истинности высказывания, нам достаточно провести тест Ферма
по основанию а. Такое а называют свидетелем того, что п составное.
Если же в результате работы теста мы получим сообщение: «прав­
доподобно простое», то можно заключить: п — составное с вероят­
ностью ^ 1/2^.
Возьмем, например, число п = 43 040 357. Оно является состав­
ным, что можно проверить тестом Ферма по основанию а = 2. Дей­
ствительно,
243040356 (mod43040357) = 9888212 ^ 1.
В качестве следующего примера рассмотрим число п = 2^^^ — 2^^* — 1.
Алгоритм выдаст на печать «правдоподобно простое», поскольку
мы не сможем найти свидетеля обратному. Фактически, это число
является простым, так что нет ничего удивительного в том, что мы
не смогли найти свидетеля его делимости.
Тем не менее, существуют составные числа, относительно кото­
рых тест Ферма выдаст ответ
правдоподобно простое,
для всех взаимно простых с п оснований а. Такие числа называются
8.1, Простые числа 213

числами Кармайкла. К сожалению, их бесконечно много. Первые из
них — это 561, 1105 и 1729. Числа Кармайкла обладают следующими
свойствами:
- они нечетны,
- имеют по крайней мере три простых делителя,
- свободны от квадратов^,
- если р делит число Кармайкла iV, то р — 1 делит Л^ — 1.
Чтобы получить представление об их распределении, посмотрим
на числа, не превосходящие 10^^. Среди них окажется примерно
2,7-10^^ простых чисел, но только 246683 ?^ 2,4 • 10^ чисел Кар­
майкла. Следовательно, они встречаются не очень часто, но и не
настолько редко, чтобы их можно было игнорировать.

8.1.3. Тест Миллера - Рабина
Из-за существования чисел Кармайкла тест Ферма применяют край­
не неохотно. Существует модификация теста Ферма, называемая
тестом Миллера - Рабина, которая обходит проблему составных чи­
сел, для которых не находится свидетеля. Это не означает, что лег­
ко найти свидетеля для каждого составного числа, это значит, что
такой свидетель в принципе должен быть. Кроме того, тест Милле­
ра-Рабина принимает составное число за простое с вероятностью
1/4 для любого случайного основания а. Поэтому многократное по­
вторение теста позволяет уменьшить вероятность ошибки до лю­
бой наперед заданной величины. Приведем тест Миллера - Рабина
на псевдокоде.

Зсшисать п-1 = 2"s m, с нечетным т ;
for (j=0; j<k; j++)
{ выбрать a из [ 2 , . . . , n - 1 ] ;
b = a"m mod n;
i f (b!=l)
{ флажок=истина;
for ( i = l ; i < s ; i++)
{ i f (b==(n-l))
{ флажок=ложь;
остановка алгоритма;
}
b=b"2 mod n;
}
^He делятся на квадраты простых чисел. — Прим. перев.
Глава 8. Тесты на простоту и факторизация

if (флажок=истина)
{ напечатать (составное, а);
exit;
}
}
}
напечатать «правдоподобно простое»;

Мы не будем объяснять, почему тест Миллера - Рабина работа­
ет. Если Вам это интересно, то можете посмотреть любую книгу
по алгоритмической теории чисел, например, книги Коэна или Ба-
ча и Шаллита, на которые есть точные ссылки в конце этой главы.
Так же как и тест Ферма, тест Миллера - Рабина повторяют к раз с
разными основаниями и получают результат с вероятностью ошиб­
ки 1/4^, если алгоритм выдает ответ «правдоподобно простое». Та­
ким образом, можно ожидать, что если тест Миллера - Рабина после
А > 20 проходов напечатает «правдоподобно простое», то тестиру­
;
емое число окажется действительно простым.
Если тест Миллера - Рабина по основанию а нашел, что п —
составное, то основание а называют свидетелем Миллера - Рабина
делимости п, и согласно обобш;енной гипотезе Римана (в справед­
ливость которой верит'большинство математиков) для составно­
го числа п найдется свидетель Миллера Рабина, не превосходяш;ий
0((1пп)2).

8.1.4. Доказательство простоты
До сих пор мы говорили только о свидетелях делимости чисел и ин­
терпретировали наличие свидетелей как доказательство того, что
тестируемое число является составным. Кроме того, у нас были ме­
тоды, говорящие о том, что данное число правдоподобно простое,
но стопроцентной уверенности в простоте чисел у нас не было (за
исключением алгоритма пробного деления). Вероятностные отве­
ты вполне приемлемы, поскольку вероятность того, что составное
число выдержит тест Миллера - Рабина с двадцатью основаниями
примерно равна 2˜^^, чего никогда не встречается на практике. Но
с теоретической точки зрения (и может быть с практической, если
Вы одержимы паранойей) этого может оказаться недостаточным.
Точнее говоря, нам может потребоваться по-настоящему простое
число, а не только правдоподобно простое.
Есть алгоритмы, выдающие свидетельства простоты чисел. Та­
кие свидетельства называют доказательством простоты. Фактиче-
8.2, Алгоритмы факторизации

ски, соответствующие алгоритмы применяются тогда, когда уже
есть уверенность в простоте числа, но нет строгого доказательства

<< Предыдущая

стр. 32
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>