2. Асиметричні криптосистеми. Методи та засоби формування загальносистемних параметрів та генерування ключів. Аналіз стійкості та складності асиметричних криптографічних перетворень

2.1. Мета роботи

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

2.2. Методичні вказівки до організації самостійної роботи студентів

При підготовці до лабораторної роботи необхідно:

- вивчити основні поняття і визначення з питань несиметричних дискретних перетворень;

- вивчити криптографічний алгоритм RSA;

- ознайомитися з описом лабораторної роботи і її програмним забезпеченням;

- вивчити порядок роботи на ЕОМ;

- підготувати бланк звіту;

- підготувати відповіді на контрольні питання.

2.3. Короткі відомості з теорії.

Концепція криптографії з відкритими ключами була висунута Уїтфілдом Діффі (Whitfield Diffie) і Мартіном Хеллманом (Martin Hellman), і незалежно Ральфом Мерклом (Ralph Merkle). Їх внеском в криптографію було переконання, що ключі можна використовувати парами - ключ шифрування і ключ дешифрування - і що може бути неможливо одержати один ключ з іншого. Діффі і Хеллман вперше представили цю ідею на Національній комп'ютерній конференції (National Computer Conference) 1976 року, через декілька місяців була опублікована їх основоположна робота "New Directions in Cryptography" ("Нові напрями в криптографії").

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

Небагато алгоритмів є і стійкими, і практичними. Ці алгоритми засновані на одній з важких проблем. Деякі з них підходять тільки для розподілу ключів. Інші підходять для шифрування (і для розподілу ключів). Треті корисні тільки для цифрових підписів. Тільки три алгоритми добре працюють як при шифруванні, так і для цифрового підпису: RSA, EIGamal і Rabin. Всі ці алгоритми шифрують і дешифрують дані набагато повільніше, ніж симетричні алгоритми. Звичайно їх швидкість недостатня для шифрування великих об'ємів даних.

Гібридні криптосистеми дозволяють прискорити події: для шифрування повідомлення використовується симетричний алгоритм з випадковим ключем, а алгоритм з відкритим ключем застосовується для шифрування випадкового сеансового ключа.

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

, (2.1)

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

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

, (2.2)

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

, (2.3)

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

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

. (2.4)

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

, (2.5)

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

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

. (2.6)

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

, (2.7)

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

= .

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

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

, (2.8)

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

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

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

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

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

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

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

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

,

де

.

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

ax+by=1. (2.9)

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

, (2.10)

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

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

, (2.11)

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

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

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

, (2.12)

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

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

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

, (2.13)

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

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

,

.

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

. (2.14)

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

.

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

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

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

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

.

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

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

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

.

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

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

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

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

. (2.15)

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

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

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

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

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

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

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

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

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

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

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

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

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

1) автентифікацію абонента, тобто процедуру встановлення дійсності абонента, що хоче підключитися до мережі або одержати захищену інформацію;

2) автентифікацію мережі, тобто процедуру встановлення дійсності даної мережі, до якої отриманий доступ;

3) автентифікацію повідомлень у вигляді встановлення дійсності змісту, отриманого по каналах зв'язку повідомлення і рішення питань про авторство цього повідомлення;

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

Автентифікація абонента може бути здійснена такими способами:

- контроль об'єкта - перевірка паспорта, пропуску, спеціальної картки;

- перевірки деяких знань - пароля, ключа;

- перевірка деяких дій (своєрідність "почерку" оператора і т.п.) ;

- фізіологічні перевірки (відбитки пальців, колір роговиці очей та ін.).

Захист об'єктів від несанкціонованого проникнення - предмет широкого дослідження. Найбільший інтерес представляє рішення задачі автентифікації повідомлень.

По загальноприйнятій моделі вважається, що повідомлення в каналі зв'язку доступно криптоаналітику, але суттєвий зміст повідомлення криптоаналітик зможе одержати лише після виконання криптоаналізу. При цьому можливі наступні ситуації:

1) зловмисник, знаючи лише загальну схему автентифікацїї, яка використовується передавачем і приймачем,може послати помилкове повідомлення приймачу, у надії,що той інтерпретує його як справжнє, у той час як передавач повідомлення не посилав (у цьому випадку зловмисник здійснює нав'язування за допомогою імітації повідомлення);

2) інша стратегія криптоаналітика полягає в підміні повідомлення. При цій стратегії він перехоплює справжнє повідомлення і посилає замість нього помилкове, їм сформоване або модифіковане повідомлення;

3) "зловмисник" повторює раніше передане повідомлення, що передавач А посилав приймачу.

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

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

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

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

Цифровий підпис являє собою зашифровану сукупність даних, що складаються з:

- адреси відправника;

- адреси одержувача;

- підпису відправника;

- часу створення підпису;

- відомості про повідомлення (довжина файлу, контрольна сума і т.п.).

Цифровий підпис може бути реалізована за допомогою:

- симетричного шифрування;

- несиметричного шифрування.

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

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

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

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

Mi повідомлення

N1

N2

A

Li

Ks

Tv

повідомлення (файл) Цифровий підпис

довжиною К

Цифровий підпис (відкрита структура) включає:

N1 - адреса відправника ;

N2 - адреса одержувача ;

A - підпис відправника;

Li - довжина повідомлення;

Ks - контрольна сума Mi ;

Tv - час формування ЦПi.

До теперішнього часу обчислювально стійкими вважаються системи цифрового підпису, у яких N_j є число, що містить не менш 130 десяткових цифр. (На практиці застосовують 256, 512 і 1024 бітні модулі N_j).