Інформаційні технології

УДК 004.056.55

Колесник Дмитро Олександрович

студент

Харківського національного університету імені В.Н. Каразіна

 ПОРІВНЯЛЬНИЙ АНАЛІЗ ПЕРСПЕКТИВНИХ ЦИФРОВИХ ПІДПИСІВ НА ОСНОВІ АЛГЕБРАЇЧНИХ РЕШІТОК

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

Ключові слова: алгебраїчні решітки, постквантова криптографія, асиметричне шифрування.

На конкурс PQC, що проводить NIST США, було подано 69 пакетів заявок. Деякі пакети містять декілька алгоритмів, тому у сумі було отримано до розгляду більше 80 алгоритмів різного типу – шифрування, підпису, інкапсуляції ключів. З них було отримано 22 алгоритми (електронного) підпису (ЕП), що базуються на різних математичних апаратах. З усіх цих підписів я обрав лише 5, які відносяться до підписів на основі алгебраїчних решіток. У табл. 1 наведено криптографічні алгоритми типу ЕП [1].

Таблиця 1

Механізми підпису на основі решіток

Джерело: розробка автора

У таблиці 2 наведено механізми підпису, які були на сьогоднішній день вже атаковані, або відкликані [2].

Таблиця 2

Атаковані (відкликані) механізми підпису

У таблиці 3 наведено розміри основних параметрів вищерозглянутих механізмів підпису [2].

sk – особистий (секретний) ключ; pk – відкритий ключ;

sk size – розмір особистого (секретного) ключа у байтах;

pk size – розмір відкритого ключа у байтах;

pk/sk size – розмір відношення відкритий/особистий ключ у байтах;

Sign Average (signing (average)) – кількість тактів процесора, що витрачається на процес підпису (в середньому);

Keypair Average (KeyGeneration (Average)) – кількість тактів процесора, що витрачається на генерацію ключової пари (в середньому);

Open Average (Verification (average)) – кількість тактів процесора, що витрачається на перевірку підпису (в середньому);

bytes (Signature Size) – розмір підпису в байта

Джерело: розробка автора

1. Порівняльний аналіз механізмів підпису за основними параметрами

Наведемо порівняння механізмів підпису, що розглянуті у таблиці 3 за параметрами цієї ж таблиці.

Результати порівняння наведено на рисунках 1 – 7 [2]

Рис. 1. Порівняння розміру особистих (секретних) ключів механізмів підпису у байтах

Джерело: розробка автора

Рис. 2. Порівняння розміру відкритих ключів механізмів підпису у байтах

Джерело: розробка автора

Рис. 3. Порівняння розміру відношення відкритих/особистих ключів механізмів підпису у байтах

Джерело: розробка автора

Рис. 4. Порівняння кількості тактів процесора, що витрачається на процес підпису (в середньому)

Джерело: розробка автора

Рис. 5. Порівняння кількості тактів процесора, що витрачається на генерацію ключової пари (в середньому)

Джерело: розробка автора

Рис. 6. Порівняння кількості тактів процесора, що витрачається на перевірку підпису (в середньому)

Джерело: розробка автора

Рис. 7. Порівняння розміру підпису в байтах

Джерело: розробка автора

2. Порівняльний аналіз механізмів підпису за сукупністю безумовних та умовних критеріїв

Під час порівняльного аналізу використовувалася сукупність безумовних та умовних оцінок. Умовними виступали наступні характеристики алгоритмів:

• I_ст. – рівень криптографічної стійкості;
• l_в.к – довжина відкритого ключа;
• l_о.к – довжина особистого ключа;
• l_рез. – довжина результату криптоперетворення;
• Т_пр. – швидкість прямого криптоперетворення;
• Т_зв. – швидкість зворотного криптоперетворення.

Експертні оцінки використовувалися для оцінки важливості кожної наведеної характеристики, а безпосередньо при оцінці алгоритмів використовувалися об’єктивні числові значення, шкала оцінки та вагові коефіцієнти важливості характеристик, що були отримані при експертному оцінюванні (таблиця 4) [3].

Таблиця 4

Експертні оцінки характеристик криптоалгоритмів

В цьому дослідженні при виборі алгоритмів висувалися додаткові безумовні вимоги:

1. Алгоритм повинен гарантувати, що найменше 3 рівень безпеки за класифікацією NIST.
2. Якщо існує декілька варіантів наборів параметрів для одного алгоритму, то в порівнянні бере участь варіант, який гарантує найбільшу безпеку.

В таблиці 5 наведені характеристики обраних для порівняння алгоритмів, що засновані на використані перетворень в алгебраїчних решітках [4-5].

Таблиця 5

Характеристики алгоритмів підпису

У таблиці 6 наведено результати оцінювання вибраних механізмів підпису.

Таблиця 6

Результати оцінювання механізмів підпису

Джерело: розробка автора

На рисунку 8 відображено діаграму відносної переваги алгоритмів. Як видно за рисунка, перше місце займає Dilithium_very_high, друге місце ділять falcon1024 та falcon768, а третє місце займає qTesla_256.

Рис. 8. Відносна перевага алгоритмів підпису

Джерело: розробка автора

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

Розглядаючи алгоритми, можна відмітити наступне. Алгоритм falcon768 відрізняється від falcon1024 більш низькою стійкістю на рівні Dilithium_very_high. Falcon1024 має більш високий рівень стійкості, а falcon768 має більш високі інші основні характеристики. Алгоритм qTesla_256 має більші розміри підпису, але все одно не сильно поступається переможцям.

Література

1. Post-quantum crypto project. – Access mode: http://csrc.nist.gov/groups/ST/post-quantum-crypto/index.html.
2. Post-quantum cryptography lounge. [Електронний ресурс] – Режим доступу: https://www.safecrypto.eu/pqclounge/.
3. Yesina Maryna, Gorbenko Yurij (supervisor). Methods of cryptographic primitives comparative analysis // Inżynier XXI wieku (“Engineer of XXI Century” – the VI Inter University Conference of Students, PhD Students and Young Scientists: University of Bielsko-Biala, Poland, December 02, 2016). – Bielsko-Biała: Wydawnictwo Naukowe Akademii Techniczno-Humanistycznej w Bielsku-Białej, 2016. – P. 451–462. – ISBN 978-83-65182-51-7. – Chapter in monograph.
4. Post-Quantum Cryptography [Electronic resource]. – Access mode: https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions.
5. NIST Software performance tests [Electronic resource]. – Access mode: https://www.safecrypto.eu/pqclounge/.