Congratulation from Internet Conference!
Hello
ПРО ДОКВАНТОВІ ТА ПОСТКВАНТОВІ АСИМЕТРИЧНІ КРИПТОСИСТЕМИ
10.11.2023 08:46
[1. Information systems and technologies]
Author: Оберишин Роксолана Ростиславівна, асистент кафедри спеціалізованих комп’ютерних систем, Національний університет “Львівська політехніка” м. Львів; Попович Роман Богданович, доктор фізико-математичних наук, професор, професор кафедри спеціалізованих комп’ютерних систем, Національний університет “Львівська політехніка” м. Львів
У даній доповіді розглядаємо ризики зламу традиційних асиметричних криптосистем з використанням квантових комп’ютерів, а також нові криптосистеми, які були б стійкими до квантових обчислень.
Двома найбільш використовуваними асиметричними криптосистемами є RSA (заснована на факторизації цілих чисел) та ECC (заснована на задачі дискретного логарифмування) [1,с. 2].
При побудові RSA випадково вибираємо два великі прості числа p i q та обчислюємо добуток n = p q. Також випадково вибираємо число e таке, що e < ф(n) = (p-1)(q-1), та e взаємно просте з ф(n). Крім того, обчислюємо число d, що задовольняє умову e d = 1 (mod ф(n)). Пара чисел e, n є публічним ключем, а число d - приватним ключем. Щоб отримати число d, треба знати множники p i q.
Шифрування (числа з проміжку 0 <= m <= n) полягає в обчисленні E(m) = me mod n. Тоді для блоку явного тексту m отримуємо криптограму c = E(m). Дешифрування полягає в обчисленні значень D(c) = cd mod n. RSA можна використати і для цифрового підписування.
RSA є криптосистемою, стійкість якої ґрунтується на складності розв’язування задачі розкладу великих цілих чисел на прості множники. При використанні класичних комп’ютерів ця задача є обчислювально складною. Зокрема, для найкращого відомого методу решета [2,с. 50] обсяг обчислень залежить від кількості бітів k = log2 n числа n так: 
, де стала Е > 0 (субекспоненційна складність).
, де стала Е > 0 (субекспоненційна складність).Криптографія з використанням еліптичних кривих ґрунтується на складності обчислення дискретного логарифму на еліптичних кривих. Нехай q – степінь простого числа, і нехай a та b - такі елементи поля , що 4a3 + 27b2 ≠ 0. Еліптичною кривою Е над полем називають множину розв’язків (x, y) рівняння y2 = x3 + ax + b разом з додатковою точкою в нескінченності. Множина точок еліптичної кривої Е із заданою певним способом операцією утворює абелеву групу. Користуючись операцією додавання точок на кривій, визначаємо операцію множення точки кривої на довільне ціле число n: nP = P + P + P +…+ P, P є E, де додавання виконують n разів.
У загальному випадку задача криптоаналізу системи, побудованої на еліптичних кривих, рівносильна розв’язуванню такої задачі дискретного логарифмування. Задано еліптичну криву Е, точку P є E на цій кривій та добуток nP; визначити число n. На сьогодні, найбільш ефективним для вирішення цієї задачі є алгоритм, реалізований з використанням методів Поларда [3,с. 333]. Його складність оцінюють як:
де k - кількість біт для зображення точки еліптичної кривої.
де k - кількість біт для зображення точки еліптичної кривої.Квантові комп’ютери використовуючи квантовий алгоритм Шора, можуть ефективно розв’язати дві розглянуті раніше задачі, що приведе до порушення безпеки RSA [4,с. 1499] та ECC [4,с. 1503]. Цей алгоритм може розкласти на прості множники і розв’язати логарифмічне рівняння за час O(k3) (поліноміальна складність) при використанні O(k) кубітів. Слід зауважити, що відомі на сьогодні квантові комп’ютери мають щонайбільше 66 кубітів. Цього недостатньо, щоб провести описані квантові атаки.
Отже, з часом квантові комп’ютери зможуть розкривати приватні ключі, які зараз вважаються стійкими на класичних комп’ютерах. Це створює потенційну загрозу для існуючих криптографічних систем з відкритим ключем, таких як RSA і ECC. Тому, розробляються квантовостійкі криптосистеми на основі різних математичних принципів та алгоритмів, які будуть складними для розв’язання як за допомогою класичних, так і квантових комп’ютерів.
На даний час, існує декілька типів квантово-стійких алгоритмів [1,с. 1]: криптографія на основі ґраток (lattice-based cryptography); криптографія багатьох змінних (multivariate cryptography); криптографія на основі хеш-функцій (hash-based cryptography); криптографія на основі кодів коригування помилок (code-based cryptography); криптографія на основі ізогеній (isogeny-based cryptography). Далі розглянемо два найбільш перспективні напрямки.
Криптографія на основі ґраток ґрунтується на складності розв’язування задач, пов’язаних із ґратками. Зокрема, це задача найкоротшого ненульового вектора, яка має експоненційну складність [1,с. 147].
Типовою для цього напрямку криптосистемою з відкритим ключем є система NTRU [5,с. 267]. Процедура шифрування в ній використовує змішування на основі алгебри многочленів та зведення за модулями двох чисел p та q, в той час як дешифрування використовує розділення, чия правильність спирається на елементарну теорію ймовірностей. Безпека NTRU випливає з поєднання поліноміальної системи змішування з незалежністю зведення за модулями p та q. Безпека також спирається на (експериментально спостережений) факт, що для більшості граток, дуже важко знайти надзвичайно короткі вектори.
NTRU задають числами (N,p,q) та множинами Lf,Lg,Lr,Lm многочленів степеня N-1 з цілими коефіцієнтами. p та q взаємно прості і q значно більше від p. Обчислення проводять в фактор-кільці 
Очевидно, що множення 
двох многочленів (елементів цього кільця) зводиться до циклічної згортки двох масивів коефіцієнтів цих многочленів.
Очевидно, що множення двох многочленів (елементів цього кільця) зводиться до циклічної згортки двох масивів коефіцієнтів цих многочленів.Для утворення ключів випадково вибирають многочлени f є Lf (приватний ключ),g є Lg . f повинен мати обернені за модулями p та q: 
Тоді обчислюють 
(публічний ключ). При шифруванні повідомлення m є Lm випадково вибирають r є Lr і знаходять криптограму 
При дешифруванні обчислюють 
Для відповідних значень параметрів, є дуже велика ймовірність, що дешифрування відтворить початкове повідомлення.
Тоді обчислюють (публічний ключ). При шифруванні повідомлення m є Lm випадково вибирають r є Lr і знаходять криптограму При дешифруванні обчислюють Для відповідних значень параметрів, є дуже велика ймовірність, що дешифрування відтворить початкове повідомлення.Атака на приватний ключ NTRU полягає в розгляді гратки, породженої векторами, елементами яких є коефіцієнти публічного ключа та певний параметр a. Гратка містить вектор r=(af, g) довжини 2N, що включає N коефіцієнтів многочлена f помножених на a, а після них N коефіцієнтів многочленна g. Знайшовши цей вектор, зможемо обчислити приватний ключ f. Криптографія багатьох змінних [6,с. 28] - це загальний термін для асиметричних примітивів на основі поліномів багатьох змінних над скінченним полем F. Типова побудова передбачає використання двох лінійних перетворень 
та нелінійного перетворення 
для якого знаємо обернене V-1. Трійка 
є приватним ключем. Публічний ключ це композиція перетворень 
для якої важко знайти обернене перетворення (розв’язати систему поліноміальних рівнянь багатьох змінних над скінченним полем), не маючи приватного ключа.
та нелінійного перетворення для якого знаємо обернене V-1. Трійка є приватним ключем. Публічний ключ це композиція перетворень для якої важко знайти обернене перетворення (розв’язати систему поліноміальних рівнянь багатьох змінних над скінченним полем), не маючи приватного ключа.При утворенні цифрового підпису повідомлення хешуємо до вектора y є Fn та, використовуючи приватний ключ, обчислюємо підпис 
Для перевірки підпису обчислюємо хеш y та виконуємо перевірку W(x) = y.
Для перевірки підпису обчислюємо хеш y та виконуємо перевірку W(x) = y. Близькою до вказаного напрямку є також криптосистема [7,с. 1279], яка базується на загальній лінійній групі квадратних невироджених матриць над груповим кільцем. Важким обчислювальним завданням є комбінація проблеми дискретного логарифму та проблеми спряженості.
Література
1.Bernstein J., Buchmann D., Dahmen E. Post-quantum Cryptography. Springer, Berlin. 2009. 246 p.
2.Buhler J. P.; Lenstra H. W. Jr., Pomerance C. Factoring Integers with the Number Field Sieve. Lecture Notes in Mathematics, vol 1554, Springer. 1993. P. 50–94.
3.Proos J., Zalka C. Shor’s Discrete Logarithm Quantum Algorithm for Elliptic Curves. Quantum Information and Computation. 2003.Vol.4. P. 317-344.
4.Shor P. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing. 1997. No. 26. P. 1484-1509.
5.Hoffstein J., Pipher J., Silverman J.H. NTRU: A Ring Based Public Key Cryptosystem. Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, Berlin. 1998. P. 267–288.
6.Ustimenko V. On Computations with Double Schubert Automaton and Stable Maps of Multivariate Cryptography. Interdisciplinary Studies of Complex Systems. 2021. No. 19. P. 18–32.
7.Inam S., Ali R., A New ElGamal-like Cryptosystem Based on Matrices over Groupring. Neural Computing and Applications. 2018. vol. 29. P. 1279-1283.
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter
Another articles in this section
-
АКТУАЛЬНІСТЬ ВИКОРИСТАННЯ ПРОГРАМНОГО ПРОДУКТУ «СИСТЕМА КУР'ЄРСЬКОЇ СЛУЖБИ»
31.10.2023 12:26 -
КОМП'ЮТЕРНА СИСТЕМА ДЛЯ ПЛАНУВАННЯ ПРИМІЩЕННЯ
12.11.2023 20:34 -
КОМП'ЮТЕРНА СИСТЕМА ДЛЯ ЧИСЕЛЬНОГО ІНТЕГРУВАННЯ
12.11.2023 20:23 -
ДОСЛІДЖЕННЯ МОДЕЛЮВАННЯ МЕРЕЖ ПЕТРІ НА БАЗІ РОЗРОБЛЕНОГО ПРОГРАМНОГО ПРОДУКТУ
12.11.2023 20:13 -
ПРОГРАМНЕ ЗАБЕЗПЕЧЕННЯ ДЛЯ АВТОМАТИЗАЦІЇ ОСВІТНІХ ПРОЦЕСІВ
12.11.2023 20:03
Сonferences
Conference 2024
Conference 2023
Conference 2022
Conference 2021
