В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 13. Алгоритм RSA модулю не требуется. Злоумышленник Е сможет восстановить m , просто из- влекая корень пятой степени из m 5 . Это будет очень легко, так как операции взятия по модулю в данном случае не задействованы. Подобные ситуации часто возникают тогда, когда пользователь Б пытается отослать пользовате- лю А ключ AES. Если рассматривать 256-битовое значение ключа как целое число, тогда значение зашифрованного ключа будет меньше 2 256 · 5 = 2 1280 , т.е. намного меньше нашего n . К такому числу не будут применяться опера- ции взятия по модулю, поэтому злоумышленник Е сможет вычислить ключ, просто извлекая корень пятой степени из значения зашифрованного ключа. Одна из причин такого подробного объяснения теории, лежащей в основе RSA, состоит в том, что мы хотим немного познакомить вас с обнаруженной нами математической структурой. Такая структура допускает осуществле- ние сразу нескольких типов атак. Наиболее простые из них уже упоминались выше. Но существуют и более изощренные атаки, основанные на методах ре- шения полиномиальных уравнений по модулю n . Все они сводятся к одному: подчинение чисел, которыми оперирует алгоритм RSA, какой бы то ни было структуре крайне нежелательно. Для решения этой проблемы используют функцию, которая разрушает любую имеющуюся структуру. Иногда ее называют функцией дополнения, но это неправильно. Термином дополнение (padding) обычно обозначают до- бавление лишних битов, которое применяют, чтобы получить строку нужной длины. Различные виды дополнения часто использовались для шифрования и цифрового подписывания RSA, и в большинстве случаев это приводило к осуществлению атак на такие системы. Нам же нужна функция, которая уничтожает всякую имеющуюся структуру настолько, насколько это возмож- но. Мы называем такую функцию функцией кодирования (encoding function) . Наиболее примечательным из всех стандартов функций RSA является, пожалуй, PKCS #1 v.2.1 [84]. Как обычно, это не единственный стандарт. Существует две схемы шифрования и две схемы цифровых подписей RSA, причем каждая из этих схем может работать с целым рядом функций хэши- рования. Нельзя сказать, что это плохо, но нам не нравится дополнительная сложность. Поэтому представим вам несколько более простых методов, хотя они могут и не обладать всеми свойствами методов PKCS. Стандарт PKCS #1 v.2.1 также демонстрирует распространенную пробле- му технической документации: он смешивает спецификацию с реализацией. Функция дешифрования RSA описывается в нем дважды: один раз с помо- щью уравнения m = c d mod n , а второй раз с помощью CRT-представлений. И то и другое выражение дает одинаковый результат: одно из них является лишь оптимизированной реализацией второго. Подобные описания реализа- ции не должны быть частью стандарта, потому что они не задают разное поведение. Каждый из них должен рассматриваться отдельно. Впрочем, мы 13.6. Шифрование 259 не собираемся критиковать именно этот стандарт PKCS. Данная проблема весьма широко распространена во всех сферах компьютерной индустрии. 13.6 Шифрование Шифрование сообщений является канонической областью применения ал- горитма RSA. Тем не менее оно редко используется на практике. Причи- на проста: размер сообщения, которое может быть зашифровано с помощью RSA, ограничивается размером числа n . В реальных системах мы даже не можем использовать все биты сообщения, так как функции кодирования тре- буются дополнительные биты. Подобное ограничение на размер сообщения для большинства систем крайне непрактично, а поскольку в терминах вы- числений каждая операция RSA обходится довольно дорого, вряд ли кому- нибудь захочется разбивать сообщение на блоки меньшего размера и шифро- вать каждый из них с помощью отдельной операции RSA. В большинстве случаев эту проблему решают следующим образом: выби- рают случайный секретный ключ K и зашифровывают его с помощью клю- чей RSA. После этого фактическое сообщение m зашифровывается с помо- щью обыкновенного блочного или поточного шифра, где в качестве ключа шифрования используется K . Таким образом, вместо того чтобы отсылать нечто наподобие E RSA ( m ) , мы отсылаем E RSA ( K ) и E K ( m ) . Размер сооб- щения больше не ограничен, а для шифрования даже больших сообщений требуется только одна операция RSA. Конечно, нам приходится передавать немного дополнительной информации, но затраты на это несоизмеримо малы по сравнению с преимуществами данного подхода. Наш метод шифрования еще проще. Вместо того чтобы выбирать и за- шифровывать ключ K , мы выбираем случайное r ∈ Z n и определяем ключ группового шифрования как K := h ( r ) для некоторой функции хэширования h . Шифрование числа r выполняется путем простого возведения r в пятую степень по модулю n . (Напомним, что для шифрования применяется e = 5 .) Это решение простое и безопасное. Поскольку значение r выбирается слу- чайным образом, оно не подчиняется какой-либо структуре, которая могла бы использоваться для атаки на шифрование RSA. Функция хэширования, в свою очередь, гарантирует, что ни одна зависимость между различными значениями r не перейдет на значения K , за исключением очевидного требо- вания, что одинаковым r должны соответствовать одинаковые K . Для простоты реализации будем выбирать r в диапазоне 0 , . . . , 2 k − 1 , где k — наибольшее число, для которого выполняется 2 k < n . Гораздо легче сгенерировать случайное k -битовое число, чем случайное число из Z n , а по- |