Концепція

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

Розділ V

Підсумок

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

· Є ефективні тести, за допомогою яких легко розпізнати, простим чи складеним е задане число. Як наслідок, для практичних потреб легко вибрати просте число заданого порядку.

· Є ефективний алгоритм для добування квадратних коренів за простим модулем р. У випадках р = 4m + 3 і р = 8m+5 алгоритм працює детермінованим чином і є особливо простим.

· Невідомо ефективних алгоритмів для факторизації і дискретного логарифмування - ці задачі на сьогодні є важкими.

· Є ефективне зведення добування квадратних коренів за модулем п = pq до факторизації числа n = pq, iнавпаки - факторизації до добування кореня.

· Еквівалентними задачами є також обчислення функції Ойлера ф(п) від п = pq і факторизація числа n = pq. Більше того, щоб факторизувати n = pq, досить мати довільне кратне числа ф(п) = НСК(р-l,q-1).

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

ЛЕКЦІЯ 16

1976 рік відкрив сучасний етап у криптографії. Для новітньої криптографії характерною рисою єпоява принципово нових криптографічних задач, а також принципово нових розв'язків задач класичних. Тому часто говорять про революцію у галузі криптографії. Поступ, що відбувся у 1976 році, пов'язаний з іменами американських математиків Вайтфілда Діффі та Мартіна Гелмана, а також Ральфа Меркле, які розвинули ідеологію відкритого ключа.

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

Пригадаємо нашу базову криптографічну схему з пункту 1.1.1. Вона передбачає поняття ключа К, який використовується як при шифруванні, так і при дешифруванні. При розгляді у § II.3 афінних шифрів ми дещо модернізували нашу термінологію. Безпосередньо за допомогою ключа К здійснювалось лише шифрування, а для дешифрування використовувався дешифруючий ключ К'. Оскільки К¹ = К'(К) легко отримувався з К, то такий поділ ключа був не принциповим відходом від початкової схеми, а лише справою домовленості та зручності. В такому контексті ключ К природно назвати шифруючим. Для повідомлення М і криптотексту С матимемо співвідношення С = Ек(М) і М = Dк'(М), де К і К' — шифруючий і дешифруючий ключі, а Е і D — алгоритми шифрування та дешифрування, відповідно.

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

Поняття криптосистеми з відкритим ключем включає такі об'єкти (див. малюнок 1):

Малюнок 1. Нова криптографічна схема.

Алфавіт А, в якому записуються повідомлення (відкриті тексти), і алфавіт В, в якому записуються криптотексти.
Простір ключів К. (множина слів у деякому алфавіті).
Алгоритм генерування ключів. Це поліноміальний ймовірнісний алгоритм, який на вході k, де k N — записаний в унарній системі параметр надійності, видає випадкову пару К, К'К. К називається відкритим ключем і використовується для шифрування, а К' називається таємним ключем і використовується для дешифрування.
Поліноміальний детермінований алгоритм шифрування Е, який отримує на вхід повідомлення М і відкритий ключ К, а видає криптотекст С, що записуємо як С = Е_к(М).

· Поліноміальний детермінований алгоритм дешифрування D, який
отримує на вхід криптотекст С і таємний ключ К', а видає відкритий текст С, що записуємо як М = Dк'(C).

Перелічені алгоритми мають задовольняти такі умови:

· Якщо пара (К, К') породжена алгоритмом генерування ключів, то з С = Ек(М) випливає М = Dk’> (С) для будь-якого відкритого текту М.

· Немає (чи, принаймні, невідомо) жодного ефективного алгоритму, який за відомими С = Ек(М) і К знаходив би М.

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

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

Криптосистеми з відкритим ключем ще називають асиметричними. В цьому контексті класичні криптосистеми називають симетричними.

Тепер з'ясуємо переваги нової криптографічної схеми над старою. Уявімо комунікаційну мережу, якою користуються п абонентів — Аліса, Боб, Вітольд, Габріеля,... Припустимо, що кожна пара абонентів може мати свої маленькі таємниці і хоче мати можливість спілкуватися таємно від решти абонентів. Оскільки всіх пар є п(п — 1)/2, то саме таку кількість ключів ми потребуємо, коли послуговуємося старою симетричною схемою. Нова асиметрична схема дозволяє влаштувати довірливе спілкування в мережі оптимальнішим чином. Кожен абонент, власноручно або через менеджера мережі, генерує власну пару ключів (К, К'). Аліса стає власником пари ключів (К_A, К'_А), Боб — (К_Б, К'_Б) і т.д. Кожен абонент свій приватний ключ зберігає в таємниці, в той час як список всіх відкритих ключів (К_А, k_Б, k_В, K_Г,...) е у загальному доступі. Коли Боб хоче послати Алісі повідомлення М, він посилає їй криптотекст С = Ек_А(М). Оскільки тільки Аліса знає таємний ключ К'_А, лише вона здатна дешифрувати С. Таким чином, таємницю листування збережено з використанням лише п пар відкритого та таємного ключів, на противагу до необхідних раніше п(п — 1)/2 ключів.

Наступні параграфи присвячені конкретним втіленням описаної вище схеми, а також її модифікаціям.

ЛІТЕРАТУРА

Піонерські роботи Діффі і Гелмана, та Меркле опубліковані в [20] та [119]. Цікавим вступом до предмету може служити ретроспективний огляд [19] (див. також [21]). У подальшому викладі ми не торкаємось класу криптосистем з відкритим ключем, пов'язаних із задачею про рюкзак. Про ці криптосистеми та успіхи в і'х криптоаналізі йдеться в [10].

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Первісні корені за простим модулем	\|	Система Рабіна

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.