Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра безопасности информационных систем (БИС)
Отчёт по практической работе №1
По дисциплине
“Криптографические методы защиты информации”
АФФИННЫЙ И АФФИННЫЙ РЕКУРРЕНТНЫЙ ШИФР
Студент гр. 744
П.И. Култаев
Руководитель
К.т.н, доцент
О. О. Евсютин
Томск 2016
Цель
Целью данной работы является реализация программу, кодирующая входную строку, используя Аффинный и Аффинный рекуррентный шифр, а также проведения криптоанализа.
Ход работы
Аффинный шифр
Краткая теория
Аффинный шифр – это частный случай более общего моноалфавитного шифра подстановки.
В аффинном шифре номеру каждой буквы алфавита размера m ставится в соответствие номер из диапазона [0; m-1]. Затем при помощи модульной арифметики для каждого числа, соответствующего букве исходного алфавита, вычисляется новый номер буквы, которая заменит старую в шифртексте.
Функция шифрования:
,
Где – номер получаемой в результате шифрования буквы,
– номер шифруемой буквы;
б, в – ключи шифрования;
m – размер алфавита.
При этом, на ключ накладывается некоторое ограничение: значение ключа a и размерности алфавита m должны быть взаимно простыми.
Функция расшифрования:
,
Где – обратное к б число по модулю m, то есть .
Число б обратимо только в том случае, если оно взаимно простое к числу m. Все обратимые б для латинского алфавита, размер которого равен 26, можно представить в виде списка из 13 чисел:1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.
Пример шифрования с помощью Аффинного шифра
Для шифрования был использован латинский алфавит, состоящий из 26 букв. Попробуем зашифровать и расшифровать слово «master», используя при этом Аффинный шифр. Для примера будем использовать следующие ключи: б=5, в=7.
· Буква m имеет номер 12, тогда зашифрованный номер будет равен (5*12+7) mod 26 = 15, что соответствует букве p
· Буква a имеет номер 0, тогда зашифрованный номер будет равен (5*0+7) mod 26 = 7, что соответствует букве h
· Буква s имеет номер 18, тогда зашифрованный номер будет равен (5*18+7) mod 26 = 19, что соответствует букве t
· Буква t имеет номер 19, тогда зашифрованный номер будет равен (5*19+7) mod 26 = 24, что соответствует букве y
· Буква e имеет номер 4, тогда зашифрованный номер будет равен (5*4+7) mod 26 = 1, что соответствует букве b
· Буква r имеет номер 17, тогда зашифрованный номер будет равен (5*17+7) mod 26 = 14, что соответствует букве o
В результате шифрования получилась строка phtybo
Расшифровывать будет строке, полученную в примере (phtybo)
Для начала, нужно найти . а* по модулю 26 должно давать единицу. Значит, нам подходят результаты 27, 53, 79, 105 и т.д. Т.к. а=5,нам нужно число, заканчивающееся на 5. 105 подходит. 105/5=21, отсюда следует, что =21
Таким образом:
· Буква p имеет номер 15, тогда расшифрованный номер будет равен 21*(15-7) mod 26 = 12, что соответствует букве m
· Буква h имеет номер 7, тогда расшифрованный номер будет равен 21*(7-7) mod 26 = 0, что соответствует букве a
· Буква t имеет номер 19, тогда расшифрованный номер будет равен 21*(19-7) mod 26 = 18, что соответствует букве s
· Буква y имеет номер 24, тогда расшифрованный номер будет равен 21*(24-7) mod 26 = 19, что соответствует букве t
· Буква b имеет номер 1, тогда расшифрованный номер будет равен 21*(1-7) mod 26 = 4, что соответствует букве e
· Буква o имеет номер 14, тогда расшифрованный номер будет равен 21*(14-7) mod 26 = 17, что соответствует букве r
Получилось «master» – Наша начальная строка.
Реализация шифра
Был реализован алгоритм шифрования на языке программирования C#. Программа представляет собой форму с кнопками и полями для заполнения:
Рисунок 1 – Главная форма программы
Кнопками «Аффинный шифр» и «Аффинный рекуррентный шифр» выбирается, какой именно шифр нам нужен с данный момент. В зависимости от выбора, некоторые поля пропадут. «Аффинный шифр» содержит в себе поля для ввода ключей, входной строки, выходной строки, расшифрованной строки и кнопки «Зашифровать» и «Расшифровать».
Рисунок 2. – Пример работы программы
Описание алгоритма работы программы
На вход программы подаются 2 ключа (a и b соответственно), а также входная строка в виде массива символов. Далее идет проверка на корректность ключей. Если ключи корректны, идет проверка, являются ли введенные символы буквами латинского алфавита. Если символ является таковым, производится зашифрование, если нет – символ пропускается. После окончания символов, выводится результат. При расшифровании, программа находит обратный для a ключ и далее аналогично зашифрованию.
Криптоанализ
Так как аффинный шифр является по сути моноалфавитным шифром замены, то он обладает всеми уязвимостями этого класса шифров. Например, для случая использования латинского алфавита из 26 букв, число возможных a равно 13 вариантам. b может принимать 26 различных значений. Значит существует всего 338 возможных вариантов ключей для этого алфавита, что позволяет методом «грубой силы» подобрать ключи.
Также можно применить метод статистического анализа, если текст достаточно большой. Чем больше размер текста, тем лучше и точнее работает этот метод. Метод основан на подсчете встречаемости каждой буквы в шифртексте и сравнении результатов с реальной встречаемостью букв в каким-либо алфавите. Покажу на примере. У нас есть текст, представленный на рисунке 2., зашифрованный Аффинным шифром. Мы не знаем ключей и исходного текста.
Рисунок 3 – шифртекст
Проведем анализ текста для помощью сервиса http://www.abakbot.ru/
Рисунок 4 – Частотный анализ
Также возьмем реальную таблицу частоты использования букв латинского алфавита.
Рисунок 5. – Частота использования английских букв
Мы видим, что в нашем шифртексте чаще всего встречается буква h. А в реальном алфавите чаще всего встречается буква e. Исходя из этого, можно предположить, что буква e зашифровалась как h. Буква e имеет номер 4, а буква h номер 7. Значит a*4+b=7,33,59 и т.д. Перебрав несколько вариантов, доберемся до a =11, b=15. 11*4+15=59. Подставив в программу a = 11 и b=15, получим читаемый английский текст, изображенный на рисунке 6.
Рисунок 6. – Расшифрованный текст
Аффинный рекуррентный шифр
Краткая теория
Аффинный рекуррентный шифр похож на простой Аффинный, но в рекуррентном шифре для каждой буквы, начиная с третьей, ключи составляются новые. Новые ключи рассчитываются по формуле:
; ,
А , , , – исходные ключи шифрования, заданные изначально.
Пример шифрования в помощью Аффинного шифра
Снова зашифруем слово «master», но в этот раз используем рекуррентный шифр. Ключи шифрования , , , .
· Буква m имеет номер 12, тогда зашифрованный номер будет равен (5*12+2) mod 26 = 10, что соответствует букве k
· Буква a имеет номер 0, тогда зашифрованный номер будет равен (7*0+4) mod 26 = 4, что соответствует букве e
Далее ключи будут получаться новые. Например, для третьей буквы a=(5*7)mod26 = 9, b=(2*4)mod26=8. И так далее, для каждой буквы
· Буква s имеет номер 18, тогда зашифрованный номер будет равен (9*18+8) mod 26 = 13, что соответствует букве m
· Буква t имеет номер 19, тогда зашифрованный номер будет равен (11*19+6) mod 26 = 11, что соответствует букве l
· Буква e имеет номер 4, тогда зашифрованный номер будет равен (21*4+18) mod 26 = 22, что соответствует букве w
· Буква r имеет номер 17, тогда зашифрованный номер будет равен (23*17+0) mod 26 = 1, что соответствует букве b
Получили kemlwb
Теперь попробуем это расшифровать и получить исходный текст
27 => = 21;
27 = 105 => = 15;
27 => = 3;
27 = 209 => = 19;
27 = 105 => = 5;
27 = 481 => = 21;
· Буква k имеет номер 10, тогда зашифрованный номер будет равен 21*(10-2) mod 26 = 12, что соответствует букве m
· Буква e имеет номер 4, тогда зашифрованный номер будет равен 15(4-4) mod 26 = 0, что соответствует букве a
· Буква m имеет номер 13, тогда зашифрованный номер будет равен 3*(13-8) mod 26 = 18, что соответствует букве s
· Буква l имеет номер 11, тогда зашифрованный номер будет равен 19*(11-6) mod 26 = 19, что соответствует букве t
· Буква w имеет номер 22, тогда зашифрованный номер будет равен 5*(22-18) mod 26 = 4, что соответствует букве e
· Буква b имеет номер 1, тогда зашифрованный номер будет равен 21*(1-3) mod 26 = 17, что соответствует букве r
Получили «master»
Реализация шифра
Для зашифрования и расшифрования текста Аффинным рекуррентным шифром используется вторая часть формы, показанной ранее.
В зависимости от выбора, некоторые поля пропадут. «Аффинный рекуррентный шифр» содержит в себе поля для ввода ключей, входной строки, выходной строки, расшифрованной строки и кнопки «Зашифровать» и «Расшифровать».
Рисунок 7. – Пример работы программы
Описание алгоритма работы программы
Алгоритм почти аналогичен Аффинному шифру, за исключением того, что вместо двух ключей, задаются четыре первых ключа и два массива для ключей, и после каждого зашифрованного символа, рассчитываются новые ключи.
Криптоанализ
Аффинный рекуррентный шифр уже не получится взломать при помощи частотного анализа, в отличие от аффинного. Это невозможно, потому что одни и те же символы могут шифроваться разными буквами и наоборот. Это происходит из-за смены ключей. Однако, имея ключ, но не имея информации о нем, возможно получение исходного текста путем многократного повторного шифрования. Приведу пример: была зашифрована строка. У нас имеется шифртекст. После многократного повторения шифрования (на 11 итерации) шифртекст превратился в читаемую строку, что и было начальной строкой.
Рисунок 8 – Получение начальной строки
Вывод
В результате выполнения работы был реализован алгоритм аффинного и рекуррентного аффинного шифра на языке С#, а также было произведено ознакомлении с криптоанализом и получены навыки работы с данными шифрами.
аффинный рекуррентный шифр программа
Список использования источников
1. Аффинный шифр [Электронный ресурс] // URL: ru.wikipedia.org/wiki/Аффинный_шифр (Дата обращения 06.11.2016)
2. Частотность букв английского алфавита [Электронный ресурс] // URL: ru.wikipedia.org/wiki/Английский_алфавит (Дата обращения 06.11.2016)
3. Частотный анализ произвольного текста онлайн [Электронный ресурс] // URL: http://www.abakbot.ru/online-5/97-freq-letter (Дата обращения 06.11.2016)
