Шифры одноалфавитной замены. Шифр Цезаря, квадрат «Полибия».

Вопросы к экзаменам по курсу «Криптография»

Шифры одноалфавитной замены. Шифр Цезаря, квадрат «Полибия».

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

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

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

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

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

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

Вместо буквы в письме записывалась пара чисел: номер строки и номер столбца ячейки, в котором она располагалась. Также как и у шифра Цезаря у данной схемы не счесть модификаций. В связи с тем, что в латинском алфавите 26 букв (а в современном русском- 33), и оба эти числа очень «неудачно» раскладываются на сомножители, модификации либо выбрасывали редко встречающиеся буквы, либо добавляли знаки препинания и пустые элементы, добиваясь прямоугольников и квадратов: 5*5, 5*6, 4*7, 6*6, 5*7.

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

Шифр Плейфейера.

Создан в 1854г.

M	O	N	A	R
C	H	Y	B	D
E	F	G	I/J	K
L	P	Q	S	T
U	V	W	X	Z

Шифрование на основе биграмм. Нельзя, чтобы в одной биграмме повторялась одна буква.

Открытый текст шифруется порциями по две буквы по следующему алгоритму:

Ø Если оказывается, что повторяющиеся буквы открытого текста образуют одну пару для шифрования, то между этими буквами вставляется специальная буква заполнитель- X.

Ø Если буквы открытого текста попадают в одну и ту же строку матрицы, каждая из них заменяется буквой следующей за ней с права в той же строке. Для замены последнего элемента используется 1-ый элемент той же строки.

Ø Если буквы открытого текста попадают в один и тот же столбец, то правило то же, что и для строки.

Ø Если не выполняется ни одно из перечисленных условий, каждая буква из биграммы заменяется буквой, стоящей на пересечении той же строки, что и заменяемая из столбца её пары.

Шифр Хилла.

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

A=0,B=1,C=2,D=3,E=4,F=5,G=6,H=7,I=8,J=9,K=10,L=11,M=12,N=13,O=14,P=15,Q=16,R=17,S=18,T=19,U=20,V=21,W=22,X=23,Y=24,Z=25Ex: M=3

C1=(K11P1+K12P2+K13P3)mod26

C2=(K21P1+K22P2+K23P3)mod26

C3=(K31P1+K32P2+K33P3)mod26

C- символ шифрованного текста.

P- символ открытого текста.

C=KP

K- матрица; K^-1- обратная матрица; K*K^-1=1.

Криптосистема Хилла в общем виде записывается так:

C=E_k(P)=KP; P=D_k(C)=K^-1C=KK^-1P=P.

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

Нелинейные поточные шифры

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

Фильтрующие шифры имеют, пожалуй, наиболее простую структуру из нелинейных поточных шифров. Они строятся на базе одного ЛРС созданием от его ячеек дополнительных отводов, никак не связанных с отводами обратной связи. Значения, получаемые по этим отводам, смешиваются на основе какой-нибудь нелинейной функции- фильтра. Бит-результат данной функции и подается на выход схемы как очередной бит гаммы.

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

ЛРС- самые простые схемы, которые используются для построения поточных шифров. ЛРС состоят из нескольких ячеек памяти, в каждую из которых может быть занесён бит информации. Совокупность бит, которые находятся в данное время в РС- его состояние.

Алгоритм такта:

Ø первый бит из последовательности поступает на выход РЛС- очередная гамма;

Ø содержимое всех промежуточных ячеек памяти сдвигается на одну позицию вправо;

Ø в пустую ячейку памяти, которая появилась в результате сдвига у левого края помещается бит, который вычисляется как операция XOR над значением из ячеек ЛРС с определенным номером.

Число бит, охваченных операцией сдвига- разрядность.

Перед использованием ЛРС в ячейках побитно помещают ключ.

Динамический поточный шифр.

Динамические шифры строятся также на базе нескольких ЛРС, но объединяют их не на равноправных условиях, а по схеме «начальник-подчиненный». Так, например, бит, порождаемый управляющим регистром, определяет бит, какого из подчиненных ЛРС (первого или второго) будет подан на выход всего алгоритма. Бит от противоположного выбранному регистра просто отбрасывается.

По другой схеме, если на очередном своем шаге управляющий ЛРС генерирует “1”, то бит подчиненного ЛРС, полученный на этом же шаге, поступает на выход системы, а если же управляющий ЛРС выдал “0”, то бит подчиненного регистра просто отбрасывается. Разумеется, возможны и сложные схемы взаимодействия ЛРС и их комбинации с уже описанными методами.

При правильном построении закона объединения нескольких ЛРС как в комбинирующих, так и в динамических шифрах период результирующей последовательности будет равен произведению периодов или полупериодов каждого отдельно взятого ЛРС (в зависимости от схемы их объединения). Единственным необходимым условием для этого является то, чтобы разрядности всех ЛРС были попарно взаимно просты, т.е. не имели общих делителей кроме единицы. Чаще всего разрядности всех ЛРС, входящих в общий блок, выбираются как простые числа из подходящего диапазона.

Алгоритм TandemDM.

Алгоритм MD5.

DES: расширение ключа.

Расширение ключа (создание ключей раунда) производится в DES по следующей схеме. На основе 56 значащих бит из ключа на начальном этапе создаются два 28-битных вектора С0 и D0 путем выбора бит из ключа в определенной последовательности.

Для выбора 48 бит ключа i–го раунда, получившиеся после циклических сдвигов вектора СiDi объединяются, и из 56 бит получившегося массива отбираются 48 по закону.

По-настоящему заставили DES уйти с рынка конкурентно-способных блочных шифров две причины: ориентация на аппаратную реализацию и слишком малый размер ключа.

ТЕА: расширение ключа

Алгоритм использует 128 битный ключ, который превращается в ключи раунда по очень простой схеме. Ключ разбивается на четыре 32-разрядных машинных слова К0, К1, К2, К3. Во всех четных (считая с 0) раундах в качестве 64-битного ключа раунда используется пара (К0, К1) в нечетных- пара (К2, К3). В общепринятой схеме номер раунда обозначается переменной i; раундов- r, компоненты ключа раунда- как массив k[i] (он использует сквозную нумерацию по машинным словам- в нулевом раунде используются k[0] и k[1], в первом- k[2] и k[3] и т.д.). В таких обозначениях общая формула создания 128 компонент материала ключа для ТЕА выглядит следующим образом: k[i] =К(i mod 4)

IDEA: расширение ключа

Получение из 128-битного ключа материала ключа в IDEA предельно просто. Первые 8 16-битных компонент k[0]...k[7] материала ключа получаются непосредственно разбиением 128 бит ключа на блоки без каких-либо преобразований. Затем 6 раз повторяется следуюшая операция: ключ сдвигается циклически влево на 25 бит и очередные 8 компонент получаются таким же разбиением уже сдвйнутого ключа на 16-битные блоки.

В псевдокоде:

k[0]...k[7]=key

key=key ROL 25

k[8]...k[15]=key

key=key ROL 25

. . .

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

Цели и суловия конкурса

Конкурс АЕS (Advanced Encrypton Standart)- “улучшенный стандарт шифрования” и был проведен под эгидой Национального Институга Стандартизации и Техники (National Institute of Standart- NIST) в 1997-2000 годах.

Требования к новому стандарту были чрезвычайно просты:

Ø шифр должен быть блочным;

Ø шифр должен иметь длину блока, равную 128 битам;

Ø шифр должен поддерживать ключи длинной 128, 192, 256 бит.

NIST представил общественности документ, в котором сравнивались все 15 претендентов и были объявлены 5 финалистов, прошедших во второй этап конкурса. Все критерии, по которым производилось сравнение алгоритмов, были разбиты сотрудниками Института на категории: криптографические и практические характеристики.

Среди наиболее важных криптографических характеристик специалисты NIST указывали:

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

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

Ø отсугствие слабых ключей;

Ø стойкость к криптоатакам, специфичным для применяемых в шифе схем и криптоопераций;

Ø отсутствие корреляций между данными или ключом и временем, требуемым на операции шифрования/дешифрования;

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

Ø отсутствие необоснованно сложных преобразований и “необъяснимых” констант (что дает некоторый шанс исключить недокументированные свойства шифра, известные только разработчикам);

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

К наиболее важным практическим аспектам жюри отнесло:

Ø оптимизацию по скорости выполнения кода (в первую очередь, на 32-, 8- и 16-разрядных архитектурах ЭВМ);

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

Ø возможность оптимизации по размеру кода (для хранения в ПЗУ «слабых» микросхем и в других запоминающих устройствах с ограниченными ресурсами);

Ø возможность распараллеливания кода (естественно без потерь в криптостойкости);

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

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

Ø характер зависимости скорости работы алгоритма от размера используемого ключа (128, 192 и 256 бит).

Вопросы к экзаменам по курсу «Криптография»

Шифры одноалфавитной замены. Шифр Цезаря, квадрат «Полибия».

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

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

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

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

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

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

Вместо буквы в письме записывалась пара чисел: номер строки и номер столбца ячейки, в котором она располагалась. Также как и у шифра Цезаря у данной схемы не счесть модификаций. В связи с тем, что в латинском алфавите 26 букв (а в современном русском- 33), и оба эти числа очень «неудачно» раскладываются на сомножители, модификации либо выбрасывали редко встречающиеся буквы, либо добавляли знаки препинания и пустые элементы, добиваясь прямоугольников и квадратов: 5*5, 5*6, 4*7, 6*6, 5*7.

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