Сравнительный обзор алгоритмов PGP

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

А вот что написано по этому поводу в черной книге:

Когда-нибудь квантовая механика фундаментально изменит способ работы компьютера. В настоящее время можно смело утверждать, что квантовые компьютеры способны сложить два 1-битовых числа, но кто знает, что будет дальше? Возможно если иметь ввиду новые квантовые методы расчета, большинство алгоритмов открытых ключей покажутся устаревшими, но на самом деле они всего-лишь заставят нас удвоить длины ключа для симметричных шифров, хэш функций и МАСs(кодов аутентификации)

Б. Шнайер "Секреты и ложь. Безопасность данных в цифровом мире".

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

Мда, – еще из книги Шнайера.

Все считают, что разложение на множители является трудной математической задачей, но это никогда не было доказано математически.
Разлагать большие числа на множители нелегко, но, к несчастью для проектировщиков алгоритмов, этот процесс становится все легче. Что еще хуже, он становится легче с большей скоростью, чем предсказывалось математиками. В 1976 году Ричард Гай писал: «Я был бы немало удивлен, если бы кто-нибудь научился разлагать на множители произвольные числа порядка 10^80 в течении данного столетия». В 1977 году Рон Ривест заявил, что разложение на множители 125-и разрядного числа потребует 40 квардиллионов лет. В 1994 году было разложено на множители 129-разрядное число.

Остается надеяться, что ключи 2048 бит и более все же будут достаточно надежны в течении нами обозримого промежутка времени. Но мало кто думает о том, что будет через сотню лет, или же просто боятся делать прогнозы. Я все же думаю, что будут придуманы новые ассиметричные алгоритмы, и возможно с уже доказанной стойкостью. Может быть я и заблуждаюсь, но исключительно образно я бы сравнил RSA с песочными часами – это одна система, в которой песочек медленно сыплется из одной колбочки в другую через то самое узкое отверстие, которое можно гипотетически сравнить с медленным процессом разложения чисел на множители, больше длина ключа – тоньше отверстие. А можно ли придумать единую систему без такого отверстия? Насколько я помню основательница сайта Kat писала что-то о порванной фотографии. Если фотографию порвать не пополам (археологи как известно по костям воссоздают внешность древних животных), а в удачном месте? Или что то еще, пока мысли не идут, а интересно…

Одна из лучших на мой взгляд работ, до сих пор не утратившая свой актуальности, где даны (в том числе) прогнозы стойкости RSA:

"Selecting Cryptographic Key Sizes" Arjen K. Lenstra, Eric R. Verheul. October 27, 1999

http://www.secinf.net/uplarticle/4/cryptosizes.pdf


Там же про симметричные шифры, дискретные логарифмы и эллиптические кривые. Пока прогнозы совпадают с теми графиками и таблицами, которые там есть.

Я все же думаю, что будут придуманы новые ассиметричные алгоритмы, и возможно с уже доказанной стойкостью.

Christofer Wolf и Bart Preenel исследовали ассиметричные алгоритмы типа "Multivariate quadratic public key systems", устойчивые (пока) к квантовому вскрытию.

(Проблема решения мультивариантных квадратичных уравнений в конечном поле. Исследовалась еще с конца восьмидесятых годов)

Может когда-нибудь вместо RSA и ECC будет MQ?

Но пока их стойкость малодоказанна.

В чем суть недоказанности (или даже недоказуемости может быть) долговечной стойкости асимметричных алгоритмов? В том, что существует открытый ключ, по которому можно пытаться вычислить закрытый или есть какие-либо дополнительные факторы?

Собственно, я только повторяю вышеизложенное:

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

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

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

И это характерно для всех ассиметричных систем. В их основе лежит "трудная проблема", решение которой не удавалось получить в течении сотен или тысяч лет (разложение на множители волновало умы еще древнегреческих математиков) но кто может точно доказать, что она всегда будет трудной?

Нет ни одного абсолютного доказательства!

Есть еще более фундаментальная проблема P=NP. Если смогут решить и ее то криптография в худшем случае вообще прекратит свое существование даже в области симметричных шифров.

Вот интересная статья с http://www.cryptography.ru/db/msg.html?mid=1169815

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

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

Но пока такие достижения в математике выглядят чистой фантастикой вроде "машины времени" или "путешествия в гиперпространстве".

Более вероятно, что "трудные проблемы" не смогут решить мгновенно, а будут постепенно изобретать все более быстрые численные способы их решения.

В 2006 году состоится конференция по постквантовой крипографии:
http://postquantum.cr.yp.to/

Вопрос по генерированию асимметричный ключей.
Предположим, что в симметричной системе шифрования существует множество ключей 2^128. При получении ключа используется алгоритм случайного подбора. Допустим соответствие каждого из 128 бит нулю или единице определяется подкидыванием монеты 128-ю разными людьми по выстрелу стартового пистолета. Здесь все ясно.
Теперь что касается асимметричных ключей. Из сравнительных таблиц известно, что имея длину асимметричного ключа около 2304 бит для подбора правильного ключа грубой силой с вероятностью встречи нужного ключа 50% нужно перебрать примерно 2^127 вариантов. Но для генерирования асимметричного ключа требуется не просто подкинуть монеты n-раз, а произвести вычисления. Позволяют ли методы формирования ключа получить столько разных ключей, что бы их количество действительно было около 2^128? Т.е. есть ли соответствие между количеством вариантов перебора при поиске ключа и количеством ключей, которые можно сгенерировать?

Позволяют ли методы формирования ключа получить столько разных ключей, что бы их количество действительно было около 2^128?

Да! Вы подметили правильный критерий генерации ассиметричных ключей.

Нужно к примеру выбрать интервал в котором встретится примерно 2^128 простых чисел (этот интервал можно предсказать с большой точностью, он небольшой, числа в нем будут иметь примерно одинаковый порядок длины в битах), среди них перебирать случайным образом числа кандидаты и проверять на простоту тестом Рабина-Миллера. А именно так и делается.

Требование перебора 2^128 (например среди простых чисел из интервала) для асимметричных алгоритмов соблюдается обязательно.

Ну есть еще кое-какие тонкости, но это уже в специальной литературе читайте.

Наконец-то я добрался до полки со Шнайером (и Фергюссоном)
Вот Вам от них хороший пример:

В окружении числа n приблизительно одно из каждых ln n чисел является простым <...>
Число длиной 2000 бит находится в диапазоне от 2^1999 до 2^2000.

В этом диапазоне примерно одно из каждых 1386 чисел является простым.

От себя: 2^2000 / 1386 это примерно 2^1990 или 1990 бит. Явно больше, чем 128.

Вся проблема только в скорости подбора простого числа из заданного диапазона.

Так что проблема защиты ключа от брутфорса самая легкая и была продумана с самого начала.

SATtva:

Более того, PGP кроме RSA поддерживает алгоритм шифрования Эльгамаля (названный в PGP Diffie-Hellman'ом, что формально неверно) и алгоритм подписания DSA, оба основанные на математической проблеме вычисления дискретного логарифма в конечном поле.

Ничего неверного в этом нет. Шифрование ElGamal — ничто иное, как генерирование сеансого DH-ключа и согласование секретного симметричного ключа на его базе с публичным DH-ключем корреспондента. Публичная половина сеансового DH-ключа передается вместе с сообщением. Ключ ElGamal и ключ DH — одно и тоже.

Один и тот же ключ и один и тот же алгоритм использованный в разных протоколах. В случае DH — для согласования ключа, в случае ElGamal — для шифрования.
Но называть ключ ElGamal ключем DH совершенно корректно, так как это одно и то же.

Но называть ключ ElGamal ключем DH совершенно корректно

Скажем иначе, не совсем точно. Диффи-Хеллманом принято называть интерактивный протокол согласования ключа. Эльгамаль — его частный случай и, одновременно, семейство дискретно-логарифмических алгоритмов, в том числе, и для цифровой подписи.

Не думаю, что совсем уместно проводить между ними прямую параллель. Это всё равно, как сравнивать схему одноразовых блокнотов с пороговой схемой разделения секрета. Да, между ними много общего, и OTP скорее частный случай схем secret sharing на базе простого XOR, но это не одно и то же.

Все так интересно, жаль, что не очень понятно.
Скажите. Известно, что блочные симметричные шифры работают с блоками текста. К примеру блок текста с которым работает алгоритм равен 64 битам, а длина ключа равна 128 битам. Значит количество вариантов перестановок битов в блоке может быть намного меньше чем позволил бы это сделать ключ. Каким образом тогда достигается "полное" использование всех вариантов ключа?

2 Sattva:

Скажем иначе, не совсем точно. Диффи-Хеллманом принято называть интерактивный протокол согласования ключа. Эльгамаль — его частный случай и, одновременно, семейство дискретно-логарифмических алгоритмов, в том числе, и для цифровой подписи.

Это формальности, просто один параметр (случайное число x) не создается в ходе сеанса, а зафиксирован в ключе в виде g^xmodP. Заменили эфемерность на постоянство. Подпись – это "шифрование наоборот", поэтому x генерирует подписывающая сторона. Формулы те же. Возведение в степень – мультипликативные группы те же. А дискретные логарифмы злоумышленнику для взлома придется считать, что в одном что в другом случае абсолютно одинаково.

Разница слишком мала, даже в профессиональной литературе "путают", а точнее уравнивают или обобщают эти определения.

2 Гость:

Все так интересно, жаль, что не очень понятно.
Скажите. Известно, что блочные симметричные шифры работают с блоками текста. К примеру блок текста с которым работает алгоритм равен 64 битам, а длина ключа равна 128 битам. Значит количество вариантов перестановок битов в блоке может быть намного меньше чем позволил бы это сделать ключ. Каким образом тогда достигается "полное" использование всех вариантов ключа?

Если шифры бы были устроены, так как Вы предполагаете, они бы взламывались элементарно. :-)
Ключ дает не 2^128 перестановок, а значительно больше.

Значит количество вариантов перестановок битов в блоке может быть намного меньше чем позволил бы это сделать ключ.

Ни в коем случае!

КАЖДЫЙ ключ создает уникальную псевдослучаюную таблицу перестановок размером 2^64 (pseudorandom permutation). Для уникального соответствия каждого из 2^64 возможных открытых текстов каждому 2^64 шифртексту.

<...>

Дальше было неправильно :-(

Вот еще пара замечаний:

128 битовый конкретный уникальный ключ = 128 бит.
А когда говорят "шифр имеет 128-бит ключ" подразумевают все множество ключей 2^128.
Поэтому может возникнуть путаница в некоторых предложениях, например когда приводят расчеты на один ключ или на множество ключей. И один ключ и множество, все называют ключ, key. Следите за контекстом, чтобы не запутаться.

Если бы у какого-то алгоритма использовались не все биты ключа – это сокращенное пространство ключей, обычно грубый просчет в дизайне или тайная закладка для легкого взлома шифра (совместно с другими методами).