В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 16. Проблемы реализации. Часть II тических операций вместо g x возвращает x , но ошибку такого типа без труда обнаружит любое нормальное тестирование. При необходимости можно использовать алгоритм DH с библиотекой, ко- торая не поддерживает вупинг. Тот тип весьма редких арифметических оши- бок, который нас беспокоит, вряд ли позволит злоумышленнику узнать значе- ние x при вычислении g x . Любая другая ошибка выглядит вполне безобидной, особенно вследствие того, что в алгоритме DH нет долгосрочных секретных данных. Тем не менее там, где это возможно, мы все-таки предпочитаем ис- пользовать библиотеку с поддержкой вупинга — просто чтобы чувствовать себя в безопасности. 16.1.3 Проверка шифрования RSA Алгоритм шифрования RSA более уязвим для нападения злоумышленни- ков, а потому требует дополнительных проверок. Если что-нибудь пойдет не так, злоумышленник может узнать секретные данные, которые вы пытались зашифровать, или даже ваш секретный ключ. Если реализовать верификацию на основе вупинга невозможно, мы можем порекомендовать вам еще два метода проверки правильности шифрования RSA. Предположим, что реальный алгоритм шифрования RSA вычисляет c = m 5 mod n , где m — это сообщение, а c — шифрованный текст. Чтобы проверить правильность этой операции, мы могли бы подсчитать c 1 / 5 mod n и сравнить его с m . Недостаток этого подхода состоит в крайне медленной скорости верификации (что особенно неудобно для такого быстрого алгорит- ма, как этот). Кроме того, данный метод требует знания закрытого ключа, который при шифровании с помощью RSA обычно недоступен. Пожалуй, более удачное решение — выбор случайного значения z и про- верка того, что c · z 5 = ( m · z ) 5 mod n . Здесь нам придется выполнить три операции возведения в пятую степень: вычислить c = m 5 и z 5 , а также убе- диться, что ( mz ) 5 совпадает с c · z 5 . Такая верификация с высокой степе- нью вероятности позволит перехватить случайные арифметические ошибки. Выбирая случайное значение z , мы лишаем злоумышленника возможности инициировать ошибки с нужным отклонением. В наших системах алгоритм шифрования RSA применяется только для шифрования случайных значе- ний, поэтому злоумышленнику вообще не удастся никоим образом повлиять на результат верификации. 16.1.4 Проверка цифровых подписей RSA Проверять цифровые подписи RSA очень просто. Пользователю, подпи- савшему сообщение, достаточно лишь запустить стандартный алгоритм вери- 16.2. Быстрое умножение 309 фикации подписи. Последний выполняется относительно быстро и с большой долей вероятности позволяет перехватить арифметические ошибки. Каждая процедура вычисления подписи RSA должна верифицировать результат, про- веряя только что сгенерированную подпись. Исключений из этого прави- ла нет. 16.1.5 Заключение Попытаемся немного прояснить ситуацию. Проверки, о которых шла речь в предыдущих разделах, должны выполняться в дополнение к обычному те- стированию библиотек арифметических операций над большими числами. Они ни в коей мере не заменяют обычного тестирования, которому должен подвергнуться любой элемент программного обеспечения, особенно если речь идет о системе обеспечения безопасности. Если хотя бы одна из перечисленных выше проверок окончится неудачей, это означает, что программное обеспечение содержит ошибку. Возможных вариантов действия здесь немного. Продолжать работу небезопасно; мы ведь не знаем, что именно привело к возникновению ошибки. Пожалуй, единствен- ное, что стоит сделать в подобной ситуации, — это записать ошибку в журнал и аварийно завершить работу программы. 16.2 Быстрое умножение Существует множество способов ускорить умножение по модулю таким образом, чтобы системе не приходилось выполнять полное умножение и по- следующее деление “в столбик”. В протоколах с большим количеством умно- жений широко используется метод Монтгомери [67]. К сожалению, статья самого Монтгомери слишком трудна для понимания. Более понятное описа- ние этого метода содержится в [25]. В основе метода Монтгомери лежит способ вычисления ( x mod n ) , где число x намного больше n . Классический метод деления “в столбик” подра- зумевает вычитание из числа x подходящих чисел, кратных n . Идея Монтго- мери гораздо проще: многократное деление x на 2. Если число x четное, мы делим x на 2, сдвигая его двоичное представление на один бит вправо. Если же x нечетное, мы вначале прибавляем к нему n (что, разумеется, не изме- няет значения x по модулю n ), а затем делим полученный четный результат на 2. (Данный метод работает только для нечетных n . Напомним, что в на- ших системах всегда применяются нечетные n . Впрочем, данный метод легко обобщить и на четные значения n .) Если длина n равна k бит, а значение x не превышает ( n − 1) 2 , мы выполним k делений на 2. Полученный резуль- |