Использование алгебраических систем в симметричных криптосистемах
Одним из первых среди тех, кто применил, сам того не зная, при зашифровании и расшифровании текстов действия в аддитивной группе классов-вычетов по модулю 26, был император Гай Юлий Цезарь.
Шифр Цезаря, также известный, как шифр сдвига, код Цезаря или сдвиг Цезаря – один из самых простых и наиболее широко известных методов шифрования.
Шифр Цезаря — это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется символом, находящимся на некотором постоянном числе позиций левее или правее его в алфавите. Например, в шифре со сдвигом 3 в русском языке буква А была бы заменена на Г, Б на Д, и так далее.
Если сопоставить каждому символу алфавита его порядковый номер (нумеруя с 0), то шифрование и дешифрование можно выразить формулами модульной арифметики:
y 
( 
где x – символ открытого текста, y – символ шифрованного текста, m – мощность алфавита, b – ключ.
С точки зрения математики шифр Цезаря является частным случаем аффинного шифра. В аффинном шифре каждой букве алфавита, состоящего из m символов, ставится в соответствие число из множества {0,…,m -1}. Затем при помощи модульной арифметики для каждого числа, соответствующего букве исходного алфавита, вычисляется новое число, которое заменит старое в шифротексте. Функция шифрования для каждой буквы следующая:
где m – мощность алфавита, a, b – ключ, причем a должно выбираться таким образом, чтобы m и a были бы взаимно простыми числами. Только в этом случае у элемента a будетчисло, обратное ему по модулю m . В этом случае функция дешифрования имеет следующий вид:
|
|
|
где 
– обратное к числу a по модулю m.
Чтобы ускорить шифрование и расшифрование, можно провести процедуру шифрования для всех букв алфавита и получить таблицу соответствий между буквами исходного сообщения и шифротекста.
Пример 1. Составить таблицу зашифрования для аффинного шифра с ключом a =13, b =7 и зашифровать слово шифр.
Будем использовать русский алфавит, исключив из него три буквы: й, 
, ъ. В таблице сначала для каждой буквы русского алфавита приведено ее численное значение, затем по формуле
для каждого числа найдено соответствующее ему число, которое, в свою очередь, переводится в букву русского языка.
| а | Б | в | г | д | е | Ж | з | и | к | л | М | н | о | П |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 7 | 20 | 3 | 16 | 29 | 12 | 25 | 8 | 21 | 4 | 17 | 0 | 13 | 26 | 9 |
| з | Х | г | с | я | н | Ы | и | ц | д | т | А | о | ь | К |
| р | С | т | у | ф | х | Ц | ч | ш | щ | ы | Ь | э | ю | Я |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
| 22 | 5 | 18 | 1 | 14 | 27 | 10 | 23 | 6 | 19 | 2 | 15 | 28 | 11 | 24 |
| ч | Е | у | б | п | э | П | ш | ж | ф | в | Р | ю | м | Щ |
|
|
|
Тогда для слова шифр шифртекстом будет слово жцпч.
Если взять алфавит с числом символов p , где p – число простое, то кольцо классов вычетов 
будет полем. Это означает, что любой ненулевой элемент a этого поля обратим, то есть может быть взят в качестве ключа.
Так как аффинный шифр является шифром замены, то он обладает всеми уязвимостями этого класса шифров.
В случае шифрования сообщений на русском языке (то есть m = 33) существует 627 нетривиальных аффинных шифров, не учитывая 33 тривиальных шифра Цезаря. Это число легко посчитать, зная, что существует всего 20 чисел взаимно простых с 33 и меньших 33 (а это и есть возможные значения a). Каждому значению могут соответствовать 33 разных дополнительных сдвига (значение b); то есть всего существует 660 возможных ключей. Аналогично, для сообщений на английском языке (то есть m = 26) всего существует 312 возможных ключей. Такое ограниченное количество ключей приводит к тому, что система не является криптостойкой. Основная уязвимость шифра заключается в том, что криптоаналитик может выяснить путем полного перебора соответствие между двумя любыми буквами исходного текста и шифротекста.
|
|
|
ШифрХилла – шифр, похожий на аффинный шифр, но при этом вместо элементов a и b в формуле шифрования используются матрицы A и B. Лестер С. Хилл изобрел этот шифр в 1929, и это был первый шифр, который позволял на практике оперировать более чем с тремя символами одновременно.
Каждой букве алфавита так же, как и в аффинном шифре, сначала сопоставляется число. Для латинского алфавита часто используется простейшая схема: A = 0, B =1, ..., Z = 25, но это не является существенным свойством шифра. Блок из n букв рассматривается как n-мерный вектор и умножается на n × n матрицу по модулю 26, затем к полученному вектору прибавляют матрицу B . (Если в качестве основания модуля используется число большее 26, то можно использовать другую числовую схему для сопоставления буквам чисел и добавить пробелы и знаки пунктуации.) Две матрицы являются ключом шифра. Матрица A должна быть обратима, чтобы была возможна операция расшифрования.
Вот формулы для зашифрования и расшифрования текста:
(для векторов X и Y будем считать, что X Y ( mod m ), еслиу векторов X и Y сравнимы по модулю m соответствующие координаты).
Пример 2. Зашифровать слово шифр шифром Хилла с ключом A = 
, B = 
. Найти ключ для расшифрования этого шифра.
|
|
|
Зададим соответствие между буквами русского языка и элементами кольца классов вычетов по модулю 30 так, как в примере 1. Слово шифр при этом превратится в вектор X = (23, 8, 19, 15).
Умножим матрицу A на матрицу X 
:
Тогда Y = (6,21,29,18). Поэтому шифртекстом является слово жцяу.
Найдем обратную матрицу для матрицы A, это будет матрица A 
= 
Поэтому формула расшифрования следующая:
Заметим, что если длина сообщения не совпадает с размерностью матрицы – ключа, то первые n символов сообщения помещают в первый столбец, следующие n символов сообщения – во второй столбец матрицы и т.д. Если длина сообщения не делится на n , то оставшиеся элементы можно заполнить любыми числами. Затем полученная матрица умножается на матрицу A .
Для того, чтобы можно было расшифровать сообщение, необходимо, чтобы шифрующая матрица была обратимой. Матрица будет иметь обратную в том и только в том случае, матрица является невырожденной. Таких матриц существуют множество, и их число возрастает с возрастанием порядка шифрующей матрицы. Поэтому данный шифр проблематично вскрыть путем перебора всевозможных матриц.
В шифре Хилла в качестве основания модуля обычно выбирают простое число. Например, в более удобном варианте шифра Хилла в русском алфавите берут число символов 29 или 31.
Стандартный шифр Хилла уязвим к атаке по выбранному открытому тексту, потому что он полностью линейный. Криптоаналитик, который перехватит открытый текст вместе с соответствующим шифртекстом, сможет составить систему линейных уравнений, которую обычно не сложно решить. Такого рода расчеты средствами обычных алгоритмов линейной алгебры требуют совсем немного времени.
Дата добавления: 2019-02-12; просмотров: 298; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!