Атестаційна робота пояснювальна записка

Міністерство освіти і науки України
Харківський національний університет радіоелектроніки
Факультет _______________Комп’ютерних наук______________________
(повна назва)
Кафедра _
________________
Програмної інженерії_
_______________________
_
(повна назва)
АТЕСТАЦІЙНА РОБОТА
Пояснювальна записка
_____________другий (магістерський)_____________
(рівень вищої освіти)
Дослідження несиметричних криптографічних алгоритмів в умовах використання квантових комп’ютерів. Дискретний логарифм
(тема)
Виконав: студент 2 курсу, групи ІПЗм-17-2 спеціальності 121- Інженерія програмного забезпечення
(код і повна назва спеціальності)
Освітньо-наукової програми
Інженерія програмного забезпечення
(повна назва освітньої програми)
Максутов Д.С.
(прізвище, ініціали)
Керівник проф. Качко О.Г.
(посада, прізвище, ініціали)
Допускається до захисту
Зав. кафедри, проф. ____________________ З.В.Дудар
2019 р.

Харківський національний університет радіоелектроніки
Факультет Комп’ютерних наук
Кафедра Програмної інженерії
Рівень вищої освіти другий (магістерський)
Спеціальність 121– Інженерія програмного забезпечення
(код і повна назва)
Освітньо-професійна програма Інженерія програмного забезпечення
(повна назва)
ЗАТВЕРДЖУЮ:
Зав. кафедри ______________
(підпис)
«_____»________________
20 ___ р.
ЗАВДАННЯ
НА АТЕСТАЦІЙНУ РОБОТУ студентові Максутову Дмитру Сергійовичу
(прізвище, ім'я, по батькові)
1. Тема роботи Дослідження несиметричних криптографічних алгоритмів в умовах використання квантових комп’ютерів. Дискретний логарифм затверджена наказом по університету від “07” _лютого_20 _19_ р № _546СТ_ заповнюється вручну після отримання наказу
2. Термін подання студентом роботи до екзаменаційної комісії
3. Вихідні дані до роботи алгоритми пошуку дискретного логарифму,
пояснювальна записка, емулятор квантового комп’ютера, середовище об’єктно-
орієнтованого проектування
.
4. Перелік питань, що потрібно опрацювати в роботі мета роботи, аналіз
проблемної галузі і постановка задачі, опис проблеми пошуку дискретного
логарифму, використовувані методи та алгоритми, опис розробленої програмної
системи
.
5. Перелік графічного матеріалу із зазначенням креслеників, схем, плакатів, комп’ютерних ілюстрацій (слайдів) мета роботи, обґрунтування доцільності
розроблення, постановка задачі, об'єктна модель системи, базові моделі,
результати тестування продуктивності програмної системи, демонстраційні
матеріали, висновки

6 Консультанти розділів роботи
Найменування розділу
Консультант
(посада, прізвище, ім’я, по батькові)
Позначка консультанта про виконання розділу підпис дата
Снецчастина проф. Качко О. Г.
КАЛЕНДАРНИЙ ПЛАН
№
Назва eтапів роботи
Терміни виконання етапів роботи
Примітка*
1.
Аналіз предметної галузі
08.02.2019 2.
Огляд існуючих методів
20.03.2019 3. Алгоритми пошуку дискретного логарфиму
16.04.2019 4.
Підготовка пояснювальної записки
08.05.2019 5.
Спецчастина
15.05.2019 6.
Підготовка презентації та доповіді
25.05.2019 7.
Попередній захист
28.05.2019 8.
Нормоконтроль, рецензування
9.
Занесення диплома в електронний архів
10.
Допуск до захисту у зав. кафедри
* заповнюється вручну після виконання чергового пункту
Дата видачі завдання _____ _____________2019 р.
Студент ___________________________________
(підпис)
Kepiвник роботи _______________________ __ проф. Качко О. Г._________
(підпис) (посада, прізвище, ініціали)

РЕФЕРАТ / ABSTRACT
Пояснювальна записка до атестаційної роботи: 89 с., 23 рис., 4 додатки, 26 джерел.
КВАНТОВИЙ КОМПЬЮТЕР, КВАНТОВИЙ АЛГОРИТМ, ДИСКРЕТНИЙ
АЛГОРИТМ ШОРА, КВАНТОВИЙ ПАРАЛЕЛІЗМ, Q#, JAVA, JMH,
ДИСКРЕТНИЙ ЛОГАРИФМ, NP ЗАДАЧА.
Об'єктом є несиметричні криптографічні алгоритми в умовах використання квантових обчислень, квантовий алгоритм Шора пошуку дискретного логарифму.
Метою роботи є дослідження квантового алгоритму Шора для пошуку дискретного логарифму та його порівняння з не-квантовими аналогами.
Методи розробки базуються на мовах програмування C#, Java та спеціальній мові для квантових обчислень Q#. Також використовуються наступні методи розробки: паралельні обчислення, об'єктно-орієнтований підхід до розробки програмної системи, функціональний підхід до розробки системи.
У результаті роботи були дослідженні переваги та недоліки квантових обчислень, дискретний квантовий алгоритм Шора для пошуку дискретного логарифму та його не квантові аналоги
QUANTUM COMPUTER, QUANTUM ALGORITHM, DISCRETE SHOR`S
ALGORITHM, QUANTUM PARALLELISM, Q#, JAVA, JMH, DISCRETE
LOGARITHM, NP COMPLEXITY CLASS.
The object of research are asymmetric cryptography algorithms in conditions of quantum computer usage, discrete quantum Shor’s algorithm.
The aim is development of application for research of discrete logarithm by discrete
Shor`s quantum algorithm and it’s comparison to non-quantum analogs.

ПЕРЕЛІК СКОРОЧЕНЬ
ECDLP асинхронний генератор;
GF поле Галуа (Galois field);
NP-клас клас задач не поліноміальної складності;
P-клас клас задач поліноміальної складності;
BQP-клас клас задача квантової поліноміальної складності з обмеженою помилкою;
VRP
Задача маршрутизації транспортного засобу (Vehicle routing problem);
ECDH протокол Діффі-Хелмана на еліптичних кривих (Elliptic- curve Diffie–Hellman);
ECDSA алгоритм цифрового підпису на еліптичних кривих
(Elliptic Curve Digital Signature Algorithm);
QCP
Quantum Computing Playground
MQM
Microsoft Quantum Machinery
QDK
Quantum Development Kit;

6
ЗМІСТ
Вступ ................................................................................................................................. 8 1 Аналіз предметної галузі та постановка задачі ......................................................... 11 1.1 Асиметричні алгоритми криптографії. Односторонні функції та їх застосування. ................................................................................................................ 14 1.2 Класифікація задач за обчислювальною складністю. Задачі класу NP .............. 18 1.3 Сьогоднішній стан розробки квантових комп’ютерів ......................................... 23 1.4 Постановка задачі .................................................................................................. 29 2 Дослідження особливостей квантових комп’ютерів та квантових алгоритмів для дискретного логарифмування ........................................................................................ 30 2.1 Особливості квантових комп’ютерів та обмеження, що вони накладають на квантові алгоритми ...................................................................................................... 30 2.2 Головні проблеми квантових обчислень .............................................................. 34 2.2.1 Проблема клонування стану регістра на квантовому комп’ютері ............... 35 2.2.2 Проблема декогеренції ................................................................................... 37 2.2.3 Ймовірнісний характер квантових обчислень .............................................. 39 2.2.4 Проблема вимірювання поточного стану системи ....................................... 39 2.3 Фізична реалізація квантових комп’ютерів .......................................................... 41 3 Аналіз алгоритмів дискретного логарифмування для до та пост квантового періодів
......................................................................................................................................... 43 3.1 Класичні алгоритми пошуку дискретного логарифму ......................................... 43 3.2 Алгоритм пошуку дискретного логарифму Шора та його варіації. .................... 45 4 Програмна реалізація алгоритмів для обчислення дискретного логарифму ........... 51 4.1 Реалізація не квантових алгоритмів пошуку дискретного логарифму ............... 51 4.1.1 Алгоритм Гельфонда – Шенкса ..................................................................... 51 4.1.2 ρo-алгоритм Полларда для дискретного логарифма ..................................... 52

7 4.1.3 Алгоритм Поліґа-Геллмана ............................................................................ 54 4.1.4 Структура програмного коду ......................................................................... 55 4.1.5 Результати тестування продуктивності алгоритмів за допомогою JMH ..... 56 4.2 Реалізація квантового алгоритму Шора пошуку дискретного логарифму ......... 58 4.2.1 Вибір інструментів для реалізації .................................................................. 59 4.2.2 Реалізація алгоритму і її результати .............................................................. 61
Висновки ......................................................................................................................... 66
Перелік джерел ............................................................................................................... 68
Додаток А ....................................................................................................................... 71
Додаток Б ........................................................................................................................ 78
Додаток В ....................................................................................................................... 86
Додаток Г ........................................................................................................................ 89

8
ВСТУП
На початку ери дослідження квантової механіки та квантових обчислень, ніхто навіть і не мріяв про їх практичне застосування, яке б могло впливати на повсякденне життя оточуючих. Усі дослідження у цій області вважалися дуже суперечливими.
Наукова спільнота, у своїй більшості, сприймала квантові ефекти, скоріше, як фантастику, а не реально існуючі фізичні явища. До того ж, дослідження ускладнювалися неможливістю пояснити природу спостережуваних явищ та результатів експериментів. Тим не менш, сьогодні на базі квантової механіки вчені будують, і навіть продають, квантові комп’ютери, а теорія квантових обчислень обзавелася несуперечливою математичною моделлю, на якій тепер базується ідея програмування квантових комп’ютерів.
За будь якого часу, інформація мала велику ціну у світі. Ще з давніх давен, певну, важливу, інформацію намагалися захистити різними способами, основним з яких було шифрування. Проте за давніх часів інформація передавалася за допомогою гінців, або ж спеціально навчених птиць. Інформацію, відправлену таким чином, було досить важко перехопити. Сьогодні ж, інформація пронизує усе життя суспільства.
Інформаційні канали, такі як оптоволоконні кабелі з високою пропускною здатністю, або ж радіосигнали різних частот охоплюють усю планету. Перехід до такої моделі розповсюдження інформації призвів до того, що тепер, перш ніж дійти до адресата,
інформаційний пакет проходить через десятки вузлів – пристроїв, які до адресата не мають ніякого відношення. Це значно збільшує ризик перехоплення повідомлення на одному з таких вузлів. Для захисту інформації, що подорожує, через відкриті, вразливі, канали зв’язку сьогодні застосовуються методи асиметричної криптографії.
За допомогою цих методів, інформаційні повідомлення надійно шифруються і відправник повідомлення може бути впевнений, що зміст його повідомлення не буде розкрито. Така система задовольняла усіх користувачів, аж доки квантові комп’ютери

9 не стали набирати популярність. Справа у тому, що протоколи асиметричної криптографії, базуються на складності вирішення деяких математичних проблем. І ця складність дійсно зберігалася, аж доки не виявилося, що ці проблеми можуть бути вирішені у прийнятний час за допомогою можливостей для обчислень, що надають квантові комп’ютери.
Такі обчислювальні можливості досягаються квантовими комп’ютерами завдяки тому, що їх робота заснована на використанні різноманітних квантових ефектів, таких як невизначеність, зчеплення та суперпозиція кубітів. Кубіті – це саме те, що, в першу чергу, відрізняє квантові комп’ютери від класичних. Кубіт, або ж квантовий біт, виділяється тим, що на відміну від звичайного біту, його стан виражається ймовірнісним полем. Тобто його стан – це не певна задача величина (1 або 0), а набір ймовірностей величин.
Завдяки цьому, обчислення над кубітами також набувають ймовірнісного характеру і це, разом з можливістю впливу на ймовірності, дозволяє значно прискорити вирішення таких задач, як: моделювання поведінки мікрочасток (молекул
і т.і.), секвенування ДНК, пророкування біржових котирувань і підбір криптографічних ключів, оптимізація маршрутів транспорту.
В наші дні, розробка квантових комп’ютерів та написання програм під них набувають все більшого поширення IT-гіганти такі, як Google, Intel, Microsoft,
International Business Machines (IBM), D-Wave Systems [1] вступили у гонку по розробці першого потужного квантового комп’ютера, який буде придатний для вирішення багатьох реальних проблем. На сьогодні уже існують квантові комп’ютери, що придатні для рішення незначних задач, або проведення певних досліджень в областях фізики, біології, хімії і криптографії. В силу цього, останнім часом, досить велика, увага приділяється пост-квантовим алгоритмів криптографії. Таким чином, можна спрогнозувати, що існує велика вірогідність побачити потужні квантові комп'ютери у недалекому майбутньому.

10
Метою даної роботи є дослідження алгоритмів квантових обчислень, а саме дискретній версії квантового алгоритму Шора для знаходження дискретного логарифму у циклічній групі чи на еліптичній кривій, яка уявляє собою окремий випадок циклічної групи та порівняння цього алгоритму з його не квантовими аналогами. Методи розробки базуються на мовах програмування C#, Java та Q#.
Також використовуються наступні методи: квантові обчислення, об'єктно- орієнтований підхід до розробки програмної системи. Окрім цього будуть застосовані готові бібліотеки чи інструменти для квантових обчилсень, які містять реалізовані квантові примітиви, що допоможуть значно спростити та пришвидшити розробку та сконцентрувати розробку та дослідження саме на квантових алгоритмах, а саме, квантовому алгоритму Шора для пошуку дискртеного логарифму у звичайних групах та на еліптичних кривих.

11
1 АНАЛІЗ ПРЕДМЕТНОЇ ГАЛУЗІ ТА ПОСТАНОВКА ЗАДАЧІ
Криптографія має на меті проаналізувати, які проблеми можна зробити простими в той же час роблячи пов’язані з ними проблеми важкими. На практиці, якщо я хочу відправити своєму другові повідомлення, яке ніхто інший не зможе прочитати, я хочу, щоб мені було легко закодувати це повідомлення, моєму другові було просто його розшифрувати і третій особі було важко його розшифрувати. Одна з проблема, які вважаються важкою, і на базі якої побудовано багато криптографічних систем, це проблема дискретного логарифму. Наразі немає швидких методів для вирішення цієї проблеми, хоча цілком можливо, що вони коли-небудь будуть знайдені. Проблема дискретного логарифму більшою мірою задається з використанням еліптичних кривих, ніж кінцевих областей.
Так сталося, що ключ шифрування одного і того ж розміру забезпечить більшу безпеку, якщо ми використовуємо ECC. Іншими словами, ми можемо використовувати менший ключ, щоб отримати той саме обсяг безпеки, що прискорює розрахунки, які ми хочемо прискорити.
У 1985 році Н. Кобліц і В. Міллер незалежно запропонували використовувати групу точок на еліптичній кривій визначеній над кінцевим полем у криптосистемі дискретного логарифму. Це зовсім інший шлях у вирішенні криптографічних проблем. З ним можна використовувати групу еліптичних кривих, яка менша за розміром ніж звичайна кінцева група і при цьому надає той же рівень безпеки. У багатьох випадках це призводить до використання меншого за розміром ключа, економії трафіку і більш продуктивної імплементації, що особливо важливо для смарт карток і смартфонів.
У 2005 році американське агентство національної безпеки США опублікувало роботу, в якій вони рекомендували "взяти" до уваги результати останніх 30 років

12 дослідження алгоритмів з публічним ключем і перейти від алгоритмів першого покоління (RSA) до алгоритмів на еліптичних кривих.
Класична проблема дискретного логарифму полягає в наступному: нехай, існує таке ціле число k, що 𝑎
𝑘
≡ 𝑏 (𝑚𝑜𝑑 𝑝), де p являється простим числом, і треба знайти k. Зазвичай, для знаходження k використовується операція обчислення логарифму. В рамках задачі пошуку саме дискретного логарифму k є цілим числом. Так як за визначенням 𝑎
𝑘
повинно ділити p-1, k може бути визначено у кільці за модулем (mod p-1).
У 1997 році Certicom анонсував декілька призів за вирішення проблеми дискретного логарифму на еліптичних кривих (ECDLP). Задача була поставлена наступним чином: розрахувати приватні ключі ECC маючі список публічних ключів і асоційованих з ними параметрів. Загалом, це проблема з якою стикається кожен, хто хоче повністю зламати криптосистему базовану на еліптичних кривих.
Таблиця 1.1 – Основні числа ECDLP Break Challenge
Число
Двійкових чисел
Винагорода
Зламано
ECCp-79 79 book
1997 Baisley and Harley
ECC2-79 79 book
1997 Harley et al.
ECCp-89 89 book
1998 Harley et al.
ECC2-89 89 book
1998 Harley et al.
ECCp-97 97
$5,000 1998 Harley et al. (1288 комп’ютерів)
ECC2K-95 95
$5,000 1998 Harley et al. (200 комп’ютерів)
ECC2-97 97
$5,000 1999 Harley et al. (740 комп’ютерів)

13
Кінець таблиці 1.1
Число
Двійкових чисел
Винагорода
Зламано
ECC2K-108 108
$10,000 2000 Harley et al. (9500 комп’ютерів)
ECCp-109 109
$10,000 2002 Monico et al. (10000 комп’ютерів)
ECC2-109 109
$10,000 2004 Monico et al. (2600 комп’ютерів)
ECC2K-130 130
$20,000
-
ECCp-131 131
$20,000
-
ECC2-131 131
$20,000
-
ECC2K-163 163
$30,000
-
ECCp-163 163
$30,000
-
ECCp-191 191
$40,000
-
ECC2K-238 238
$50,000
-
ECC2-238 238
$50,000
-
ECCp-359 359
$100,000
-
У таблиці 1.1 наведено дані про характеристики еліптичних кривих які були представлені на змаганні, а також результати їх злому.
Як видно з таблиці, спроби злому з використанням звичайних комп’ютерів не дали позитивних результатів навіть для ключів порівняно невеликого розміру. Тим не менш, згідно з дослідженнями останніх років, квантові комп’ютери та алгоритм Шора
є великою загрозою для криптографії на еліптичних кривих. У 2015 році NASA опублікувало роботу у який закликає до розробки нових, так званих, пост-квантових алгоритмів криптографії і відмови від алгоритмів на базі еліптичних кривих і RSA [2].

14 1.1 Асиметричні алгоритми криптографії. Односторонні функції та їх застосування.
У своїй відомій роботі "New Directions in Cryptography" Діффі і Хеллман описали абсолютно новий і надійний спосіб встановлення каналу для обміну секретною інформацією. Новизна способу виражалась у тому, що зникала необхідність попереднього обміну секретними ключами. Необхідні ключи могли вільно передаватися по відкритим каналам зв’язку. За цю властивість, цей спосіб отримав назву шифрування з відкритим ключем. Представлений спосіб, або ж протокол, передбачає використання декількох ключів. Одного відкритого ключа і одного закритого ключа. Плюс декількох відкритих змінних. При чому знання одного з цих ключів не дозволяю тут же визначити другий. Як наслідок цієї властивості, один з ключів (ключ шифрування) може бути відкритим без ризику злому шифрограм,
інший же ключ (ключ розшифрування) все ще повинен триматися в таємниці. В результаті такої організації схеми шифрування, системи в яких використовується шифрування з відкритим ключем також називають асиметричними (несиметричними) криптосистемами [3].
Шифрування з відкритим ключем базується на такому такій математичній сутності, як одностороння функція (one-way function) [4]. Основною властивістю такої функції є те, що її значення 𝐹(𝑥), легко обчислити для заданого аргументу 𝑥 ∈ 𝑋, в той час, як інверсію, тобто пошук значення 𝑥 за значенням 𝐹(𝑥), зробити досить важко. Під важко, тут розуміється відсутність алгоритму для пошуку інверсу за поліноміальний час роботи. Теоретично, завжди можна знайти 𝑥 по відомим значенням 𝐹(𝑥) перебравши усі можливі варіанти з множини 𝑋 і підставляючи їх у функцію 𝐹(𝑥), тобто використати метод простого перебору. Тим не менш, з практичної точки зору, такий підхід не є прийнятним при великій розмірності множини 𝑋, так як перебір займе занадто багато часу.

15
Доказ існування таких односторонніх функцій такого роду і до сих пір являється відкритою проблемою. Доказ їх існування автоматично доводить твердження про нерівність класів складності P та NP. Уся сучасна асиметрична криптографія базується на тому, що гіпотеза про існування односторонніх функцій все ж вірна.
З математичної точки зору, односторонніми називають такі функції 𝐹(𝑥): 𝑋 →
𝑍, 𝑥 ∈ 𝑋, що володіють двома наступними властивостями:
 існує поліноміальний алгоритм обчислення значень 𝑧 = 𝐹(𝑥);
 не існує поліноміального алгоритму для знаходження інверсу функції, або ж функції інверсу 𝐹(𝑧) = 𝑥.
Варто зауважити, що існування односторонніх функцій все ще не було математично доведено, тому використання їх як основи для асиметричних алгоритмів шифрування може мати місце до тих пір, доки не знайдені ефективні алгоритми, для пошуку інверсу односторонніх функцій за поліноміальний час.
Одним з прикладів можливо односторонньої функції є зведення у ступінь по модулю (або ж у кільці) (1.1):
𝐹(𝑥) ≡ 𝑎
𝑥
𝑚𝑜𝑑 𝑝,
(1.1) де
𝑎 – примітивний елемент поля 𝐺𝐹(𝑝) (генератор);
𝑝 – велике просте число.
Досить легко можна продемонструвати, що така функція може бути розрахована за ефективний час навіть для параметрів великої розрядності (сотні знаків). Візьмемо за приклад: 𝑎
30
можна обчислити за допомогою шести операцій множення
(множенням вважається і зведення в квадрат).Число 30 в двійковій системі числення записується як 11110, тому 30 = 2 4
+ 2 3
+ 2 2
+ 2 згідно з формулою (1.2).
𝑎
30
𝑚𝑜𝑑 𝑝 ≡ (𝑎
16
𝑎
8
𝑎
4
𝑎
2
)𝑚𝑜𝑑 𝑝 ≡ ((((𝑎
2
𝑎)
2
𝑎)
2
𝑎)
2
)𝑚𝑜𝑑 𝑝,
(1.2) де
𝑎 – примітивний елемент поля 𝐺𝐹(𝑝);

16
𝑝 – велике просте число.
Завдання пошуку функції виду (1.3), називається завданням пошуку дискретного логарифму. log
𝑎
𝐴 = 𝑏 ⇔ 𝑎
𝑏
= 𝐴 𝑚𝑜𝑑 𝑝,
(1.3) де
𝑎 – примітивний елемент поля 𝐺𝐹(𝑝);
𝑝 – велике просте число.
На даний момент не було знайдено будь-яких ефективних алгоритмів для обчислення дискретних логарифмів у полях великої розмірності.
Сама по собі, будь-яка одностороння функція не придатна для використання у якості функції шифрування, так як повідомлення 𝑥 зашифроване односторонньою функцією 𝐹(𝑥) – не можливо розшифрувати згідно з визначенням односторонньої функції. Для вирішення цієї проблеми можна використовувати односторонню функцію з секретом (one-way trapdoor function). Роздивимось приклад: Дана функція
𝐸
𝑘
: 𝑋 → 𝑌, яка має обернену функцію 𝐷
𝑘
: 𝑌 → 𝑋, проте знайти обернену функцію використовуючи тільки інформацію про 𝐸
𝑘
(без знання секрету
𝑘) - неможливо. Тож функція 𝐸
𝑘
: 𝑋 → 𝑌, результат виконання якої залежить від параметра 𝑘 називається односторонньою функцією з секретом 𝑘. Односторонній функції з секретом має наступні три властивості:
 існує поліноміальний алгоритм розрахунку значень 𝐸
𝑘
(𝑥), для будь-якого 𝑘;
 поліноміального алгоритму інвертування 𝐸
𝑘
не може бути знайдений якщо значення 𝑘 не відоме;
 поліноміальний алгоритм інвертування 𝐸
𝑘
існує і може бути знайдений, якщо значення 𝑘 відоме.

17
Функцію 𝐸
𝑘
придатна для шифрування інформаційних пакетів. Інформацію зашифровану функцією 𝐸
𝑘
можна розшифрувати використовуючи обернену їй функцію 𝐷
𝑘
, так як для всіх
𝑥 ∈ 𝑋 виконується 𝐷
𝑘
(𝐸
𝑘
(𝑥)) = 𝑥.
Варто звернути увагу на головну властивість цієї комбінації функцій, а саме, той хто шифрує інформацію за допомогою функції 𝐸
𝑘
не обов’язково повинен мати змогу
її розшифрувати. Існування односторонніх функцій з секретом, так само як і існування односторонніх функцій, не було математично доведено.
Існує декілька функцій, які ймовірно являються односторонніми функціями з секретом і використовуються у практичній криптографії. Друга властивість односторонніх функцій з секретом, для цих функцій не доведена. Тим не менш, про них відомо, що пошук інверсу цих функцій еквівалентний вирішенню важкої
(затратної по часу) математичної задачі.
Першою і досить важливою односторонньою функцією з секретом, що використовується у практичній криптографії для протоколів з відкритим ключем, можна назвати функцію факторизація цілих чисел. Іншою, не менш важливою і досить широко використовуваною функцію, являється функція пошуку дискретного логарифму.
Задіяння цих функцій в криптографії дозволяє досягти наступних переваг:
 прибрати необхідність підтримки секретних каналів зв’язку, які раніше були необхідні для обміну ключами симетричного шифрування, і використовувати для обміну інформацією тільки відкриті канали зв’язку;
 підвищити стійкість шифрування і легко змінювати стійкість шляхом зміни довжини ключа;
 застосовувати криптографію для вирішення нових класів завдань, таких як електронний цифровий підпис та ін.
Тож безпека та стійкість до злому переважної більшості сучасних асиметричних протоколів шифрування залежить від складності вирішення двох складно обчислювальних математичних проблем:

18
 факторизація великих цілих чисел;
 пошуку дискретного логарифму на кінцевих полях.
Ці дві математичні задачі широко засновуються в асиметричних криптографічних протоколах, так як досі не було знайдено ефективних алгоритмів для вирішення цих задач або ж такі алгоритми були знайдені для певних виключних параметрів таких задач.
В заключення, можна констатувати, що односторонні функції являються фундаментальним компонентом асиметричної криптографії, протоколів ідентифікації та автентифікації особи та інших областей пов’язаних з захистом інформації. Не зважаючи на те, що їх односторонність все ще математично не доведена існує декілька функцій, що піддалися десятиліттям безперервного аналізу і активно застосовуються в системах, які стали невід’ємною частиною повсякденного життя. Таких, як інтернет, телефонний зв’язок та ін.
1.2 Класифікація задач за обчислювальною складністю. Задачі класу NP
Якщо звернутися до класичної теорії складності алгоритмів, алгоритми поділяються за обчислювальною складності на наступні категорії: NP-складні, NP,
BQP та P. Задачі, що відносяться до класу складності P мають обчислювальну складність (за часом), що виміряється поліномом залежним від обсягу вихідних даних
і можуть бути вирішені за поліноміальний час на детермінованої обчислювальної машини (машині Т'юрінга). Задачі, що відносяться до класу BQP з певною ймовірністю можуть бути вирішні на квантовому комп’ютері за поліноміальний час.
До NP[5] класу відносяться задачі, які мають поліноміальну складність при їх вирішенні з використанням недетермінованої обчислювальної машини, особливістю якої є те, що кожен її наступний стан не завжди однозначно залежить від

19 попереднього. Тобто на відміну від класичного детермінованої машини, обчислення на такій машині будуть розгалужуватися (виконуватися паралельно) при кожному виникненні неоднозначності: Іншою особливістю недетермінованої машини, являється те, що обчислення на ній можуть ніколи не зупинитися, тобто рішення задачі може бути не знайдено. Тому задача запущена на такий машині вважається вирішеною, тільки в тому випадку, коли хоча б одна гілка розгалуженого процесу обчислень процесу привела до якоїсь відповіді. Тобто, хоча б одна з гілок завершилася. Належність до NP класу складності можна також визначити по іншому критерію. Якщо вирішення задачі може бути перевірене за поліноміальний час з використанням додаткової інформації поліноміальної довжини (що була надана ззовні), то таку задачу можна віднести до NP класу. Таким чином до NP класу також відносяться усі задачі, вирішення яких можна перевірити за поліноміальний час.
Варто зауважити, що NP клас включає в себе P клас. Прикладом задач NP класу можуть служити задача про комівояжера, або її узагальнений варіант VRP.
Так як клас NP включає в себе клас P, неможливо гарантовано довести належність задачі до класу NP. Тому відношення задач до того чи іншого класу зазвичай відображає лише нагальний рівень знань про способи вирішення того чи
іншого завдання і не є постійною величиною. Загалом, у нас не має підстав вважати, що відношення здачі до NP класу є справедливим і кінцевим, так як на даний момент відсутність рішень складності P для NP задач не доведена. Це питання, а саме, питання еквівалентності P і NP класів (існування P-рішення для будь-якої NP-задачі) вважається однією з основних проблем теорії складності алгоритмів. Доказів того чи
іншого не було представлено до сих пір. Саме ж питання еквівалентність P і NP класів виникає через існування класу NP-повних задач. Множина NP-повних задач, як і множина задач P класу) є підмножиною задач NP класу і вирізняється тим, що усі завдання NP класу так чи інакше можуть бути зведені до цього класу NP-повних задач.
А це означає, що якщо для NP-повної задачі буде знайдено рішення складності класу

20
P, то таке рішення буде знайдено для всіх завдань NP класу. Одним з прикладів NP- повної задачі є задача про кон’юнктивну форму.
Історично склалося, що дослідження складності алгоритмів відкрило нові ракурси при погляді багато класичних математичних задач і способи їх вирішення. Це дозволило знайти рішення, які є менш ресурсно-затратними порівняно з традиційними, для таких завдань, як: множення многочленів і матриць, рішення систем лінійних рівнянь і т.і.
У теорії складності, множину алгоритмів, складність яких суттєво залежить від розміру вхідних даних; і при цьому знижується до поліноміальної, якщо надати алгоритму певні додаткові дані (так звані свідки рішення), називають множиною недетермінованих поліноміальних алгоритмів.
Теоретично, NP клас складається з задач, для яких за поліноміальний час , використовуючи недетерміновану машину Т’юрінка можна перевірити потенційне рішення задачі. Іншими словами задачі з множини NP класу можуть бути вирішені за поліноміальний час на недетермінованої машині Т'юрінга.
NP клас можна визначити для множини мов, які уявляють собою множини слів над кінцевим алфавітом. Мова 𝐿𝑒𝑛 можна назвати належною до класу NP, коли існує певний двомісний предикат R (x, y) з P класу і многочлен 𝑛
𝑐
такі, що постулат "
𝑥 належить 𝐿𝑒𝑛" рівноцінний постулату "існує y довжиною менше 𝑛
𝑐
(де 𝑛 - довжина слова 𝑥) таке, що предикат R (x, y) виконується" для будь-якого слова x. У такому випадку слово 𝑦 називають свідком належності 𝑥 до мови 𝐿𝑒𝑛. Тобто, якщо у нас є слово, що належить мові, і слово-свідок обмеженої довжини, то можна швидко переконатися в тому що 𝑥 дійсно належить 𝐿𝑒𝑛.
Клас складності NP можна визначити і іншим чином, вводячи поняття недетермінованої машини Т'юрінга, яка уявляє собою машину Т'юрінга, у програмі якої можуть існувати різні рядки з однаковою лівою частиною. У разі появи "розвилки", тобто неоднозначність в програмі, під час виконання обчислення може піти різними шляхами. Недетерміновану машину Т'юрінга можна представити

21 предикат R (x), який вважається рівним одиниці в тому випадку, коли існує хоча б один варіант, або ж шлях, обчислення, результатом якого є 1. В іншому випадку цей предикат дорівнює 0. У разі, коли довжина шляху обчислення, що призводить до одиниці, не перевищує деякого многочлена від довжини x, предикат називають таким, що належить класу NP. Коли у певній мові є предикат що належить NP класу і розпізнає його, мова називається такою, що належить класу NP. Наведене визначення еквівалентно визначенню, що приведено вище. Якщо в якості свідка взяти номери необхідних гілок на розвилках в обчисленні. Беручі до уваги, що x належить мові, довжина усього шляху обчислення не буде перевищувати многочлен від довжини x, тому довжина свідка також буде обмежена многочленом від довжини x.
Можна зауважити, що будь-яку задачу NP класу, можна вирішити за експоненціальний час методом перебору усіх можливих свідків довжини яких менше
𝑛
𝑐
З вищенаведеного можна побачити, що множина мов з класу NP не є замкненою щодо доповнення. Клас мов, доповнення яких належить класу NP, називається co-NP класом.
Далі наведено задачі, належність яких класу P не визначена, але точно відома їх належність до класу NP[6]:
 VRP-задача: полягає в знаходженні оптимального маршруту на графі для декількох агентів і уявляє собою узагальнення задачі про комівояжера;
 задача доказу існування цілочисельного рішення системи лінійних нерівностей. Свідком в даному випадку виступає знайдене рішення;
 задача пошуку клік (повних підграфів) певного розміру у даному графі.
Свідок виступають номери вершин, з яких складається знайдена кліка;
 задача про комівояжера, яка полягає у пошуку найбільш ефективного шляху по усіх вершинах графа і є більш наближений до реальності варіантом здачі наведеної вище;

22
 задача пошуку Гамільтонова циклу на графі. Свідком в даному випадку виступає послідовність вершин, з яких будується Гамільтонів цикл.
Окрім цього до задач NP класу відносять задачу факторизації цілих чисел і задачу пошуку дискретного логарифма. Проте ці задачі не відносяться класу NP- повних задач, тому алгоритму P класу для пошуку дискретного логарифма не буде означати еквівалентності P та NP класів.
Як згадувалося раніше, багато сучасних криптосистем побудовано на базі асиметричних протоколів. Серед таких протоколів можна виділити DH, стійкість якого базується на складності пошуку дискретного логарифму, і популярний в останній час ECDH, стійкість якого базується на складності задачі пошуку дискретного логарифму на еліптичних кривих.
До теперішнього часу ніяких крипто атак небезпечних для протоколів ECDH та
ECDSA виявлено не було. Основними атаками є атака заснована на MOV алгоритмі та атака заснована на алгоритмі Гельфонда - Шенкса. Безпека алгоритму ECDH заснована на складності задачі пошуку дискретного логарифму на еліптичних кривих
(пошук порядку у циклічній групі). У рамках цього протоколу відкритий та закритий ключі уявляють собою точки на еліптичній кривій, кожна координата яких має розмір
50-150 розрядів або більше і є простим числом. При чому, розшифрування зашифрованої відкритим ключем інформації еквівалентно знаходженню дискретного логарифма на еліптичній кривій. Існує достатньо багато алгоритмів для пошуку дискретного логарифма, але жоден з них не може знайти дискретний логарифм на стандартизованій еліптичній кривій за поліноміальний часу (тобто не входить до P класу). Для того щоб забезпечити безпеку, ECDH вимагає, щоб модуль був принаймні
160 бітів завдовжки.. Навіть при використанні потужного і найшвидшого комп'ютера, доступного на сьогодні, пошук дискретного логарифму у групі такого прядку вимагає нездійсненно великого часу. Це означає, що ECDH безпечний, поки не буде знайдений ефективний алгоритм пошуку дискретного алгоритму на еліптичних кривих.

23
Для пошуку простого дискретного логарифму та для інших задач з класу NP на сьогодні також не знайдено рішень класу P, і усі запропоновані класичні алгоритми для вирішення цих задач мають експоненційну складність. Для груп великого порядку, робота таких алгоритмів може займати роки. В наслідок чого атаки на криптосистеми, в основі яких лежать ці алгоритми, стають не доцільними і не ефективними, з точки зору час витрат та актуальності здобутої інформації.
Таким чином, можна заявити, що на даний момент існує проблема рішення задач класу NP, і використання для їх рішення класичних комп’ютерів будь-якої потужності не є раціональним і не переведе до їх рішення у задовільний час. Виходом можуть послужити квантові комп’ютери та алгоритми для них. Далі більш детально будуть розглянуті особливості квантового алгоритму для пошуку дискретного логарифму та його реалізація.
1.3 Сьогоднішній стан розробки квантових комп’ютерів
Квантові комп'ютери, придатні для вирішення актуальних задач, мають усі шанси з’явитися у найближчий час, і їх поява змінить світ. З їх допомогою науковці можуть зробити нову революцію у медицині, фізиці, хімії, біології, інформаційній безпеці, машинному навчанні і багатьох інших областях науки.
Мова про квантові комп'ютери, що будуть здатні швидко зламувати криптосистеми іде уже декілька десятиліть. Проте до недавніх років, усе це було лише красивою картинкою у головах математиків, фізиків та криптоаналітиків.
З недавнього часу усі ці мрії почали переходити у реальні реалізації. Про це свідчать рекомендації американського випущені в серпні 2016 року. Агентства національної безпеки США захищає державні таємниці і виступає радником американського державного та приватного секторів у питаннях актуальних

24 алгоритмів комп'ютерного захисту, і криптографії в тому числі. В рамках оновлення рекомендацій було оновлено набір рекомендованих криптографічних алгоритмів
(SUITE B).
З оглядом на швидкий прогрес фізики і техніки в області дослідження та розробки квантових комп’ютерів, АНБ рекомендує готуватися до швидкої появи квантових комп'ютерів придатних для практичного використання у сфері криптографії. Поява цих комп’ютерів призведе до можливості злому найпопулярніші сьогодні асиметричних криптографічних протоколів та цифрового підпису.
Багато великих гравців взялося за створення власних квантових комп’ютерів намагаючись виграти у конкурентній боротьбі за потенційні ринки.
Наприклад Google анонсував та випустив наступні продукти пов’язані з квантовими обчисленнями:
 7 липня 2016 року Google почав експеримент пов’язаний з пост-квантовою криптографією який проходив на базі їх браузера Chrome. Експеремент полягав у тому, що в Chrome Canary (версії браузера для розробників у якій випускаються різні функції з раннім доступом) для певних користувачів була ввімкнена нова система шифрування з’єднання до серверів Google що базувалася на новому алгоритмі. Базою для розробки системи послужила наукова робота у якій йшлося про впровадженню пост-квантового алгоритму шифрування в протокол TLS. Назва алгоритму ("Нова надія") була такою-собі відсилкою до поп-культури; За словами розробників головною метою було дати дослідникам можливість проведення криптоаналізу практичної реалізації пост-квантового алгоритму у продакшені. Окрім цього розробники хотіли оцінити швидкість і надійність з'єднання при використанні цього алгоритму. Google не збирається нав'язувати цей алгоритм, як новий крипто стандарт, чи просувати його іншим чином;
 QCP. Своєрідний ігровий майданчик для тих, хто хоче спробувати свої сили в написанні алгоритмів для квантового комп’ютера, або ознайомитися ближче з квантовими обчисленнями. Додаток представлений у вигляді веб-додатка Chrome, і

25 використовує WebGL, для імітації кубітів (до 22) на GPU. Додаток включає в себе просте середовище розробки, для написання, компіляції та запуску коду. Окрім цього додаток надає можливість проекспериментувати з відомими реалізованими квантовими алгоритмами Гровера та Шора, має зручний інструментарій для дебагу та
3D візуалізації квантових станів, що наглядно демонструє результат застосування квантових операцій (гейтів) на кубіти. Для написання програм використовується мова
QScript. 22-х кубітів не достатньо для практичного застосування, тож QCP варто сприймати, як навчальну платформу.
Далі детально розглянемо успіхи інших гравців на рику продуктів для квантових обчислень:
 IBM представила IBM Q, в якості ініціативи направленої на розвиток квантових обчислень та створення доступних та універсальних квантових комп’ютерів придатних для використання в науці і бізнесі. Ця ініціатива стала першою у своєму роді. На даний момент IBM вже має прототип комерційного квантового комп’ютеру, на основу якого далі будуть будуватися інші системи.
Співпрацюючи зі своїми ключовими партнерами по галузі, IBM збирається вагомо збільшити обчислювальну потужність квантових комп’ютерів у майбутньому і показати перевагу в ефективності порівняно з класичними обчислювальними системами. IBM збирається відкрити комерційне API для хмарних квантових обчислень та перший комерційний центр квантових обчислень в 2019 році. В даний час найбільший квантовий комп’ютер доступний в рамках IBM Q має тільки 20 кубітів, проте IBM обіцяє надати комп’ютер з 50ю кубітами до кінця 2019 року;
 D-Wave Systems. Невелика компанія в порівнянні з гігантами індустрії, яка була заснована спеціально для розробки квантових комп’ютерів. Обравши для розробки дещо інший підхід ніж лідери ринку. У листопаді 2017 року D-Wave Systems анонсувала вихід свого нового квантового комп'ютера під назвою D-Wave 2000Q.
Анонсований комп’ютер містить в два рази більше кубітів ніж його попередник D-
Wave X2. Вже 23 січня 2017 D-Wave Systems почала продаж анонсованих D-Wave

26 2000Q. D-Wave 2000Q, як і попередні комп’ютери компанії уявляє собою адіабатичний комп'ютер, який працює за принципом квантового відпалу. D-Wave
2000Q складається з великої кількості компонентів і має багато контрольованих параметрів. Для функціонування D-Wave 2000Q, компоненти у ньому охолоджують до дуже низьких температур (комп'ютер попередньої моделі функціонував при температурі близькій до абсолютного нуля - близько -273 ° C). Після охолодження і досягнення системою мінімальної енергії, задані параметри повільно змінюються з використанням законів квантової механіки для переводу системи з початкового стану в новий стан мінімальної енергії за рахунок квантового тунелювання. Не заважаючи на велику кількість кубітів, комп'ютери компанії D-Wave System придатні для виконання лише одного типу завдань, а саме - завдань оптимізації. Беручи це до уваги,
D-Wave System не варто порівнювати з іншими компаніями розробниками квантових систем, а їх комп’ютери вважати повноцінними квантовим комп’ютерами[7];
 Google. Google представи 20 кубітний квантовий комп’ютер ще в 2017 році.
За словами інженерів кубіти в цьому комп’ютері були розташовані в довгі рядки.
Пізніше, наприкінці 2017 року, Google анонсував вихід нового 49-кубітного комп’ютера, кубіти в якому розташовані у сітці 7 на 7. Невдовзі після цього було анонсовано 72-кубітний комп’ютер з сіткою 6 на 12, який за словами інженерів буде використано для демонстрації так званої «квантової переваги», тобто для показу переваги ефективності обчислень на квантовому комп’ютері в порівнянні з класичним. Таким чином Google поки що виграє квантову гонку з найближчім конкурентом у вигляді IBM і їх 50-кубітного квантового комп’ютера;
 Microsoft. MQM – ініціатива, представлена Microsoft наприкінці 2017 року і направлена залучення до дослідження квантових обчислень усіх бажаючих. Нові можливості для дослідження стають можливі завдяки QDK що складається з нової мови програмування Q# [8] та емулятора квантового комп’ютера, який можна запустити, як локально, так і використовуючи Microsoft Azure. Окрім цього,
ініціатива включає розробку квантових комп’ютерів з підтримкою розподілених

27 квантових обчислень, що в найближчій час плануються до виходу у загальний доступ на платформі Azure.
Зважаючи на стрімкий розвиток квантових комп’ютерів, варто згадати про способи захисту своїх даних у пост-квантову еру:
 збільшити розмір ключів в алгоритмах шифрування. Навіть враховуючи те, що до появи потужного квантового комп'ютера можуть пройти десятиліття, не можна виключати появу інших варіантів криптоатак. Заважаючи на це, використання ключів
RSA-8192, P-384, або навіть P-521 цілком себе виправдовує, особливо якщо справа стосується конфіденційних документів;
 почати використовувати, або хоча б впроваджувати, пост-квантові криптографічні алгоритми. Різні пост-квантові алгоритми лежать у широкому спектрі практичності і зручності використання. Окрім того, зважаючи на досить короткий час в використання криптостійкість ряду з них залишається під питанням. Тим не менш, тим хто вже сьогодні хоче ступити в майбутнє, варто ознайомитися за найперспективнішими "постквантовими" алгоритмами, побудованими на базі завдань теорії решіток;
 уникати обміну ключами з використанням асиметричних протоколів під час обміну конфіденційною інформацією. Вже на сьогодні існують квантові алгоритми для ефективного вирішення задач, які лежать в основі сучасної асиметричної криптографії (задачі факторизації та пошуку дискретного логарифму), що робить використання, шифрування і цифрового підпису за дорогою RSA або еліптичних кривих, протоколи Ель-Гамаля і Діффі – Хеллмана небезпечним, так як їх компрометація це тільки питання часу і нарощування потужності квантових комп’ютерів. Необхідно впроваджувати інші протоколи обміну ключами або проводити обмін ключами фізично. Наприклад, в мессенджері Signal для обміну ключами можна взаємно просканувати QR-код на телефоні співрозмовника, що є дає непогані гарантії безпеки подальшого чатингу;

28
 почати використовувати більш криптостійкі симетричні алгоритми. Згідно останніх досліджень і уже розроблених алгоритмів, квантові комп’ютери у скорому майбутньому дозволять ефективно підбирати паролі і ключи симетричного шифрування. На даний момент передбачається двократний ріст ефективності вирішення подібних задач порівняно з класичним комп’ютером. Це означаю, що довжину ключів в використовуваних симетричних алгоритмах варто збільшити в два рази. Що стосується найпопулярнішого симетричного алгоритму шифрування AES, доцільним виглядає збільшення розміру ключів до 256-біт.
Базуючись на вищенаведеній інформації можна впевнено говорити про перспективність квантових обчислень, які надають вагоме прискорення в вирішенні цілого класу задач. Тим не менш, варто також зауважити, що в даний момент, як проектування і створення квантових комп’ютері, так і написання програм під них є досить складними задачами.
Попри це, треба розуміти, що квантові обчислення допомагають ефективно вирішувати тільки певний спектр задач. З цього виходить, що квантові комп’ютери не
є панацеєю і не є універсальним методом для подолання закону Мура про фундаментальні межі зменшення компонентів комп’ютерних систем.
Згідно з останніми дослідженнями, природний паралелізм, що надають квантові комп'ютери і нейрообчислювачі дозволяє значно збільшувати ефективність обчислень завдяки паралельній обробці інформації з величезною кількістю каналів (потоків), що приблизно дорівнює 106 і виконувати, таким чином, до 1013-1015 операцій в такт, що значно більше за максимальне число операцій в такт в інших комп’ютерних системах.
Імплементація квантових алгоритмів та побудова квантових систем - це дуже складна і трудомістка задача, через велику кількість проблем пов’язаних з ефектами квантової механіки. Серед таких проблем руйнування стану суперпозиції кубітів, під час виконання обчислень, внаслідок спостереження, неможливість забезпечення дебагу квантових додатків під час виконання, в силу вже згаданого ефекту спостереження, неможливість копіювання стану квантових регістрів, складності при

29 створенні та управлінні квантовими процесами всередині квантового комп'ютер. Тим не менш, навіть попри ці складності, уже існують багато реалізацій квантових комп’ютерів. Лідерами цього ринку є таки компанії Google, IBM, Intel та Microsoft.
Особняком стоїть D-Wave Systems з її вузькоспеціалізованими рішеннями. Окрім цього з’явилися зручні емулятори для навчання та досліджень, такі як QCP від Google, або QDK від Microsoft. Зважаючи на це, на «паралельному фронті» активно проходить розробка та тестування пост квантових криптографічних алгоритмів та протоколів.
1.4 Постановка задачі
Виходячи з проведеного аналізу предметної галузі метою даної роботи є дослідження квантового алгоритму Шора для пошуку дискретного логарифму та його порівняння з не-квантовими аналогами.
Однією з основних задач дослідження є оцінка ефективності роботи алгоритму
Шора для пошуку дискретного логарифму за умови використання сучасних
інструментів для квантових обчислень. Окрім цього в рамках роботи повинні бути виконані наступні завдання:
 дослідження NP - повних задач, пов’язаних з криптографією та дискретним логарифмуванням;
 дослідження особливостей побудови квантових комп’ютерів та особливостей квантових обчислень;
 аналіз алгоритмів дискретного логарифмування для до та пост квантового періоду;
 реалізація та порівняльний аналіз реалізованих алгоритмів.