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

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

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

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

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

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

Можна назвати такі задачі, що приводять до односторонніх функцій:

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

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

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

Твердження 3.17. Проблема криптоаналізу асиметричних алгоритмів є задачею з класу NP.

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

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

Рюкзакові шифри

Розглянемо задачу про заповнення рюкзака. Задано множину натуральних чисел А = (а1 ..., аn) і ще одне натуральне число k. Задачею є відшукання таких аj, сума яких дорівнює k. Іншими словами, шукаємо такі числа і1, ...,in, є {0,1}, що виконується рівність

У цій задачі число k дає розмір рюкзака, а кожне з чисел а, визначає розмір предмета, який можна покласти в рюкзак. Задачею є відшукання такого набору предметів, щоб рюкзак був цілком заповнений.

Приклад 3.13. Нехай k = 3231, а множина А складається з десяти чисел (43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523).

Оскільки 3231 = 129+473+903+561+1165, то наведена сукупність чисел-доданків дає розв'язок задачі.

Загалом розв'язання задачі про заповнення рюкзака завжди можна побудувати шляхом перебирання підмножин чисел з множини А і наступної перевірки, яка з їхніх сум дорівнює k. Для наведеного прикладу кількість можливих варіантів дорівнює 210=1024. Однак що буде, якщо множина A матиме, скажімо, 300 елементів?

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

Шифрування за допомогою рюкзакових векторів ґрунтується на тому, що послідовність бітів i1 ...,in„ заміняють числом . У цьому разі виникають такі задачі:*

одна криптограма повинна відповідати одному явному тексту (може виявитися, що , де ij - інша послідовність бітів).*

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

Обидві задачі можна розв'язати за обмежень, накладених на рюкзакові вектори.

Вектор (аi, ...,аn) називають суперзростаючгш, якщо для всіх і<п.

Тоді для кожного суперзростаючого вектора