Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Концепція

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

Розділ 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. Нова криптографічна схема.

  • Алфавіт А, в якому записуються повідомлення (відкриті тексти), і алфавіт В, в якому записуються криптотексти.
  • Простір ключів К. (множина слів у деякому алфавіті).
  • Алгоритм генерування ключів. Це поліноміальний ймовірнісний ал­горитм, який на вході 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. Економічні проблеми підприємництва. Концепція та шляхи їх вирішення




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

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

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

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


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