Контрольная работа: Основні поняття й ознаки теорії складності

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

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

У результаті:

Як відкритий ключ пара чисел та .

Як секретний ключ – число d .

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

Алгоритм шифрування Е в системі RSA полягає в піднесенні двійкового числа М до степеня . Запишемо це так

.

У результаті виходить шифроблок .

Дешифрування. Алгоритм дешифрування шифроблоку полягає у піднесенні двійкового числа С до степеня , тобто

.

Для простоти викладення припустимо, що відкритий текст і криптограма мають однакову довжину n. Крім того, вважаємо, що відкритий текст, криптограма й обидва ключі – рядки в двійковому алфавіті.

Припустимо, що супротивник атакує цю криптосистему. Йому відомий відкритий ключ K ₁ . Він перехопив криптограму d і намагається знайти повідомлення М , де =. Оскільки алгоритм загальновідомий, супротивник може послідовно перебирати всі повідомлення довжини n , обчислювати для кожного такого повідомлення криптограму і порівнювати D_і з D . Якщо D_і =D, то M_і - шуканий текст. Якщо пощастить, то відкритий текст буде знайдений швидко. У найгіршому випадку перебір буде виконаний за час приблизно 2ⁿ T (n ), де T (n ) - час, потрібний на обчислення функції E₁ від повідомлення довжини n. Якщо повідомлення мають довжину біля 1000 бітів, то такий перебіру є на практиці, навіть за допомогою найпотужніших комп’ютерів. Наведений алгоритм пошуку відкритого тексту називають алгоритмом повного перебору або „метод брутальної сили”.

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

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

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

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

– Задача комівояжера. Комівояжер повинен об’їхати різних міст, використовуючи тільки один бак з пальним (задано максимальну відстань, яку він може проїхати). Чи існує такий маршрут, що дозволяє йому відвідати кожне місто лише один раз, використовуючи цей єдиний бак з пальним?

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

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

І, нарешті, існує клас . Ці задачі розв’язуються за експоненційний час. На теперішній час можна довести, що -повні задачі неможливо розв’язати за детермінований поліноміальний час. Крім того доведено, що .

Дамо деякі визначення. Ми говоритимемо про алгоритми.

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

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

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

Якщо ми маємо справу з алгоритмом, то вважають зафіксованими два алфавіти: вхідний – А і вихідний – В. Робота алгоритму полягає у тому, що він отримує на вхід слово вхідного алфавіту, і як результат виконання послідовності елементарних операцій, подає на вихід слово у вихідному алфавіті.

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

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

Якщо t (n ) £ cn^c для деякої константи с , то алгоритм вирішує задачу за поліноміальний (від довжини входу) час.