Нові напрями

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

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

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

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

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

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

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

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

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

Про існування функцій з секретом можна сказати те ж саме, що сказане про однобічні функції. Для практичних цілей криптографії було побудовано декілька функцій, які можуть виявитися функціями з секретом. Для них властивість б поки строго не доведено, але вважається, що завдання інвертування еквівалентне деякому важкому математичному завданню, що давно вивчається. Найбільш відомою і популярною з них є теоретико-числова функція, на якій побудований шифр 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) нульове розголошування - в результаті роботи протоколу абонент не збільшить свої знання про твердження або, іншими словами, не зможе витягувати жодної інформації про те, чому істинно.

Дата добавления: 2014-01-07