В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа ( n − 1) 2 = 1(mod n ) .) Таким образом, если n — простое, тогда одно из чи- сел в этой последовательности должно равняться n − 1 , так как в противном случае последнее число никогда не будет равно единице. В действительности это и все, что проверяет тест Рабина–Миллера. Если хотя бы одно случайно выбранное a показывает, что число n является составным, мы сразу же воз- вращаем результат false . Если же n продолжает успешно проходить тест как простое число, мы повторяем проверку для другого значения a до тех пор, по- ка вероятность получения неверного результата не составит менее чем 2 − 128 . Если применить этот тест к случайно выбранному числу, вероятность ошибки будет во много раз меньше установленного нами предела. Почти все составные числа n могут быть распознаны тестом Рабина–Миллера при ис- пользовании практически любых базисов. Создатели многих программных библиотек исходили именно из этого и ограничивались выполнением провер- ки примерно для 5-10 базисов. Идея в принципе неплоха, хотя нам нужно было исследовать, сколько попыток требуется для достижения уровня ошиб- ки 2 − 128 или менее. Однако обратите внимание, что данное утверждение спра- ведливо только при применении функции isPrime к случайно выбранным числам. Позднее мы столкнемся с ситуациями, когда тест Рабина–Миллера будет применяться к числам, полученным от кого-нибудь другого. Эти числа могут быть выбраны злоумышленником, поэтому функция isPrime долж- на выполнить все необходимые действия для гарантированного достижения уровня ошибки 2 − 128 . Выполнение всех 64 тестов Рабина–Миллера необходимо тогда, когда чис- ло, проверяемое на простоту, получено от кого-нибудь другого. Это совершен- но излишне, когда мы пытаемся сгенерировать простое число случайным об- разом. С другой стороны, пытаясь сгенерировать простое число, мы потратим б´ольшую часть времени на отбрасывание составных чисел. (Практически все составные числа будут распознаны в ходе первого же теста Рабина–Миллера.) Поскольку для получения простого числа нам, вероятно, придется отбросить сотни составных чисел, выполнение 64 тестов для простого числа, когда оно в конце концов будет найдено, займет ненамного больше времени, чем вы- полнение 10 аналогичных тестов. В более ранней версии этой главы у функции Rabin-Miller был еще один аргумент, который мог применяться для выбора максимальной вероят- ности ошибки. Впоследствии он оказался чудесным примером бесполезного параметра, а потому был удален. Гораздо проще (да к тому же и безопаснее применительно к возможности неправильного использования) всегда прово- дить проверку до тех пор, пока уровень ошибки не снизится до 2 − 128 . У нас все еще остается вероятность 2 − 128 того, что функция isPrime вы- даст неверный ответ. Чтобы понять, насколько в действительности мала эта вероятность, представьте себе, что вас убьет случайно залетевший метеорит 11.4. Большие простые числа 227 в то время, когда вы читаете это предложение. Так вот, вероятность этого печального события значительно превышает 2 − 128 . Все еще живы? Тогда не беспокойтесь о функции isPrime . 11.4.2 Оценивание степеней Б´ольшая часть времени выполнения теста Рабина–Миллера уходит на вы- числение a s mod n . Мы не можем вначале подсчитать значение a s и затем взять его по модулю n . Ни один компьютер в мире не обладает достаточным количеством памяти даже для того, чтобы просто разместить в ней значение a s , не говоря уже о процессорной мощности, необходимой для вычисления по- следнего. И a и s могут быть в тысячи бит длиной. Вместе с тем нам нужно только a s mod n . Поэтому мы можем применять операцию mod n ко всем про- межуточным результатам, что не позволит числам разрастись до гигантских размеров. Существует несколько способов вычисления a s mod n , но мы приведем лишь несколько простых соображений. Чтобы подсчитать a s mod n , исполь- зуйте приведенные ниже правила. • Если s = 0 , тогда ответом будет 1. • Если s > 0 и является четным числом, тогда вначале подсчитайте y := a s/ 2 mod n , используя эти же правила. Окончательный результат будет выглядеть следующим образом: a s mod n = y 2 mod n . • Если s > 0 и является нечетным числом, тогда вначале подсчитайте y := a ( s − 1) / 2 mod n , используя эти же правила. Окончательный резуль- тат будет выглядеть следующим образом: a s mod n = a · y 2 mod n . Это рекурсивная формулировка так называемого двоичного алгоритма. Если вы проанализируете описанные выше операции, то увидите, что необхо- димый показатель степени формируется бит за битом от наиболее значимой части двоичного представления показателя к наименее значимой его части. При желании данный рекурсивный алгоритм можно переписать в виде цикла. Сколько операций умножения потребуется, чтобы вычислить a s mod n ? Пусть k — это число бит значения s ; другими словами, 2 k − 1 ≤ s < 2 k . Тогда данный алгоритм требует выполнения не более чем 2 k умножений по моду- лю n . Это совсем неплохо. Если мы проверяем, является ли простым 2000- битовое число, тогда длина s тоже будет составлять около 2000 бит и нам понадобится лишь 4000 вычислений. Этот объем работы, хотя и достаточ- но большой, определенно доступен вычислительным возможностям большин- ства настольных компьютеров. Многие криптографические системы с открытым ключом используют опе- рации возведения в степень по модулю наподобие рассмотренной выше. Хоро- |