Шифри Кардано і Ардженті, з варіацією

Лабораторна робота 1

Шифри Полібія, Цезаря, Тритемія, Віженера

1. Опис методів шифрування

1.1. Шифр на основі квадрату Полібія (ІІ вік до н.е.). Символи алфавіту, який застосовується для представлення повідомлення, розміщуються в виді квадратної таблиці (в загальному випадку така таблиця може бути прямокутною). Шифрування полягає в заміні кожного символу повідомлення впорядкованою парою чисел , де та – номера, відповідно, рядка і стовпця таблиці , на перетині яких розташований символ . Розшифрування основане на послідовному перегляді шифротексту, виділенні чергової пари чисел і її заміні символом , розташованому в таблиці на перетині -го рядку і -го стовпця.

Приклад 1.1. Таблиця 1.1 – варіант квадрату Полібія для російської мови (символ «_» – знак пробілу).

Таблиця 1.1

	А	Б	В	Г	Д	Е	Ж
	З	И	Й	К	Л	М	Н
	О	П	Р	С	Т	У	Ф
	Х	Ц	Ч	Ш	Щ	Ъ	Ы
	Ь	Э	Ю	Я	_	,	;
	:	.	!	?	“	”	-

Зашифруємо за допомогою таблиці 1 фразу

МАТЕМАТИКА_–_ЭТО_“ГИМНАСТИКА”_УМА!

Замінимо кожний символ впорядкованою парою чисел , де та – відповідно, номер рядка і номер стовпця таблиці 1, на перетині яких розташований символ . Отримаємо послідовність чисел:

Розшифруємо тепер шифротекст

2647553634163315273155331112313511162662,

отриманий за допомогою таблиці 1.

Розіб’ємо отриману послідовність на пари чисел:

(26)(47)(55)(36)(34)(16)(33)(15)(27)(31)(55)(33)(11)(12)(31)(35)

(11)(16)(26)(62).

Замінимо кожну пару чисел символом, розташованим в таблиці 1 на перетині -го рядку і -го стовпця. Отримаємо фразу:

МЫ_УСЕРДНО_РАБОТАЕМ!

1.2. Шифр Цезаря (І вік до н.е.). Нехай повідомлення, які передаються, представлені в -літерному алфавіті . Побудуємо матрицю , у якої перший рядок − це символи алфавіту , а другий рядок − це алфавіт , зсунутий циклічно на позицій ліворуч. Таким чином, отримаємо підстановку елементів множини . Позначимо через − символ повідомлення, а через − символ шифротексту. Шифрування полягає в заміні символу його образом у підстановці: . Ключ шифру − кількість позицій зсуву . Для розшифровки необхідно побудувати підстановку , і потім замінити символ шифротексту його прообразом: .

Приклад 1.2. Таблиця 1.2 – це підстановка з зсувом на 3 позиції для російського алфавіту, розглянутого в прикладі 1.

Таблиця 1.2

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

_

,

;

:

.

!

?

“

”

-

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ъ

Ы

Ь

Э

Ю

Я

_

,

;

:

.

!

?

“

”

-

А

Б

В

Зашифруємо за допомогою таблиці 1.2 фразу

МАТЕМАТИКА_–_ЭТО_“ГИМНАСТИКА”_УМА!

Отримаємо шифротекст:

ПГХИПГХЛНГ:В:_ХС:АЖЛПРГФХЛНГБ:ЦПГ”

1.3. Шифр на основі таблиці Тритемія (1518 р.). Нехай повідомлення, які передаються, представлені в -літерному алфавіті . Таблиця Тритемія – це квадратна таблиця розміру , рядки якої занумеровані числами , а стовпці – елементами алфавіту , причому -й рядок таблиці – це алфавіт , зсунутий циклічно на позицій ліворуч. Ясно, що кожна матриця порядку , у якої 1-й рядок – це номера стовпців таблиці , а 2-й рядок – це -й рядок таблиці , визначає деяку перестановку елементів множини , причому, якщо , то перестановки – відмінні.

Шифрування полягає в заміні -го символу повідомлення його образом при перестановці

,

тобто при шифруванні 1-го символу використовується 1-й рядок таблиці , при шифруванні 2-го символу – 2-й рядок таблиці і т.д.

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

Приклад 1.3. Таблиця 1.3 – це таблиця Тритемія для російського алфавіту, розглянутого в прикладі 1.1.

Зашифруємо за допомогою цієї таблиці фразу

МАТЕМАТИКА_–_ЭТО_“ГИМНАСТИКА”_УМА!

Таблиця 1.3

Отримаємо:

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, ,

, .

Таким чином, шифротекст має вид:

НВХЙСЖЩРУКГВГБ;ЮЗПЧЬ;.Ч,Б:?ЬЩФИВ;Ь

Зазначимо, що шифр на основі таблиці Тритемія – це нетривіальне узагальнення шифру Цезаря, в якому для шифрування повідомлень, представлених в -літерному алфавіті , застосовується лише -й рядок таблиці . Ясно також, що таблицю для -літерного алфавіту можна розширити до таблиці розміру . Для цього достатньо взяти в якості рядків таблиці всі можливі перестановок -елементної множини .

1.4. Шифри Віженера (XVI вік). Засновані на таблиці Віженера . В них вперше реалізовано поняття сеансовий ключ, що істотно залежить від повідомлення, яке передається. Таблиця відрізняється від таблиці Тритемія лише тим, що в таблиці рядки (як і стовпці) занумеровані елементами алфавіту . Нехай повідомлення – це послідовність , де . Відправник і адресат заздалегідь домовлялися про пароль, тобто коротку послідовність символів алфавіту . Відомі такі шифри Віженера.

1-й шифр Віженера. При шифруванні формуються послідовності – вихідний текст і – сеансовий ключ. Представимо ці послідовності в виді

,

,

де

,

.

Шифрування вихідного тексту здійснюється у відповідності до алгоритму 1.

Алгоритм 1.

Крок 1. .

Крок 2. , де – символ алфавіту , розташований в таблиці на перетині -го рядка и -го стовпця, .

Крок 3. Якщо , то перехід до кроку 2, інакше – кінець.

Розшифровка шифротексту здійснюється згідно з алгоритмом 2.

Алгоритм 2.

Крок 1. .

Крок 2. В – у стовпці таблиці здійснюється пошук елементу .

Крок 3. , де – номер рядка таблиці , на перетині якого з -м стовпцем розташований елемент , .

Крок 4. Якщо , то перехід до кроку 2, інакше – перехід до кроку 5.

Крок 5. и кінець.

Фінальний відрізок шифротексту представляє собою «підпис» відправником зашифрованої інформації, якщо під «підписом» розуміти зашифрований пароль. Таким чином, в шифрах Віженера вперше закладений механізм автентифікації (тобто розпізнавання автентичності) як користувача, так і інформації. Така автентифікація здійснюється у відповідності до алгоритму 3.

Алгоритм 3.

Крок 1. .

Крок 2. В – у стовпці таблиці здійснюється пошук елементу .

Крок 3. , де – номер рядку таблиці , на перетині якої з -м стовпцем розташований елемент , .

Крок 4. Якщо , то перехід до кроку 2, інакше – перехід до кроку 5.

Крок 5. Якщо , то інформацію прийняти і кінець, інакше, інформацію відкинути і кінець.

Алгоритми 2 і 3 можна об’єднати в один алгоритм, тобто при використанні 1-го шифру Віженера автентифікація здійснюється безпосередньо в процесі розшифрування інформації.

2-й шифр Віженера (або шифр з автоключем). Відрізняється від 1-го шифру Віженера тим, що сеансовий ключ має вид , де – шифротекст, тобто сеансовий ключ формується в процесі шифрування вихідного тексту . Шифрування здійснюється у відповідності до алгоритму 1. Оскільки адресат має пароль (тобто послідовність ), то він має і сеансовий ключ . Розшифровка здійснюється у відповідності до алгоритму 2. Для 2-го шифру Віженера автентифікація здійснюється за допомогою алгоритму 3.

3-й шифр Віженера (або шифр з періодичним ключем). Відрізняється від 1-го шифру Віженера тим, що сеансовий ключ формується з періодичної (потенційно нескінченої) послідовності , згідно з правилом:

( ).

Шифрування здійснюється у відповідності до алгоритму 1. Адресат формує сеансовий ключ з паролю . Розшифровка здійснюється згідно з алгоритмом 2. Для 3-го шифру Віженера автентифікація також здійснюється за алгоритмом 3.

Приклад 1.4. Таблиця 1.4 – це таблиця Віженера для російського алфавіту з лабораторної роботи 1. Зашифруємо з допомогою 1-го шифру Віженера фразу

МАТЕМАТИКА_–_ЭТО_“ГИМНАСТИКА”_УМА!

В якості пароля оберемо слово

ШИФР.

Таким чином, сеансовий ключ має наступний вид

ШИФРМАТЕМАТИКА_–_ЭТО_“ГИМНАСТИКА”_УМА!

Для зручності шифрування, запишемо послідовності і одна під іншою:

Таблиця 1.4

Скористаємось таблицею 1.4. Отримаємо:

, , , , ,

, , , , ,

, , , , ,

, , , , ,

, , , , ,

, , , ,

, , , , ,

, , .

Таким чином, шифротекст має вид:

?Й“ЦЩБ?ОЧБЙЗБЮЙНЧЫЦЧГЛДЪЯЦЛТП,ЮН“ЫВХХЛ

□

2. Завдання на проведення лабораторної роботи

2.1. Зашифрувати довільну фразу довжиною не менше 16 символів за допомогою шифрів

а) Полібія;

б) Цезаря (значення ключа − номер варіанту);

в) Тритемія.

2.2. Розшифрувати фразу за допомогою таблиці Тритемія. Символи L і R позначають, відповідно, “ та ”. Номер фрази для розшифровки − це номер варіанту за .

Таблиця 1.5

№	фраза
	ДТЛЕУЛЛЦЛАУЭЬЬЪВШ_ХФ_МЩОАЬ,!ИФД-ИФЕ!РЬЦЕУР
	РКФ_СЖLЩЧОРЬУОЪШЗЦЫ._!.ШБ:И;Д-L?ЧЗЗЛЖRЛЕЮ.
	СВФОХ;ТР,ЫУЭЯУЫ.ЗЕ?:Ш!НЖ;ДБЬУВМ?ДФЩЙЛКППН.
	ТНСКНСП-ФТЬЮ-ДСЖ:!;.Я,Н_П,БАД_!И,ГБЪЖRКМНЙ
	СЗЫЙЧРЗЗ,ЬДСЖДЩЫЕ,ТК_ЫЪ:LРЭАДЕЗ_Д:?ЕГ--И,СГ

2.3. Зашифрувати довільну фразу довжиною не менше 16 символів за допомогою трьох шифрів Віженера.

2.4. Розшифрувати фразу за допомогою таблиці Віженера. Символи L і R позначають, відповідно, “ та ”.

Таблиця 1.6

№	ключ	фраза	№ шифру
	ПУСТОТА	RЩЭЕГЙГ-ЛПБХЦЕЭ?Й;ИХ.Ь_НХЪИ,Ц!-Е,_ЙЭ!ВИЧПЬ.ПЫЩИФАЮП
	RЩЭЕГЙГОЯ;Ф!,ЖЪХLLМЯLБЦЕАХИЖЗРRГМЦЗЯСИЙГШ.Б_ШЭХБИФ;
	RЩЭЕГЙГ;ЩХ;ЕИГЫЙЧ?_И;_ФЩХЧ?ЙХНИХЕ_БLФЭШЕФЬЫ:;R_?П:Ф
	МИНЕРАЛ	ЬЬЯШЯУМЖ!ТЪСЫГ;ЬБЩЯ,Л;ЭУТ-;,ГТ?ЖЬЙRЦ!Й..ЧRО!ВВЯЧДКСМЪ
	ЬЬЯШЯУМУГ__:ЬПФП;ИХУШЛ;КЙ;ФПШ:ЭПИЭХ:ЬФГЫВМLЭ_Т-ЛЪГД;Ю
	ЬЬЯШЯУМГЩОНУЙОНФОЧГ;ФГЪ_ЖЬБВЩЙ_Л;ЙСЦВД..ПВСЙЩФЭЙЩТЩОС
	РАСТЕНИЕ	ЭЙЯШЦОФRЭЙХИЩГМВ:_-Л,ФУМЭЦLС.ГЯ!В,LRХAГ-;ФЕДУ_ЙКОФФ
	ЭЙЯШЦОФRДКLЫЯСХИЦАЮ!Ц.-Й:;?ГЩХЛГЩАЬ;В!ВИЪМБИГМХО-ХЗ
	ЭЙЯШЦОФR;БЩХОРЙС:_ИЫRЯЫЖЬ;ШЫИ,Х,ЗЙИЖШЬ,КСМ_.ЖЯЫЛЮЙЧ
	ЖИВОТНОЕ	ЧЙФ;ШЫЧЛЗСТЪИЦЛЖВЯТ!.С.ТЮПЭБЧН.ЪЦБЮБИ!RВLЗЫЯ_ИЗИ,
	ЧЙФ;ШЫЧЛОЪХ,Ы!ЪМЪ,LЬТГСЮГAЙБЙИФLЗБЬЮЫ-О;БИ?;АСЬЖЗ
	ЧЙФ;ШЫЧЛLЩГЦХЦСЖТЧФБЙЦЕЧЩЙОЭЙТСОКЙХБ!ГИ,AПЛС;_ЬФМ
	ЧЕЛОВЕК	ЮООЭХУЩМ,УПЪРЧИ;ЬПЩЯ,Л;Э;Т-Е,И_ЪОМ;RЭБХ,НМЭС-ЬЮТД
	ЮООЭХУЩ!ЕЯЮЭЦ:LЖБГЕЙЩЖLУЦЖХ-LП:ЮФЦСГЫХВЖ.ЛЫ;;СЙ,Ц
	ЮООЭХУЩЭRЬПКИУЪЖЧЭФ:Б_RЭ;ГСЩОЧЪЦРЖЭЭС-ЬЮТДЕЛЧЭЕЛХ
	ДУХОВНЫЙ	ЬЩ;ЭЕУRА-ЖУСЛИЛВ:_-Л,СВЬЧБЧХКУТЯЧЮУЖК:.ЭИЧЭЕЕ:R!ЕЗОLШ
	ЬЩ;ЭЕУRАГЪ,_ОЦLМХР_,Е?,ЭЫЬЧМЩАРВГЕКЖРЮ.С!КЛТЯ.НLЙНЩД,
	ЬЩ;ЭЕУRАХФЭСЛРЬХЦЙМЧ.ЬЭЪКЯМЫЦТВШЦRИИ.БДШ?ШЦЪСТЕЯУЦ.АМ
	АНГЕЛ	Е;ЩФОТЕЯЕЪУLШ.ЭРВ_ХЖЦЧ;;МЩЕ;;-ВЕ.ХБ_ЕЦРАОИЕЫЯТЕ
	Е;ЩФОУУ.ЛRЩЯИОВ!ЦЪ;ГЖНАЖПФЬТЩВЙУ!ЬСЛ:,АГШЬАОЗЮ-
	Е;ЩФОО,НR.ЖЩТИСЛДХШММДУФЧОЬХШ-ЯДХИЪВЬИУLНЗДУПЖЩ

Лабораторна робота 2

Шифри Кардано і Ардженті, з варіацією