В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 13. Алгоритм RSA верку, то должны были бы обрабатывать ошибки в случае их возникновения. Поскольку поведение системы при обработке ошибок всегда отличается от по- ведения в нормальной ситуации, вполне вероятно, что злоумышленник смо- жет обнаружить факт возникновения ошибки. В результате у него появится функция, которая раскрывает информацию о закрытом ключе: злоумыш- ленник Е может выбрать любое c и проверить, выполняется ли отношение c 1 /e mod n < 2 k . Злоумышленник Е не может проверить данное свойство без помощи пользователя А, но зачем же лишний раз помогать злоумышлен- нику, если этого можно избежать? Отказавшись от проверки условия, мы в худшем случае получим лишь бессмысленные выходные данные, а это мо- жет произойти и при наличии проверки, поскольку c может быть повреждено таким образом, что r все равно будет попадать в нужный диапазон 3 . Небольшое замечание: существует огромная разница между раскрытием информации о случайной паре ( c, c 1 /e ) и вычислением c 1 /e для c , выбранного кем-то другим. Генерировать пары вида ( c, c 1 /e ) может каждый. Для этого достаточно выбрать случайное r , вычислить пару ( r e , r ) и затем обозначить c := r e . Ничего секретного в таких парах нет. Но, если пользователь А будет так добр, что подсчитает значение c 1 /e для c , полученного от злоумышлен- ника, последний сможет выбирать значения c некоторым специальным об- разом, что было невозможно для случайных пар ( c, c 1 /e ) , сгенерированных самим злоумышленником. Отсюда вывод: не следует лишний раз помогать злоумышленнику. 13.7 Подписи Реализовать схему цифровых подписей несколько сложнее. Проблема со- стоит в том, что сообщение m , которое мы хотим подписать, имеет довольно четкую структуру. Допускать, чтобы эта структура перешла на числа, для которых подсчитываются корни RSA, нежелательно. Поэтому структуру со- общения необходимо уничтожить. Первый шаг к уничтожению структуры состоит в хэшировании сообще- ния. Таким образом, вместо сообщения произвольной длины m будем ра- ботать со значением фиксированной длины h ( m ) , где h — функция хэши- рования. Если мы используем функцию SHA d -256, то получим 256-битовый результат. Но значение n намного больше, поэтому мы не можем применять h ( m ) непосредственно. 3 Введение каких бы то ни было ограничений на r не решает проблему бессмыслен- ных выходных данных. Злоумышленник Е всегда может использовать открытый ключ пользователя А и измененную функцию EncryptRandomKeyWithRSA , чтобы отсылать пользователю А бессмысленные ключи в зашифрованном виде. 13.7. Подписи 263 Самое простое решение — использовать псевдослучайное отображение, которое будет “растягивать” h ( m ) , отображая его на случайное число s из диапазона 0 , . . . , n − 1 . Затем подпись сообщения m будет вычисляться как s 1 /e (mod n ) . Отображение h ( m ) на число по модулю n выполнить довольно сложно (см. раздел 10.8). В нашем случае можно упростить проблему, отобра- жая h ( m ) на случайный элемент из диапазона 0 , . . . , 2 k − 1 , где k — наибольшее число, такое, что 2 k < n . Числа из диапазона 0 , . . . , 2 k − 1 генерировать гораз- до проще, поскольку для этого достаточно сгенерировать лишь k случайных бит. В нашем конкретном случае подобное решение можно использовать без опаски, однако не применяйте его повсеместно. Существует множество ситу- аций, в которых подобное упрощение разрушит безопасность всей системы. Мы будем использовать генератор псевдослучайных чисел Fortuna, опи- санный в главе 10, “Генерация случайных чисел”. Многие разработчики ис- пользуют функцию хэширования h , чтобы построить небольшой генератор случайных чисел, предназначенный специально для этой цели, но у нас уже есть хороший генератор. Кроме того, нам все равно понадобится генератор псевдослучайных чисел, чтобы выбирать простые числа для генерации клю- чей RSA. Для реализации схемы цифровых подписей понадобятся три функции: од- на, чтобы отобразить сообщение m на s , вторая, чтобы подписать сообщение, и третья, чтобы проверить подпись. функция MsgToRSANumber вход: n Открытый ключ RSA, модуль, по которому выполняются вычисления. m Сообщение, которое должно быть преобразовано в число по модулю n . выход: s Число по модулю n . Создадим новый генератор псевдослучайных чисел. G ← InitializeGenerator () Обновим начальное число генератора с помощью хэш-кода сообщения. ReSeed ( G , SHA d − 256( m )) Вычислим k . k ← b log 2 n c x ← PseudoRandomData ( G , d k/ 8 e ) Как обычно, мы рассматриваем строку байтов x как целое число, пред- ставленное в формате, в котором наименее значимый байт запи- сывается первым. Операция взятия по модулю будет выполняться путем простого применения операции AND к последнему байту x . s ← x mod 2 k |