В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 15. Протокол согласования ключей Как видите, наш протокол обеспечивает наилучшую возможную защиту от взлома ключей. 15.9 Вычислительная сложность протокола Теперь обсудим вычислительную сложность нашего решения. Будем ис- ходить из предположения, что процедуры выбора и проверки параметров алгоритма DH кэшированы, поэтому они не будут учитываться в объеме вы- числений, необходимых для проведения одного сеанса работы протокола. Как следствие этого, у нас остаются такие вычисления: • три операции возведения в степень в подгруппе DH для каждого из пользователей А и Б; • одна генерация аутентификатора; • одна проверка аутентификатора; • различные относительно эффективные операции, такие, как генерация случайных чисел, сравнение и хэширование 2 . Если мы применяем аутентификацию с симметричным ключом, тогда вре- мя выполнения протокола будет определяться показателями степеней алго- ритма DH. Давайте посмотрим, сколько вычислений для этого потребуется. Каждый из пользователей А и Б должен проделать три операции возведе- ния в степень по модулю с 256-битовым показателем степени. Это потребует около 1150 операций умножения по модулю 3 . Чтобы получить представление о том, насколько велик этот объем вычислений, давайте сравним его с вычис- лительной стоимостью создания цифровой подписи RSA, если модуль RSA и простое число DH будут иметь одинаковый размер. Для s -битового моду- ля алгоритм создания цифровой подписи потребует 3 s/ 2 вычислений, если не использовать китайскую теорему об остатках (Chinese Remainder Theo- rem — CRT). Использование CRT-представления позволяет сократить объ- ем вычислений в четыре раза, поэтому вычислительная стоимость цифровой подписи RSA для s -битового модуля будет эквивалентна вычислительной сто- имости 3 s/ 8 операций умножения. Мы пришли к интересному заключению: алгоритм RSA относительно медленнее алгоритма DH при использовании мо- дулей большого размера и относительно быстрее при использовании модулей 2 Все сказанное в этом разделе касается объема вычислений для одного из двух участ- ников протокола. И пользователь А и пользователь Б должны выполнить по три операции возведения в степень в подгруппе DH, по одной генерации аутентификатора, по одной проверке аутентификатора и по набору различных эффективных операций. 3 Речь идет о простом бинарном алгоритме возведения в степень. При использовании хорошо оптимизированного алгоритма количество операций умножения можно сократить до 1000 или еще меньшего числа. 15.10. Сложность протокола 297 малого размера. “Переломная” точка находится примерно на уровне 3000 бит. Причина такого эффекта состоит в том, что алгоритм DH всегда использует 256-битовые показатели степеней, в то время как размеры показателей RSA возрастают вместе с размером модуля. Мы пришли к выводу, что при используемых размерах открытых ключей объем вычислений для алгоритма DH примерно равен объему вычислений для схемы цифровых подписей RSA. Описанная выше нагрузка составляет основной объем вычислений нашего протокола, но она находится в разумных пределах. Если для аутентификации применяются цифровые подписи RSA, вычис- лительная нагрузка примерно удваивается. (Проверку подписей RSA можно не учитывать, так как она выполняется очень быстро.) Тем не менее данную нагрузку все еще нельзя назвать чрезмерной. Скорость процессоров стреми- тельно растет изо дня в день, и, как показывает практика, коммуникацион- ные задержки и передача служебной информации отнимают гораздо больше времени, чем криптографические вычисления. 15.9.1 Методы оптимизации Вычисления, выполняемые в рамках протокола DH, поддаются оптими- зации. С помощью эвристики аддитивной цепочки (addition chain heuristics) каждую операцию возведения в степень можно осуществлять путем меньшего количества умножений. Более того, пользователь А должен вычислить значе- ния X q и X y . Используя эвристику аддитивной последовательности (addition sequence heuristics), эти значения можно вычислить параллельно, сэкономив при этом около 250 операций умножения. Более подробно это рассматрива- ется в работе Боса (Bos) [10, глава 4]. Существуют также разнообразные приемы, которые позволяют быстрее генерировать случайное число y и вычислять g y , но они настолько усложняют систему, что мы предпочитаем обходиться без них. 15.10 Сложность протокола Описанный протокол согласования ключей является прекрасным приме- ром того, почему структура большинства протоколов столь сложна. Даже простой протокол наподобие нашего разрастается на целую страницу, а ведь мы еще не включили в его описание все правила генерации параметров алго- ритма DH и все необходимые проверки, выполняемые в рамках схемы аутен- тификации (на нашем уровне абстракции они неизвестны). Несмотря на это, уследить за всем, что происходит в рамках такого протокола, уже очень труд- но. Спецификации более сложных протоколов занимают еще больше места. |