О длине ключей

От длины ключа шифрования зависит сложность взлома шифра методом грубой силы.

Смысл длины ключа для симметричных и ассимитричных алгоритмов шифрования различен. Для симметричных алгоритмов в среднем для взлома ключа длиной N бит требуется перебрать 2^(N-1) вариантов. Для ассиметричных это не так из-за того, что пространство ключей не является непрерывным. Теоретически трудоёмкость взлома ассимметричного ключа длиной 512 бит сравнимо с взломом 56-бит симметричного, 1024 бит - с 128-битным.

В EFF был создан специализированный процессор для взлома DES (56 бит), процесс занимает несколько часов. Каждый добавочный бит должен увеличивать продолжительность процесса в 2 раза.

Существует также энергетический подход для оценки возможности взлома шифра. Один из примеров см. тут. В общих чертах, с исправлением ошибок:
для реализации AES требуется примерно 50000 вентилей. Предположим, что в одной попытке меняют значения где-то 10000 из них.
Если считать энергией, необходимой для изменения состояния вентиля 1 эВ, то для взлома 128-битного ключа потребуется затратить 2.7E23 Дж.
Энергия в 1 барели нефти - 6E9 Дж, т.е. для взлома ключа потребуется сжечь около 4.5E13 барелей нефти. При этом считаем, что КПД электростанций - 100%. Хотя всё едино разведанные запасы нефти - около 1E12 барелей.

Причём 1эВ - это нечто нереальное при текущем развитии технологии. Как более реалистичный случай можно рассмотреть некий специализированный процессор, проверяющий 1 ключ за цикл, с частотой 1 ГГц и с тепловыделением 1 Вт. В этом случае потребуется уже около 3E19 барелей нефти....

Итого, 128-битный ключ _вполне_ надёжен, _если_ не будут найдены математические способы, позволяющие сократить возможное поле ключей.

Кроме того, следует принимать во внимание, что ключ для симметричных алгоритмов шифрования обычно _вычисляется_ из пароля с помощью некоторой хэш-функции. Т.е. для большинства случаев стойкость шифра определяется длиной пароля, а не ключа шифрования. Для успешного противостояния взлому грубой силой пароли должны быть достаточно длинными.

Эффективную длину пароля можно оценить следующим образом:
пароль из случайной последовательности символов ASCII - 5-6 бит/символ
парольная фраза - 1.3 - 1.5 бит/символ слова.

Следует отметить, что получение хэша по паролю - достаточно трудоёмкая операция. Из документации к keyring следует, что P4 1.2 GHz может вычислить 1.5E6 хэшей MD5 в секунду.
Итого, пароль должен быть длиной не менее 8-10 случайных символа или 3-4 слова с символами пунктуации между ними.

Выбор хэш-функции является весьма важным, т.к. "плохая" хэш-функция может резко сократить поле ключей. И, естественно, возможны ошибки в реализации алгоритмов, криптостойких самих по себе, который делают возможным взлом шифров…

Дата создания: 2006-05-24 11:27:22 (Фетисов Н. А. (naf))
Последнее изменение: 2006-05-24 11:27:22 (Фетисов Н. А. (naf))
Владелец: Фетисов Н. А. (naf)
Версия: 1