Основные методы криптоанализа(краткий обзор).

El Jefe

Consejero
Проверенный сервис
Сообщения
1.483
Реакции
3.942
Криптоанализ - это целая наука. Ни один серьёзный криптоаналитик не будет брутфорсить ключ длиннее 56-64 бит, ибо это займёт у него мало что не целую вечность даже на суперкомпьютере. Для этого существуют разные методы криптоанализа - линейный, дифференциальный и прочие, для всех них нужен определённый набор пар зашифрованных и незашифрованных на данном ключе текстов.

Во-первых, можно использовать метод "встречи посередине", этим вдвое сокращается время возможного поиска ключа.

Во-вторых, можно использовать дифференциальный криптоанализ, изобретённый Бихамом-Шамиром. Он основан на анализе открытых текстов, между которыми есть некая разность. При этом способе криптоанализа анализируют изменение выходного текста при определённом изменении входного, для этого необходимо немало пар текстов. Разность текстов определяется как XOR(исключающее ИЛИ) одного на другой. И смотрят, как эти разности соотносятся одна с другой, при этом нередко удаётся угадать таким образом часть битов ключа(из 64 в DES, например), и уменьшить множество ключей для брутфорса до приемлемого.

Есть ещё линейный криптоанализ, созданный японским математиком Мацуи. Идея его в том, что результат операции XOR соответствующих по номерам битов шифрованного текста и первичного текста равно соответствующим битам ключа с вероятностью 50%; для тех номеров битов, для которых это не так, появляется возможность угадывания неизвестных битов ключа. Этот вид криптоанализа хорош тем, что для него не требуются даже незашифрованные тексты, можно обойтись и без них.

Есть "метод бумеранга" - усиление дифференциального криптоанализа заменой пар открытых и закрытых текстов на квартеты.

Есть неплохая сдвиговая атака, для неё всё равно количество раундов алгоритма шифрования, при условии, что все раунды одинаковые.

Есть "метод интерполяции", есть "невозможные дифференциалы"...

Методы вскрытия криптоалгоритмов с ключами длиной 128 и 256 бит требуют творческого подхода, не дают 100% результата и нередко используют слабость ключей (например
00000000FFFFFFFF - такие ключи использовать нельзя). Но это никак не тупой брутфорс. Они сводятся к тому, чтобы угадать нек-рые биты ключа и брутфорсить не на полном ключевом множестве, а на уменьшенном на много порядков).

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

Чистый брутфорс(грубый перебор) в т.ч. на суперкомпьютерах за разумное время угрожает только алгоритмам с короткими(до 56-64 бит) ключами. Но и алгоритмы с более длинными ключами можно в принципе вскрывать различными методами но не со 100%-ной вероятностью и в основном в случае косяков пользователя - использование слабых ключей, сбои в работе шифратора, редкая замена ключей и тому подобное.

Секретность информации определяется не секретностью алгоритма, а секретностью ключа. Длина ключа обычно стандартна, сам алгоритм тоже - сдвиги, XORы и подстановки по таблицам. Главное ИМХО - не использовать так называемые слабые ключи, генерировать их на специальном алгоритме, а не брать от балды.

К тому же есть такая тонкая тема как возможные АНБ-шные закладки в алгоритмах криптования(их наличие в DES подозревал ещё Брюс Шнайер). Там парочку таблиц подстановки они подредактировали, насколько он пишет... В наличии подобных закладок уже от ФАПСИ в алгоритмах ГОСТ я даже не сомневаюсь, поэтому они в принципе не сертифицируют буржуйскую криптографию, например, для использования в банк-клиентах и т.п.

В любом случае, хорошие криптоалгоритмы можно пересчитать по пальцам 2-х рук, а то и одной…

А теперь ещё цитата из книги “Практическая криптография” Брюса Шнайера, этого гуру криптографии:

“Одним из следствий закона второго термодинамики является то, что для представления информации необходимо некоторое количество энергии. Запись одиночного бита, изменяющая состояние системы, требует количества энергии не меньше чем kT; где Т — абсолютная температура системы и k — постоянная Больцмана. (Не волнуйтесь, урок физики уже почти закончен.)

Приняв, что k = 1,38*10-16 эрг/K, и что температура окружающей вселенной 3,2K, идеальный компьютер, работая при 3,2K, потреблял бы 4,4*10-16 эрга всякий раз, когда он устанавливает или сбрасывает бит. Работа компьютера при температуре более низкой, чем температура космического пространства, потребовала бы дополнительных расходов энергии для отвода тепла.

Далее, энергия, излучаемая нашим Солнцем за год, составляет около 1,21*1041 эргов. Это достаточно для выполнения 2*1056 перемен бита в нашем идеальном компьютере, а этого, в свою очередь, хватит для того, что бы 187-битовый счетчик пробежал все свои значения. Если мы построим вокруг Солнца сферу Дайсона и перехватим без всяких потерь всю его энергию за 32 года, мы сможем получить компьютер для вычисления 2192 чисел. Конечно, энергии для проведения каких-нибудь полезных вычислений с этим счетчиком уже не останется.

Но это только одна жалкая звезда. При взрыве типичной сверхновой выделяется около 1051 эргов. (В сто раз больше энергии выделяется в виде нейтрино, но пусть они пока летают). Если всю эту энергию удастся бросить на одну вычислительную оргию, то все свои значения сможет принять 219-битовый счетчик.

Эти числа не имеют ничего общего с самой аппаратурой, они просто показывают максимальные значения, обусловленные термодинамикой. Кроме того, эти числа наглядно демонстрируют, что вскрытие грубой силой 256-битового ключа будет невозможно, пока компьютеры построены из обычной материи и располагаются в обычном пространстве.”

Также скептически Брюс Шнайер отзывается и о возможности брутфорса криптографических алгоритмов с помощью квантовых компьютеров(уже обсуждалось на этом форуме), и вот почему. Существенной здесь видится проблема некогерентности, вызванная потерей отчётливости волновыми огибающими и приводящая к сбою квантового компьютера каждую наносекунду. К тому же, для постройки квантового устройства для разложения на множители потребуется слишком большое количество вентилей, а это, пишет Шнайер, может не дать построить машину.
 

tueda65

Местный
Сообщения
1.125
Реакции
1.078
К тому же, для постройки квантового устройства для разложения на множители потребуется слишком большое количество вентилей, а это, пишет Шнайер, может не дать построить машину.
И тем не менее это позволит обнаружить слабые места и уязвимости конкретных реализаций в программах и протоколах. Что опять же подстегнет виток развития в сторону надёжности, но старые алгоритмы окажутся относительно ненадежны.
За статью спасибо, читается неплохо.
 

El Jefe

Consejero
Проверенный сервис
Сообщения
1.483
Реакции
3.942
Исходя из всего вышесказанного какие шифраторы данных посоветуете?
Для бытовых целей алгоритм RSA и программу реализующую его программу kgpg.
Для линукса устанавливается через:
sudo apt-get install kgpg
 

Nyash Kun

Местный
Подтвержденный
Сообщения
773
Реакции
1.528
Сделки
1
Для бытовых целей алгоритм RSA и программу реализующую его программу kgpg.
У RSA должна быть большая длина ключа и правильные параметры, иначе он будет уязвимым
 

El Jefe

Consejero
Проверенный сервис
Сообщения
1.483
Реакции
3.942
Рекомендованные длины открытых ключей в битах(из кн. Брюса Шнайера "Прикладная криптография").

Год Частное лицо Корпорация Правительство
1995 768 1280 1536
2000 1024 1280 1536
2005 1280 1536 2048
2010 1280 1536 2048
2015 1536 2048 2048

Долгосрочный прогноз разложения на множители (оттуда же)

Год Длина ключа в битах
1995 1024
2005 2048
2015 4096
2025 8192
2035 16384
2045 32768

Оптимистичные рекомендации Ривеста для длины ключей в битах(оттуда же)

Год Минимальная Средняя Максимальная
1990 398 515 1289
1995 405 542 1399
2000 422 572 1512
2005 439 602 1628
2010 455 631 1754
2015 472 661 1884
2020 489 677 2017
 
Последнее редактирование:

RayZR

Пассажир
Сообщения
8
Реакции
12
Замечательная статья!
Судя по рекомендациям каждые 30 лет относительно безопасная длина ключа удваивается. Интересно что будет к 2050 году, учитывая что кремний уже приближается к своему пределу, а квантовые вычисления остаются пока только хайпом.
 
Сверху Снизу