6.4 Асиметрична криптографія та цифровий підпис.

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

Асиметрична ж криптографія вирішує це питання кардинально інакше – по-перше, кількість ключів скорочується до . А симетричну криптографію застосовувати для конфіденційного зберігання інформації на своєму власному твердому диску неможливо.

При асиметричній криптографії кожний абонент інформаційного поля, володіє двома ключами – відкритим (відомий всім іншим абонентам) та закритим (відомий тільки йому та таким, що зберігається у суворій таємниці). Відкритий ключ використовується для відправки повідомлень і з його допомогою на основі спеціального алгоритму будь-хто може провести асиметричне шифрування яке необоротне без знання закритого документа. А ось дешифрувати повідомлення зможе тільки той, хто володіє закритим ключем. Тобто тільки законний одержувач.

Якщо асиметричну схему використовувати навпаки (тобто коли для шифрування задіяно закритий ключ), з невеликими доповненнями породила ще одну величезну галузь сучасної криптографії – електронно цифровий підпис (ЕЦП). Тут користувач обчислює контрольну суму повідомлення, шифрує її таємним ключем та приклеює шифрограму до повідомлення.

Під час створення електронного підпису під документом в неї закладається достатньо інформації, щоб будь який одержувач зміг засвідчитись за допомогою відкритого ключа відправника. Що тільки він міг підписати, як наслідок, відправити це повідомлення.

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

Зазначимо, що асиметричне шифрування та ЕЦП вирішують зовсім різні завдання: перше – забезпечення конфіденційності послання, друге – автентичність відправника та цілісність повідомлення. Тому цілком можливо і чисто використовують шифроване повідомлення. а потім його підпис за допомогою ЕЦП.

В основі будь якої схеми асиметричного шифрування або інверсної їй схеми ЕЦП лежить конкретна тяжковирішуєма математична задача. При цьому до даної задачі насправді є спосіб знайти рішення, але для цього треба володіти деякою додатковою інформацією ( - таємні двері).

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

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

Під час формування ЕЦП процес іде дещо у іншому напрямку. Відправник листа додає до листа деяку частину закритого ключа у такому вигляді, щоб за нею неможливо було повністю відновити закритий ключ. Але цієї інформації достатньо, щоб допомогти будь кому бажаючому (тому, хто перевіряє ЕЦП) вирішити те саме рівняння, на базі якого побудована ця схема ЕЦП. У якості інших параметрів рівняння, той хто перевіряє підставляє контрольну суму отриманого листа та значення з відкритого ключа відправника. Якщо рівняння успішно розрішилося, тобто при підстановці всіх даних воно перетворилося у рівність, то це означає, що лист з цією контрольною сумою відправив саме той абонент, чий підпис під ним стоїть. Якщо ж рівність не вийшла. То на якомусь з етапів вийшов збій у каналі зв’язку або ж зловмисне збільшення банківського платежу в десять разів.

З практичних схем асиметричного шифрування найбільш відома схема , яка була винайдена трьома дослідниками ( ).

Перший етап будь якого асиметричного алгоритму – створення пари ключів для схеми складається з таких операцій:

• вибирають два великих простих (ті, що поділяються на одиницю та самих себе) числа та ;

• вибирають . Яке дорівнює ;

• вибирають довільне число , таке, що найбільший загальний подільник (НЗП) ( , тобто повинно бути взаємно простим з числом ;

• методом Евкліда вирішується в цілих числах рівняння . Тут невідомими є перемінні та - а метод Евкліда якраз і знаходить множину пар , кожна з яких є рішення рівняння у цілих числах;

• пара чисел - публікують як відкритий ключ. Число зберігають у суровій таємниці бо це і є закритий ключ який дозволяє читати всі послання, зашифровані за допомогою пари чисел ( ).

Другий етап є власно шифрування за допомогою відкритого ключа.

1. Відправник розбиває своє повідомлення на блоки, які дорівнюють біт, де квадратні дужки означають взяття цілої частини від дрібного числа. Такий блок може бути інтерпретований як число з діапазону (0; ).

2. Для кожного такого числа (назвемо його ) обчислюється вираз . Блоки і є зашифроване повідомлення.

Їх можна без остраху передавати відкритим каналом. Тому що операція піднесення до степеня за модулем простого числа є тією самою тяжковирішуємою математичною задачею.

Третій етап – дешифрування повідомлення за допомогою таємного ключа. Окремий випадок теореми Ейлера стверджує, що якщо число представити у вигляді добутку двох простих чисел та , то для будь якого має місце рівність:

.

Для дешифрування - повідомлень скористаємося цією формулою. Піднесемо дві його частини у ступінь ( ) . Після помноження обох частин рівності на отримаємо А тепер нагадаємо, як створювався відкритий та закритий ключі. Величина була підібрана за допомогою алгоритму Евкліда так, що , тобто . Як наслідок, у останньому виразі ступені на число ( ). Одержимо Тобто для того, щоб прочитати повідомлення , достатньо піднести його до ступеню за модулем : . Загальний вигляд системи наведено на рис. 6.22.

Рис. 6.22. Загальний вигляд системи

Слід підкреслити, що двома необхідними властивостями для будь якої асиметричної схеми є:

1. Неможливість прочитати повідомлення, знаючи тільки відкритий ключ.

2. Неможливість вирахувати закритий ключ за відкритим.

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

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

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

• числа та повинні містити в своєму розкладі на множники великі прості подільники (назвемо їх та );

• числа та також повинні містити в своєму розкладі на множники великі прості подільники (назвемо їх ), при цьому такі, щоб числа та також містили в своєму розкладі досить великі подільники;

• числа та повинні дуже близько співпадати за порядком довжини (це природня вимога в плані атаки повним перебором – потенційно зловмисник у цьому випадку першим знайде обов’язково менший подільник, і як наслідок, стійкість всієї схеми залежить від розміру саме меншого подільника). Але небажано, щоб вони виявились поруч один з одним за значенням.

• Таємний ключ не повинен у результаті процедури створ0ення ключів виявитися дуже маленьким. Якщо така умова випадково виконалась, треба „перевибрати” випадкове число та повторити процедуру обчислення ;

• Кожен абонент мережі повинен використовувати унікальне значення . Неприпустимо використання схеми, при якій супервізор ключів роздає абонентам пари , відповідаючи одному й тому ж , в надії, що абонент не зможе розкласти на множники без знання та . Це не так – за відомими та останнє розкладається на множники за поліноміальний час. Тобто у будь якого абонента такої мережі з’являється можливість читати повідомлення усіх інших користувачів.

У сучасній криптографії порогом розкриття схеми вважається довжина в 512 біт. Ця величина знаходиться на „межі довіри”. На сьогоднішній день спеціалізований чіп вартістю 10 млн.$ розкриває ключ довжиною 1024 біта за 1 рік, а чип вартістю 10 тис.$ ключ довжиною 512 біт за 10 хвилин.

Далі. Розглянемо приклад роботи схеми на невеликих числах. Зрозуміло, що ніяких додаткових вимог на вибір чисел та не висуваємо. Нехай а , тоді . У якості відкритого ключа виберемо число 7. таким чином весь відкритий ключ має вигляд . Обчислимо закритий ключ : рівняння має вигляд та в цілих числах рішення . Таким чином, закритий ключ є числом 23.

Нехай якийсь відправник бажає передати абоненту комбінацію біт , її числовий еквівалент . Підносимо 39 у ступінь відкритого ключа за модулем . Число 19 є шифрограма і воне передається каналом зв’язку. Одержувач після переходу повідомлення підносить його у ступінь . Первісне повідомлення таким чином відновлено.

Інверсія асиметричного алгоритму для отримання схеми цифрового підпису є самою простою схемою з усіх алгоритмів ЕЦП. Для формування електронного підпису відправник виконує над контрольною сумою документа тіж самі дії, що й при шифруванні, але використовує не відкритий ключ одержувача, а свій особистий закритий ключ, тобто . Відкритий та закритий ключі просто змінюються місцями. На приймальній стороні одержувач підносить підпис у ступінь відкритого ключа відправника і отримує (Згідно тих же формул, що й в асиметричному шифруванні ). Якщо значення, яке вийшло після піднесення у ступінь співпадає з вирахуваною незалежно на приймальній стороні контрольною сумою документа, то перевірка вважається виконаною, а документ справжнім. Ніхто, крім відправника . не знаючи , не може вирахувати такий підпис , щоб піднесення його в ступінь відкритого ключа дало потрібну контрольну суму – це такаж сама тяжковирішувальна задача, що й в асиметричному шифруванні . Тобто, спорядити документ таким підписом міг тільки дійсний Володар закритого ключа. Схема ЕЦП наведена на рис. 6.23.

Рис. 6.23. Схема ЕЦП

Використання таємного ключа для цифрового підпису, тобто розкриття деякої інформації про нього не зашкодить йому. Навіть перехопивши велику кількість підписаних повідомлень, зловмисник не зможе з їх допомогою вирахувати за поліноміальний час, а довжини ключа, який застосовується на цей час вистачить на декілька десятків років стійкості.

І все таки при користування ЕЦП, треба дотримуватися деяких правил: наприклад, ніколи не підписувати того, що не створював сам, а прийнято за правило підписувати тільки контрольну суму свого повідомлення, навіть якщо все воно таке мале, що розміщується в один блок перетворень . При цьому для таких цілей завжди використовуються тільки крипостійкі (необоротні) контрольні суми – так звані ХЕШ-функції. Вони не дають зловмиснику можливості сформувати документ так, щоб його контрольна сума співпала з бажаним значенням ( ).

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

Серед найбільш відомих практичних схем асиметричного шифрування є схема RSA, яку розробили в 1978 році Рональд Рівестом, Аді Шамір та Леонард Адельман. А також схеми ним Рабіна, Ель Гамальта та Марка Еліса.

Питання для самоперевірки

1. Що стало революційним кроком у розвитку криптографії?

2. Наведіть узагальнену схему класифікації шифрів.

3. ЩО таке абсолютна практична стійкість шифрів?

4. Назвіть рекомендовану довжину ключів для комерційних та державних потреб.

5.Яка характерна риса поточних шифрів.

6. Що використовується у якості бази при побудові поточних шифрів?

7.Яка відмінна риса існує при побудові блочних шифрів?

8. Які перетворення застосовуються у блочному шифруванні?

9.Що є однією з найбільш розповсюджених схем блочних шифрів?

10. Що є основою стандарту шифрування DES?

11. Назвіть характерні особливості шифру, створеного за ГОСТ 28147-89

12. Який алгоритм став переможцем конкурсу ASE у 2000 РОЦІ?

13. Яка характерна особливість асиметричного шифрування?

14. В чому різниця між асиметричним шифруванням та електро-цифровим підписом?

15. Назвіть практичні схеми асиметричного шифрування.

Розділ 7. Методи закриття мовних сигналів