на главную | войти | регистрация | DMCA | контакты | справка | donate |      

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я


моя полка | жанры | рекомендуем | рейтинг книг | рейтинг авторов | впечатления | новое | форум | сборники | читалки | авторам | добавить



Длина ключей

Один из простейших критериев сравнения криптографических алгоритмов – длина ключа. Пресса любит обращать на нее внимание, поскольку ее легко считать и сравнивать. Как и в большинстве случаев, когда речь идет о безопасности, реальность более сложна. Короткий ключ плох, но длинный ключ не будет хорошим автоматически. Почему это так, я расскажу в следующей главе, а сейчас лучше разъяснить понятие длины ключа и его важность.

Начнем с самого начала. Криптографический ключ – это секретное число, которое делает криптографический алгоритм уникальным для тех, кто совместно пользуется этим ключом. Если Алиса и Боб договорились об общем ключе, то при помощи алгоритма они могут тайно пообщаться. Если Ева-перехватчица не знает ключа, ей придется исследовать и ломать алгоритм.

Одна очевидная вещь, которую можно сделать, – это перепробовать все возможные ключи. Это так называемая атака «в лоб», или лобовая атака. Если длина ключа n битов, то существует 2^n всевозможных комбинаций ключей. При длине ключа в 40 бит, придется перебрать около триллиона вариантов ключей. Такая задача покажется ужасно скучной для Евы, но компьютеры неутомимы. Они лучше всех решают ужасно скучные задачи. В среднем компьютеру пришлось бы испробовать половину ключей, прежде чем он найдет правильный, то есть компьютер, который мог бы проверять миллиард ключей в секунду, потратил бы на поиски правильного 40-битового ключа примерно 18 минут. В 1998 году Electronic Frontier Foundation создала машину, которая могла атакой «в лоб» ломать DES-алгоритм. Эта машина, названная DES Deep Crack, проверяла 90 миллиардов ключей в секунду; она могла найти 56-битовый ключ DES в среднем за 4,5 дня. В 1999 году распределенный интернет-проект подбора ключей для взлома DES, distributed net (включающий в себя Deep Crack), был способен проверить 250 миллиардов ключей в секунду.

Все схемы таких взломов «в лоб» линейны: вдвое большее количество ключей потребует вдвое больше компьютерного времени. Но сложность такого взлома зависит от длины ключей экспоненциально: добавим один бит к длине ключа, и взлом «в лоб» станет в два раза сложнее. Добавим два бита – в четыре раза. Десять битов – в тысячу раз сложнее.

Сила атак «в лоб» в том, что они работают против любого алгоритма. Поскольку эта атака не касается внутренней математики алгоритма, ей все равно, что же там внутри. Одни алгоритмы могут быть быстрее других, и поэтому атака «в лоб» проходит быстрее, но длина ключа легко это перевешивает. Достаточно просто сравнить длины ключей различных алгоритмов, чтобы выяснить, какие из них более уязвимы для лобовой атаки.

В 1996 году группа шифровальщиков (включающая и меня) исследовала различные технологии, которые можно использовать для создания дешифрующих машин, действующих по принципу лобовой атаки, и пришла к выводу, что 90-битовый ключ сможет обеспечивать безопасность до 2016 года. Ключ Triple-DES состоит из 112 бит, а наиболее современные алгоритмы имеют по меньшей мере 128-битовые ключи. (Улучшенный стандарт шифрования (AES) правительства США поддерживает длины ключей 128,192 и 256 бит.) Даже машине, работающей в миллиард раз быстрее Deep Crack, потребовался бы миллион лет, чтобы перебрать 2^112 ключей и восстановить открытый текст; еще более, чем в тысячу раз, возрастает время при переходе к 128-битовому ключу. Он будет обеспечивать безопасность в течение тысячелетия.

К этим числам нужно относиться с некоторым скептицизмом. Я – не ясновидящий и ничего не знаю о будущих достижениях компьютерных технологий. Реальная безопасность зависит от нескольких вещей: насколько ваши данные ценны, как долго их требуется хранить в тайне и т. п. Но это означает, что должны существовать «законсервированные» числа – длины ключей для симметричных алгоритмов и MAC. Хэш-функции должны иметь длину, равную удвоенной длине ключа.

Длина ключа для симметричного алгоритма открытого ключа определяется более сложным образом. Наиболее эффективная атака против RSA, например, состоит в том, чтобы разложить на множители большое число. Наиболее действенная атака против Эль-Гамаля, алгоритма Диффи-Хеллмана, DSA и других систем – вычислить нечто, называемое дискретным логарифмом. (По существу, это – та же проблема.) Алгоритмы эллиптических кривых еще более сложны.

Для алгоритмов с открытым ключом специалисты сейчас рекомендуют 1024-битовые и более ключи. Параноики используют ключи еще длиннее. Системы, для которых не слишком важна долговременная секретность, пользуются 768-битовыми ключами. (Для алгоритмов эллиптических кривых применяют разные длины ключей.)

Трудно оценивать будущие трудности разложения на множители и вычисления дискретных логарифмов, поскольку нет никакого математического доказательства, что эти задачи имеют фиксированную степень сложности. (С другой стороны, мы знаем, насколько трудно перебирать все возможные ключи.) Итак, еще раз: отнеситесь ко всем этим рекомендациям, как к мнению квалифицированных специалистов – и не более того.


Генераторы случайных чисел | Секреты и ложь. Безопасность данных в цифровом мире | Глава 7 Криптография в контексте