В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 16. Проблемы реализации. Часть II тат всегда будет находиться в диапазоне 0 , . . . , 2 n − 1 , что уже совсем близко к искомому значению по модулю n . И все же что-то здесь не так! Ведь мы все время делили на 2, поэтому ответ неверен. В действительности метод Монтгомери дает нам не ( x mod n ) , а x/ 2 k mod n для некоторого k . Данная операция выполняется намного быст- рее, но “в нагрузку” мы получаем дополнительный множитель 2 − k . Существу- ет несколько соображений относительно того, как убрать этот дополнитель- ный множитель. Одна из самых неудачных идей — просто переопределить протокол, что- бы включить в вычисления дополнительный множитель 2 − k . Данный при- ем никуда не годится, так как приводит к смешению уровней. Он изменяет спецификацию криптографического протокола, адаптируя ее к конкретному методу реализации. Возможно, в будущем вам захочется реализовать этот же протокол на другой платформе без применения метода Монтгомери. (На- пример, это может быть медленная платформа, имеющая сопроцессор для работы с большими числами, который выполняет умножение по модулю на- прямую.) В этом случае наличие в спецификации протокола множителей 2 − k будет только мешать. Стандартный прием, к которому прибегают в данной ситуации, — изме- нить представление чисел. Число x будет внутренне представлено как x · 2 k . Если требуется перемножить x и y , мы применим умножение Монтгомери к соответствующим внутренним представлениям. Перемножив эти числа, мы получим x · 2 k · y · 2 k , но вследствие взятия числа x · 2 k · y · 2 k по модулю n у нас появится множитель 2 − k . Конечный результат операции умножения будет выглядеть как x · y · 2 k , а это и есть внутреннее представление произведения xy . Таким образом, дополнительные расходы, связанные с применением ме- тода Монтгомери, включают в себя стоимость преобразования входных дан- ных во внутреннее представление (умножение на 2 k ) и стоимость обратного преобразования выходных данных для получения фактического результата (деление на 2 k ) . Первое преобразование может быть выполнено путем умно- жения Монтгомери числа x на (2 2 k mod n ) . Второе преобразование, в свою очередь, можно выполнить, сдвинув число x · y · 2 k еще на k бит вправо, по- скольку это будет эквивалентно делению на 2 k . Конечный результат метода Монтгомери не обязательно будет меньше n , однако в большинстве случаев можно показать, что он будет меньше 2 n − 1 . В подобных случаях для полу- чения корректного результата достаточно лишь небольшой проверки и (при необходимости) одного вычитания числа n . На практике взятие числа по модулю методом Монтгомери выполняет- ся не по битам, а по словам. Предположим, что процессор оперирует w - битовыми словами. Для заданного числа x необходимо найти такое малое z , чтобы наименее значимое слово числа x + zn равнялось нулю. Можно пока- 16.3. Атаки с использованием побочных каналов 311 зать, что искомое z является одним словом и может быть вычислено путем умножения наименее значимого слова числа x на слово-константу, которое зависит только от n . Если наименее значимое слово числа x + zn будет равно нулю, мы можем поделить это число на 2 w , сдвигая двоичное представление сразу на слово вправо. Это намного быстрее, нежели сдвигать его по биту. 16.3 Атаки с использованием побочных каналов Мы уже затрагивали тему тайминг-атак и других атак с использованием побочных каналов в разделе 9.5. Причина, по которой мы были столь немно- гословны, состоит отнюдь не в их безобидности. Напротив — наибольшую опасность для криптографических систем с открытым ключом представля- ют именно тайминг-атаки. Как уже отмечалось, в криптосистемах с симметричным ключом програм- ма для каждого вычисления использует простой путь кода. Следовательно, время, необходимое для выполнения одной операции шифрования с помощью блочного шифра, будет постоянным. Вернее, относительно постоянным — су- ществует масса мелких операций с участием кэша, время выполнения ко- торых варьируется самым неожиданным образом. Впрочем, пока еще никто не пытался нападать на криптосистемы с симметричным ключом, исполь- зуя разницу во времени кэширования, хотя теоретически такие атаки все же возможны. Некоторые шифры требуют программных реализаций, применяющих раз- личные пути кода для обработки тех или иных частных случаев. В качестве примера таких шифров можно привести IDEA [60, 61] и MARS [13]. Другие шифры используют операции процессора, время выполнения которых зави- сит от обрабатываемых данных. У некоторых процессоров время выполнения умножения (используемого шифрами RC6 [77] и MARS) или циклического сдвига битов (используемого шифрами RC6 и RC5), величина которого за- висит от данных, во многом определяется спецификой входных данных. Все это делает возможным осуществление тайминг-атак. Отметим, что функции, с которыми мы работали при написании этой книги, подобные типы операций не используют. Криптографические системы с открытым ключом еще более уязвимы по отношению к тайминг-атакам. Путь кода, который выбирает программа для выполнения операций над открытым ключом, зачастую зависит от самих данных. Это практически всегда приводит к тому, что обработка разных дан- ных занимает разное время. Информация о времени выполнения той или иной операции, в свою очередь, может привести к осуществлению атаки. Представьте себе защищенный Web-сервер электронной коммерции. В рам- |