Основні поняття й ознаки теорії складності
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
тільки на недетермінованій машині Тьюрінга (це варіант звичайної машини Тьюрінга, що може робити припущення). Така машина робить припущення щодо розвязку задачі чи „вдачно вгадуючи”, чи перебираючи усі припущення паралельно та перевіряє своє припущення за поліноміальний час.
Рисунок 1 Класи складності
Важливість задач у криптографії визначається умовою, що за недетермінований поліноміальний час можна зламати багато симетричних алгоритмів та алгоритмів з відкритим ключем. Для даного шифротексту , криптоаналітик просто вгадує відкритий текст і ключ , потім поліноміальний час виконує алгоритм шифрування по входах і та перевіряє, чи рівний результат .
Приклад криптосистема з відкритим ключем. Вам уже відомо, що вона визначається трьома алгоритмами: алгоритмом генерації ключів, алгоритмом шифрування та алгоритмом розшифрування. Алгоритм генерації є загальнодоступним. Хто завгодно може подати на вхід алгоритму рядок r належної довжини й отримати пару ключей (K1,K2). Відкритий ключ K1 публікується, а секретний ключ K2 і випадковий рядок r зберігаються в секреті. Нагадаємо, що криптосистема RSA запропонована в 1977 році, і є однією з найбільш популярних криптосистем з відкритим ключем. Назва системи утворена з перших букв прізвищ її творців Рональда Райвеста, Аді Шаміра і Леонарда Адлемана.
Генерування ключів. Обирають два достатньо великих простих числа і .
Для їх добутку функція Ейлера буде дорівнювати (в теорії чисел використовують поняття функції Ойлера , під якою розуміють кількість чисел менших від і взаємопростих з ). Потім випадковим чином вибирають число е, яке не перевищує значення і буде взаємопростим з ним. Для цього числа е за алгоритмом Евкліда знаходять елемент d, зворотний до е, тобто такий, що і .
Цей запис у теорії чисел означає, що добуток при діленні на число дає залишок рівний 1 (читається порівнян з одиницею за модулем ).
У результаті:
Як відкритий ключ пара чисел та .
Як секретний ключ число d.
Шифрування виконується блоками. Для цього повідомлення записують у цифровому вигляді та розбивають на блоки так, що кожний блок являє число, яке не перевищує . Скажімо, якщо блок М записаний у двійковому вигляді довжини , то має виконуватися .
Алгоритм шифрування Е в системі RSA полягає в піднесенні двійкового числа М до степеня . Запишемо це так
.
У результаті виходить шифроблок .
Дешифрування. Алгоритм дешифрування шифроблоку полягає у піднесенні двійкового числа С до степеня , тобто
.
Для простоти викладення припустимо, що відкритий текст і криптограма мають однакову довжину n. Крім того, вважаємо, що відкритий текст, криптограма й обидва ключі рядки в двійковому алфавіті.
Припустимо, що супротивник атакує цю криптосистему. Йому відомий відкритий ключ K1. Він перехопив криптограму d і намагається знайти повідомлення М, де . Оскільки алгоритм загальновідомий, супротивник може послідовно перебирати всі повідомлення довжини n, обчислювати для кожного такого повідомлення криптограму і порівнювати Dі з D. Якщо Dі D, то Mі шуканий текст. Якщо пощастить, то відкритий текст буде знайдений швидко. У найгіршому випадку перебір буде виконаний за час приблизно 2n T(n), де T(n) час, потрібний на обчислення функції E1 від повідомлення довжини n. Якщо повідомлення мають довжину біля 1000 бітів, то такий перебіру є на практиці, навіть за допомогою найпотужніших компютерів. Наведений алгоритм пошуку відкритого тексту називають алгоритмом повного перебору або „метод брутальної сили”.
Одним з інших найпростіших алгоритмів пошуку відкритого тексту угадування. Цей алгоритм потребує малої кількості обчислень, але спрацьовує знехтовно низькою вірогідністю.
Насправді супротивник може намагатися атакувати криптосистему різними шляхами, використовувати різноманітні, більш складні алгоритми пошуку відкритого тексту.
Клас містить у собі клас , оскільки будь-яку задачу, що можна розвязати за поліноміальний час на детермінованій машині Тьюрінга, можна розвязати й на недетермінованій машині Тьюрінга за поліноміальний час, просто етап припущення опускається.
Якщо всі задачі класу розвязуються за поліноміальний час і на детермінованій машині Тьюрінга, . Хоч здається очевидним, що деякі задачі набагато складніші від інших (лобове розкриття алгоритму шифрування проти шифрування випадкового блоку шифротексту), ніхто не доказав, що (чи ). Однак більшість спеціалістів, що займаються теорією складності, переконані, що ці класи нерівні. Можна навести приклади. Майкл Кері та Девід Джонсон склали перелік більш ніж 300 -повних задач. Ось деякі з них:
Задача комівояжера. Комівояжер повинен обїхати різних міст, використовуючи тільки один бак з пальним (задано максимальну відстань, яку він може проїхати). Чи існує такий маршрут, що дозволяє йому відвідати кожне місто лише один раз, використовуючи цей єдиний бак з пальним?
Задача про трійні шлюби. У кімнаті чоловіків, жінок і священиків (жерців, равінів тощо). Окрім того існує список припустимих шлюбів, записи яких містять одного чоловіка, одну жінку й одного священика, що згоден провести обряд. Чи можливо, за умов цього списку, побудувати шлюбів так, щоб кожен чи вступав у шлюб тільки з однією людиною, чи реєстрував тільки один шлюб.
Нас?/p>