Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 38

Визначимо n=p*q=3*7=21. Знайдемо (p-1)(q-1)=12. Виберемо d = 5. Знайдемо число е, для якого справедливо

ed mod ((p-1)(q-1)) = 1.(вирішуємо рівняння  де а=1,2...n;) виберемо з безлічі рішень відмінне від числа d число, е = 17.

Представимо шифруєме слово у вигляді послідовності чисел 2 6 4 (порядковий номер букв у алфавіті)

Шифрування по відкритому ключу (17,21):

C1=217 mod(21) = 131032 mod (21) =11;

C2 = 617mod (21) = 16926659444736 mod (21) = 6;

C3 = 417mod(21) = 17179869184 mod (21) = 16.

Отримане зашифроване повідомлення :11 6 16.

Розшифруємо зашифроване повідомлення по секретному ключу (5,21)

М1= 115mod (21) = 161051 mod (21) = 2;

M2 = 65 mod (21) = 7776 mod (21) = 6;

M3 = 165 mod (21) = 1048576 mod (21) = 4.

У підсумку одержуємо вихідне повідомлення БІГ.

Отже, у реальних системах алгоритм RSA реалізується в такий спосіб: кожен користувач вибирає два великих простих числа, і від­повідно до описаного вище алгоритма вибирає два простих числа e і d. Як результат множення перших двох чисел (p і q) установлюється n.

{e,n} утворить відкритий ключ, а {d,n} – закритий (хоча можна взяти і навпаки).

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

Особливості методу накладають деякі обмеження на значення деяких змінних. Наприклад: змінна D повинна бути взаємно простою відносно M, тобто ці числа не повинні мати спільних дільників, а змінна E повинна бути такою, щоб залишок від ділення (D*E) на M дорівнював 1.

Порядок виконання лабораторної роботи

1.  Вивчити опис криптосистеми RSA та відомості з елементарної теорії чисел.

2.  Розібрати схему шифрування алгоритмом RSA.

3.  Зашифрувати повідомлення алгоритмом RSA за ключами поданими у додатку 1. Передостання цифра номеру студентського квитка означає номер варіанту відкритого тексту, остання цифра номеру студентського квитка означає ключі шифрування.

4.  Повідомлення шифрується вручну посимвольно з використанням алфавіту: _АБВГДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ

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

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

Контрольні питання

1.  У чому полягає суть систем з відкритим ключем (СВК)?

2.  За допомогою яких ключів шифрується і розшифровується повідомлення в СВК?

3.  Що таке необоротні функції? Які типи необоротних перетворень використовуються в СВК?

4.  Які головні вимоги пред'являються до СВК?

5.  Як можна використовувати алгоритми криптосистем з відкритим ключем?

6.  На яких математичних фактах заснований алгоритм RSA?

7.  Як вибираються числа P і Q алгоритму RSA?

8.  Які значення користувач, що генерує ключі RSA, повідомляє іншим користувачам, а які зберігає в таємниці?

9.  Чи можна розшифрувати повідомлення за допомогою відкритого ключа?

10.  Як обчислюється значення функції Ейлера? Для чого воно використовується в алгоритмі RSA?

11.  Чи зміниться криптограма, якщо числа P і Q поміняти місцями?


2.10Лабораторна робота № 10. Криптосистема Ель-Гамаля

Тема роботи: Криптосистема Ель-Гамаля

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

Загальні відомості

Криптосистема Ель-Гамаля є альтернативою RSA і при рівному значенні ключа забезпечує ту ж саму криптостійкість.

На відміну від RSA метод Ель-Гамаля заснований на проблемі використання дискретного логарифма. Цим він схожий на алгоритм Діффі-Хелмана. Якщо підносити число до ступеня в кінцевому полі досить легко, то відновити аргумент за значенням (тобто знайти логарифм) досить важко [1].

Теоретичні відомості

Основу системи складають параметри p і g – числа, перше – просте, а друге – ціле.

Олександр генерує секретний ключ а й обчислює відкритий ключ y = gа mod p. Якщо Борис хоче послати Олександрові повідомлення m, то він вибирає випадкове число k, менше p і обчислює

y1 = gk mod p і

y2 = m Å (y kmod p), де Å означає побітове додавання по модулю 2. Потім Борис посилає (y1,y2) Олександрові.

Олександр, одержавши зашифроване повідомлення, відновлює його:

m = (y1a mod p) Å y2.

Алгоритм цифрового підпису DSA, розроблений NIST (National Institute of Standard and Technology), що є частиною стандарту DSS частково спирається на розглянутий метод.[14]

Порядок виконання лабораторної роботи

1.  Вивчити опис криптосистеми Ель-Гамаля та відомості з елементарної теорії чисел.

2.  Розібрати схему шифрування алгоритмом Ель-Гамаля

3.  Зашифрувати повідомлення алгоритмом Ель-Гамаля за ключами поданими у додатку 1. Передостання цифра номеру студентського квитка означає номер варіанту відкритого тексту, остання цифра номеру студентського квитка означає ключі шифрування.

4.  Повідомлення шифрується вручну посимвольно з використанням алфавіту: _АБВГДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ

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

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

Контрольні питання

1.  Яка важка обчислювальна задача покладена в основу шифрсистеми Ель-Гамаля?

2.  Які основні параметри системи складають основу шифру Ель-Гамаля?

3.  Яким чином виконується шифрування методом Ель-Гамаля. В чому його різниця від RSA?

4.  Чи є можливим використання криптосистеми Ель-Гамаля у якості схеми цифрового підпису?