МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
КонцепціяКриптосистеми з відкритим ключем Розділ 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 афінних шифрів ми дещо модернізували нашу термінологію. Безпосередньо за допомогою ключа К здійснювалось лише шифрування, а для дешифрування використовувався дешифруючий ключ К'. Оскільки К1 = К'(К) легко отримувався з К, то такий поділ ключа був не принциповим відходом від початкової схеми, а лише справою домовленості та зручності. В такому контексті ключ К природно назвати шифруючим. Для повідомлення М і криптотексту С матимемо співвідношення С = Ек(М) і М = Dк'(М), де К і К' — шифруючий і дешифруючий ключі, а Е і D — алгоритми шифрування та дешифрування, відповідно. У всіх криптосистемах, які ми розглядали досі, подібно до згаданого афінного шифру дешифруючий ключ знаходився за шифруючим ефективно. Раніше ми (як і все криптографічне співтовариство до 1976 року) й не замислювались, що такий стан речей можна змінити, і то з неабиякою користю. А якраз в допущенні того, що знаходження К' за К може бути важким, і полягає ідея, яка визначила подальший напрям розвитку криптографії. Поняття криптосистеми з відкритим ключем включає такі об'єкти (див. малюнок 1):
Малюнок 1. Нова криптографічна схема.
· Поліноміальний детермінований алгоритм дешифрування D, який Перелічені алгоритми мають задовольняти такі умови: · Якщо пара (К, К') породжена алгоритмом генерування ключів, то з С = Ек(М) випливає М = Dk’> (С) для будь-якого відкритого текту М. · Немає (чи, принаймні, невідомо) жодного ефективного алгоритму, який за відомими С = Ек(М) і К знаходив би М. Остання умова забезпечує надійність криптосистеми навіть тоді, коли із відкритого ключа К не робиться таємниці. З цієї умови випливає зокрема, що немає ефективного алгоритму знаходження за К такого К', що пара (К, К') могла б бути породженою алгоритмом генерування ключів. Зауважимо, що коли відкритий ключ є доступним для суперника, останній має достеменно ті ж можливості криптоаналізу, які для традиційних криптосистем називалися атакою з вибраним відкритим тектом. Як і раніше, сильнішим видом криптоаналізу залишається атака з вибраним криптотекстом. Криптосистеми з відкритим ключем ще називають асиметричними. В цьому контексті класичні криптосистеми називають симетричними. Тепер з'ясуємо переваги нової криптографічної схеми над старою. Уявімо комунікаційну мережу, якою користуються п абонентів — Аліса, Боб, Вітольд, Габріеля,... Припустимо, що кожна пара абонентів може мати свої маленькі таємниці і хоче мати можливість спілкуватися таємно від решти абонентів. Оскільки всіх пар є п(п — 1)/2, то саме таку кількість ключів ми потребуємо, коли послуговуємося старою симетричною схемою. Нова асиметрична схема дозволяє влаштувати довірливе спілкування в мережі оптимальнішим чином. Кожен абонент, власноручно або через менеджера мережі, генерує власну пару ключів (К, К'). Аліса стає власником пари ключів (КA, К'А), Боб — (КБ, К'Б) і т.д. Кожен абонент свій приватний ключ зберігає в таємниці, в той час як список всіх відкритих ключів (КА, kБ, kВ, KГ,...) е у загальному доступі. Коли Боб хоче послати Алісі повідомлення М, він посилає їй криптотекст С = ЕкА(М). Оскільки тільки Аліса знає таємний ключ К'А, лише вона здатна дешифрувати С. Таким чином, таємницю листування збережено з використанням лише п пар відкритого та таємного ключів, на противагу до необхідних раніше п(п — 1)/2 ключів. Наступні параграфи присвячені конкретним втіленням описаної вище схеми, а також її модифікаціям. ЛІТЕРАТУРА Піонерські роботи Діффі і Гелмана, та Меркле опубліковані в [20] та [119]. Цікавим вступом до предмету може служити ретроспективний огляд [19] (див. також [21]). У подальшому викладі ми не торкаємось класу криптосистем з відкритим ключем, пов'язаних із задачею про рюкзак. Про ці криптосистеми та успіхи в і'х криптоаналізі йдеться в [10]. Читайте також:
|
||||||||
|