Главная | Обратная связь | Поможем написать вашу работу!

Математичні основи криптографії

Великий вплив на розвиток криптографії зробили роботи американського математика Клода Шеннона, що з'явилися в середині XX століття. У цих роботах були закладені основи теорії інформації, а також був розроблений математичний апарат для досліджень в багатьох галузях науки, пов'язаних з інформацією. Більш того, прийнято вважати, що теорія інформації як наука народилася в 1948 році після публікації роботи К. Шенона "Математична теорія зв’язку").

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

Шифр заміни є простим, найбільш популярним шифром. Типовими прикладами є шифр Цезаря. Як видно з назви, шифр заміни здійснює перетворення заміни букв або інших "частин" відкритого тексту на аналогічні "частини" шифрованого тексту. Легко дати математичний опис шифру заміни. Нехай і - два алфавіти (відкритого і шифрованого текстів відповідно), що складаються з однакової кількості символів. Нехай також - взаємо-однозначне відображення в . Тоді шифр заміни діє так: відкритий текст перетвориться в шифрований текст .

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

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

Цей результат був доведений К. Шенноном за допомогою розробленого ним теоретико-інформаційного методу дослідження шифрів.

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

Тут - відкритий текст, - ключ, - шифрований текст.

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

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

2) рівність довжини ключа і довжини відкритого тексту;

3) однократність використання ключа.

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

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

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

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

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

Тому у користувача залишається єдиний шлях - отримання практичних оцінок стійкості, і складається з таких етапів:

- зрозуміти і чітко сформулювати, від якого противника ми збираємося захищати інформацію; необхідно з'ясувати, що саме противник знає або зможе дізнатися про систему шифру, а також які сили і засоби він зможе застосувати для його злому;

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

- найкращий з розроблених алгоритмів використовувати для практичної оцінки стійкості шифру.

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

Нові напрями

Центральним поняттям є поняття однобічної функції.

Однобічною називається функція , що володіє двома властивостями:

а) існує поліноміальний алгоритм обчислення значень ;

б) не існує поліноміального алгоритму інвертування функції (тобто вирішення рівняння відносно ).

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

Ще одним новим поняттям є поняття функції з секретом. Інколи ще використовується термін функція з пасткою. Функцією з секретом називається функція що залежна від параметра і володіє трьома властивостями:

а) існує поліноміальний алгоритм обчислення значення для будь-яких та ;

б) не існує поліноміального алгоритму інвертування при невідомому ;

в) існує поліноміальний алгоритм інвертування при відомому .

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

Використання функцій з секретом дозволяє:

1) організувати обмін шифрованими повідомленнями з використанням лише відкритих каналів зв'язку, тобто відмовитися від секретних каналів зв'язку для попереднього обміну ключами;

2) включити в шифрування важке математичне завдання і тим самим підвищити обґрунтованість стійкості шифру;

3) вирішувати нові криптографічні завдання, відмінні від шифрування (електронний цифровий підпис).

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

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

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

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

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

1) підписати повідомлення , тобто вирішити рівняння , може лише абонент - володар даного секрету ; іншими словами, підроблювати підпис неможливо;

2) перевірити достовірність підпису може будь-який абонент, що знає відкритий ключ, тобто саму функцію ;

3) при виникненні суперечок відмовитися від підпису неможливо через його непідробність;

4) підписані повідомлення можна, не побоюючись збитку, пересилати будь-якими каналами зв'язку.

Окрім принципу побудови криптосистеми з відкритим ключем, Діффі і Хеллман в тій же роботі запропонували ще одну нову ідею - відкритий розподіл ключів. Вони задалися питанням: чи можна організувати таку процедуру взаємодії абонентів по відкритих каналах зв'язку, аби вирішити такі завдання:

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

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

Діффі і Хеллман запропонували вирішувати ці завдання за допомогою функції

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

Сама процедура або, як прийнято говорити, протокол вироблення загального ключа описується таким чином.

Абоненти незалежно один від одного випадково вибирають по одному натуральному числу - скажемо і . Ці елементи вони тримають в секреті. Далі кожен з них обчислює новий елемент:

, .

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

Аналогічно чинить абонент :

Тим самим в і з'явився загальний елемент поля, рівний . Цей елемент і оголошується загальним ключем.

З опису протоколу видно, що противник знає , не знає і і хоче взнати . В даний час немає алгоритмів дій противника, ефективніших, ніж дискретне логарифмування, а це - важке математичне завдання.

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

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

Наведемо ще декілька прикладів завдань, що вирішуються віддаленими абонентами.

1 Взаємодіють два абонента, що не довіряють один одному. Вони хочуть підписати контракт. Це треба зробити так, щоб не допустити наступну ситуацію: один з абонентів отримав підпис іншого, а сам не підписався.

Протокол рішення цієї задачі прийнято називати протоколом підписання контракту.

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

Протокол рішення цієї задачі прийнято називати протоколом підкидання монети.

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

1) - множина цілих чисел, яка містить однакову кількість парних і непарних чисел;

2) будь-які числа , що мають один образ , мають одну парність;

3) за образом "важко" обчислити парність невідомого аргументу .

Роль підкидання монети відіграє випадковий і рівноймовірний вибір елементу , а роль орла і решки - парність і непарність відповідно. Хай А - абонент, що підкидає монету, а В - абонент, що вгадує результат. Протокол складається з наступних кроків:

а) вибирає х ("підкидає монету"), зашифровує х. Обчислює , і відсилає абонентові В;

б) отримує у, намагається вгадати парність х і відсилає свою здогадку абонентові А;

в) отримує здогадку від В і повідомляє В, чи вгадав він, відсилаючи йому вибране число х;

г) перевіряє, чи не обманює А, обчислюючи значення і порівнюючи його з отриманим на другому кроці значенням у.

3 Взаємодіють два абоненти А і В (типовий приклад: А - клієнт банку, В - банк). Абонент А хоче довести абонентові В, що він саме А, а не противник.

Протокол рішення цієї задачі прийнято називати протоколом ідентифікації абонента.

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

Це завдання прийнято називати завданням про візантійських генералів, а протокол її рішення - протоколом візантійської угоди.

Осмислення різних протоколів і методів їх побудови привело в 1985-1986 р.р. до появи двох плідних математичних моделей - інтерактивної системи доказу і доказу з нульовим розголошуванням. Математичні дослідження цих нових об'єктів дозволили довести багато тверджень, вельми корисних при розробці криптографічних.

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

1) повнота - якщо дійсно істинно, то абонент переконає абонента визнати це;

2) коректність – якщо помилково, то абонент навряд чи переконає абонента , що істинно.

Підкреслимо, що у визначенні системи не допускалося, що може бути супротивником. А якщо виявився противником, який хоче "вивідати" в яку-небудь нову корисну для себе інформацію про твердження ? В цьому випадку , природно, може не хотіти, аби це сталося в результаті роботи протоколу . Протокол , що вирішує таке завдання, називається доказом з нульовим розголошуванням і повинен задовольняти, окрім умов 1 і 2, ще і наступну умову:

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

⇐ Предыдущая 1 2 3 456 7 8 9 10 Следующая ⇒