Алгоритм RSA: Методичні вказівки до виконання і оформлення практичної роботи № 5, страница 2

Якщо користувач А хоче передати користувачеві В повідомлення М, він виконує наступні кроки:

-  користувач А розбиває вихідний відкритий текст М на блоки, кожний з яких може бути представлений у вигляді числа

М_i=0,1,2,...,N-1 ;

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

;

-  користувач А відправляє криптограму

C₁, С₂, С₃,...,C_i, ...

користувачеві В;

-  користувач В розшифровує прийняту криптограму

C₁, С₂, С₃,...,C_i, ...,

використовуючи секретний ключ К_B, по формулі

.

У результаті буде отримана послідовність чисел M_i, яка являє собою вихідне повідомлення М. Щоб алгоритм RSA мав практичну цінність, необхідно мати можливість без істотних витрат генерувати великі прості числа, уміти оперативно обчислювати значення ключів К_A і К_B.

Приклад розв’язання задачі

Необхідно зашифрувати повідомлення “КНИГА”, яке складається з символів українського алфавіту, за допомогою алгоритму RSA.

Виконаємо зашифрування відкритого тексту.

Дії користувача В.

Для простоти обчислень будуть використовуватися невеликі числа. На практиці застосовуються дуже великі числа.

НехайР= 3 і Q=11, тоді N =33.  Обчислимо значення функції Ейлера для N=33, отримаємо:

.

Виберемо у якості відкритого ключа К_A =3 і перевіримо виконання умов (3), (4):

.

Обчислюємо значення секретного ключа К_B відповідно до формули (5)

.

Розв’язуючи вищевказане порівняння, одержуємо К_B =7, тому що

.

Передаємо користувачеві А пару чисел (N=33 , K_A =3 ).

Дії користувача А.

Повідомлення, яке буде шифруватися і складається з символів українського алфавіту, представляється як послідовність цілих чисел у діапазоні 0...32. Кожному символу відповідає ціле число. Таким чином, відкритий текст «КНИГА» буде  послідовністю чисел

М={14, 17, 10, 3, 0}.

Виконаємо зашифрування тексту, представленого у вигляді послідовності чисел M, використовуючи ключ К _A = 3 і N = 33, за формулою

.

В результаті отримаємо:

Відправляємо користувачеві В криптограму C ={5, 29, 10, 27, 0}.

Виконаємо розшифрування шифртексту.

Дії користувача В.

Розшифруємо прийняту криптограму C, використовуючи секретний ключ К_B=7, за формулою

.

У результаті одержуємо:

            Таким чином, відновлене вихідне повідомлення
М={14, 17, 10, 3,  0}відповідає символьному повідомленню "КНИГА".

Вимоги до виконання і оформлення практичної  роботи

            Для виконання і оформлення роботи необхідно:

1.  Ознайомитися з алгоритмом шифрування даних RSA;

2.  Виконати програмну реалізацію шифрування й дешифрування даних за допомогою алгоритму RSA, відповідно до свого варіанта;

3.  Протестувати роботу програми;

4.  Оформити звіт.

Результатом виконання практичної роботи є :

1.  Звіт про виконану лабораторну роботу в друкованому  вигляді

2.  Працездатна програмна реалізація поставленого завдання на будь-якій мові програмування

Звіт про виконану лабораторну роботу повинен включати:

1.  Титульний аркуш із вказівкою номера практичної роботи, на якому повинна стояти підпис студента й дата здачі завдання;

2.  Постановку завдання;

3.  Теоретичний матеріал по темі практичного завдання;

4.  Вихідні дані, які були застосовані для виконання поставленого завдання;

5.  Текст програми;

6.  Результати роботи програми;

7.  Висновки.

Алгоритм розв’язання задачі:

1.  Згенерувати прості числа в інтервалі [A,B]( A,B брати з Таблиці 1, згідно Вашого варіанта). Записати їх у текстовий файл prime.txt;

2.  Випадковим чином зі згенерованих на попередньому кроці чисел, вибрати два простих числа P, Q;

3.  Використовуючи алгоритм Евкліда, згенерувати 1000 ключів K_a.(третину ключів брати з інтервалу  [0;N/3], третину ключів брати з інтервалу [N/3;2*N/3], третину ключів брати з інтервалу [2*N/3;N]). Записати їх у файл Ka.txt;

4.  Випадковим чином вибрати ключ K_a, із ключів, згенерованих на попередньому кроці;

5.  Згенерувати ключ K_{b ,} використовуючи розширений алгоритм Евкліда;

6.  Зробити зашифрування даних за допомогою алгоритму RSA;

7.  Зробити розшифрування даних зашифрованих за допомогою алгоритму RSA;

8.  Вивести результати роботи програми на екран. В якості результату повинні бути виведені:

а)   алфавіт;

б)   ключі K_a і K_b ;

в)  P,Q, N, ;

г)  відкритий текст у символьному й цифровому вигляді;

д)  зашифрований текст у цифровому вигляді;

е)  розшифрований текст у цифровому й символьному вигляді.

Примітка.

1.  Вихідний текст брати довільного змісту довжиною 100 символів, використовуючи символи з Алфавіту (Алфавіт брати з Таблиці 1, згідно Вашого варіанта) ;