лаб 15. Лаб раб 15. Лабораторные работы
 Скачать 0.6 Mb.
|
Вычисление ключейПеред тем как обратиться к криптосистеме с открытым ключом, каждая сторона должна генерировать пару ключей. Это означает выполнение следующих задач: определение двух простых чисел р и q; выбор одного из чисел е или d и вычисление второго. Сначала рассмотрим процедуру выбора р и q. Ввиду того что значение n = pq будет известно любому потенциальному противнику, то для того, чтобы не допустить возможности нахождения р и q с помощью простого перебора вариантов, эти простые числа должны быть выбраны из достаточно большого множества (т.е. р и q должны быть большими числами). В то же время метод нахождения больших простых чисел должен быть практически эффективным. На сегодняшний день нет хороших методов вычисления произвольно больших простых чисел, поэтому для решения этой проблемы приходится прибегать к различным хитростям. Чаще всего процедура заключается в выборе случайного нечетного число приблизительно желаемой величины и выяснения, является ли это число простым. Если окажется, что число простым не является, выбирается следующее случайное число, пока не будет найдено простое. Для проверки того, что числа простые, существует целый ряд тестов. Почти все такие тесты носят вероятностный характер. Это значит, что тест определит только, что данное целое число, вероятно, простое. Несмотря на отсутствие полной уверенности, такие тесты могут выполняться так, чтобы обеспечить уверенность с вероятностью, как угодно близкой к 1. Процедуру выбора простого числа можно представить в следующем виде. Выберите нечетное целое число n некоторым случайным образом (например, используя генератор псевдослучайных чисел). Выберите целое число а < n некоторым случайным образом. Выполните вероятностный тест на простоту. Если n не выдерживает тестирования, отбросьте данное значение n и перейдите к пункту 1. Если n выдерживает достаточное число повторных тестов, примите данное значение n как подходящее, в противном случае перейдите к пункту 2. Это процедура несколько утомительна. Однако не забывайте о том, что этот процесс выполняется относительно нечасто — только тогда, когда требуется новая пара (KU, KR). При этом неплохо знать, как много чисел, скорее всего, окажутся отброшенными прежде, чем обнаружится простое число. Одна из теорем теории чисел, известная под названием теоремы о простых числах, утверждает, что простые числа около N распределяются в среднем по одному на каждые ln(N) целых чисел. Таким образом, в среднем придется протестировать порядка ln(N) целых чисел прежде, чем найдется простое число. В действительности из-за того, что все четные целые числа можно отбросить сразу же, истинный порядок задается числом ln(N)/2. Например, если искать простые числа в области величин порядка 2200, то для нахождения простого числа потребуется около ln(2200)/2 = 70 попыток. После определения простых чисел р и q процесс вычисления ключей завершается выбором значения е и вычислением d или, наоборот, выбором значения d и вычислением е. В первом случае необходимо сначала выбрать такое е, что gcd((n), е) = 1, а потом вычислить d e-1mod (n). К счастью, имеется один алгоритм, который в одно и то же время вычисляет наибольший общий делитель двух целых чисел и, если наибольший общий делитель оказывается равным 1, определяет обратное для одного из целых чисел по модулю другого. Этот алгоритм называется обобщенным алгоритмом Евклида. Процедура заключается в генерировании случайных чисел и сравнении их с (n) до тех пор, пока не будет найдено число, взаимно простое с (n). Теперь мы снова можем спросить, как много случайных чисел придется проверить прежде, чем будет найдено подходящее число, т.е. число, взаимно простое с (n)? Легко показать, что вероятность того, что два выбранных случайно числа окажутся взаимно простыми, равна примерно 0,6 — это значит, что для нахождения подходящего целого значения понадобится всего несколько проверок. |