• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Концепція

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

Розділ 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].

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

1. Абстрактна небезпека і концепція допустимого ризику.
2. Аналітична психологія. Концепція Карла Юнга
3. Англійська педагогіка XVII ст. Педагогічна концепція Дж.Локка
4. Витратна концепція оцінки потенціалу підприємства
5. Витратна концепція оцінки потенціалу підприємства
6. Відповідно до розділу 5 Тимчасового регламенту Кабінету Мі­ністрів України концепція повинна мати шість розділів.
7. Вітчизняна концепція витрат виробництва і прибутку.
8. Геоцентрична концепція.
9. Гуманітарно-демократичний напрям (концепція).
10. Економічна концепція вартості відображає погляд ринку на вигоди, що придбаваються тим, хто стає власником даних товарів або користується даними послугами
11. Економічна концепція Прудона.
12. Економічні проблеми підприємництва. Концепція та шляхи їх вирішення

Переглядів: 650