2.3.4. Криптоанализ блочных шифров

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

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

C_k(j)=(j+k)(mod n), где n - количество букв в алфавите, k- ключ шифрования, j – номер шифруемого символа в алфавите. Очевидно, что обратной подстановкой является C_k(j)=(j+n-k)(mod n)

Частотный анализ использует то свойство зашифрованного текста, что частота встречаемости символов в нем совпадает с частотой встречаемости соответствующих символов в открытом тексте. Если же учесть, что частоты встречаемости различных символов в текстах соответствующего языка распределены неравномерно (так, например, относительная частота встречаемости буквы «А» в текстах на русском языке составляет 0.069, а буквы «Ф» 0.003), то, подсчитав относительную частоту встречаемости букв в шифротексте, можно предположить, что символ, наиболее часто встречающийся в шифротексте, соответствует символу, наиболее часто встречающемуся в текстах на соответствующем языке, и найти таким образом ключ k. Такой метод криптоанализа применим только к моноалфавитным криптоалгоритмам, и для его успешной работы требуются тексты большого размера.

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

Дифференциальный метод криптоанализа был предложен Э.Бихамом и А.Шамиром в 1990 г. Дифференциальный криптоанализ представляет собой атаку на основе выборочного шифротекста. В качестве материала для анализа используется изменение меры несходства двух открытых текстов при их прохождении по основным этапам криптопреобразования. В качестве меры несходства двух двоичных векторов используется расстояние Хэмминга – количество бит, в которых эти вектора отличаются друг от друга.

Успех попыток вскрытия r-циклического шифра зависит от существования дифференциалов (r-1)-го цикла c  большей долей вероятности. Дифференциал i-го цикла определяется как пара ( a , b ) _i такая, что пара различных открытых текстов x, x* c расстоянием Хэмминга a может привести к паре выходных текстов y, y* после i-ого цикла, имеющих расстояние Хэмминга b. Об этом говорит сайт https://intellect.icu . Вероятность i-циклового дифференциала ( a ,b ) _i - это условная вероятность P( D _y(i)=b | D _x(i)= a ) того, что расстояние Хэмминга пары шифртекстов ( y, y*) после i-ого цикла равна b при условии, что пара текстов (x,x*) имеет расстояние a.

Алгоритм дифференциального криптоанализа включает следующие этапы:

1. На предварительном этапе путем многократного шифрования различных текстов накапливаем статистику для множества (r-1)-цикловых дифференциалов (a1, b1)_r-1 ,

 (a2,b2)_r-1 ,.... (as,bs)_r-1 . Упорядочиваем это множество дифференциалов по величине их вероятности.

2. Выбираем открытый текст x произвольным образом и подбираем x* так, чтобы расстояние Хэмминга между x и x* было равно a1 . Тексты x и x* шифруются на подлинном ключе и после r циклов получаем пару шифртекстов y , y*. Предполагаем, что на выходе предпоследнего (r-1)-ого цикла разность шифртекстов равна наиболее вероятной: D_y(r-1)= b1 . Для тройки ( D _y(r-1), y , y*) находим каждое возможное значение подключа последнего цикла к(r) . Добавляем его к количеству появлений каждого такого значения подключа к(r) .

3. Повторяем п.2 до тех пор, пока одно или несколько значений подключа к(r) не станет появляться чаще других. Этот подключ или множество таких подключей используем в качестве криптографического решения для подключа  к(r) .

4. Повторяем пп.1-3 для предпоследнего цикла, при этом значения y(r-1) вычисляются расшифрованием шифртекстов на найденном подключе последнего цикла к(r) . Далее действуем аналогично, пока не будут раскрыты ключи всех циклов шифрования.

         Для успешного осуществления дифференциального криптоанализа необходимо иметь большой набор пар открытый текст/шифротекст (до 2⁴⁷подобных пар для атаки на 16 раундов DES). Повышение стойкости шифра к дифференциальному криптоанализу возможно путем увеличения количества раундов: для алгоритма DES при 17 раундах шифрования дифференциальный криптоанализ не эффективнее силовой атаки.

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

         m_i1 Å m_i2 Å … Å m_ir Å c_j1 Å c_j2 Å …Å c_js = k_t1 Å k_t2 Å …Å k_tn,                         (2.1)

где i1..ir, j1..js, t1..tn – позиции некоторых бит открытого текста m, шифротекста c и ключа k.

Пусть p - вероятность того, что (2.1) выполняется для случайно выбранных m и с. Тогда необходимо, чтобы p ¹ 1/2 и величина | p -1/2 | должна быть как можно больше. Если | p -1/2 | достаточно велика и криптоаналитику известно достаточное число пар открытых и соответствующих зашифрованных текстов, то сумма по модулю 2 бит ключа на соответствующей позиции в правой части (2.1) равна наиболее вероятному значению суммы по модулю 2 соответствующих бит открытых и зашифрованных текстов в левой части. Если p > 1/2, то сумма бит ключа в правой части (2.1) равна нулю, если сумма бит в левой части равна нулю больше, чем для половины пар зашифрованных текстов, и сумма бит ключа в правой части (2.1) равна единице, если сумма бит в левой части равна единице больше, чем для половины текстов . Если p < 1/2 , то наоборот, сумма бит ключа в правой части (2.1) равна нулю, если сумма бит в левой части равна единице больше, чем для половины пар открытых и зашифрованных текстов, и сумма бит ключа в правой части (2.1) равна единице, если сумма бит в левой части равна нулю больше, чем для половины текстов. Таким образом формируется система линейных уравнений, неизвестными в которых являются биты ключа, и задача дальнейшего анализа заключается в поиске решения этой системы. Для увеличения стойкости алгоритма к линейному криптоанализу в его состав вносят нелинейные функции преобразования (например, табличные подстановки).

         Силовая атака на блочные шифры предполагает полный перебор всех возможных ключей шифрования, и ее эффективность зависит от размера ключевого пространства шифра. Так, если ключ шифрования имеет размер 56 бит, то возможно использование 2⁵⁶ ключей, что, как уже отмечалось, не составляет в настоящее время вычислительных трудностей криптоаналитику, особенно если учесть, что задача полного перебора ключей легко поддается распараллеливанию. Так, при проведении фирмой RSA Data Security inc. в сети Internet конкурса по взлому шифра RC5 количество компьютеров, одновременно участвующих в атаке, достигло 4500 единиц, а пиковая производительность – 440 млн. ключей в секунду[11]. По оценкам ведущих специалистов в области криптографии длина ключа шифрования, гарантирующая криптостойкость к силовой атаке, должна составлять от 75 до 90 бит.

 

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

Из статьи мы узнали кратко, но содержательно про криптоанализ блочных шифров