Создание криптографии с помощью модулярной математики

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

Ключевые слова: криптография, шифр, алгоритм шифрования, модулярная арифметика, шифр Цезаря.

Abstract. This article covers the basics of cryptography, as well as modular arithmetic, which formed the basis of many ciphers. A special place in cryptography takes Caesar cipher, which is also based on the principles of modular arithmetic. Having studied the mechanism for constructing this cipher to encrypt word transcript of which is the reverse process.

Keywords: cryptography, cipher encryption algorithm, modular arithmetic, the Caesar cipher.

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

Криптография – это искусство кодированного письма, которая появилась еще с возникновением письменности.

Основной задачей криптографии является, передать информацию, нуждающуюся в секретности. В таких случаях говорят, что информация содержит тайну или является защищаемой, приватной, конфиденциальной. Для часто встречающихся ситуаций такого типа, существуют специальные понятия, которые представлены в схеме 1[3,с.7].

Схема 1

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

Схема 2

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

Остановимся на работе шифра Цезаря, которая может быть проиллюстрирована теорией, привычной для математики и еще в большой степени для криптографии - модульной арифметикой, иногда называемой часовой арифметикой. Что же такое модульная арифметика и почему она называется часовой? В шифре Цезаря ключи представляют собой число символов, на которое сдвигаются буквы алфавита. При шифровании вместо каждой буквы открытого текста ставится буква, отстоящая от нее правее на число букв задаваемое значением ключа. Расшифровка заключается в смещении каждой буквы левее на число букв, задаваемое тем же значением ключа, которое использовалось при шифровании [1, с.26].

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

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

Первые труды связанные с криптографией были найдены в работах Евклида, которые были тесно связаны с арифметическими операциями на конечных числовых множествах или операциями по модулю, которые являются одним из основ современной теории криптографии. Для примера рассмотрим часы со стрелками и электронные часы. Циферблат стрелочных часов разделен на 12 частей, которые в электронных часах обозначаются, как 0, 1, 2, ,3 ,4 , 5, 6, 7, 8, 9, 10, 11.

В таблице 1 можно видеть, как время на аналоговом циферблате соответствует времени после полудня на экране цифровых часов.

Таблица 1

Допустим, если на часах 16:00, то можем сказать, что время четыре часа вечера. Тот же самый принцип используется и при расчете с углами. Если нам нужно рассчитать угол в 800 градусов, то  записываем, что он равен 80 градусам. При этом вычитаем количество полных оборотов, то есть 800=(2*360)+80, получается, что 80 это остаток от деления 800 на 360, а в математике это записывается следующем образом:

800≡ 80 (mod 360) («800 сравнимо с 80 по модулю 360»).

В случае с часами это будет: 16≡4 (mod 12). Другими словами в общем случае это выглядит так: a≡b(mod m), если остаток от деления a на m равен b, при условии что a, b и m-целые числа [2,c. 27].

Итак, проследим связь между модульной арифметикой и шифром Цезаря. Составим таблицу 2 стандартного алфавита и алфавита со сдвигом на три буквы, добавим титульный ряд из 26 чисел.

Таблица 2

Заметим, что зашифрованная буква под номером x (в стандартном алфавите) стоит на позиции x+3. Поэтому необходимо найти преобразование, которое каждому числу ставит в соответствие число, сдвинутое на три единицы, и взять результат по модулю 26. Получаем, что 3 это и есть ключ нашего шифра. Таким образом, наша функция записывается как:

C(x) = (x+3) (mod 26)

где x –изначальное значение, а C(x)-зашифрованное значение.

Для примера рассмотрим слово TABLE   и зашифруем его.

Буква T стоит на позиции 19, C(19)= 19+3≡22(mod 26), число 22 соответствует букве  W.

Буква A стоит на позиции 0, C(0)= 0+3≡3(mod 26), число 3 соответствует букве  D.

Буква B стоит на позиции 1, C(1)= 1+3≡4(mod 26), число 4 соответствует букве  E.

Буква Lстоит на позиции 11, C(11)= 11+3≡14(mod 26), число 14 соответствует букве  O

Буква E стоит на позиции 4, C(4)= 4+3≡7(mod 26), число 7 соответствует букве  H.

В итоге слово TABLE, зашифрованное с ключом 3, превратится в слово WDEOH.

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

C(x)= (x+k) (mod n), где n- длина алфавита (в английском алфавите) ,

а k- ключ, используемый в данном шифре.

Для расшифровки нужно провести расчеты обратные тем, что использовали при шифровании, то есть:

(x)= (x-k) (mod n).

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

(x)= (x-3) (mod 26).

Получим, что шифр Цезаря является математическим преобразованием в криптографии. Он определяется следующим образом:

где а и b — два целых числа, меньших, чем число (п) букв в алфавите. Наибольший общий делитель (НОД) чисел а и п должен быть равен 1

[НОД (a, n) = 1], потому что иначе получится несколько возможностей для шифрования одной и той же буквы. Ключ шифра определяется парой (а, b). Шифр Цезаря с ключом 3 является, следовательно, аффинным шифром со значениями, а = 1 и                  b = 3.

Обобщенный аффинный шифр имеет более высокий уровень безопасности, чем обычный шифр Цезаря. Почему? Как мы видели, ключом аффинного шифра является пара чисел (а, b). Если сообщение написано с использованием алфавита из 26 букв и зашифровано с помощью аффинного шифра, то и а, и b могут принимать любые значения от 0 до 25. Таким образом, в этой системе шифрования с алфа­витом из 26 букв возможное количество ключей составит 25 х 25 = 625. Заметим, что количество ключей для алфавита из п букв в п раз больше, чем в шифре Цезаря. Это значительное улучшение, но аффинный шифр все еще возможно расшифровать методом перебора всех возможных вариантов [2,c. 32].

К сожалению, шифр Цезаря обладает низкой стойкостью и это не единственный его недостаток, в нем также (в случае русского алфавита) возможны всего 32 различных ключей, один из которых отображает открытый текст в тот же открытый текст.

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

Литература:

1.                  Баричев С.В. Криптография без секретов. – М.: Наука, 2004. –120 с.

2.                  Гомес Ж. Математики, шпионы и хакеры. Кодирование и криптография. – М.: Де Агостини, 2014. – 144 с.

3.                  Медведев Н.В. Теория чисел в криптографии: учеб. пособие. – М.: Изд-во МГТУ им. Н. Э. Баумана, 2011. – 223 с.