В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 13. Алгоритм RSA Проверим, правильно ли задан интервал. assert 1024 ≤ k ≤ 4096 Подсчитаем максимальное количество попыток. r ← 100 k repeat r ← r − 1 assert r > 0 Выберем в заданном интервале случайное число n . n ∈ R 2 k − 1 , . . . , 2 k − 1 Продолжим попытки до тех пор, пока не найдем простое число. until n mod 3 6 = 1 ∧ n mod 5 6 = 1 ∧ isPrime ( n ) return n Вместо того чтобы указывать полный диапазон, в котором должно нахо- диться искомое простое число, мы задаем лишь размер последнего. Назвать это определение слишком гибким нельзя, зато применять его для RSA го- раздо проще и эффективнее. Дополнительные требования к простому числу фигурируют в качестве условия цикла. При более умелой реализации этого алгоритма можно позволить себе обойтись без вызова функции isPrime ( n ), если n дает нежелательный остаток по модулю 3 или 5, поскольку выполне- ние функции isPrime ( n ) включает в себя огромное количество вычислений. Для чего же мы снова вставили в функцию счетчик цикла с условием ошибки? Неужели при наличии такого большого интервала мы не найдем подходящего простого числа? Хотелось бы верить, но иногда в этом мире происходят странные вещи. Нас беспокоит отнюдь не возможность получе- ния интервала, в котором не окажется простых чисел, а испорченный генера- тор псевдослучайных чисел, который всегда будет возвращать одно и то же составное число. Это, к сожалению, один из самых распространенных сбоев генераторов случайных чисел. Выполнение простой проверки защитит функ- цию GenerateRSAPrime от неправильного поведения генераторов. Еще од- ной распространенной проблемой является сбой функции isPrime , в резуль- тате которого каждое сгенерированное число объявляется составным. Приведенная ниже функция генерирует все параметры закрытого ключа. функция GenerateRSAKey вход: k Размер модуля в битах. выход: p , q Множители модуля. n Модуль длиной приблизительно k бит. d 3 Показатель степени для цифрового подписывания. d 5 Показатель степени для дешифрования. Проверим, правильно ли задан интервал. 13.5. “Подводные камни” использования RSA 257 assert 2048 ≤ k ≤ 8192 Сгенерируем простые числа. p ← GenerateRSAPrime ( b k/ 2 c ) q ← GenerateRSAPrime ( b k/ 2 c ) Небольшая проверка на случай, если генератор испорчен. . . assert p 6 = q Вычислим t как НОК ( p − 1 , q − 1) . t ← ( p − 1)( q − 1) / GCD ( p − 1 , q − 1) Вычислим секретные показатели степеней. Для этого найдем обрат- ное число по модулю с помощью расширенного алгоритма Евклида. g, ( u, v ) ← ExtendedGCD (3 , t ) Проверим правильность НОД. В противном случае обратного числа не существует. assert g = 1 Возьмем u по модулю t , потому что u может быть отрицательным, а d 3 должно быть положительным. d 3 ← u mod t Повторим описанные выше действия для d 5 . g, ( u, v ) ← ExtendedGCD (5 , t ) assert g = 1 d 5 ← u mod t return p, q , pq, d 3 , d 5 Обратите внимание, что в качестве открытых показателей степеней при- меняются фиксированные значения и что мы сгенерировали ключ, который может применяться как для подписывания ( e = 3) , так и для шифрования ( e = 5) . 13.5 “Подводные камни” использования RSA Использовать алгоритм RSA описанным выше способом очень опасно. Проблема заключается в том, что RSA имеет четкую математическую струк- туру. Например, если пользователь А подпишет цифровой подписью два со- общения — m 1 и m 2 , пользователь Б сможет вычислить, какой должна быть подпись пользователя А для сообщения m 3 := m 1 m 2 mod n . Действительно, подписывая сообщения, пользователь А вычислил значения m 1 /e 1 и m 1 /e 2 , а пользователь Б может перемножить эти значения, чтобы получить ( m 1 m 2 ) 1 /e . Еще одна проблема возникает тогда, когда пользователь Б зашифровыва- ет с помощью открытого ключа пользователя А сообщение небольшого раз- мера. Если e = 5 и m < 5 √ n , тогда m e = m 5 < n , поэтому взятия числа по |