Міністерство освіти та науки України Національний університет “Львівська політехніка” Алгоритм шифрування з відкритим ключем RSA Інструкція до лабораторної роботи № 3 з дисципліни “Основи збору, передавання та обробки інформації” для студентів базового напрямку 6.0914 “Комп’ютеризовані системи, автоматика і управління” та базового напрямку 050201 “Системна інженерія” Затверджено на засіданні кафедри “Комп’ютеризовані системи автоматики” Протокол № __ від __.__.2008 Львів 2008 Алгоритм шифрування з відкритим ключем RSA: Інструкція до лабораторної роботи № 3 з дисципліни “Основи збору, передавання та обробки інформації” для студентів базового напрямку 6.0914 “Комп’ютеризовані системи, автоматика і управління” та базового напрямку 050201 “Системна інженерія” / Укл.: А.Г. Павельчак, Р.В. Проць, В.В. Самотий – Львів: НУЛП, 2008. – 36 с. Укладачі: А.Г. Павельчак, к.т.н., асистент Р.В. Проць, к.т.н., доцент В.В. Самотий, д.т.н., професор Відповідальний за випуск: А.Й. Наконечний, д.т.н., професор Рецензент: З.Р. Мичуда, д.т.н., професор Мета роботи: вивчити принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідити числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA. 1. Загальні відомості Ідею, що покладено в основу асиметричних криптосистем, було висунуто Вайтфілдом Діффі (Whitfield Diffie) та Мартіном Гелманом (Martin Hellman), та незалежно Ральфом Меркле (Ralph Merkle). Ця революційна ідея була опублікована Діффі та Гелманом в 1976 році у статті «Нові напрямки в криптографії». Асиметричні криптосистеми, на відміну від симетричних алгоритмів, використовують для шифрування та розшифрування повідомлень не один секретний ключ, а пару ключів для кожного учасника протоколу – відкритий ключ E для шифрування та не співпадаючий з ним секретний ключ D для розшифрування. Для цих ключів, послідовно застосованих для повідомлення M, повинно виконуватися таке співвідношення
(1.1) Співвідношення (1.1) можна розглядати як замок, що закривається одним ключем, а відкривається іншим. Для безпеки такої системи секретний ключ D повинен бути таким, щоб його неможливо було визначити з відкритого ключа E або, щоб це визначення було нездійсненним з причин обмеження часу та пам’яті. У асиметричних системах робота з ключами є простою. Щоб одержувач А, власник секретного ключа, зміг розшифрувати повідомлення, зашифроване відправником Б, по каналах зв’язку треба передати лише відкритий ключ учасника А. Цей принцип і визначає відкритість сеансу зв’язку: для безпечної взаємодії двох учасників достатньо домовитися про асиметричну процедуру шифрування та обмінятися відкритими ключами. Однак така простота керування ключами теж має певні обмеження. Учасники передбачуваного безпечного сеансу зв’язку повинні бути впевнені, що відкриті ключі інших учасників є справжніми, тобто, щоб порушник, що має намір перехопити секретну інформацію, не зміг непомітно проникнути в сеанс зв’язку та видати «свій» ключ за відкритий ключ чийогось партнера. Справжність відкритих ключів гарантується складними процедурами, та існують відповідні державні закони, що регулюють діяльність у цій області. Принцип асиметричних криптосистем має широке застосування. За допомогою цих систем можна створювати цифрові підписи, у яких ключова функція перевернена задом наперед. Для формування цифрового підпису ми «шифруємо» повідомлення секретним ключем та передаємо отримане разом з повідомленням по каналу зв’язку. Тепер кожен, хто знає відповідний відкритий ключ, зможе розшифрувати зашифроване повідомлення та порівняти результат з вихідним текстом. При цьому сформувати цифровий підпис може лише власник секретного ключа. Варто зазначити, що, по відношенню до цифрових підписів, використання термінів «шифрування» та «розшифрування» є не зовсім коректним, тому кажуть, як правило, про «формування» та «перевірку» цифрово...