Методы и средства защиты компьютерной информации (стр. 4 )

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

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

Ck(j)=(j+k)(mod n),

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

Ck(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. Вероятность 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)-ого цикла разность шифртекстов равна наиболее вероятной: Dy(r-1)= b1 . Для тройки ( D y(r-1), y , y*) находим каждое возможное значение подключа последнего цикла к(r) . Добавляем его к количеству появлений каждого такого значения подключа к(r) .

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

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

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

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

mi1 Å mi2 Å … Å mir Å cj1 Å cj2 Å …Å cjs = kt1 Å kt2 Å …Å ktn, (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 бит, то возможно использование 256 ключей, что, как уже отмечалось, не составляет в настоящее время вычислительных трудностей криптоаналитику, особенно если учесть, что задача полного перебора ключей легко поддается распараллеливанию. Так, при проведении фирмой RSA Data Security inc. в сети Internet конкурса по взлому шифра RC5 количество компьютеров, одновременно участвующих в атаке, достигло 4500 единиц, а пиковая производительность – 440 млн. ключей в секунду[11]. По оценкам ведущих специалистов в области криптографии длина ключа шифрования, гарантирующая криптостойкость к силовой атаке, должна составлять от 75 до 90 бит.

2.4. Симметричное поточное шифрование

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

ci = mi Å ki.

Дешифрование происходит аналогичным образом:

mi = ci Å ki.

Учитывая свойства операции сложения по модулю 2, можно отметить, что выполняется:

ki = ci Å mi,

поэтому криптостойкость поточных шифров полностью зависит от качества генератора потока ключей. Очевидно, что если поток ключей будет включать в себя только двоичные нули, то шифротекст будет представлять собой точную копию открытого текста. Поток ключей поточных шифров принято обозначать греческой буквой g (гамма), вследствие чего подобные шифры получили название шифров гаммирования. Большинство современных генераторов гаммы построено на линейных регистрах сдвига (ЛРС). Он представляет собой (рис.2.9) последовательность бит, которая на каждом такте шифрования сдвигается вправо на 1 разряд, при этом выход из крайнего правого бита является выходом генератора, а на вход крайнего левого бита подается значение, вычисляемое как сумма по модулю 2 нескольких разрядов ЛРС. Ключ шифрования поточного шифра заносится в ЛРС перед началом генерации гаммы.