Використання модулярної арифметики в алгоритмах криптографії

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ЗАПОРІЗЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

МАТЕМАТИЧНИЙ ФАКУЛЬТЕТ

Кафедра загальної математики

КВАЛІФІКАЦІЙНА РОБОТА БАКАЛАВРА

на тему: «ВИКОРИСТАННЯ МОДУЛЯРНОЇ АРИФМЕТИКИ В АЛГОРИТМАХ КРИПТОГРАФІЇ»

Виконала: студентка	4	курсу,	групи	4215

напряму підготовки	6.040201 математика
	(шифр і назва напряму підготовки)
В.І. Мерзлікіна
(ініціали та прізвище)

Керівник	завідувач кафедри загальної математики,
	доцент, к.ф.-м.н. Зіновєєв І.В.
	(посада, вчене звання, науковий ступінь, прізвище та ініціали)
Рецензент	доцент кафедри програмної інженерії, доцент, к.т.н., Мухін В. В.
	(посада, вчене звання, науковий ступінь, прізвище та ініціали)

Запоріжжя - 2019



ЗАВДАННЯ

Тема роботи	Використання модулярної арифметики в алгоритмах
	криптографії
керівник роботи	Зіновєєв Ігор Валерійович, к.ф.-м.н., доцент
	(прізвище, ім'я та по-батькові, науковий ступінь, вчене звання)
затвердженні наказом ЗНУ від « 11 »	12 2018 р. № 1805-с
Строк подання студентом роботи	27. 05. 2019 р.
Вихідні дані до роботи	Постановка задачі
	Перелік літератури.
4. Зміст розрахунково-пояснювальної записки (перелік питань, які потрібно розробити)
Постановка задачі.
Основні теоретичні відомості.
Розробка першого розділу.
Розробка другого розділу.
5. Перелік графічного матеріалу (з точним значенням обов'язкових креслень)	__________
ілюстрації до тексту

6. Консультанти розділів роботи

Розділ	Прізвище, ініціали та посада консультанта	Підпис, дата
		Завдання видав	Завдання прийняв
7. Дата видачі завдання	11. 12. 2018 р.

КАЛЕНДАРНИЙ ПЛАН

№	Назва етапів кваліфікаційної роботи	Строк виконання етапів роботи	Примітка
1.	Розробка плану роботи.	12.12.2018 - 18.12. 2018
2.	Збір вихідних даних.	18. 12.2018- 03. 01.2019
3.	Обробка методичних та теоретичних	03.01.2019 - 15. 01. 2019
	джерел.
4.	Розробка першого розділу.	15.02.2019 - 07. 03. 2019
5.	Розробка другого розділу.	07. 03. 2019 - 05. 04. 2019
6.	Оформлення і нормоконтроль	05. 04. 2019 - 16. 05. 2019
	кваліфікаційної роботи.
7.	Захист кваліфікаційної роботи.	10. 06. 2019 - 15. 06. 2019

Студент			В. І. Мерзлікіна

(підпис)(ініціали та прізвище)

Керівник роботи			І. В. Зіновєєв

(підпис) (ініціали та прізвище)

Нормоконтроль пройдено

Нормоконтролер			О. Г. Спиця

(підпис) (ініціали та прізвище)

РЕФЕРАТ

Кваліфікаційна робота бакалавра «Використання модулярної арифметики в алгоритмах криптографії»: 56 с., 1 рис., 1 табл., 19 джерел, 2 додатків.

ДЕШИФРУВАННЯ, ДИСКОВІ ШИФРИ ЗАМІНИ, КРИПТОГРАФІЯ, КРИПТОСИСТЕМА ДІФФІ-ХЕЛЛМАНА, КРИПТОСИСТЕМА ЕЛЬ-ГАМАЛЯ, КРИПТОСИСТЕМА RSA, МОДУЛЯРНА АРИФМЕТИКА, ПРОТОКОЛ ДІФФІ-ХЕЛЛМАНА, ПРОТОКОЛ ФІАТА-ШАМІРА, СИСТЕМА РАБІНА, ТАБЛИЧНЕ ГАМУВАННЯ, ШИФРИ ГАМУВАННЯ, ШИФРИ ЗАМІНИ, ШИФР ЦЕЗАРЯ.

Об'єкт дослідження -алгоритми на основі модулярної арифметики.

Мета роботи: дослідити основні поняття криптографії, модулярної арифметики; дослідити класичні шифри криптографії, в алгоритмах яких використовуєтьсямодулярна арифметика; дослідити сучасні алгоритми криптографії з використанням модулярної арифметики; навести та розв'язати приклади з застосуванням конкретних алгоритмів з використанням модулярної арифметики.

Методи дослідження - аналіз, порівняння, практичний.

У кваліфікаційній роботі розглянуто основні поняття з криптографії та модулярної арифметики. Досліджено класичні шифри криптографії, серед яких виявлено шифри, алгоритми яких будуються на основі модулярної арифметики.Розглянуто сучасні алгоритми криптографії, з використанням модулярної арифметики. Наведено приклади використання модулярних алгоритмів до шифрування та дешифрування.



SUMMARY

Bachelor's qualifying paper «Using of the Modular Arithmetic in Cryptography Algorithms»: 56 pages, 1 figures, 1 tables, 19 references, 2 supplements.

DECLINEING, DRIVE SHIFT REPLACEMENT, CRYPTOGRAPHY, DIFFIE-HELLMAN'S CRYPTOSYSTEM, EL-GAMAL'SCRYPTOSYSTEM, RSA CRYPTOSYSTEM, MODULAR ARITHMETIC, DIFFIE-HELLMAN`SPROTOCOL, FIATE SHAMIR`S PROTOCOL, RABIN'S SYSTEM, TABLE GAMMING, CIPHERS OF GAMMING, REPLACEMENT CIPHERS, CAESAR'S CIPHER.

The object of the study is algorithms based on modular arithmetic.

The aim of the study is to study the basic concepts of cryptography, modular arithmetic; to study the classic cryptography ciphers in algorithms which use modular arithmetic; to study modern algorithms of cryptography, which use modular arithmetic; to give and to solve examples with application the concrete algorithm with modular arithmetic;

The methods of research are analysis, comparison and practical.

In qualifying work basic concepts are considered from cryptography and modular arithmetic. The classic codes of cryptography, among that codes the algorithms of that are built on the basis of модулярної arithmetic are educed, are investigational. The modern algorithms of cryptography are considered, with the use of modular arithmetic. Examples of the use of modular algorithms are made to enciphering and decoding.



ЗМІСТ

ВСТУП

1. ОСНОВНІ ПОНЯТТЯ КРИПТОГРАФІЇ ТА МОДУЛЯРНОЇ АРИФМЕТИКИ

1.1 Означення та терміни

1.2 Історія виникнення і розвитку криптографії. Класичні шифри

1.3 Багатоалфавітні шифри заміни

1.4 Дискові багатоалфавітні шифри заміни

1.5 Шифри гамування. Табличне гамування

2. СУЧАСНІ АЛГОРИТМИ КРИПТОГРАФІЇ

2.1 Криптосистема Діффі-Хеллмана

2.2 Протокол Діффі-Хеллмана

2.3 Протокол Фіата-Шаміра

2.4 Криптосистема Ель-Гамаля (навчальна)

2.5 Система Рабіна з використанням модулярної арифметики

2.6 Криптосистема RSA (навчальний варіант)

ВИСНОВКИ

ПЕРЕЛІК ПОСИЛАНЬ

ДОДАТОК А

ДОДАТОК Б

ВСТУП

Захист інформації перетворюється сьогодні на одну з найактуальніших задач внаслідок надзвичайно широкого розповсюдження як власне різноманітних систем обробки інформації, так і розширення локальних та глобальних комп'ютерних мереж, якими передаються величезні об'єми інформації державного, військового, комерційного, приватного характеру, власники якої часто були б категорично проти ознайомлення з нею сторонніх осіб. Надійні методи захисту від таких загроз надає криптографія.

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

Серед алгоритмів шифрування важливу роль відіграють алгоритми, що побудовані на основі модулярної арифметики. Саме вони створюють складну криптосистему, на злам якої витрачається багато часу.



1. ОСНОВНІ ПОНЯТТЯ КРИПТОГРАФІЇ ТА МОДУЛЯРНОЇ АРИФМЕТИКИ

1.1 Означення та терміни

Мета нашого дослідження - дослідити використання модулярної арифметики в алгоритмах криптографії. Тому виникає необхідність дати визначення основним поняттям криптографії, для того щоб надалі користуватися ними. Будемо користуватися означеннями, які наведено у підручниках[1, 2, 3, 4] та у криптографічному словнику [5].

Дамо визначення криптографії як науки:

Означення 1.1 Криптологія (математична криптографія) - галузь криптографії, математики і математичної кібернетики, яка вивчає математичні моделі криптографічних систем.

Означення 1.2Криптографія- область наукових, прикладних, інженерно-технічних досліджень та практичної діяльності, яка пов'язана з розробкою методів криптографічного захисту інформації від загроз зі сторони противника або порушника, а також аналізом і обґрунтуванням їх криптографічної стійкості. Основними задачами криптографії є забезпечення конфіденційності, цілісності, аутентифікації.

Означення 1.3 Цілісність - відсутність змін у інформації, яку передають або зберігають у порівнянні з її вихідним записом. Необхідною умовою дотримання цілісності є захист повідомлення від навмисної або випадкової несанкціонованої модифікації або знищення.

Означення 1.4 Аутентифікація - встановлення (перевірка та підтвердження) справжності різних аспектів інформаційної взаємодії: змісту та джерела повідомлень, що передаються, сеансу зв'язку, часу взаємодії.

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

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

Означення 1.7Шифртекст - текст, який отримано у результаті зашифровування відкритого тексту.

Означення 1.8Зашифровування - процес перетворення відкритого повідомлення у шифроване повідомлення за допомогою ін'єктивної функції, що залежить від ключа з ключової множини (криптосистеми).

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

Означення 1.10 Криптограма - текст, який зашифровано.

Означення 1.11 Криптостійкість - характеристика шифру, яка визначає його стійкість до розшифровування. Найчастіше криптостійкість вимірюється кількістю операцій, які необхідні для перебору усіх можливих ключей, або інтервалом часу, необхідним для розшифровування.

Означення 1.12Ключ - елемент (параметр), який змінюється і кожному значенню якого однозначно відповідає одне з відображень, що реалізується криптосистемою. Усі можливі значення ключа це ключова множина криптосистеми. Ключі можуть бути зіставними, тобто містити декілька частин, які забезпечують різні функції криптосистеми.

Означення 1.13Відкритий ключ - несекретний ключ асиметричної шифрсистеми.

Означення 1.14Секретний ключ - ключ, який зберігається у таємниці від осіб, які не мають допуску до ключів даної симетричної шифрсистеми або до використання деяких функцій даної шифрсистеми.

Означення 1.15Криптографічна система - система забезпечення безпеки інформації криптографічними методами у сенсі конфіденційності, цілісності, аутентифікації, неможливості відмови та невідстеження.

Існує декілька видів криптосистем, дамо визначення асиметричній та симетричній криптосистемам:

Означення 1.16Асиметрична шифрсистема - система шифрування, у якій асиметричним способом використовуються ключі двох видів - ключі відкриті та секретні.

Означення 1.17Симетрична шифрсистема - система шифрування, у якій симетричним способом використовуються секретні ключі зашифровування та ключі розшифровування. В такій системі ключі зашифровування та розшифровування у більшості випадків співпадають, а у окремих випадках один ключ легко визначається по іншому ключу.

Означення 1.18Алгоритм шифрування -криптографічний алгоритм, який реалізує функцію шифрування.

Означення 1.19Функція шифрування - функція, яка описує процес зашифровування та здійснює відкрите відображення послідовностей блоків тексту (повідомлень), яке залежить від ключа, у послідовності блоків тексту (повідомлень) шифрованого.

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

Означення 1.21Симетричні криптоалгоритми - алгоритми для шифрування і дешифрування яких використовується один і той же блок інформації (ключ).

Означення 1.22Асиметричні криптоалгоритми - алгоритми такі, що для шифрування повідомлення використовується один (відкритий) ключ, відомий усім бажаючим, а для дешифрування -інший (закритий), який існує тільки в одержувача.

В залежності від характеру впливу на інформацію алгоритми підрозділяються на:

Означення 1.23Перестановочні алгоритми - блокиінформації не змінюються самі по собі, але змінюється їх порядок проходження, що робить інформацію недоступною сторонньому спостерігачеві.

Означення 1.24Підстановочні алгоритми -алгоритми, де самі блоки інформації змінюються за законами криптоалгоритму. Переважна більшість сучасних алгоритмів належить цій групі

Розглянемо основні поняття модулярної арифметики, а саме теорії чисел для подальшого застосування алгоритмів на основі модулярної арифметики в криптографії та криптоаналізі. Для цього звернемося до підручників [6, 7], у яких наведені означення та формули з теорії чисел.

Означення 1.25Модулярна арифметика -це системаарифметикицілих чисел, в якій числа «обертаються навколо» деякого значення - модуля.

Модулярна арифметика пов'язаназ залишком від діленняцілих чисел на певне заданенатуральне число. Фактично в ній розглядаються класи еквівалентності певного натурального числа.

У сучасному вигляді модулярна арифметика була розвинута Карлом Фрідріхом Гаусом(1777-1855р.р.) -німецьким математиком.

Означення 1.26Два цілих числа називаються рівними за модулем , якщо при діленні на ціле число на вони мають однаковий залишок. Рівність чисел і за модулем записують так:

Еквівалентні означення:

а) різницяділиться нанаціло. Тобто де- якесь ціле число;

б) число  може бути записано у вигляді ,де- якесь ціле число.

Наприклад:

а) Справді, і 11 очевидно ділиться на 11;

б) Маємо і ділиться на націло.

Властивості, що виконуються для відношення рівності, виконуються також для рівності за модулем. Якщо тоді

З визначення рівності за модулем випливають такі властивості:

а) рефлексивність: ;

б) симетричність: ;

в) транзитивність:

Тобто відношення рівності за модулем є відношенням еквівалентності на множині цілих чисел . Тоді розбивається на класи еквівалентності.

Клас еквівалентності відношення рівності за модулемдо якогоналежить числопозначається. Так як, то додати , теж саме, що і додати 0. Тому клас числа

Множина класів рівності за модулем позначається і за означенням це:

Коли , має елементів, і може бути записано:

Для цих класів можна задати операції додавання, віднімання, множення. Таким чином є комутативним кільцем.

Деякий елемент має обернений елемент тоді і лише тоді коли і є взаємно простими числами. Справді, якщо і є взаємно простими, то тоді існують такі, що Звідси:

Навпаки, якщо для деякого , то для деякого , враховуючи взаємну простоту mі n. Відповідно, якщо просте число, то є полем.

Розглянемо розв'язування порівнянь першого степеню над полем .Рівняння записується у вигляді

(1.1)

Знайти розв'язок (1.1), тобто знайти всі значення , які задовольняють даному рівнянню.

Розв'язок (1.1) можна подати за допомогою формули

(1.2)

якщо , (найбільший спільний дільник чисел ) тобто взаємно прості числа.

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

Інше порівняння має два розв'язки

Справедлива мала теорема Ферма, яка стверджує що якщо - просте число та НСД, то

Узагальнення малої теореми Ферма, отримане Ейлером, стверджує що якщо , то З урахуванням наведених вище фактів отримаємо, що найбільше просте значення

Алгоритм Евкліда знаходження найбільшого спільного дільника. Найбільше ціле число, що ділить одночасно цілі числа і , називається їх найбільшим дільником і позначається або просто . Якщо , то і називаються взаємно простими числами.

Алгоритм Евкліда знаходження найбільшого спільного дільника двох цілих чисел полягає у зведенні наступної послідовності операцій ділення з остачею:

де цілі числа, - неповне часне, - остача від ділення числа на число .

Коректне завершення алгоритму гарантується тим, що остачі від ділення створюють строго спадну послідовність натуральних чисел. З наведених рівностей: Тому найбільший дільник чисел співпадає з

Як наслідок з алгоритму Евкліда, можна отримати ствердження, що найбільший дільник цілих чисел можу бути представлен у виді лінійної комбінації цих чисел, тобто існують цілі числа і такі, що справедлива рівність

Розглянемо розв'язування порівнянь другого степеню над полем .З порівнянь степеню будемо розглядати тільки найпростіші, а саме - двочлені порівняння:

(1.3)

Якщо порівняння (1.3) має розв'язок, тоді називається лишком степеню за модулем . У протилежному випадку називається нелишкомстепеняза модулем . Зокрема, при лишки або не лишки називаються квадратичними, при - кубічними , при -біквадратичними .

Розглянемо конкретний випадок, коли і в першу чергу розглянемо двочлені порівняння другого степеню за простим непарним модулем :

(1.4)

Якщо - квадратичний лишок за модулем, то порівняння (1.4) має два розв'язків.

Дійсно, якщо - квадратичний лишок, то порівняння (1.4) має, принаймні, один розв'язок . Але тоді, з огляду на теж саме порівняння має і другий розв'язок Цей другий розв'язок відрізняється від першого, так як з ми мали б що неможливе, з огляду на

Вказаними двома розв'язками вичерпуються всі розв'язки (1.4), так як останнє, будучи порівнянням другого степеню, більш ніж два розв'язки мати не може.

Приведена система лишків за модулем складається зквадратичних лишків, які порівнюються з числами

(1.5)



і квадратичних лишків.

Дійсно, серед лишків наведеної системи за модулем квадратичними лишками є ті, і тільки ті, які можна порівняти з квадратами чисел.

(1.6)

тобто з числами (1.5). При цьому числа (1.5) за модулем не можна порівняти, так як з випливало б, що порівнянню всупереч

Перейдемо до лінійних систем порівнянь. Для знаходження розв'язку такої системи звернемося докитайської теореми про залишки - один з основних результатів елементарної теорії чисел, отриманий у Iст. китайським математиком Сун Це. Використовуючи позначення модулярної арифметики її можна сформулювати наступним чином.

Нехай попарно взаємно прості числа. Тоді для цілих чисел порівняння:

мають в інтервалі єдиний спільний розв'язок виду:

де а 

Китайська теорема про залишки стверджує, що кільце лишків за модулем добутку кількох попарно взаємно простих чисел є прямим (декартовим) добутком відповідних множникам лишків.

1.2 Історія виникнення і розвитку криптографії. Класичні шифри

Будемо досліджувати історію криптографії звернувшись до [8, 9, 10].

Криптографія почала розвиватися 4 тис. років назад. Вже в історичних документах древньої цивілізації - Індії, Єгипті, Китаї, Месопотамії -є довідки про системи та способи створення шифрувального листа. Періоди становлення криптографії можна поділити на чотири основних. I період (3 тис. р. до н. е.) - моноалфавітні шифри, тобто шифри, де одна літера алфавіту замінюється на іншу. II період (з IX ст. на Ближньому Сході та з XV ст. у Європі до початку XX ст.) - період поліалфавітних шифрів, тобто шифрів простої заміни, де застосовується цикл моноалфавітних шифрів до зазначеної кількості літер зашифрованого тексту. III період (початок XX ст. до середини XX ст.) - період створення електротехнічних засобів до шифрувального апарату. IV період (з середини XX ст. до 70-х років XX ст.) - період застосування математичної концепції до криптографії, тобто з'являються математичні означення кількості інформації, передачі даних, ентропії, функції шифрування і тому подібне.

За ці періоди криптографія зазнала великих змін, за допомогою яких можна виділити способи завдання шифрів: шифр заміни(підстановки), перестановки, аналітичне перетворення, гамування і комбіновані шифри.

Великі внески в історію криптографії зробили багато відомих особистостей. Розглянемо декілька класичних шифрів кожного періоду криптографії. Наприклад, перші відомості про використання шифру у воєнній справі пов'язані з ім'ям спартанського полководця Лисандра (шифр «cцитала»). Це був жезл циліндричної форми, який обгортала стрічка з пергаменту. Вздовж осі циліндра на пергаменті записувався текст, який зашифровувався. Такий шифр здійснював перестановку літер повідомлення. Ключом цього шифру був діаметр cцитали.

Грецький письменник Полібій використовував систему сигналізації, яка була розповсюджена як метод шифрування. Цей метод шифрування представляє собою, квадрат, який поділено на клітинок (застосовується латинський алфавіт), у кожну клітинку записуються всі літери алфавіту, при цьому літери I, J не відрізняються, тобто I=J, приклад таблиці наведено нижче. Він записував літери алфавіту у квадратну таблицю і замінював їх координатами: парами чисел , де -номер рядку, а -номер стовпця.

Ускладнений варіант шифру квадрат Полібія полягає у тому, що запис літер у квадраті виконується у довільному порядку і цей довільний порядок і є ключем. Але такий порядок складно запам'ятати, через це користувачу шифру необхідно завжди мати ключ, тобто квадрат. Це призводило до можливості зламу. Щоб розв'язати цю проблему було запропоновано ключ - пароль. Цей пароль вписувався без повторення літер у квадрат.

Таблиця 1.1 - Квадрат Полібія

	1	2	3	4	5
1	A	B	C	D	E
2	F	G	H	I,J	K
3	L	M	N	O	P
4	Q	R	S	T	U
5	V	W	X	Y	Z

Пари передавалися за допомогою факелів. Наприклад, для передачі літери О треба було взяти 3 факела у праву руку і 4 факела у ліву.

Подібні шифрувальні методи з деякими змінами проіснували до епохи військових походів Юлія Цезаря, де шифри створювалися за допомогою модулярної арифметики, що робило їх більш стійкими до атаки ворога. Застосування модулярної арифметики до алгоритмів криптографії має окремий розділ в криптографії.

Шифр Цезаря - симетричний алгоритм шифрування підстановками. Використовувався римським імператором Юлієм Цезарем для приватного листування.

Юлій Цезар використовував адитивний шифр, щоб зв'язатися зі своїми чиновниками. Із цієї причини адитивні шифри згадуються іноді як шифри Цезаря. Цезар для свого зв'язку використовував цифру 3.

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

(1.7)

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

Можна помітити, що суперпозиція двох шифрувань на ключахє просто шифруванням на ключі . Більш загально, множина перетворень шифрування шифру Цезаря утворює групу .

Припустимо, що, використовуючи шифр Цезаря, з ключем, який дорівнює 4, необхідно зашифрувати слово

Для цього зрушимо алфавіт так, щоб він починався з п'ятої літери (). Отже, отримаємо:

-вихідний алфавіт. Зміщуємо всі літери вліво на 4, відповідно отримаємо:



де і т.д.

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

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

З часів Цезаря до XV ст. криптографія змінилась, але на жаль, дуже мало відомостей про методи шифрування у цей період. Але як відомо, за допомогою застосування саме модулярної арифметики до шифрування тексту криптографія вже мала серйозні наміри щодо захисту інформації. Дешифрування такого шифру, що будувався на основі алгоритмів модулярної арифметики, вимагав багато часу і труднощів, а отже мав стійкість до зламу і надійність. У XIV ст. з'явилась книга про системи тайнопису, автором якої є Папа Римський Чікко Сімонетті. У цій книзі містяться приклади шифру заміни, у яких голосні літери відповідають декільком значковим виразам. Такі шифри пізніше отримали назву шифри многозначної заміни або омофони.

Ще один значний крок уперед криптографія зробила завдяки Леону Альберті. Відомий філософ, архітектор у 1466 р. написав працю про шифри, де було запропоновано шифр, в основу якого полягав шифрувальний диск. Також ідея шифрувального диску простежувалась у працях Енея Тактіка. Ім'я цього винахідника пов'язують з декількома техніками шифрування і тайнопису - диск Енея, лінійка Енея і книжковий шифр. Диск мав отвори для ниточки під кожною літерою, для запису тексту, нитка простягалася через потрібний отвір під літерою. Одержувач, що витягував нитку, міг прочитати текст, але в зворотному порядку, що було легко зробити. Лінійка Енея носила більш складний характер шифру, який реалізовував шифр заміни. Суть з ниткою і отворами така ж як і з диском, але одержувач повинен був мати точно таку ж лінійку з такими ж отворами, щоб прочитати текст. Що стосується книжкового шифру, то тут Еней запропонував робити малопомітні дірки поруч з літерою у книжці або іншому документі. Таку техніку тайнопису використовували навіть німецькі шпигуни під час Другої Світової війни.

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

При цьому пара літер, що знаходяться одна під одною в і , вказує, відповідно, номери рядків і стовпців таблиці, на перетині яким знаходиться знак шифрованого тексту (). Приклад таблиці Віженера можна подивитись у додатку А.

На початку XVII ст. над розвитком криптографії працював Матео Ардженетті. Він уперше запропонував використовувати деяке слово у якості мнемонічного ключа для змішаного алфавіту.

В цілому можна сказати, що XVII та XVIII ст. не надали нових ідей для криптографії, але вже у XIX ст. ситуація змінилась на протилежне.

У 1917 році американський інженер Гілберт Вернам (1890-1960 р.) створив шифр, який мав неабияку стійкість до зламу. Це був поточний шифр над двійковим алфавітом з літерами 0 і 1. Принцип дії полягає у наступному: відкритий текст подається у двійковому виді, ключ якого є випадкова двійкова послідовність тієї ж довжини, що використовується тільки один раз для шифрування даного тексту. У результаті отримана криптограма є додаванням по символам відкритого тексту та ключа за модулем 2. Зауважимо, що оскільки за модулем 2 віднімання співпадає з додаванням, для дешифрування криптограма додається по символам з ключом. Як приклад, візьмемо відкритий текст . За допомогою телеграфної кодової таблиці Бодо (додаток Б) знаходимо відповідні позначення літер: так що отримаємо шифрувальну двійкову послідовність довжиною : . У якості ключа візьмемо двійковий запис цифр після коми у числа . Для двійкового представлення будь-якого числа від 0 до 15 достатньо чотирьох цифр: 0 - 0000, 1 - 0001, 2 - 0010, 3 - 0011, 4 - 0100, 5 - 0101, 6 - 0110, 7 - 0111, 8 - 1000, 9 - 1001, …, 15 - 1111. Обираючи перші 35 двійкових знаків, які кодують послідовність знаходимо ключ



Для отримання криптограми по символам додаємо за модулем 2 двійкові коди відкритого тексту і ключа:

Зауважимо що при додаванні криптограми і ключа ми отримаємо відкритий текст.

Винахід у середині XIX ст. телеграфу та інших технічних видів зв'язку дало новий поштовх розвитку криптографії. Інформація представлялась у вигляді двійкового коду, який ми розглядали вище. Тому виникла проблема «раціонального» представлення інформації, яка вирішувалась за допомогою кодів. Коди дозволяли передавати довге слово або цілу фразу двома-трьома знаками. З'явилася необхідність у високошвидкісних засобах шифрування та у корекційних кодах, для зв'язку з неминучими помилками при передачі повідомлення. На цьому етапі розвитку відомий дисковий шифратор Т. Джефферсона, чия криптосистема мала велику кількість ключових елементів, та отримала назву блочні шифри. Чарльз Уітстон винайшов шифр, який отримав назву шифр Плейфера. Це був перший з відомих бігамних літерних шифрів. У другій половині XIX ст. з'явився вельми стійкий спосіб ускладнення числових кодів - гамування, метод симетричного шифрування. Він полягав у «накладанні» послідовності, яка насамперед складалася з випадкових чисел, на відкритий текст. Така послідовність отримала назву гамма-послідовність і швидко розповсюджувалась у використанні до шифрування і дешифрування текстів. Клод Шеннон, американський криптоаналітик, математик і інженер, довів, що такий метод шифрування є досить стійким до зламу.

Надалі у наступних пунктах розглянемо принцип дії основних шифрів, які використовувались ще з давніх часів.

1.3 Багатоалфавітні шифри заміни

Розглянемо правило шифрування багатоалфавітного шифру однозначної заміни, звернувшись до підручників [11, 12], де описано принцип дії даних шифрів.

Нехай -відкритий текст, який представлено послідовністю шифр-величин -довільний ключ. Тоді

(1.8)

де , деякі підстановки на множині всіх шифр-величин, які однозначно визначаються даним ключем.

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

(1.9)

Така послідовність (1.9) називається розподільником, що відповідає даним значенням .

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

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

1.4 Дискові багатоалфавітні шифри заміни

Загальна характеристика та принцип дії дискового шифратора описано у пункті 1.2. Тут ми розглянемо правило шифрування і деякі властивості такого шифру. Для цього звернемося до підручників[11, 13].

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

(1.10)

Якщо ввести у розгляд підстановку 

(1.11)

то після повороту диска на кут диск реалізує підстановку, що подається у вигляді добутку підстановок:

Тепер ми бачимо, що при повороті диску на кут , диск буде реалізовувати підстановку

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

Нехай у початкових кутових положеннях диски, які ми розглядаємо реалізують підстановки з симетричної групи (вони також є ключовими елементами) і в даний такт шифрування данні диски знаходяться у відповідних кутових положеннях Це означає, що й диск реалізує підстановку Тоді чергова літера відкритого тексту буде зашифрована у літеру , де

Формально визначити правило шифрування будь-якого відкритого тексту для дискового шифратора складно (через велику кількість ключових елементів). Для поточних шифрів, як правило, буває достатньо інформації правила шифрування літери тексту.

Число простих замін, з яких складається багатоалфавітний шифр, що реалізується дисковим шифратором, може бути досить великим. Чим більше це число, тим складніше дешифрування такого шифру. Як висновок, параметри дискових схем (число дисків, підстановки що реалізуються ними, схеми руху дисків) повинні бути ретельно продумані.

1.5 Шифри гамування. Табличне гамування

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

Для дослідження шифру гамування звернемося до підручників [11, 14], де описано принцип дії даного шифру.

Історично перший шифр гамування був схожий на шифр Віженера, однак без використання таблиці Віженера.

Шифр табличного гамування в алфавіті визначається довільним латинським квадратом на ,і способом отримання послідовності літер з, яка отримала назву гамма шифру (див. малюнок 1.1). Буква відкритого тексту під дією знаку гамми переходить у літеру тексту шифрування, яка знаходиться у рядку та стовпці квадрату (мається на увазі що рядки в мають номери у відповідності з порядком послідовності літер в алфавіті ).



Рисунок 1.1 - Латинський квадрат

З алгебраїчної точки зору літера є результатом застосування до літер квазігруповою операцією *, табличним заданням якої є латинський квадрат :

(1.12)

У випадку шифру Віженера квазігрупа є групою При цьому рівняння шифрування представляється у виді

(1.13)

апредставляє собою періодичну послідовність, що утворюється повторенням деякого ключового слова.

Поряд з додаванням використовується й віднімання знаків гамми. Відповідні рівняння шифрування можуть бути записані мовою теорії чисел такими формулами:

(1.14)

(1.15)

Шифри гамування з рівняннями шифрування (1.13) - (1.15) зазвичай називають шифрами медулярного гамування.

Якщо у якості квазігрупової операції * на множині 5-вимірних двійкових векторів використовується операція покоординатного додавання за модулем 2:

(1.16)

то отримаємо шифр Вернама.

Зауваження. Як шифр заміни, довілний шифр гаммування має наступну інтерпретацію.

З -м рядком латинського квадрату () можна поєднати підстановку (зсув на ):

з симетричної групи . Нехай тоді у кожному такті шифрування знак відкритого тексту замінюється по одній з підстановок з . Розподільником такого n-алфавітного шифру заміни є сама гамма шифру. Іноді -це група або суміжний клас за деяким класом підгрупи . У таких випадках шифр табличного гамування називається груповим. Довільний шифр табличного гамування не досить зручний для практичної реалізації. Більш зручним є саме груповий шифр, до яких відноситься шифр модульного гамування.

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



2. СУЧАСНІ АЛГОРИТМИ КРИПТОГРАФІЇ

2.1 Криптосистема Діффі-Хеллмана

Передача ключа по відкритим каналам була великою проблемою криптографії у XX ст.. Цю проблему змогли вирішити після появи алгоритму Діффі-Хеллмана, що дозволив дати відповідь на головне питання: «Як при обміні зашифрованими повідомленнями не використовувати передачу секретного ключа, який як правило, не менший ніж саме повідомлення?».

Великим внеском у криптографію було ствердження Діффі та Хеллманом, що ключі можна використовувати парами - ключ за шифрування і ключ розшифрування, але з однією умовою, що можливість визначення вмісту ключа для розшифрування виключається. Також свою частку праці вклав РальфМеркл, але назва алгоритму не містить його прізвища. Як стверджував у 2002 р. Мартін Хеллман:«Ця система з тих пір відома під назвою алгоритму Діффі-Хеллмана. Однак, коли систему було вперше описано на листі Діффі і мною, це була система розповсюдження відкритих ключів, концепція якої була побудована Мерклом, і через це вона повинна називатися «алгоритмом Діффі-Хеллмана-Меркла», якщо її пов'язують з іменами. Я сподіваюсь, що ця невелика зміна допоможе визнанню рівного вкладу Меркла у винаході криптографії з відкритим ключем.»

Історично криптосистема Діффі-Хеллмана є першою криптосистемою з відкритим ключем, яка будується на експоненційної односпрямованої функції. Спочатку ця криптосистема використовувалася як схема розподілу ключів для класичної симетричної криптосистеми з таємними загальними ключами. Розглянемо дану криптосистему за допомогою підручників [14, 15, 16, 17].

Попередньо всі користувачі мережі отримують від сервера по достовірному каналу системні константи - велике просте число і -примітивний елемент поля (поле Галуа) -скінченна довільна множина елементів,з заданими між ними операціями додавання, добутку та ділення.

Примітивним елементом поля є всякий первісний корінь степеню, тобто всякий генератор мультиплікативної групи цього поля.

Протокол ключового обміну

Протоколом ключового обміну називають процедуру взаємодії з відкритого каналу зв'язку віддалених абонентів А (Аліна) і В (Валерія), що володіє наступними властивостями:

а) в кінці процедури у А і В з'являється загальна секретна інформація (загальний секретний ключ), якої до початку дії не було;

б) зловмисник, який здатний перехоплювати всі повідомлення і знає алгоритм протоколу, не зможе відновити сформований секретний ключ.

На перший погляд неможливий протокол базується на задачі дискретного логарифмування і має наступний алгоритм.

Абоненти A і B незалежно один від одного:

а)виробляють два випадкових числа і ;

б) обчислюють значення

(2.1)

в) обмінюються повідомленнями з (2.1);

г) отримавши повідомлення обчислює

(2.2)

В отримав повідомлення і обчислює

(2.3)

д) елемент який дорівнює , називається секретним ключем.

Розглянемо на прикладі застосування алгоритму Діффі-Хеллмана до шифрування інформації, для цього звернемося до підручника [18].

Приклад 2.1Для генерування секретного ключа A та B по відкритому каналу зв'язку (наприклад по телефону або ) домовляються про константи. Абонент A випадковим чином обирає = 18, формує заготовку для ключа

і повідомлення відправляє В. Абонент В випадковим образом обирає , діє ним на отримане повідомлення :

і отримаємо секретний ключ Після цього абонент В обчислює

і ключову заготовку відправляє абоненту А. Абонент А отримавши заготовку, діє на неї своїм :



і отримує такий ж секретний ключ .

Тепер даний ключ може бути використаний у секретній переписці, наприклад по афінній криптосистемі.

2.2 Протокол Діффі-Хеллмана

Щоб виключити роботу з системою незаконних користувачів, необхідна процедура розпізнавання. Для цього в системі зберігається список ідентифікаторів (login),присвоєних кожному користувачеві. Перед доступом до ресурсів користувач зобов'язаний себе ідентифікувати. Отримавши ідентифікатор (в найпростішому випадку password), система проводить його аутентифікацію. Процедура аутентифікації повинна бути стійка до фальсифікації, підбору і підробці.

Дану схему протоколу Діффі-Хеллмана, розглянемо звернувшись до [16, 17], де схема являє собою сукупність процедур вироблення загального секретного ключа і взаємної аутентифікації суб'єктів взаємодії. Нехай -примітивнийелемент поля Галуа. Абоненти A і B володіють парою функцій:

відкрита функція зашифровки;

замкнена функція розшифровки ( );

а) абонент А обирає випадкове число та відправляє абоненту В заготовку ключа

б) абонент В обирає випадкове число , обчислює заготовку ключа для А за формулою . На своєму секретному ключі створює підпис обчислює сеансовий ключ зашифровує підпис на цьому ключі і відправляє повідомлення для Аі за допомогою формули ;

г) абонент А обчислює за заготовкою сеансовий ключза допомогою свого секретного ключа створює підпис зашифровує його на ключі і відправляє В повідомлення

АбонентА перевіряє дійсність підписуВ за допомогою нерівності

Аналогічно, В перевіряє на дійсність підписи А з нерівності

2.3 Протокол Фіата-Шаміра

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

Для реалізації схеми необхідний центр довіри, який обирає і публікує ціле число виду . Припустимо абонент А -це той, що доводить , абонент В - це той, що перевіряє. Абонент А (центр довіри) формує відкритий секретний ключі:

а) обирає випадкових чисел і оголошує їх секретним ключом ;

б) обчислює чисел , які задовольняють умові

та оголошує вектор відкритим ключем.

Протокол аутентифікації Е. Фіата і А. Шаміра складається з -кратного повторення кроків, розглянемо його алгоритм:

а) абонент А обирає випадкове число x, обчислює

(2.4)

б) абонент В обирає випадкову числову послідовність

і відправляє її до А;

в) абонент А обчислює добуток

і відправляє його до В;

г) абонент В перевіряє рівність

і приймає доведення.

Розглянемо принцип дії даного алгоритму на прикладі, для цього звернемося до підручника [18].

Приклад 2.2 Абонент А за допомогою простих обчислює модуль шифрування і обирає довільним чином цілі числа формує вектор секретного ключа:



,…,.

Компоненти вектору відкритого ключа обчислюються за формулою Ейлера

.

Враховуючи те, що і підставляючи конкретні значення для першої компоненти отримаємо

Для другої компоненти

і т.п.. В результаті ми отримаємо вектор відкритого ключа

а) тепер абонент А обирає випадкове число , обчислює



та відправляє абоненту В;

б) абонент В обирає випадковий двоїстий вектор

і відправляє його до А;

в) абонент А обчислює добуток

і відправляєабоненту В;

г) абонент В перевіряє рівність

і приймає доведення.



2.4 Криптосистема Ель-Гамаля (навчальна)

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

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

Для того щоб дослідити алгоритм криптосистеми Ель-Гамаля звернемося до [11, 19].

Алгоритм криптосистеми Ель-Гамаля

Ключ

Для створення ключа Аліна повинна здійснити наступні дії.

а) обрати випадкове просте число ;

б) обчислити випадковий мультиплікативний елемент, що породжується ;

в) вилучити випадкове ціле число і вважати його своїм закритим ключем;

г) обчислити відкритий ключ

;

д) використати трійку у якості параметрів відкритого ключа і запам'ятати число у якості закритого ключа.

Перейдемо до шифрування.

Для того щоб відправити Аліні таємне повідомлення , Валерія вилучає випадкове число і обчислює зашифрований текст ():

Дешифрування

Для того щоб розшифрувати текст (), Аліна обчислює формулу:

Припустимо, що Валерія шифрує вихідне повідомлення . Вона вилучає випадковий показник степеню, що дорівнює 26, і обчислює наступні значення.

В результаті виникає зашифрований текст (15,31).

Для того щоб розшифрувати повідомлення (15,31), Аліна знаходить наступне число.

Для ділення необхідно застосувати алгоритм Евкліда, однак Аліна не робить цього і обчислює значення 14 по іншому.

Покажемо, що система, яка описана алгоритмом, дійсно є криптографічною, тобто у результаті дешифрування Аліна відновлює той самий вихідний текст, який був надісланий Валерією. Оскільки



Для ділення, необхідно застосувати алгоритм Евкліда, що в загальному випадку супроводжується великими затратами, аніж множення. Однак Аліна може уникнути ділення, використавши наступне обчислення:

Число у цій формулі означає число .

Наведемо декілька прикладів застосування даного алгоритму, вилучивши їх з [18, 20].

Приклад 2.3PIN-код студентської банківської картки для виплат у зашифрованому вигляді було два рази надіслано від абонента М до абонента К. Для шифрування використано алгоритм шифрування Ель-Гамаля, (7,30) і (49, 139) - надіслані шифротексти. Розкрийте PIN-код якщо перша частина відкритого ключа

Розв'язання. Нехай -відкритий ключ криптосистеми, -рандомізатори, які використовуються при шифруванні у перший та другий рази. У криптосистемі Ель-Гамаля шифротекст повідомлення складається за допомогою рівнянь:

Тоді за умовою задачі

Оскільки Отже,

Із виразу отримаємо

Приклад 2.4 Уявіть, що менеджер страхової компанії надіслав шефу нешифрований запит, чи купувати йому акції. За домовленістю шеф у відповідь може надіслати одне з двох повідомлень «ТАК» або «НІ», а для збереження таємниці відповіді вони шифрують своє листування за допомогою криптоситеми Ель-Гамаля у групі . Відомо, що відповіді перед зашифруванням кодуються: «ТАК» = 18915, «НІ» = 4886 або може і навпаки. Припустимо, що шеф надіслав менеджеру шифротекст (4457 1979). Як криптоаналітик, не обчислюючи дискретних логарифмів, може змінити шифротекст на альтернативний (щоб при розшифруванні менеджер отримав замість «ТАК» відповідь «НІ» і навпаки)?

Розв'язання. У криптосистемі Ель-Гамаля відкритому тексту відповідає шифротекст де -примітивний корінь за модулем , -секретний ключ абонента, - рандомізатор. Перехопивши шифрований текст, йгого можна модифікувати двома шляхами: помножити на додатковий множник тільки його другу частину, або піднести обидві його частини до деякого степеня. Наприклад, розшифрування шифротексту дає відкритий текст .

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

У другому випадку криптоаналітику потрібно підібрати таке число , для якого Логарифмувавши порівняння, отримаємо:

звідки При перевірці нетривіального значення отримаємо наступне тому другий підхід з обраним кодуванням реалізувати неможливо.

2.5 Система Рабіна з використанням модулярної арифметики

Тепер розглянемо ще одну криптосистему з відкритим ключем - криптосистему Рабіна, яку створив М. О. Рабін ізраїльській вчений в області теорії обчислювальних систем, математик, лауреат премії Тьюрінга та інших.

Ця криптосистема будується на складності обчислень квадратного кореня за модулем зіставного числа. Робота Рабіна мала теоретичний характер. У даній криптосистемі наведено доведення стійкості криптосистем з відкритим ключем. Стійкість криптосистеми Рабіна еквівалентна нерозв'язності задачі про розкладання цілих чисел на множники. Алгоритм шифрування у криптосистемі Рабіна дуже ефективний. Розглянемо даний алгоритм криптосистеми Рабіна при передачі повідомлення між Валерією (В) та Аліною (А), звернувшись до [19, 20].

Для створення ключа Аліна повинна виконати наступні дії:

а) обрати два випадкових простих числа , які задовольняють умові що ;

б) знайти число ;

в) вилучити випадкове ціле число ;

г) використати пару у якості параметрів відкритого ключа та запам'ятати пару у якості параметрів закритого ключа.

Далі застосовуємо алгоритм зашифровування, який полягає у наступному. Для того щоб відправити Аліні таємне повідомлення , Валерія створює зашифрований текст (повідомлення) :

а) Валерія отримує аутентичну копію ключа Аліни, тобто число ;

б) Валерія представляє повідомлення у виді числа . У загальному випадку повідомлення може бути поділено на блоки, кожний з яких представлено своїм числом;

в) Валерія обчислює ;

г) зашифроване повідомлення В відправляє до А.

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

а) А отримує шифротекст ;

б) А вилучає з чотири квадратних кореня за модулем ;

в) А визначає потрібне значення з чотирьох коренів.

Покажемо, що даний алгоритм дійсно описує криптосистему, тобто процедура розшифровування, яку виконує Аліна, дійсно відтворює вихідний текст, який зашифрувала Валерія.

З елементарної математики відомо, що загальний розв'язок квадратного рівняння має вид:

де

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

Отримаємо розв'язок . Потім, використовуючи алгоритм Евкліда обчислимо коефіцієнти Безу для рівняння Тоді розв'язком порівняння буде вираз

Зауважмо, що розв'язок вказаних рівнянь легко зводиться до розв'язку порівнянь вигляду Воно легко розв'язується за В цьому випадку

Тому при практичному використані системи Рабіна використовують прості числа виду . Зауважимо також, що порівняння примає чотири розв'язки.

Тепер розглянемо задачу вилучення квадратного кореня за модулем більш докладно. Для цього звернемося до алгоритму вилучення квадратного кореня за зіставним модулем при відомій факторизації. Звернемося до [18, 20].

Приклад 2.5Налаштуємо ключі Рабіна з умовою ,



тоді модулем шифрування буде Зашифруємо повідомлення

Тепер спробуємо розшифрувати секретне повідомлення Знайдемо коефіцієнти Безу,

тобто

Тепер обчислюючи

отримаємо

У наступному пункті дослідимо відому криптосистему RSA, яка є дуже важливою для криптографії.



2.6 Криптосистема RSA (навчальний варіант)

Алгоритми RSA є класикою асиметричної криптографії. Він був запропонований трьома дослідниками - математиками: Рональдом Рівестом (R. Rivest), ді Шаміром (A. Shamir) та Леонардом Адлеманом (L. Adleman) в 1977-78 роках, який отримав назву за першими літерами прізвищ його винахідників. Також цей алгоритм є найбільш відомою криптосистемою з відкритим ключем. Алгоритм RSA складається з чотирьох етапів: генерації ключів, шифрування, дешифрування і розповсюдження ключів. Алгоритм використовує два ключі - відкритий, що не потребує зберігання в таємниці, і секретний, які разом утворюють пари ключів.

...