В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 13. Алгоритм RSA лученное небольшое отклонение от равномерного распределения в данном случае не принесет никакого вреда. Приведем формализованное описание данного алгоритма. функция EncryptRandomKeyWithRSA вход: ( n, e ) Открытый ключ RSA, в нашем случае e = 5 . выход: K Секретный ключ, который был зашифрован. c Шифрованный текст RSA. Вычислим k . k ← b log 2 n c Выберем случайное r , такое, что 0 ≤ r ≤ 2 k − 1 . r ∈ R © 0 , . . . , 2 k − 1 ª K ← SHA d − 256( r ) c ← r e mod n return ( K, c ) Получатель вычисляет K = h ( c 1 /e mod n ) и получает то же значение K . функция DecryptRandomKeyWithRSA вход: ( n, d ) Закрытый ключ RSA для e = 5 . c Шифрованный текст. выход: K Секретный ключ, который был зашифрован. assert 0 ≤ c ≤ n Остальное выполняется тривиально. K ← SHA d − 256( c 1 /e mod n ) return K Итак, мы подробно рассмотрели, как вычислить c 1 /e по известному за- крытому ключу, поэтому дальнейшее обсуждение не требуется. Напомним только, что использование CRT-представлений позволяет ускорить выполне- ние алгоритма в 3-4 раза. Теперь продемонстрируем безопасность данного решения. Предположим, что пользователь Б зашифровывает ключ K и отсылает его пользователю А. Злоумышленник Е хочет получить больше информации об этом ключе. Сооб- щение пользователя Б зависит только от некоторых случайных данных и от открытого ключа пользователя А. Поэтому в самом худшем случае сообще- ние может раскрыть злоумышленнику Е данные о ключе K , но никак не о других секретах (например, о закрытом ключе пользователя А). Ключ K вычисляется с помощью функции хэширования, и мы можем рассматривать ее как случайное отображение. (Если рассматривать функцию хэширования как случайное отображение невозможно, значит, она не удовлетворяет сфор- мулированным нами требованиям безопасности к функциям хэширования.) 13.6. Шифрование 261 Единственный способ получить информацию о результате функции хэширо- вания — это узнать б´ольшую часть ее входных данных. Для этого злоумыш- леннику нужна информация об r . Но если алгоритм RSA является безопас- ным (а мы должны исходить из предположения, что он безопасен, раз вы- брали его для шифрования), тогда получить какой-либо значительный объем информации о случайно выбранном r , зная лишь r e mod n , невозможно. По- этому у злоумышленника остается большая неопределенность относительно r и, как следствие, никакой информации о K . Предположим, через некоторое время злоумышленнику E стал известен ключ K (возможно, из-за сбоя какого-нибудь другого компонента системы). Приведет ли это к утечке информации о закрытом ключе пользователя А? Нет. Ключ K — это результат функции хэширования, а злоумышленник не может получить какую-либо информацию о входных данных функции хэ- ширования на основе ее выходных данных. Следовательно, даже если зло- умышленнику Е удастся особым образом подобрать шифрованный текст c , полученный им ключ K не предоставит никакой информации об r . Закры- тый ключ пользователя A применялся только для вычисления r , поэтому злоумышленнику Е снова ничего не удастся узнать о закрытом ключе поль- зователя А. Это одно из преимуществ применения функции хэширования в функ- ции DecryptRandomKeyWithRSA . Предположим, что последняя возвра- щала бы лишь значение c 1 /e mod n . В этом случае данная функция могла бы быть использована злоумышленником для осуществления всевозможных атак. Предположим, что другая часть системы имеет слабое место, в резуль- тате чего злоумышленник Е может узнать наименее значимый бит выходных данных. В этом случае злоумышленник может отослать пользователю А спе- циально подобранные значения c 1 , c 2 , c 3 , . . . и получить наименее значимые биты значений c 1 /e 1 , c 1 /e 2 , c 1 /e 3 , . . . . Полученные результаты будут обладать все- ми видами алгебраических свойств. Вполне вероятно, что злоумышленник Е сможет извлечь из подобной ситуации что-нибудь полезное. Функция хэши- рования h , примененная в DecryptRandomKeyWithRSA , полностью раз- рушает математическую структуру. Знание одного бита значения K не предо- ставит злоумышленнику Е практически никакой информации о c 1 /e . Более того, даже знание всего значения K не принесет слишком большой пользы, так как функция хэширования не является обратимой. Таким образом, при- менение функции хэширования делает алгоритм RSA более безопасным по отношению к сбоям остальных компонентов системы. Описанное поведение, помимо всего прочего, является также причиной того, почему мы не проверяем, попадает ли значение r , вычисленное по за- данному c , в интервал 0 , . . . , 2 k − 1 . Если бы мы реализовали подобную про- |