Етапи створення і розвитку асиметричних крипто перетворень НШ.

 

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

Основною особливістю RSA крипто системи є її асиметричність, коли ключ зашифрування К^з не співпадає з ключем розшифрування К^р, тобто

, (10.1)

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

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

У 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 дол. Відповідні результати наведені в табл. 10.4. Одиницею вимірювання складності задачі в даному випадку є MIPS-рік – обсяг роботи, виконуваної протягом року процесором, що здійснює обробку одного мільйона команд у секунду, що приблизно еквівалентно виконанню 3*10¹³ команд. Так, машина на базі Pentium з частотою 2000 МГц показує швидкість 500 MIPS.

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

 

 

Для порівняльного аналізу в таблиці 10.5 результати досягненm в області крипто аналізу з зазначенням довжини ключа, часу, який був витрачений на здійснення крипто аналізу та року коли було здійснено крипто аналіз. Одиницею виміру тимчасова складність в MIPS-Year та просторова складність у вигляді обсягу пам’яті, що була використана в процесі здійснення крипто аналізу[7].

Таблиця 10. 5

Досягнення в здійсненні крипто аналізу відносно асиметричних криптосистем

Рік	Довжина ключа, біт	Час,MIPS-Year	Пам'ять ОЗУ/HDD, Гб
RSA
			0,064/2,3
		0,128*106	1/35
		4*106	5/1000
DSA
			0,256 /5
		2,775*108	1/35*
EC-DSA
			1/400
			0,512/600
NTRU
	N = 167	2*106	2/150

Наведені в табл.. 10.5 дані підтверджують, що асиметричні крипто перетворення скоріше є ймовірно стійкими, розвиток спеціальних розділів математики та збільшення потужності крипто аналітичних систем дозволяють компрометувати їх з часом. Як правило, виходом із такої ситуації є збільшення розмірів загальних параметрів та ключів, або заміна більш стійкими крипто перетвореннями[ ].

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

 

Необхідно відмітити, що згідно вимог нормативних документів та міжнародних стандартів в інформа­ційних технологіях повинні надаватися послуги причетності джерела та одержу­вача інформації (спостережливість). Причетність джерела, тобто авторство може бути забезпечено за рахунок застосування ЦП. Складніше забезпечити причет­ність одержувача. Ця задача може бути розв’язана за рахунок використання на­правлених шифрів.

Особливістю крипто перетворень типу НШ є такі:

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

зворотне криптографічне перетворення виконується з використанням особистого ключа .

Ключова пара (К , К ) повинна бути випадковою та вибиратись із повної множини дозволених для використання ключових пар, причому

(1)

Згідно вимог нормативних документів та міжнародних стандартів в інформа­ційних технологіях повинні надаватися послуги причетності джерела та одержу­вача інформації (спостережливість). Причетність джерела, тобто авторство може бути забезпечено за рахунок застосування ЦП. Складніше забезпечити причет­ність одержувача. Ця задача може бути розв’язана за рахунок використання на­правлених шифрів.

Особливість крипто перетворень типу НШ:

пряме з використанням відкритого ключа .

зворотне з використанням особистого ключа .

Ключова пара (К , К ) повинна бути випадковою та вибиратись із повної множини дозволених для використання ключових пар, причому

Відомий ряд методів побудування Криптографічних систем направленого шифрування. Основними з них є такі:

1) Метод складання рюкзака [ ]. Необхідно вкласти в рюкзак предмети з різною вагою, але щоб вага рюкзака залишалася постійною. Це не стійка система.

2) У 1978р. була опублікована стаття, у якій був запропонований алгоритм RSA направленого шифрування. Він закріплений в міжнародному стандарті ISO 11166-1,2. Крім того в США він закріплений в стандарті ANSI Х10.31.

3) У 1985р. Єль - Гамаль запропонував нову схему НШ Є-Г. Всі ці алгоритми були запатентовані. На сьогодні рекомендовано до застосування стандарти Х10.30 та у міжнародних стандартах ISO/IEC 1170-3 ISO/IEC 15946-10.

 

В

 

10.3 Крипто перетворення НШ в кільцях (RSA)

В 10.2, по суті, розглянуто етапи створення та певні властивості RSA направленого шифру. В цьому підрозділі розглянемо сутність RSA направленного шифру.

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

, (10.2 1.49)

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

, (10.3 1.50)

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

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

. (10.4 1.51)

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

, (10.5 1.52)

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

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

. (10.6 1.53)

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

, (10.7 1.54)

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

= .

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

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

, (10.8 1.55)

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

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

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

 

Генерування асиметричної ключової пари. Система 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. (10.9 1.56)

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

, (10.10 1.57)

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

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

, (10.11 1.58)

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

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

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

, (10.12 1.59)

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

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

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

, (10.13 1.60)

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

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

,

.

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

. (10.14 1.61)

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

.

 

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

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

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

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

.

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

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

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

.

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

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

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

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

. (10.15 1.62)

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

.

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

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

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

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

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

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

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

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

10.4 Проблемні питання крипто перетворень типу RSA.

Існує ряд проблемних питань теорії та практики RSA. В першу чергу до них необхідно віднести такі.

1). Є публікації в яких стверджується існування та запропоновано один із варіантів якби «поліноміального» методу факторизації модуля. Більш детальніше ці результати розглядаються в 9 розділі.

2). Отримані теоретичні та практичні результати факторизації, перше за все у вигляді спеціального решета числового поля та загального решета числового поля, якими підтверджено субекспоненціальний характер складності факторизації. Так для двійкового та загального решіт числового поля складність крипто аналізу може бути оцінена як[11, 12]:

, (10.16 18)

– параметри методу. Наприклад, для квадратичного решета δ=1,96; ν=1/3, спеціального решета числового поля δ=1,92; ν=1/10.

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

4) Збільшення довжини ключів практично до довжини модуля, що викликає підвищення складності прямих та зворотних криптографічних перетворень, а також проблемні питання з форматами та уніфікацією.

5) Числа P і Q мають бути не просто простими, а «сильно» простими числами, наприклад, мати вигляд:

P=2R+1, (10.17 17)

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

6) Для забезпечення стійкості при побудові параметрів та ключів необхідно також:

- відбраковувати ключі-близнята, тобто відмовлятися від ключової пари у якої E_k = D_k;

- відмовлятися від простих чисел P та Q, які близькі за значенням, тобто P»Q;

- відслідковувати можливу появу блоків повідомлень, що не зашифровуються, та приймати відповідні зміни в повідомленні тощо.