Однонапрямлені функції

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

Базовим поняттям криптографії з відкритим ключем є поняття односпрямованої функції (one-way function). За заданим аргументом х Х нескладно обчислити значення цієї функції F (x), тоді як визначити х з F (x) є надто складно, тобто немає алгоритму для розв’язування цього завдання з поліноміальним часом роботи. Теоретично х за відомим значенням F (x) можна знайти завжди, перевіряючи почергово всі можливі значення х доти, поки відповідне значення F (x) не збігатиметься із заданим. Проте практично за значної розмірності множини X такий підхід неможливо здійснити.

Односпрямованою називається функція F (х): X Y, х Х, яка має дві властивості:

– існує поліноміальний алгоритм обчислення значень y = F (x);

– не існує поліноміального алгоритму інвертування функції F (x) = y.

Поліноміальним називатимемо алгоритм, виконання якого завершується понад за p (n) кроків, де n – розмір вхідного завдання, який зазвичай вимірюється кількістю символів тексту, що описує це завдання.

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

Прикладом кандидата на назву односпрямованої функції є модульне піднесення до степеня, тобто функція F (x) = mod р, де а – примітивний елемент поля GF (p); р – велике просте число. Те, що ця функція може бути ефективно обчислена навіть за розрядності параметрів у кілька сотень знаків, можна довести на прикладі: можна обчислити за допомогою шести операцій множення (за множення вважається і піднесення до квадрата). Число 25 у двійковій системі обчислення записується як 11001, тобто 25 = .

Тому

(mod р) = () mod р = (((( а) ) ) а) mod р.

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

Односпрямована функція в якості функції зашифровування є непридатна, оскільки, якщо F (x) – зашифроване повідомлення х, то ніхто, враховуючи законного одержувача, не зможе відновити х. Обійти цю проблему можна за допомогою односпрямованої функції з секретом (one-way trapdoor function).

Наприклад, функція : X Y, яка має обернену функцію : Y X, проте визначити обернену функцію лише за без знання секрету k є неможливо.

Односпрямованою функцією з секретом k називають функцію : X Y, залежну від параметра k, яка має такі властивості:

– за кожного k існує поліноміальний алгоритм обчислення значень Ek (x);

– за невідомого k не існує поліноміального алгоритму інвертування Ek;

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

Функцію можна використовувати для зашифровування інформації, а обернену до неї функцію – для розшифровування, оскільки за всіх х Х є справедлива рівність

( (x)) = x.

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

Для практичної криптографії знайдено кілька функцій – кандидатів на назву односпрямованої функції з секретом. Для них другу властивість не доведено, проте відомо, що завдання інвертування є еквівалентне до розв’язування складної математичної задачі.

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

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

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

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

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

– дискретне логарифмування в скінченних полях;

– факторизація великих чисел.

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

Дата добавления: 2015-05-08