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

Поточне випадкове число Y_i адітивного датчика виходить із суми чисел Y_i-1 і Y_i-2 обчисленням модуля від розподілу цієї суми на m:[5]

Y_i = (Y_i-1 + Y_i-2) mod m.

Приклад процедури розрахунку ряда псевдовипадкових чисел:

procedure GetRandoms(a,b,m,x,Num:integer);

{Коментар: a,b,m – параметри генератору ПВЧ (множник, збідьшення, модуль відповідно), х – перше число гами.}

var i:integer;

begin

for i:=1 to Num do

begin

x:=(a*x+b) mod m;

Writeln(x);

end;

end;

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

Вивчити відомості про шифри гамування.

Створити лінійний конгруентний генератор псевдовипадкових послідовностей за формулою:
Y_i = (a • Y_i-1 + b) mod m, де
m – модуль;
a – множник;
b – збільшення;
а Y₀ – вектор ініціалізації (вхідне значення).

Параметри генератора вибираються з додатку 1 відповідно до номеру студента у журналі.

Сгенерувати за допомогою генератору програмно і вручну гаму зі 100 елементів.

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

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

1. Що таке гамування? Що розуміють під гамою шифру?

2. Які операції можна застосовувати при накладенні гами? У чому полягає процес шифрування і дешифрування?

4. Які переваги і недоліки в методі гамування?

5. Які вимоги пред'являються до криптографічної стійкості генератора ПВП? Чому найбільш важлива довжина періоду гами?

6. Опишіть лінійний конгруентний спосіб генерації ПВП.

7. Опишіть адітивний і мультиплікативний генератори ПВП.

8. Опишіть алгоритми шифрування і дешифрування відкритого тексту методом гамування.

2.9.  Лабораторна робота №9. Системи з відкритим ключем. Криптосистема RSA.

Тема роботи: Системи з відкритим ключем. Криптосистема RSA.

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

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

Концепцію систем з відкритим ключем запропонували у 1976 році Діффі і Хеллман.[19] Криптосистеми з відкритим ключем засновуються на використанні особливих властивостей шифрування, що являє собою розрахунок оберненої величини від якоїсь функції, що не може бути реалізована числовими методами.

В сучасній криптографії стандартом де-факто на системи з відкритим ключем є система RSA, спроектована Рівестом, Шаміром та Адлеманом [2].

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

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

Теорема 1. (Мала теорема Ферма.)

Якщо р – просте число, то

x^p-1 = 1 (mod p) (1)

для будь-якого х, простого відносно р, і

x^p = х (mod p) (2)

для будь-якого х.[1]

Визначення. Функцією Эйлера j(n) називається число позитивних цілих, менших n і простих відносно n.

Теорема 2. Якщо n=pq, (p і q – відмінні друг від друга прості числа), то

j(n)=(p-1)(q-1).

Теорема 3. Якщо n=pq, (p і q – відмінні друг від друга прості числа) і х – просте відносно р и q, то

x^j(n) = 1 (mod n).

Наслідок . Якщо n=pq, (p і q – відмінні друг від друга прості числа) і є просте відносно j(n), то відображення

Е_е,n: x®x^e (mod n)

є взаємно однозначним на Z_n.

Очевидний і той факт, що якщо е – просте відносно (n), то існує ціле d, таке, що

ed = 1 (mod j(n)) (3)

На цих математичних фактах і заснований популярний алгоритм RSA.[4]

Нехай n=pq, де p і q – різні прості числа. Якщо e і d задовольняють рівнянню (3), то відображення Е_е,n і Е_d,n є інверсіями на Z_n. Як Е_е,n, так і Е_d,n легко розраховуються, коли відомі e, d, p, q. Якщо відомі e і n, але p і q невідомі, то Е_е,n являє собою однобічну функцію; перебування Е_d,n по заданому n рівнозначно розкладанню n. Якщо p і q – досить великі прості, то розкладання n практично не здійсненне. Це і закладено в основу системи шифрування RSA.

Користувач i вибирає пару різних простих p_i і q_i і розраховує пари цілих (e_i, d_i), що є простими відносно j(n_i), де n_i=p_i q_i . Довідкова таблиця містить публічні ключі {(e_i ,n_i)}.[20]

Припустимо, що вихідний текст

x =(x₀, x₁, ..., x_n-1), xÎZ_n , 0 £ i < n,

Z_n-безліч цілих чисел

спочатку представлений по підставі n_i :

N = c₀+c_{i ni}+....

Користувач i зашифровує текст, при передачі його користувачу j, застосовуючи до n відображення Ed_i,n_i :

N ® Ed_i,n_i n = n’.

Користувач j робить розшифрування n’, застосовуючи Ee_i,n_i :

N’ ® Ee_i,n_i n’= Ee_i,n_i Ed_i,n_i n = n .

Очевидно, для того щоб знайти інверсію Ed_i,n_i стосовно Ee_i,n_i, потрібно знання множників n=p_i q_i. Час виконання найкращих з відомих алгоритмів розкладання при n=10¹⁰⁰ на сьогоднішній день виходить за межі сучасних технологічних можливостей [1].

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

Приклад 1Зашифруємо повідомлення “САВ”. Для простоти будемо використовувати маленькі числа (на практиці застосовуються набагато більші).

Виберемо p=3 і q=11.

Визначимо n=3*11=33.

Знайдемо (p-1)(q-1)=20. Отже, у якості d, взаємно простої з 20, приймемо наприклад, d=3.

Виберемо число е. Як таке число може бути узяте будь-яке число, для якого задовольняється співвідношення (е*3) (mod 20) = 1, наприклад 7.

Примітка: для простого знаходження числа е досить вирішити в цілих числах рівняння  , де а=1,2..n (перебираючи значення n до першого цілого е)

Представимо повідомлення як послідовність цілих чисел за допомогою відображення: А®1, У®2, З®3. Тоді повідомлення приймає вид (3,1,2). Зашифруємо повідомлення за допомогою ключа {7,33}.

C[1] = (3⁷) (mod 33) = 2187 (mod 33) = 9,

C[2] = (1⁷) (mod 33) = 1 (mod 33) = 1,

C[3] = (2⁷) (mod 33) = 128 (mod 33) = 29.

Розшифруємо отримане зашифроване повідомлення C{9,1,29} на основі закритого ключа {3,33}:

M[1] = (9³) (mod 33) = 729 (mod 33) = 3,

M[2] = (1³) (mod 33) = 1 (mod 33) = 1,

M[3] = (29³) (mod 33) = 24389 (mod 33) = 2.

Приклад 2

Шифруємо слово БІГ . Коефіцієнти p=3, q=7.