35 Алгоритм Евкліда, його наслідок, пошук оберненого елемента, китайська теорема про остачі.

37. Опис криптосистеми rsa

Відомим прикладом криптосистеми з відкритим ключом (асиметричної криптосистеми) є криптосистема RSA, розроблена в 1977 році і отримала назву в честь її творців: Рівеста, Шаміра й Ейдельмана [62].

RSA став першим алгоритмом придатним і для шифрування і для цифрового підпису. Безпека алгоритму RSA побудована на принципі складності

факторизації [42]. Алгоритм використовує два ключі — відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пари ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключом, то розшифрувати його можна тільки відповідним секретним ключом.

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

1. Вибираються два великих простих числа p і q .

Для знаходження двох великих простих чисел p і q , при генерації ключа, звичайно використовуються імовірнісні тести чисел на простоту, які дозволяють швидко виявити й відкинути складні числа.

Для генерації p і q необхідно використовувати криптографічно надійний генератор випадкових чисел. У порушника не має бути можливості одержати будь-яку інформацію про значення цих чисел. p і q не повинні бути занадто близькими одне до одного, інакше можна буде знайти їх використовуючи метод факторизації Ферма [52]. Крім того, необхідно вибирати «сильні» прості числа, щоб не можна було скористатися p-1 алгоритмом Поларда.

2. Обчислюється їх добуток n . pq .

Число n повинно мати розмір не менше 512 біт. З 2007 року система шифрування на основі RSA вважається надійною, починаючи з величини n в 1024 біта.

3. Обчислюється Функція Ейлера.(n) . ( p .1)(q .1) .

4. Вибирається ціле e таке, що 1. e ..(n) та взаємно просте з .(n) .

5. За допомогою розширеного алгоритму Евкліда знаходиться число d таке, що ed .1(mod.(n)) .

Число n називається модулем, а числа e і d — відкритою й секретною експонентами, відповідно. Пари чисел (n,e) є відкритою частиною ключа, а (n,d) — секретною. Числа p і q після енерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті [10].

38. Генерування ключів в криптосистемы rsa

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

Алгоритм RSA складається з трьох частин: генерування ключів, шифрування і дешифрування.

Генерування ключів. Оберемо два великих різних простих числа p і q (Натуральне число називається простим, якщо воно ділиться тільки на себе і на 1. Додаток В.) та знайдемо їх добуток

Обчислимо функцію Ейлера за формулою:

Таємний ключ добираємо з умов: і в заємно просте з

тобто d\j(n) не мають спільних дільників. Відкритий ключ є обираємо з умов:

Остання умова означає, що різниця де - 1 повинна ділитись на j(n) без залишку. Для визначення числа є слід підібрати таке число к, що:

В алгоритмі RSA (є, п)- відкритий ключ, (d,n)-секретний ключ.