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

Для дослідження даної системи звернемося до підручників [11, 21]

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

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

Розглянемо алгоритм криптосистеми RSA, який використовується для шифрування тексту (повідомлення) між Валерією (В) та Аліною (А).

Для того щоб встановити ключ, Аліні необхідно виконати наступні операції:

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

б) обчислити ;

в) обчислити

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

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

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

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

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

(2.5)

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

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

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

Приклад 2.6Припустимо, що Аліна обрала числа Тоді . Застосовуючи алгоритм до пари Аліна отримує наступне число:

Інакше говорячи, Отже, таємним показником степеню, що використовує Аліна при шифруванні, є число 29. Аліна встановлює пару у якості параметрів відкритого ключа криптосистеми RSA.

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

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

Приклад 2.7 Для утворення модуля криптосистеми RSA обрано випадковим чином число і число , де . Яким способом можна зламати дану криптосистему?

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

Приклад 2.8Нехай -модуль криптосистеми RSA, -кількість файлів, які треба зашифрувати, -взаємно прості цілі числа, взаємно прості із значенням , тобто

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

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

Приклад 2.9За схемою RSA має місце де - закритий ключ:

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

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

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

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

ВИСНОВКИ

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

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

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

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

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

2. Ященко В.В., Нестернко Ю. В. Введение в криптографию: учебник, 4-е издание. Москва:МЦНМО, 2012. 348 с.

3. Вербіцький О. В. Вступ до криптології : підручник. Львів : видавництво науково-тех. літ., 1998. 247 с.

4. Ємець В., Мельник А., Попович Р. Сучасна криптографія. Основні поняття : підручник. Львів : БаК, 2003. 144 с.

5. Данилова О. Ю., Думачев В.Н. Математические основы криптографии:учебник. Воронеж: Воронежский институт МВД России, 2008.240с.

6. Погорелова Б. А. Словарь криптографических терминов. Москва: МЦНМО, 2006.91 с.

7. Алфёров А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии.StudFiles : файловый архив для студентов.URL:https://studfiles.net/preview/6311470/ (дата звернення 28. 02. 2019).

8. Воронков Б.Н., Щеголеватих А.С.Элементы теории чисел и крипто защита:учебноепособие. Воронеж: Издательско-полиграфический центр Воронежского государственного университета, 2008.88 с.

9. Нестерова Л. Ю., Карпенкова Н. В. Создание криптографии с помощью модулярной математики // Молодой ученый.2014. № 21.1. С. 237 - 240.

10. Фалалеева В. С. Реализация Windows-приложения, выполняющего шифрование и дешифрование текста шифрами Цезаря и Хилла // Молодойучёный. 2015.№15. С. 65- 69.

11. Сингх С. Книга шифров. Тайная история шифров и их расшифровки: книга; пер. Галыгин А.; ред. Русакова А. Г. Москва: Издательский центр Аст, Аванта, 2006. 447 с.

12. Мао В. Современная криптография. Теория и практика: книга; пер. Клюшин Д. Москва: Вильямс, 2005. 763 с.

13. Франчук В. М. Захистінформаційнихресурсів: криптографічні та стеганографічніметодизахистуданих: посібник для викладачів, вчителів та студентівінформатичнихспеціальностей. Київ: НПУ ім. М. П. Драгоманова. Інститутінформатики, 2012. 120 с.

14. Бауэр Ф. Р. Расшифрованные секреты. Методы и принципы криптологии: книга; пер. с англ. яз. Ахмолина В. И., Петрова В. И.; ред. Чашкина А. В. Москва: Мир, 2007. 550 с.

15. Богуш В. М., Мухачов В. А. Криптографічні застосування елементарної теорії чисел : навч. посібник. Київ : ДУІКТ, 2006. 126 с.

16. Коробейников А.Г., Гатчин Ю.А. Математические основы криптологии:учебное пособие. Санкт-Петербург: СПбГУ ИТМО, 2004.106с.

17. Задірака В. К., Олексик О. Комп'ютерна криптологія : підручник. Київ, 2002. 505 с.

18. Бабак В. П. Теоретичні основи захисту інформації : підручник. Київ : НАУ, 2008. 752 с.

19. Бабенко Т. В., Гулак Г. М., Сушко С. О., Фомичова Л. Я. Криптологія у прикладах, тестах і задачах: навч.посіб.Дніпропетровськ: НГУ, 2013. 318 с.

20. Баричев С.Г., Серов Р. Е. Основы современной криптографии:учебник. Москва:Горячая Линия - Телеком,2011. 176 с.

21. Кузнецов Г. В., Фомичов В. В., Сушко С. О., Фомичова Л. Я. Математичні основи криптографії : навч. посібник. Дніпропетровськ : НГУ, 2004. 391 с.

22. Сушко С. О., Кузнецов Г. В., Фомичова Л. Я., Корабльов А. В. Математичні основи криптоаналізу : навч. посібник. Дніпропетровськ : НГУ, 2004. 391 с.

ДОДАТОК А

Таблиця Віженера для латинського алфавіту

ДОДАТОК Б

криптографія алфавіт рабін система

Таблиця Бодо для латинського алфавіту

Размещено на Allbest.ru