Лясин Д.Н., Саньков С.Г. Методы и средства защиты компьютерной информации

Подождите немного. Документ загружается.

Применение блочного шифра для нужд практического кодирования

информации возможно в одном из четырех основных режимов шифрования (рис.

2.8):

1) режим электронной кодовой книги (Electronic Code Book, ECB);

2) режим сцепления блоков шифра (Cipher Block Changing, CBC);

3) режим обратной связи по шифротексту (Electronic Feedback, CFB);

4) режим обратной связи по выходу (Output Feedback, OFB).

В режиме ECB шифрование/дешифрование i-го блока открытого

текста/шифротекста выполняется независимо от остальных блоков:

), m

Недостатком данного режима шифрования является то, что одинаковые блоки

входного текста будут кодироваться в одинаковые блоки шифротекста, что дает

возможность злоумышленнику, во-первых, делать предположения о характере

информации в открытом тексте, а во-вторых, подменить один или несколько блоков

шифротекста. Достоинством режима можно назвать простоту реализации, а также

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

Режим CBC предполагает следующие алгоритмы шифрации/дешифрации:

i-1

a) режим ECB

б) режим CBC

i-1

i-2

i-1

i-2

в) режим CFB

i-1

г) режим OFB

Рис. 2.8. Режимы шифрования блочных шифров

 c

i-1

), m

)  c

i-1

В режиме CBC каждый блок открытого текста складывается с блоком

шифротекста, полученным на предыдущем этапе. Таким образом, происходит

сцепление блоков друг с другом и независимая манипуляция с каждым из них

невозможна, а одинаковые входные блоки будут давать на выходе разные блоки.

Однако, задача распараллеливания процедуры кодирования в этом режиме

затруднена. Дополнительным параметром процедур шифрования/дешифрования

является параметр c

В режиме CFB также происходит «маскировка» блока открытого текста уже

зашифованными блоками:

 E

i-1

), m

i-1

)  c

По своим возможностям данный режим похож на режим CBC, но если длина

сообщения не кратна размеру блока шифра, то в режиме CBC необходимо

дополнять последний блок дополнительными битами и сообщать на принимающую

сторону истинный размер сообщения, а режим CFB позволяет сформировать

шифротекст того же размера, что и исходное сообщение.

В режиме OFB исходное сообщение вообще не подвергается

криптопреобразованию, оно складывается с шифруемыми на секретном ключе

блоками s

является задаваемым несекретным параметром режима):

 s

, m

 s

, s

i-1

)

В этом режиме, как и в режиме ECB, ошибки, которые могут возникнуть при

передаче шифротекста по каналам связи, локализуются в блоке, не распространяясь

на соседние, причем в режиме OFB ошибочными будут только биты, подвергшиеся

изменению (в ECB изменится весь блок). Это дает возможность злоумышленнику

незаметно для принимающей стороны подменить блок шифротекста. Возможности

распараллеливания процедур шифрации/дешифрации затруднены.

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

Методы криптоанализа совершенствовались наряду с

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

криптоанализа является частотный анализ, который применим для

простых шифров замены. Рассмотрим принцип частотного

криптоанализа на основе шифра Цезаря. В шифре Цезаря каждая

буква исходного сообщения замещается на букву, находящуюся k

символами правее, по модулю, равному количеству букв в

алфавите:

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

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

символа в алфавите. Очевидно, что обратной подстановкой является

(j)=(j+n-k)(mod n)

Частотный анализ использует то свойство зашифрованного текста, что частота

встречаемости символов в нем совпадает с частотой встречаемости

соответствующих символов в открытом тексте. Если же учесть, что частоты

встречаемости различных символов в текстах соответствующего языка

распределены неравномерно (так, например, относительная частота встречаемости

буквы «А» в текстах на русском языке составляет 0.069, а буквы «Ф» 0.003), то,

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

предположить, что символ, наиболее часто встречающийся в шифротексте,

соответствует символу, наиболее часто встречающемуся в текстах на

соответствующем языке, и найти таким образом ключ k. Такой метод криптоанализа

применим только к моноалфавитным криптоалгоритмам, и для его успешной работы

требуются тексты большого размера.

Для современных криптоалгоритмов используются более совершенные

методы криптоанализа: дифференциальный, линейный, силовая атака.

Дифференциальный метод криптоанализа был предложен Э.Бихамом и

А.Шамиром в 1990 г. Дифференциальный криптоанализ представляет собой атаку

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

используется изменение меры несходства двух открытых текстов при их

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

несходства двух двоичных векторов используется расстояние Хэмминга –

количество бит, в которых эти вектора отличаются друг от друга.

Успех попыток вскрытия r-циклического шифра зависит от существования

дифференциалов (r-1)-го цикла c большей долей вероятности. Дифференциал i-го

цикла определяется как пара ( a , b )

такая, что пара различных открытых текстов x,

x* c расстоянием Хэмминга a может привести к паре выходных текстов y, y* после

i-ого цикла, имеющих расстояние Хэмминга b. Вероятность i-циклового

дифференциала ( a ,b )

- это условная вероятность P( D

(i)=b | D

(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

(r-1)= b1 . Для тройки ( D

(r-1), y , y*) находим каждое

возможное значение подключа последнего цикла к(r) . Добавляем его к количеству

появлений каждого такого значения подключа к(r) .

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

станет появляться чаще других. Этот подключ или множество таких подключей

используем в качестве криптографического решения для подключа к(r) .

4. Повторяем пп.1-3 для предпоследнего цикла, при этом значения y(r-1)

вычисляются расшифрованием шифртекстов на найденном подключе последнего

цикла к(r) . Далее действуем аналогично, пока не будут раскрыты ключи всех

циклов шифрования.

Для успешного осуществления дифференциального криптоанализа

необходимо иметь большой набор пар открытый текст/шифротекст (до 2

подобных

пар для атаки на 16 раундов DES). Повышение стойкости шифра к

дифференциальному криптоанализу возможно путем увеличения количества

раундов: для алгоритма DES при 17 раундах шифрования дифференциальный

криптоанализ не эффективнее силовой атаки.

‘ Линейный метод криптоанализа был предложен японским математиком Мацуи

в 1993 г. Метод также является атакой на основе выборочного шифротекста. Метод

использует линейные приближения, предполагающие с определенной вероятностью,

что существует линейная зависимость между некоторыми битами открытого текста,

шифротекста и ключа:

 m

 …  m

 c

 … c

= k

 k

 … k

, (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

бит.

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

Поточные шифры характерны тем, что шифруют информацию по одному биту

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

две обратимые – сумма по модулю 2 и логическое отрицание, то выбор принципа

шифрования очевиден – биты открытого текста должны складываться с битами

ключевой последовательности с помощью операции :

= m

 k

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

= c

 k

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

выполняется:

= c

 m

поэтому криптостойкость поточных шифров полностью зависит от качества

генератора потока ключей. Очевидно, что если поток ключей будет включать в себя

только двоичные нули, то шифротекст будет представлять собой точную копию

открытого текста. Поток ключей поточных шифров принято обозначать греческой

буквой  (гамма), вследствие чего подобные шифры получили название шифров

гаммирования. Большинство современных генераторов гаммы построено на

линейных регистрах сдвига (ЛРС). Он представляет собой (рис.2.9)

последовательность бит, которая на каждом такте шифрования сдвигается вправо на

1 разряд, при этом выход из крайнего правого бита является выходом генератора, а

на вход крайнего левого бита подается значение, вычисляемое как сумма по модулю

2 нескольких разрядов ЛРС. Ключ шифрования поточного шифра заносится в ЛРС

перед началом генерации гаммы.

Рассмотрим работу ЛРС на примере трехразрядного регистра, структура

которого приведена на рис.2.10

Занесем в регистр начальное значение 010 и посмотрим, какие значение

получим на выходе гаммы.

Таблица 2.2

Результат работы генератора гаммы на основе ЛРС

Номер

такта

Значения битов ЛРС Бит

гаммы

2 3

нач.сост

2 3

…



Рис.2.9. Линейный регистр сдвига



Рис.2.10 Линейный регистр сдвига на три разряда

Из таблицы видно, что состояние ЛРС повторяется через 7 тактов (начальное

состояние ЛРС совпадает с его состоянием на 7-м такте). Повтор состояния ЛРС

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

криптостойкость поточных шифров, позволяя криптоаналитику проводить анализ

шифротекстов, полученных кодированием на одной и той же гамме. Поэтому при

проектировании структуры ЛРС встает проблема достижения максимального

периода повтора ЛРС. Для ЛРС длиной n бит максимальный период составляет 2

-1

тактов (состояние, когда все биты равны нулю, недопустимо, поскольку ЛРС любой

структуры не выходит из этого состояния, зацикливаясь в нем). Построение ЛРС

оптимальной структуры с точки зрения периода повторения гаммы имеет четкую

математическую основу в виде теории неприводимых полиномов. Структура ЛРС

описывается многочленом вида:

n-1

n-2

+…+b

n-1

+ b

*x+1,

где b

=0, если i-й бит слева не участвует в обратной связи, и b

=1, если участвует.

ЛРС будет иметь максимально возможный период повторения гаммы, если

описывающий его многочлен не раскладывается на произведение многочленов

меньшей степени.

Основной проблемой ЛРС является их нестойкость к атаке на основе

известного открытого текста. Даже если неизвестна внутренняя структура ЛРС,

криптоаналитик с помощью алгоритма Берлекэмпа-Мэсси по известным 2N битам

открытого текста и соответствующего шифротекста имеет возможность построить

ЛРС, порождающую подобную последовательность. Поэтому современные

поточные шифры строятся на основе нелинейных регистров сдвига (НРС).

Нелинейные регистры сдвига строятся на основе линейных с добавлением в

структуру нелинейных элементов: логического сложения и логического умножения.

Наиболее популярными классами нелинейных регистров сдвига на сегодня

являются фильтрующие, комбинирующие и динамические поточные шифры [6].

Фильтрующие НРС строятся с использованием дополнительной

комбинационной схемы – фильтра – на выходах некоторых бит ЛРС (рис.2.11).

Выход комбинационной схемы и является гаммой.

Комбинирующие НРС также используют комбинационную схему с

нелинейными преобразованиями бит, но на вход этой комбинационной схемы

подаются выходы нескольких ЛРС (рис.2.12).

При проектировании НРС комбинирующего типа необходимо следить, чтобы

комбинационная схема равномерно перемешивала выходы каждого из ЛРС, иначе

может возникнуть ситуация доминирования одного из ЛРС, когда его выход на

подавляющем большинстве тактов совпадает с общим выходом НРС.

Динамические НРС также строятся на основе нескольких ЛРС, но здесь они

вступают друг с другом в отношения «главный-подчиненный» (рис.2.13). В

зависимости от выхода управляющего ЛРС на общий выход НРС подается либо

выход первого, либо второго ЛРС.

ЛРС

…

КС



Рис.2.11. Поточный шифр на основе фильтрующего НРС

ЛРС1

ЛРС2

ЛРСN

…



Рис.2.12. Поточный шифр на основе комбинирующего НРС

В качестве примера поточного шифра, построенного на основе регистров

сдвига, можно привести алгоритм A5, используемый для кодирования в стандарте

GSM. A5 включает 3 ЛРС длиной 19, 22 и 23 бита на выход гаммы подается сумма

по модулю 2 выходов всех регистров. Используется схема динамического НРС,

когда каждый регистр тактируется в зависимости от состояния средних разрядов

всех трех регистров сдвига.

Поточными являются также шифры RC4, SEAL, WAKE [12].

2.5. Асимметричное шифрование

Симметричное шифрование имеет недостатки, которые ограничивают

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

невозможно организовать секретный канал для обмена ключами шифрования между

участниками взаимодействия. Еще одним недостатком симметричных шифров

является необходимость хранения большого количества ключей: для того чтобы в

вычислительной сети могли конфиденциально попарно взаимодействовать N

участников, необходимо наличие в системе N*(N-1)/2 ключей. Эти недостатки

можно устранить, используя алгоритмы асимметричного шифрования. Например,

для асимметричной системы достаточно иметь 2*N пар открытый/закрытый ключ,

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

Управляющий

ЛРС

ЛРС1

ЛРС2



Рис.2.13. Поточный шифр на основе динамического НРС