id: Гость   вход   регистрация
текущее время 18:44 19/11/2019
Владелец: SATtva (создано 14/09/2006 22:50), редакция от 07/09/2006 21:54 (автор: SATtva) Печать
Категории: криптография, софт, pgp, сайт проекта, статьи, управление ключами
создать
просмотр
редакции
ссылки

Длина ключа


Существует вопрос, регулярно всплывающий в криптологических дискуссиях: какой должна быть верная длина ключа? На этот вопрос нет однозначного ответа, как нет и некоего математического обоснования, что конкретная длина является достаточной. Никто не может заглянуть в будущее и предсказать, какими возможностями будут обладать компьютеры завтра.


Причина, почему вопрос размера ключа важен, заключается в том, что правительство Соединенных Штатов в течение многих лет ограничивало максимально разрешенную длину ключа, потому что хотело сохранить возможность взлома всех криптографических продуктов, экспортируемых за рубеж. Они распространяли ложную информацию, утверждая, что 40 бит достаточно для всех нужд, кроме военных. Пользователи PGP и другие энтузиасты криптографии, параноики, какие они и есть, реагировали на эти ограничения прямо противоположно, используя ключи огромных размеров.


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


Понятие длины ключа имеет несколько разных значений. Я бы хотел привести здесь три значения размера ключа:
Sraw(K)
Raw key size, объем ключевого материала. Для ключа K, Sraw(K) – это количество битов, необходимое для записания K. Мы можем вывести, что для криптографического алгоритма А, Sraw(A) = Sraw(K), если K – это ключ для А, и все ключи для А имеют сходный объем ключевого материала.
Sreal(A)
Real key size, действительная длина ключа определенного алгоритма / криптосистемы А (со статичными параметрами) – это логарифм по основанию 2, взятый от общего пространства ключей. Обратите внимание, что разные ключи А не обязательно будут иметь одинаковый объем материала. Этот размер влияет на сложность атаки грубой силой – перебор всех возможных ключей.
Seff(A)
Effective key size, эффективная длина ключа, или стойкость А, – это логарифм по основанию 2, взятый от количества ключей, которые должны быть проверены для взлома системы, или от числа действий, которые должен выполнить оппонент для взлома системы. Имейте в виду, что взломщик может располагать лучшим способом атаки, чем атака грубой силой, поэтому криптографическая стойкость может оказаться меньше действительной длины ключа.

Следующее соотношение справедливо всегда:
Sraw(A) ≥ Sreal(A) ≥ Seff(A)
(1.1)

Факт 1: Криптосистема А в настоящее время (2001 год) является ненадежной, если Seff(A)<60

Вот некоторые подтверждения этого факта: в Electronic Frontier Foundation построили специальную машину по взлому DES, которая может проверить 256 ключей за несколько часов. Американское правительство в течение долгого срока накладывало ограничение на длину ключа свыше 40 бит. Это в миллион раз хуже, чем просто ненадежно.

Факт 2: Криптосистема А в настоящее время (2001 год) надежна, если Seff(A)>80

Этот факт в будущем потребует пересмотра, поскольку мощность компьютеров постоянно растет, увеличивается и их количество. В действительности, некоторые люди уже перешли от 80 к 128 битам, а другие [параноики] задумываются о еще большей длине ключа, ведь современные компьютеры в силах использовать их, а увеличение количества битов ключа бесспорно не влияет негативно на стойкость. Однако повышение длины ключа улучшает лишь сильную сторону PGP, тогда как взломщик фокусирует усилия на слабых.


Для блочных шифров разработчики стараются делать Sraw(A) = Sreal(A) = Seff(A), выбирая Sraw(A) равным 128 битам для создания некоторого безопасного задела. Поскольку ограничения на длину ключа накладываются редко, можно легко достичь Sraw(A) = Sreal(A). Один известный контрпример – это DES. DES работает с 8-байтовым (64-битовым) ключом, но последний бит каждого байта не используется, поэтому Sraw(DES) = 64, тогда как Sreal(DES) = 56. У TripleDES аналогичная проблема: Sraw(3DES) = 192, а Sreal(3DES) = 168 (причем Seff(3DES) ≤ 112 из-за атаки типа "встреча посередине").


В отдаленном будущем ученые могут построить квантовый компьютер. Это устройство, основанное на принципах квантовой механики, что позволяет ему производить вычисления над множеством чисел одновременно. Квантовые компьютеры способны уменьшить количество необходимой вычислительной работы примерно в квадратный корень раз, 1 так что людям, обеспокоенным появлением квантовых "числогрызов" стоит использовать ключи двойной длины: 160 или 256 бит вместо 80 или 128, соответственно. Если квантовые компьютеры будут работать так, как мы того ожидаем, то Seff(A) ≤ Sreal(A)/2, но, пожалуйста, воспринимайте это с долей сомнения, потому что квантовые компьютеры – это еще очень отдаленная перспектива.


У хэш-функции H нет ключа, поэтому размер ее выхода принимается как "размер ключа" хэш-функции. Атака на основе парадокса дней рождений показывает, что Seff(H) ≤ Sreal(H)/2. Поэтому Sreal(H) должна составлять по меньше мере 160 бит. MD5 не удовлетворяет этому требованию, но поскольку Sreal(MD5) > 2∗60, то нельзя сказать, что алгоритм ненадежен по определению. Скажем так, он неоднозначен. 2


Для алгоритмов с открытым ключом (public key algorithms) вопрос более сложен. Для обозначения "размера ключа" PK-алгоритма часто принимают "размер группы". Sraw(PK) зачастую больше, поскольку нужно принимать в расчет все числа для получения "сырого" объема ключевого материала. Также существует различие между открытой и закрытой частями ключа. Для Seff(PK) имеет значение только закрытая часть ключа. К тому же часто утверждают, что Sraw(PK) > Sreal(PK), потому что числа должны обладать особыми свойствами, например, быть простыми.


Для алгоритмов с открытым ключом мы также хотим, чтобы Seff(A) ≥ 80, а из-за атак, схожих с атакой на парадоксе дней рождений, необходимо Sreal(x) ≥ 160, где x – компонент секретного ключа. Эти атаки описаны в параграфе "ElGamal / Diffie-Hellman".


PK-алгоритмы часто работают в группе определенного вида. Название группы может быть известно, но определенные действия в отсутствие закрытого ключа должны быть трудно выполнимы, так, чтобы посторонние не могли определить структуру этой группы. На практике, для алгоритмов PGP это значит, что группа должна содержать по меньшей мере 21024 членов, дабы обеспечить эквивалентную 80 битам стойкость против алгоритмов факторизации. Сильно отличные группы, такие как эллиптические кривые, могут проявлять иные свойства и требовать другого размера группы.


Назад | Дальше



1 Согласно публикации Шнайера от 18.10.1998г. в Usenet-группе soc.history.what-if.


2 На конференции Crypto в августе 2004 года и в последующие месяцы была продемонстрирована неустойчивость алгоритма MD5 к коллизиям хэш-значений, что привело к Seff(MD5) ≈ 40. Продолжение криптоаналитических работ и дальнейшие исследования в области хэш-функций могут в самом ближайшем будущем привести к полному взлому данного алгоритма. Это стало главной причиной, почему в ноябре 2004-го MD5 был исключён из пересмотренной редакции стандарта OpenPGP: в дальнейшем он найдёт применение в PGP только в целях обратной совместимости, – прим. пер.


 
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3