![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
1.3.1 Імовірно стійка криптосистема з відкритими ключами
У 80-і роки ХХ століття широке розповсюдження отримала криптосистема з відкритими ключами відома на сьогодні, як RSA [12-15] система. Основною особливістю цієї системи є те, що в ній ключ зашифрування Кз не співпадає з ключем розшифрування Кр, тобто
, (1.48)
а знайти один ключ при відомому другому для відповідних значень загаль-носистемних параметрів можна не нижче ніж з субекспоненційною складністю. Хоч на сьогодні RSA криптосистема піддається нападкам і відносно неї даються різні прогнози, але вона проіснувала більше 25 років і дозволяє реалізувати направ-
лене шифрування, ЕЦП та слушні протоколи. Крім того, на наш погляд, RSA система дозволяє якісно реалізувати криптографічними методами таку основну функцію, як спостережливість, в змісті причетності відправника та отримувача. Так причетність відправника може бути забезпечена за рахунок здійснення цифрового підпису з використанням особистого (таємного) ключа, а перевірка цілісності та справжності підписаної інформації здійснюються з використанням особистого (публічного) ключа. Далі направлене шифрування може бути здійснене з використанням другої ключової пари, відкритий ключ отримувача якої застосовують для направленого шифрування, а особистий ключ застосовується для розшифрування повідомлення. Тому розглянемо цю класичну систему докладно.
RSA криптоалгоритм є блоковим, у ньому повідомлення М розбивається на блоки Мi, з довжиною блоку (на сьогодні 768 біт мінімум), реально 1024, 2048 і більше бітів. Блок криптограма Сі обчислюється за правилом
, (1.49)
де – є відкритий ключ прямого перетворення, N – модуль перетворення є добутком виду
, (1.50)
де в свою чергу P, Q – великі прості числа.
Якщо lp є довжина простого числа Р, наприклад в бітах, а lq – довжина простого числа 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 ¹ Dk, причому один з них має бути особистим, а другий – відкритим. Наприклад, Еk – особистий, а Dk – відкритий, якщо вони використовуються для ЕЦП і навпаки, якщо використовуються для направленого шифрування.
Усі параметри (N, P, Q) також поділяються на 2 класи: N – відкритий, P, Q – конфіденційні (секретні).
Сутність забезпечення моделі взаємної недовіри – кожен користувач генерує ключі сам собі. Особистий ключ залишає в себе і забезпечує його строгу конфіденційність. Відкритий ключ розсилає всім користувачам, з якими він зв'язаний. Користувач також забезпечує цілісність і дійсність відкритих ключів.
Еk, Dk – мають вибиратися з повної множини випадково, порівняно ймовір-
но і незалежно, мають забезпечувати однозначну оборотність прямого та зворотного перетворення. Відповідним чином засвідчений відкритий ключ є сертифікатом (див. п. 1.1.1).
Значення Еk, Dk для практичних використань мають задовольняти умову
,
де
.
Порівняння (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 = Ek, y = Dk.
Якщо Ek сформувати випадково, то а та b – відомі числа, а х та y – невідомі, що підлягають визначенню.
Найбільш швидке розв’язання (1.58) дає застосування ланцюгових дробів, які дозволяють визначити х та у як
, (1.59)
де m – порядок ланцюгового дробу, a і b – параметри ланцюгового дробу.
Знаходимо параметри:
a / b подається у вигляді ланцюгового дробу
, (1.60)
μ - порядок ланцюгового дробу, перший коефіцієнт, у якого залишок дорівнює 0.
Значення (а 0, b 0) та (а 1, b 1) визначаються як
,
.
Значення (а 2, b 2), (а 3, b 3) і т.д. визначаються рекурентно відповідно до правил
. (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*1013 команд. Так, машина на базі 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)
Дата публикования: 2015-01-14; Прочитано: 1174 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!