ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.06.2024
Просмотров: 20
Скачиваний: 0
Асиметричні криптосистеми
План
1 Концепція криптосистеми з відкритим ключем
2 Односпрямовані функції
3 Криптосистема шифрування даних RSA
4 Схема шифрування Поліга - Хеллмана
5 Алгоритм шифрування Ель Гамаля
6 Схема шифрування Рабіна
1 Концепція криптосистеми з відкритим ключем
Ефективними системами криптографічного захисту даних є асиметричні криптосистеми, які називають також криптосистемами з відкритим ключем. У таких системах для зашифрування даних використовується один ключ, а для розшифрування – інший ключ (звідси й назва – асиметричні). Перший ключ є відкритим і може бути опублікований для використання всіма користувачами системи, які зашифровують дані. Розшифрувати дані за допомогою відкритого ключа неможливо.
Для розшифрування даних одержувач зашифрованої інформації використовує другий ключ, що є таємним. Зрозуміло, таємний ключ не може бути визначений, виходячи з відкритого ключа.
Узагальнена схема криптосистеми з відкритим ключем показана на рисунку 1. В цій криптосистемі застосовують два різних ключі: – відкритий ключ відправника A; – таємний ключ одержувача В.
Генератор ключів доцільно розташовувати на стороні одержувача B, щоб не пересилати таємний ключ незахищеним каналом. Значення ключів і залежать від початкового стану генератора ключів.
Розкриття таємного ключа за значенням відомого відкритого ключа повинно бути обчислювально нерозв’язаною задачею.
Рисунок 1 – Узагальнена схема асиметричної криптосистеми
Характерні риси асиметричних криптосистем:
-
Відкритий ключ і криптограма C можуть бути відправлені по незахищених каналах, тобто зловмиснику відомі значення та C.
-
Алгоритми шифрування () і розшифрування є відкритими.
Захист інформації в асиметричній криптосистемі засновано на таємності ключа .
У.Діффі та М.Хеллман сформулювали вимоги, які забезпечують безпеку асиметричної криптосистеми:
-
Обчислення пари ключів (, ) одержувачем B на основі початкової умови повинно бути простим.
-
Відправник A, знаючи відкритий ключ і повідомлення М, може легко обчислити криптограму
. (4.1)
3 Одержувач В, використовуючи таємний ключ і криптограму C, може легко відновити вихідне повідомлення
. (4.2)
4 Зловмисник, знаючи відкритий ключ , при спробі обчислити таємний ключ натрапляє на непереборну обчислювальну проблему.
5 Зловмисник, знаючи пари (, C), при спробі обчислити вихідне повідомлення M натрапляє на непереборну обчислювальну проблему.
2 Односпрямовані функції
Концепція асиметричних криптографічних систем з відкритим ключем заснована на застосуванні односпрямованих функцій. Неформально односпрямовану функцію можна визначити в такий спосіб.
Нехай Х і Y – деякі довільні множини. Функція є односпрямованою, якщо для всіх можна легко обчислити функцію , але для більшості досить складно одержати значення , таке, що (при цьому вважають, що існує принаймні одне таке значення ).
Основним критерієм віднесення функції до класу односпрямованих функцій є відсутність ефективних алгоритмів зворотного перетворення .
Як приклад односпрямованої функції розглянемо множення цілих чисел. Пряма задача – обчислення добутку двох дуже великих цілих чисел й , тобто знаходження значення
(4.3)
є простою задачею для ЕОМ.
Зворотна задача – розкладання на множники великого цілого числа, тобто знаходження дільників і великого цілого числа , є практично нерозв’язною задачею при досить великих значеннях .
За сучасними оцінками теорії чисел при цілому й для розкладання числа буде потрібно близько 1023 операцій, тобто задача практично нерозв’язна.
Наступний характерний приклад односпрямованої функції – це модульна експонента з фіксованими підставою й модулем. Нехай й – цілі числа, такі, що . Визначимо множину
.
Тоді модульна експонента з основою за модулем N являє собою функцію
,
де – ціле число, .
Існують ефективні алгоритми, що дозволяють досить швидко обчислити значення функції .
Якщо , то, природно, .
Тому, задачу обернення функції називають задачею знаходження дискретного логарифма або задачею дискретного логарифмування.
Задача дискретного логарифмування формулюється в такий спосіб.
Для відомих цілих знайти ціле число , таке, що
.
Алгоритм обчислення дискретного логарифма за прийнятний час поки не знайдена, тому модульна експонента вважається односпрямованою функцією.
За сучасними оцінками теорії чисел при досить великих цілих числах A2664 й N2664 рішення задачі дискретного логарифмування (знаходження показника ступеня для відомого ) потребує близько 1026 операцій, тобто ця задача має в 103 разів більшу обчислювальну складність, ніж задача розкладання на множники. Різниця в оцінках складності задач зростає при збільшенні довжини чисел.
Відзначимо, що поки не вдалося довести, що не існує ефективного алгоритму обчислення дискретного логарифма за прийнятний час. Виходячи з цього, модульна експонента віднесена до односпрямованих функцій умовно, що однак не заважає з успіхом застосовувати її на практиці.
Другим важливим класом функцій, що використовуються при побудові криптосистем з відкритим ключем, є односпрямовані функції з "потаємним ходом".
Функція належить до класу односпрямованих функцій з "потаємним ходом" у тому випадку, якщо вона є односпрямованою й, крім того, можливо ефективне обчислення зворотної функції, якщо відомо "потаємний хід" (таємне число, рядок або інша інформація, що асоціюється з даною функцією).
Як приклад односпрямованої функції з "потаємним ходом" можна вказати модульну експоненту з фіксованими модулем і показником ступеня, що використовується в криптосистемі RSA. Змінна основа модульної експоненти використовується для вказівки числового значення повідомлення М або криптограми С.
3 Криптосистема шифрування даних RSA
Алгоритм RSA запропонували в 1978 р. Р.Райвест (Rivest), А.Шамір (Shamir) і А.Адлеман (Adleman). Алгоритм одержав свою назву від перших букв прізвищ його авторів. Алгоритм RSA став першим повноцінним алгоритмом з відкритим ключем, що може працювати як у режимі шифрування даних, так і у режимі електронного цифрового підпису.
Надійність алгоритму ґрунтується на труднощі факторизації великих чисел і труднощі обчислення дискретних логарифмів.
У криптосистемі RSA розглядають: відкритий ключ ; таємний ключ ; повідомлення й криптограма належать множині цілих чисел
, (4.4)
де - модуль
. (4.5)
Тут й – випадкові великі прості числа. Для забезпечення максимальної безпеки вибирають і однакової довжини й зберігають у секреті.
Множина з операціями додавання та множення за модулем утворює арифметику за модулем .
Відкритий ключ вибирають випадково так, щоб виконувалися умови:
(4.6)