Системи з відкритими ключами і відкритим розподілом ключів

1.3.1 Імовірно стійка криптосистема з відкритими ключами

У 80-і роки ХХ століття широке розповсюдження отримала криптосистема з відкритими ключами відома на сьогодні, як RSA [12-15] система. Основною особливістю цієї системи є те, що в ній ключ зашифрування К^з не співпадає з ключем розшифрування К^р, тобто

, (1.48)

а знайти один ключ при відомому другому для відповідних значень загаль-носистемних параметрів можна не нижче ніж з субекспоненційною складністю. Хоч на сьогодні RSA криптосистема піддається нападкам і відносно неї даються різні прогнози, але вона проіснувала більше 25 років і дозволяє реалізувати направ-
лене шифрування, ЕЦП та слушні протоколи. Крім того, на наш погляд, RSA система дозволяє якісно реалізувати криптографічними методами таку основну функцію, як спостережливість, в змісті причетності відправника та отримувача. Так причетність відправника може бути забезпечена за рахунок здійснення цифрового підпису з використанням особистого (таємного) ключа, а перевірка цілісності та справжності підписаної інформації здійснюються з використанням особистого (публічного) ключа. Далі направлене шифрування може бути здійснене з використанням другої ключової пари, відкритий ключ отримувача якої застосовують для направленого шифрування, а особистий ключ застосовується для розшифрування повідомлення. Тому розглянемо цю класичну систему докладно.

RSA криптоалгоритм є блоковим, у ньому повідомлення М розбивається на блоки М_i, з довжиною блоку (на сьогодні 768 біт мінімум), реально 1024, 2048 і більше бітів. Блок криптограма С_і обчислюється за правилом

, (1.49)

де – є відкритий ключ прямого перетворення, N – модуль перетворення є добутком виду

, (1.50)

де в свою чергу P, Q – великі прості числа.

Якщо l_p є довжина простого числа Р, наприклад в бітах, а l_q – довжина простого числа Q, то довжина модуля N

. (1.51)

Розшифрування блока криптограми здійснюється за правилом:

, (1.52)

де D_к – є ключ зворотного перетворення, тобто розшифрування .

Однозначність розшифрування можна підтвердити, підставивши (1.52) в (1.49). В результаті отримаємо:

. (1.53)

Оскільки ключова пара пов’язана між собою порівнянням:

, (1.54)

де є функцією Ойлера від модуля N

= .

Якщо (1.54) має єдине ров’язання, тобто існує єдина пара , то такий шифр є однозначним і при таких умовах RSA криптосистема забезпечує однозначне направлене шифрування.

Зазначимо, що з точки зору забезпечення максимально можливої крипто-стійкості прості числа P i Q мають бути сильними в широкому або вузькому значенні [7]. Так просте число Р вважатимемо сильним в широкому значенні, якщо

, (1.55)

де R – також велике просте число.

Аналогічно визначається і сильне в широкому значенні просте число Q.

Просте число Р вважається сильним у вузькому значенні, якщо містить в своєму канонічному розкладі велике просте число R, Р +1 містить в своєму розкладі велике просте число S, а крім того R -1 містить в своєму розкладі велике число T.

Хоч розробниками RSA системи вважають Рона Рівеста, Аді Шаміра і Леонарда Адлемана, в підручнику „Фізика квантової інформації”, авторів Д. Бауместер, А. Екерт, А. Цайлингер на стор. 37-38 стверджується, що в Англії RSA подібний алгоритм було винайдено на декілька років раніше.

1.3.2 Алгоритм формування ключових пар

Генерація ключів (задачі)

Система RSA відноситься до криптосистем з відкритими ключами. В цій системі ключі Е_k ¹ D_k, причому один з них має бути особистим, а другий – відкритим. Наприклад, Е_k – особистий, а D_k – відкритий, якщо вони використовуються для ЕЦП і навпаки, якщо використовуються для направленого шифрування.

Усі параметри (N, P, Q) також поділяються на 2 класи: N – відкритий, P, Q – конфіденційні (секретні).

Сутність забезпечення моделі взаємної недовіри – кожен користувач генерує ключі сам собі. Особистий ключ залишає в себе і забезпечує його строгу конфіденційність. Відкритий ключ розсилає всім користувачам, з якими він зв'язаний. Користувач також забезпечує цілісність і дійсність відкритих ключів.

Е_k, D_k – мають вибиратися з повної множини випадково, порівняно ймовір-
но і незалежно, мають забезпечувати однозначну оборотність прямого та зворотного перетворення. Відповідним чином засвідчений відкритий ключ є сертифікатом (див. п. 1.1.1).

Значення Е_k, D_k для практичних використань мають задовольняти умову

,

де

.

Порівняння (1.54) можна звести до Діафантового рівняння:

ax+by=1. (1.56)

Це діафантове рівняння – нормоване, тому що справа коефіцієнт дорівнює 1; a, b – цілочисельні коефіцієнти, х, у – невідомі. Порівняння (1.54) можна подати у вигляді:

, (1.57)

k – деяке невідоме число.

Діафантове рівняння (1.56) має цілочисельне розв’язання, якщо a і b цілочисленні, і , a і b взаємно прості. Подавши (1.57) у вигляді

, (1.58)

отримаємо а = j (N), x =(- k), b = E_k, y = D_k.

Якщо E_k сформувати випадково, то а та b – відомі числа, а х та y – невідомі, що підлягають визначенню.

Найбільш швидке розв’язання (1.58) дає застосування ланцюгових дробів, які дозволяють визначити х та у як

, (1.59)

де m – порядок ланцюгового дробу, a і b – параметри ланцюгового дробу.

Знаходимо параметри:

a / b подається у вигляді ланцюгового дробу

, (1.60)

μ - порядок ланцюгового дробу, перший коефіцієнт, у якого залишок дорівнює 0.

Значення (а ₀, b ₀) та (а ₁, b ₁) визначаються як

,

.

Значення (а ₂, b ₂), (а ₃, b ₃) і т.д. визначаються рекурентно відповідно до правил

. (1.61)

Середнє число ітерацій в (1.60), тобто , можна визначити як [16]

.

1.3.3 Методи криптоаналізу RSA

В системі RSA криптоаналіз метою якого є визначення особистого (таємного) ключа, наприклад Е_к ключа ключової пари (), де D_к є відкритий ключ, може бути здійснений таким чином:

1. Зловмисник отримує системні параметри (однакові для обох користувачів) та відкритий ключ Ек.

2. Використовуючи спеціальну криптоаналітичну систему здійснюється факторизація модуля , в результаті чого він визначає прості числа та .

3. Розраховується значення функції Ойлера

.

4. Використовуючи методику, наведену в (1.49), здійснюється розв’язок порівняння .

Взагалі, найбільш простим методом криптоаналізу є підбір ключової пари (), тобто при відомих визначається Dк.

Нехай має довжину тоді, якщо , то

.

Область існування для ключа можна визначити, як всі цілі числа, що не перевищують та є взаємопростими, тобто . Підбір із повної множини є задачею, що набагато складніша, ніж алгоритм, заданий вище пп. 1-4.

Проведені дослідження підтвердили, що необхідний рівень стійкості в RSA забезпечується в тому випадку, якщо прості числа є сильними.

Покладемо, що як використовуються прості числа, тоді справедливе таке: , , .

Використовуючи теорему Чебишева [17], визначимо кількість особистих ключів, як

. (1.62)

Приклад 1. Визначимо число простих 1024 бітних чисел

.

Щоб розв’язати цю задачу методом тотального перебору не вистачить енергії сонця.

Згідно з сучасними поглядами найбільш перспективними методами криптоаналізу є методи, що базуються на пп. 1-4, що розглянуті вище. При цьому найбільш складна задача факторизації модуля N вимагає найбільших ресурсів і суттєво залежить від використовуваного методу. На сьогодні відомо та апробовано такі методи факторизації:

- спробного поділу;

- -Поларда і -1 Поларда;

- Ленстра, з використанням еліптичних кривих;

- квадратичне решето;

- загальне та спеціальні решета числового поля.

Одним із перспективних методів факторизації є метод, що реалізований у вигляді квадратичного решета. В таблиці 1.1 показано результати, які отримано в світі при розв’язку задач факторизації.

Для великих з великими простими множниками розкладання на множники є серйозною проблемою, але не настільки, як потрібно. Разючою ілюстрацією цього може служити наступна історія. У 1977 році три винахідники алгоритму RSA наважилися запропонувати читачам популярного журналу Scientific American розкрити шифроване повідомлення, яке вони розмістили в розділі «Математичні ігри» Мартіна Гарднера (Martin Gardner). За розшифровку цього повідомлення вони запропонували нагороду в 100 дол. За їхніми оцінками, задача не могла бути вирішена раніше, ніж приблизно через 40 квадрильйонів років [10,18]. Але в квітні 1994 року група користувачів Internet зажадала виплати призової суми після всього восьми місяців спільної роботи в Internet. У запропонованій задачі використовувався відкритий ключ довжиною в 129 десяткових знаків (довжина модуля N), що дорівнює приблизно 428 бітам. З квітня 1996 р. до квітня 2003 р. були вирішені задачі для RSA-130 [18], RSA-140, RSA-155, RSA-160. RSA-150 залишився нефакторизованим та в подальшому відкликаний із переліку задач. Останньою з вирішених задач є задача для RSA-576, у якій довжина ключа дорівнює 576 бітів. За вирішення цієї задачі команда отримала 10000 дол. Задачі факторизації RSA від RSA-640 до RSA-2048 залишаються відкритими, з нагородами відповідно від 20000 дол. до 200000 дол. Наявні на сьогодні результати наведено в табл. 1.1. Одиницею вимірювання складності задачі в даному випадку є MIPS-рік – обсяг роботи, виконуваної протягом року процесором, що здійснює обробку одного мільйона команд у секунду, що приблизно еквівалентно виконанню 3*10¹³ команд. Так, машина на базі Pentium з частотою 2000 МГц показує швидкість 500 MIPS.

Таблиця 1.1 – Прогрес у розв’язку задач факторизації модуля N

Число десяткових знаків	Приблизне число бітів	Дата вирішення	Необхідне число MIPS-літ	Використаний алгоритм
		Квітень 1991 р.		Квадратичне решето
		Квітень 1992 р.		Квадратичне решето
		Червень 1993 р.		Квадратичне решето
		Квітень 1994 р.		Квадратичне решето
		Квітень 1996 р.		Загальне решето числового поля
		Лютий 1999 р.		Загальне решето числового поля
		Відкритий	Відкликаний
		Серпень 1999 р.		Загальне решето числового поля
		Квітень 2003 р.		Загальне решето числового поля
		Грудень 2003 р.		Загальне решето числового поля
		Відкритий
		Відкритий
		Відкритий
		Відкритий
		Відкритий
		Відкритий
		Відкритий

До 1994 року для розкладання на множники застосовувався підхід, відомий за назвою методу квадратичного решета. Для криптоаналізу RSA-130, RSA-140, RSA-155, RSA-160, RSA-576 використовувався новий алгоритм, названий методом решета в полі чисел загального виду, що дозволило скоротити обсяг обчислювальних зусиль майже на 10% у порівнянні з тими, що були потрібні раніше для аналізу RSA-129.

Погроза ключам великої довжини тут подвійна: безупинне зростання обчислювальної потужності сучасних комп'ютерів і безупинне удосконалення алгоритмів розкладання на множники.

Розглянемо двійкове решето, яке відповідно до сучасних поглядів є найбільш швидким при довжині модуля не більше ніж 120 десяткових цифр.

Сутність:

Нехай є цілі х та у, такі, що:

. (1.63)