В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 12. Алгоритм Диффи–Хеллмана ли p простым. Поскольку p должно быть нечетным, очевидно, что N должно быть четным. Длина простого числа p будет составлять несколько тысяч бит. Теперь нужно найти элемент порядка q . Это делается точно так же, как и в методе надежных простых чисел. Выберем случайное α из группы Z ∗ p и установим g = α N . Теперь убедимся, что g 6 = 1 и g q = 1 . (Случай g = p − 1 охватывается вторым условием, потому что q — нечетное.) Если полученное значение g не удовлетворяет этим условиям, выберите другое α и повторите попытку. Полученный набор параметров ( p, q, g ) пригоден для использования в протоколе Диффи–Хеллмана. Когда используется подгруппа меньшего размера, значения, которыми об- мениваются пользователи А и Б, всегда попадают в подгруппу, порожденную g . Между тем злоумышленник Е может вмешаться в процесс общения и за- менить g x абсолютно другим значением. Таким образом, каждый раз, ко- гда пользователь А или Б получает значение, которое, как предполагается, должно находиться в подгруппе, порожденной g , он должен проверить, дей- ствительно ли это так. Выполнение проверки происходит точно так же, как и в методе надежных простых чисел. Число r находится в нужной подгруппе, если r 6 = 1 ∧ r q mod p = 1 . Разумеется, следует проверить и то, не попадает ли r за пределы диапазона чисел по модулю p , поэтому полное условие проверки должно выглядеть как 1 < r < p ∧ r q = 1 . Для всех элементов r подгруппы, порожденной g , справедливо равенство r q = 1 . Таким образом, чтобы возвести число r в некоторую степень e , доста- точно подсчитать r e mod q . Это может значительно сократить объем работы, особенно если e намного больше, чем q . Насколько эффективен метод подгрупп? Длина большого простого чис- ла p составляет, как минимум, 2000 бит. В методе надежных простых чисел вычисление g x требует около 3000 умножений. При использовании подгрупп это число сокращается примерно до 384, так как значение x можно взять по модулю q , в результате чего длина x составит лишь 256 бит. Как видите, во втором случае для вычисления g x выполняется почти в 8 раз меньше дей- ствий, чем в первом. Чем больше значение p , тем больше экономия усилий. Вот почему подгруппы так широко применяются в криптографии. 12.7 Размер p Правильно выбрать размер параметров схемы Диффи–Хеллмана доволь- но сложно. До сих пор мы опирались на требование, что злоумышленнику необходимо осуществить не менее 2 128 шагов, чтобы напасть на систему. Это- го было сравнительно легко достичь для алгоритмов симметричного шиф- рования. Операции же с открытым ключом наподобие алгоритма Диффи– 12.7. Размер p 239 Хеллмана обходятся гораздо дороже, причем с увеличением необходимого уровня безопасности их стоимость возрастает намного быстрее. Если придерживаться требования относительно 2 128 шагов, тогда длина p должна составлять около 6800 бит. На практике такой размер p представляет собой реальную проблему с точки зрения производительности. Существует огромная разница между размерами ключей алгоритмов сим- метричного шифрования и алгоритмов шифрования с открытым ключом на- подобие схемы Диффи–Хеллмана. Не стоит впадать в заблуждение, срав- нивая размеры ключей симметричного шифрования (обычно это 128 или 256 бит) с размерами открытых ключей, которые могут достигать тысяч бит. Размеры открытых ключей всегда во много раз больше, чем размеры ключей симметричного шифрования 1 . Операции с открытым ключом выполняются намного медленнее, чем функции шифрования и аутентификации, которые рассматривались ранее. В большинстве систем операции симметричного шифрования не оказывают значительного влияния на производительность, в то время как операции с от- крытым ключом могут существенно ее снизить. Поэтому следует уделить осо- бое внимание аспектам производительности операций с открытым ключом. Размеры ключей симметричного шифрования обычно являются фиксиро- ванными. Ориентируя систему на использование конкретного блочного шиф- ра и функции хэширования, мы также фиксируем в ней и размер ключа. Это означает, что размер ключа симметричного шифрования остается неиз- менным на протяжении всего времени жизни системы. В отличие от этого, размеры открытых ключей практически всегда являются переменными, что позволяет легко изменять размер ключа в системе. Мы разрабатываем систе- му, которая будет использоваться в течение 30 лет, причем данные должны сохраняться в секрете на протяжении 20 лет после того, как они были впервые обработаны этой системой. Размер ключа симметричного шифрования изна- чально должен быть достаточно большим, чтобы он мог защитить систему на протяжении следующих 50 лет. Но открытые ключи, имеющие переменный размер, должны защищать данные только в течение 20 лет. В конце концов, все ключи имеют ограниченное время жизни. Открытый ключ может быть действителен на протяжении одного года и должен защищать данные еще 20 лет. Таким образом, открытый ключ должен защищать данные только на протяжении 21 года, а не 50 лет, как требуется от ключа симметричного шифрования. Каждый год мы генерируем новый открытый ключ, поэтому по 1 Это касается схем шифрования с открытым ключом, которые рассматриваются в дан- ной книге. Другие схемы шифрования с открытым ключом, например основанные на ис- пользовании эллиптических кривых, имеют совершенно другие размеры ключей. |