Министерство науки и высшего образования Российской Федерации

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

«ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ» (ТУСУР)

Кафедра комплексной информационной безопасности электронно-вычислительных систем (КИБЭВС)

АФФИННЫЙ ШИФР

Отчет по индивидуальному домашнему заданию №1 по дисциплине «Криптографические методы защиты информации»

Студент гр. 739-1

Климанов М.Д.

___________16.10.2021

Преподаватель кафедры

КИБЭВС

____Полюга В.А.

__.__.2021

Томск 2021

Содержание

1 Введение 3

2 Ход работы 4

2.1 Шифрование и дешифрование Аффинным шифром 4

2.2 Аффинно рекуррентный шифр 5

2.3 Криптоанализ аффинного шифра 6

2.4 Криптоанализ Аффинно-рекуррентного шифра 8

2.5 Программная реализация Аффинного шифра 9

3 Заключение 10

1 Введение

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

2 Ход работы

2.1 Шифрование и дешифрование Аффинным шифром

Для шифрования было выбрано слово: Назаров. Выберем ключ – a = 5, b = 3. Сопоставим буквы с индексами соответствующим номерам букв в алфавите. По формуле:

(2.1)

где – номер буквы в алфавите,

a и b – ключи шифра.

Пример шифрования слова представлен в таблице 2.1.

Таблица 2.1 – Шифрование Аффинным шифром

Входные данные	П	Р	И	В	Е	Т
Номер буквы	16	17	9	2	5	19
ax+b	83	88	48	13	28	98
(ax+b)mod n	17	22	15	13	28	32
Зашифрованный текст	р	х	о	м	ы	я

Для расшифровки текста требуется определить число, обратное a по модулю, . Для определения потребуется использовать расширенный алгоритм Евклида. В начале алгоритма столбец q пустой, после в следующих раундах в него записывается целое от деления n на a.. В начале алгоритма столбец r пустой, после он принимает значение равное остатку от деления n на a. Столбец y в начале алгоритма также пуст, после чего считается по следующей формуле:

(2.2)

где 𝑦2 и 𝑦1 принимают значение из предыдущего раунда, а 𝑞 берется из нынешнего раунда.

В начале алгоритма в столбец n записывается значение модуля (мощности алфавита), в следующих итерациях столбец принимает значения a из предыдущего раунда. В столбце а изначально хранится число, обратное к которому необходимо найти, в последующих раундах столбец а принимает значения нынешнего столбца r. В первой строке 𝑦2 и𝑦1 принимают значения 0 и 1 соответственно, после 𝑦2 принимает значение 𝑦1 из предыдущего раунда, а 𝑦1 принимает значения y из нынешнего раунда.

Алгоритм выполняется до тех пор, пока 𝑟 ≠0. Ответом является последнее значение 𝑦2. Пример поиска обратного по модулю числа через алгоритм Евклида приведен в таблице 2.2.

q	r	y	n	a
-	-	-	33	5	0	1
6	3	-6	5	3	1	-6
1	2	7	3	2	-6	7
1	1	-13	2	1	7	-13
2	0				-13

2.2 Аффинно рекуррентный шифр

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

Ключи a1,a2,b1,b2 задаются вручную, последующие задаются по формулам:

(2.3)

(2.4)

Таблица с рассчитанными ключами для шифрования представлена ниже.

Таблица 2.4 – Ключи шифрования

№ буквы	1	2	3	4	5	6
a	5	4	20	80	160	160
b	3	2	5	7	12	19
	17	20	10	2	20	7

Таблица 2.5 – Шифрование фамилии аффинно-рекуррентным шифром

Текст	п	р	и	в	е	т
Номер буквы	16	17	9	2	5	19
ax+b	83	70	185	167	835	243242
(ax+b)mod n	17	4	20	2	10	32
Зашифрованный текст	ю	з	ш	т	п	д

Воспользуемся алгоритмом Евклида для поиска обратного числа.

Таблица 2.6 – Обратное число для 2

q	r	y	n	a	y2	y1
-	-	-	33	2	0	1
16	1	-16	2	1	1	-16
2	0	33			-16

Обратное число для числа 2 = -16mod33=17mod33. Остальные числа считаются по аналогии.

Расшифровка текста представлена на таблице 2.7.

Таблица 2.7 – Расшифровка Аффинно рекуррентного шифра

Зашифрованный текст	ю	з	ш	т	п	д	е
Номер буквы	31	8	25	19	16	4	5
	476	0	140	0	-280	-84	-64
mod n	14	0	8	0	17	15	2
Расшифровка	н	а	з	а	р	о	в

2.3 Криптоанализ аффинного шифра

Имеется зашифрованный текст: суоизвфлпш ялац щдр нръжз оъудаавфлрш цзввючулзчуу, эрдръзг тзъзэдаъуоиадяг сряхъугдуаж ламрвфбут, мувздаъзвфлпт, рылрсъажаллпт, ыунниолпт, жрмувфлпт (ла ядздуьлпт), зяултърллпт дрьаэ, эзэ хъзсувр, ср сяеж хрва оъалуг, лр дзэйа срожрйлр у с ьзяду. суоизвфлпш ялац хъуяидядсиаад ср сяат ияврсугт рясаёалуг, ызйа я озэъпдпжу цвзозжу. дрьэу рядзюдяг улыусуыизвфлпжу у ла явухзюдяг, ла уожалгюд ъзожаъз. суоизвфлпш ялац яиёаядсиад с рылрш уо ысит нръж: ужхивфялпш дух у буърэрхрврялпш дух. хъу ужхивфялрж духа суоизвфлрцр ялацз, хрядрърллуа дрьэу хргсвгюдяг с хрвгт оъалуг, эзэ эзхву ырйыг лз врмрсрж ядаэва зсдржрмувг ср съажг рьалф явзмрцр ырйыг. дрьэу жрцид мпдф дажлаа уву ясадваа, ьаж нрл. рлу дзэйа жрцид ужадф ясршядср жаъчздф хр рдыавфлряду уву эзоздфяг эъийзёужуяг с хрва оъалуг. хъу буърэрхрврялрж суоизвфлрж ялаца, дрьэу хргсвгюдяг с суыа цъимрш даэядиъп (хртрйаш лз ди, ьдр суылз лз давасуоръа, аяву сэвюьудф хиядрш эзлзв) я луоэрш зжхвудиырш, яэъпсзюёаш хаъунаъую с хърядъзлядса рмкаэдрс. дрьэу жрцид эзоздфяг эзэ ясадваа, дзэ у дажлаа нрлз. с ъаыэут явиьзгт хрядрърллуа дрьэу эзйидяг ъзолпжу хр чсади.яужхдржп суоизвфлрцр ялацз рмпьлр хргсвгюдяг с даьалуа хряваылут вад с хрыърядэрсрж у юлрбаяэрж сроъзядзт. с рылрж уяяваырсзлуу яъаылуш сроъзяд хргсвалуг яужхдржрс мпв 21 цры, лр яулыърж суоизвфлрцр ялацз жрйад хргсудяг с вюмрж сроъзяда, рмрут хрврс, з дзэйа и вюыаш вюмрш ъзяп. ьдрмп иырядрсаъудфяг, ьдр ьаврсаэ ядъзызад суоизвфлпж ялацрж, и лацр ырвйал мпдф озжаьал эзэ жулужиж рыул ырхрвлудавфлпш яужхдрж, хржужр хрядргллрш ъгму с цвзозт. мпсзюд хаъурып, эрцыз рылз яужхдржздуэз яжалгад ыъицию. озьзядию мрвфлпа ужаюд жлрйаядср яужхдржрс рылрсъажаллр. ярцвзялр хряваылажи эвулуьаяэржи рхуязлую 1100 явиьзас озмрвасзлуг яулыърж суоизвфлрцр ялацз ужаад 2 рялрслпт ярхидядсиюёут озмрвасзлуг: жуцъалф у биж с ибзт.ыулзжуьаяэуа, лахъаъпслпа, эърбаьлпа дрьэу ср сяеж хрва оъалуг (биж с цвзозт / ъгмф с цвзозт / суоизвфлпш ялац / «оаълуядрядф» уормъзйалуг). у, хр эъзшлаш жаъа, рыул ырхрвлудавфлпш яужхдрж: хрявармъзо (хзвулрхяуг) (суоизвфлпа яваып рд рмкаэдрс у ясад рд рдхаьздэрс рмкаэдрс); ияуваллпа щлдрхдуьаяэуа гсвалуг (нрдрхяуг, налржал щлдрхдуьаяэрцр яулацр хрвг, ыаядъиэчуг ядаэврсуылрцр давз, хъуоъзьлра оъалуа, цзвр); ясадрмрголф (нрдрнрмуг);

Проведя частотный анализ, заметим, что самые часто встречающиеся буквы это: р (207 раза), а (155 раз), у (148 раз). На основе полученных данных, предположим, что буква о (15) была зашифрована в букву р (17), а буква е (5) в букву а (0).

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

Рисунок 2.1 – Результат взлома шифра

2.4 Криптоанализ Аффинно-рекуррентного шифра

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

2.5 Программная реализация Аффинного шифра

Пример шифрования и расшифровки программой с помощью Аффинного шифра представлен на рисунках 2.2-2.3.

Рисунок 2.2 – Аффинный шифр, шифрование

Рисунок 2.3 – Аффинный шифр, расшифровка

3 Заключение

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