Page 12 - 4395

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

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

алгоритм таку складність. Більш того, традиційні уявлення про
обчислювальну складність фокусуються на гіршому випадку або на
середньому випадку складності алгоритму. Це неприйнятно для

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

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

інформації інверсію можна обчислити за поліноміальний час. Таким
чином, одностороння функція з люком належить сімейству
односторонніх функцій f таких, що
k
Y = f (X) - легко, якщо k і Х відомі,
k
-1
X = f (Y) - легко, якщо k і Y відомі,
k
-1
Х = f (Y) - важко, якщо Y відоме, але k невідомо.
k
Як бачимо, розробка конкретного алгоритму з відкритим
ключем залежить від відкриття відповідної односторонньої функції з
люком.

2.1.3 Криптоаналіз алгоритмів з відкритим ключем

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

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

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

12