В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 12. Алгоритм Диффи–Хеллмана Пренебрежение этой информацией крайне опасно, поскольку практика пока- зывает, что рано или поздно кто-нибудь реализует данный протокол не так, как нужно. Злоумышленнику Е должно повезти, чтобы у числа p − 1 оказалось доста- точно малых делителей. Мы проектируем систему в расчете на атаку, состо- ящую из 2 128 шагов. Это позволит злоумышленнику воспользоваться всеми делителями p − 1 величиной до 2 128 или около того. Нам никогда не попадался хороший анализ вероятности того, сколько информации может получить зло- умышленник, но уже быстрая оценка показывает, что в среднем злоумышлен- ник сможет получить около 128 бит информации об x , используя делители, меньшие 2 128 . Затем злоумышленник сможет напасть на неизвестную часть x , используя атаку на основе коллизий. Поскольку длина x составляет всего 256 бит, это может привести к реальной атаке. По крайней мере могло бы при- вести, если бы мы не проверяли принадлежность X и Y к нужной подгруппе. Осуществить атаку становится еще проще, если злоумышленник является тем самым человеком, который выбирает подгруппу ( p, q, g ) . Он может сам перемножить малые делители, чтобы получить число p − 1 и таким образом выбрать p раньше, чем q . Он также может присутствовать на заседании ко- митета, который рекомендует определенные параметры в качестве стандарта. Это не так невероятно, как кажется. Правительство США в лице NIST за- ботливо предлагает простые числа, которые могут быть использованы в DSA (Digital Signature Algorithm — алгоритм цифровой подписи), схеме цифровой подписи, работающей с подгруппами наподобие этой. Другие органы того же правительства США (NSA, ЦРУ, ФБР и т.п.) весьма заинтересованы в том, чтобы иметь возможность вмешиваться в частное общение. Мы, конечно, не хотим сказать, что эти простые числа плохи, однако подобные вещи нуж- но тщательно проверять перед использованием. Это совсем несложно; более того, NIST опубликовала алгоритм выбора параметров, не имеющих малых делителей, и вы можете проверить, действительно ли параметры вашей под- группы были выбраны в соответствии с этим алгоритмом. К сожалению, его практически никто не придерживается. Подводя итог сказанному выше, можно сделать следующий вывод: самое простое решение — проверять, действительно ли каждое полученное вами значение принадлежит к нужной подгруппе. Все остальные методы борьбы с атаками, основанными на использовании подгрупп малого размера, намного сложнее. Вы можете попытаться непосредственно найти все малые делители числа p − 1 , но это слишком трудно. Вы можете потребовать, чтобы человек, генерирующий набор параметров, предоставил вам разложение на множите- ли числа p − 1 , но это существенно повышает сложность всей системы. Провер- ка полученных значений на принадлежность к нужной подгруппе занимает определенное время, зато это наиболее простое и самое надежное решение. |