Please use this identifier to cite or link to this item:
http://elartu.tntu.edu.ua/handle/lib/49893
Title: | Дослідження стійкості криптосистем побудованих на складності знаходження дискретного логарифму |
Other Titles: | Research on the resistance of cryptosystems built on the complexity of finding the discrete logarithm |
Authors: | Шевчук, Уляна Любомирівна Shevchuk, Uliana |
Affiliation: | ТНТУ ім. І. Пулюя, Факультет комп’ютерно-інформаційних систем і програмної інженерії, Кафедра кібербезпеки, м. Тернопіль, Україна |
Bibliographic description (Ukraine): | Шевчук У. Л. Дослідження стійкості криптосистем побудованих на складності знаходження дискретного логарифму : робота на здобуття кваліфікаційного ступеня бакалавра : спец. 125 - кібербезпека / наук. кер. Загородна Н. В. Тернопіль : Тернопільський національний технічний університет імені Івана Пулюя, 2025. 57 с. |
Issue Date: | 27-Jun-2025 |
Submitted date: | 13-Jun-2025 |
Date of entry: | 6-Aug-2025 |
Country (code): | UA |
Place of the edition/event: | ТНТУ ім. І.Пулюя, ФІС, м. Тернопіль, Україна |
Supervisor: | Загородна, Наталія Володимирівна Zagorodna, Nataliya |
Committee members: | Марценко, Сергій Васильович Martsenko, Serhii |
UDC: | 004.56 |
Keywords: | дискретний логарифм discrete logarithm криптосистема cryptosystem Полг-Хеллман Pohlig-Hellman атака attack |
Abstract: | Кваліфікаційна робота присвячена аналізу задачі дискретного логарифму та атак на криптосистеми, що ґрунтуються на цій проблемі.
Для кращого розуміння задачі, описано математичні основи, а саме групи, їхні типи і властивості. Проаналізовано проблему обчислення дискретного логарифму, як і в класичних мультиплікативних групах, так і в групах точок еліптичних кривих.
У роботі розглянуто такі атаки, як: метод повного перебору, метод Шенкса, алгоритм Полларда "По", алгоритм індексного числення, алгоритм Поліг-Хеллмана та інші. Оцінено переваги і недоліки кожного з методів. Також було проаналізовано специфіку атак на задачу дискретного логарифму на еліптичних кривих. Надано рекомендації щодо підвищення стійкості криптографічних систем до зазначених атак.
Розроблено математичну та програмну реалізації методу Поліг-Хеллмана, який дозволяє ефективно розв’язувати задачу дискретного логарифму. Проведено тестування цієї реалізації та досліджено ефективність. Отримані результати дозволяють краще зрозуміти принцип дії атаки та її обмеження. The qualification thesis is devoted to the analysis of the discrete logarithm problem and of attacks on cryptosystems that are based on this problem. For a better understanding of the problem, the mathematical foundations are described, namely groups, their types and properties. The problem of computing the discrete logarithm has been analysed both in classical multiplicative groups and in groups of points of elliptic curves. The thesis considers such attacks as: the brute-force method, the Shanks method, Pollard’s "Rho" algorithm, the Index Calculus algorithm, the Pohlig-Hellman algorithm and others. The advantages and disadvantages of each method have been evaluated. The specifics of attacks on the discrete logarithm problem on elliptic curves have also been analysed. Recommendations are provided for increasing the resistance of cryptographic systems to the specified attacks. Mathematical and software implementations of the Pohlig-Hellman method have been developed, which allow the discrete logarithm problem to be solved efficiently. This implementation has been tested and its effectiveness studied. The obtained results make it possible to better understand the principle of operation of the attack and its limitations. |
Content: | РОЗДІЛ 1 ТЕОРЕТИЧНІ ОСНОВИ ДИСКРЕТНОГО ЛОГАРИФМУ 8 1.1 АЛГОРИТМИ, ПОБУДОВАНІ НА ЗАДАЧІ ДИСКРЕТНОГО ЛОГАРИФМУ ТА ЇХ ІСТОРІЯ РОЗВИТКУ 8 1.2 МАТЕМАТИЧНІ ОСНОВИ 9 1.3 ПРОБЛЕМА ДИСКРЕТНОГО ЛОГАРИФМУ 12 РОЗДІЛ 2 АНАЛІЗ АТАК НА КРИПТОГРАФІЧНІ СИСТЕМИ, ЩО ПОБУДОВАНІ НА ЗАДАЧІ ДИСКРЕТНОГО ЛОГАРИФМУ 17 2.1 ЗАГАЛЬНА ХАРАКТЕРИСТИКА 17 2.2 ЗАГАЛЬНІ АЛГОРИТМИ 19 2.3 СПЕЦІАЛІЗОВАНІ АЛГОРИТМИ 23 2.4 АТАКИ НА ЕЛІПТИЧНІ КРИВІ 26 2.5 РЕКОМЕНДАЦІЇ ЩОДО ПІДВИЩЕННЯ СТІЙКОСТІ КРИПТОГРАФІЧНИХ СИСТЕМ 27 РОЗДІЛ 3 ДОСЛІДЖЕННЯ ТА РЕАЛІЗАЦІЯ АТАКИ ПОЛІГ-ХЕЛЛМАНА 31 3.1 МАТЕМАТИЧНА РЕАЛІЗАЦІЯ 31 3.2 ПРОГРАМНА РЕАЛІЗАЦІЯ 35 3.3 АНАЛІЗ ОТРИМАНИХ РЕЗУЛЬТАТІВ 42 РОЗДІЛ 4 БЕЗПЕКА ЖИТТЄДІЯЛЬНОСТІ, ОСНОВИ ОХОРОНИ ПРАЦІ 45 ВИСНОВКИ 50 СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 51 ДОДАТОК А ПРОГРАМНА РЕАЛІЗАЦІЯ POHLIG-HELLMAN 54 |
URI: | http://elartu.tntu.edu.ua/handle/lib/49893 |
Copyright owner: | © Шевчук Уляна Любомирівна, 2025 |
References (Ukraine): | 1. Christof Paar Jan. Understanding cryptography: a textbook for students and practitioners. 2nd ed. Berlin : Springer, 2010. 372 p. 2. Dummit D. S. Foote R. M. Abstract algebra. 3rd ed. Hoboken, NJ : Wiley, 2004. 932 p. 3. Gallian Joseph A. Contemporary abstract algebra. 9th ed. Boston, MA : Cengage Learning, 2017. 654 p. 4. Nils Fleischhacker Tibor Jager Dominique Schröder. On tight security proofs for schnorr. Journal of cryptology. 2019. 5. Загородна Н. В. Основи криптографії відкритих ключів. Електронне навчання ТНТУ. URL: https://dl.tntu.edu.ua/content.php?cid=415159 (дата звернення: 22.05.2025). 6. Що таке проблема дискретного логарифмування еліптичної кривої (ECDLP) і чому її важко вирішити? - Академія EITCA. EITCA Academy. URL: https://uk.eitca.org/cybersecurity/eitc-is-acc-advanced-classical-cryptography/elliptic-curve-cryptography/introduction-to-elliptic-curves/examination-review-introduction-to-elliptic-curves/what-is-the-elliptic-curve-discrete-logarithm-problem-ecdlp-and-why-is-it-difficult-to-solve/ (дата звернення: 01.06.2025). 7. A public-key infrastructure for key distribution in tinyos based on elliptic curve cryptography. Proceedings of the first IEEE international conference on sensor and ad hoc communications and networks (SECON) : conference proceedings, Santa Clara, California, 4–7 October 2004. 8. Neal Koblitz. A course in number theory and cryptography. 2nd ed. New York, USA : Springer, 2012. 235 p. 9. Contributors to Wikimedia projects. Baby-step giant-step - Wikipedia. Wikipedia, the free encyclopedia. URL: https://en.wikipedia.org/wiki/Baby-step_giant-step (date of access: 14.05.2025). 10. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Handbook of Applied Cryptography. Boca Raton : CRC Press, 1996. 780 p. 11. Contributors to Wikimedia projects. Elliptic-curve cryptography - Wikipedia. Wikipedia, the free encyclopedia. URL: https://en.wikipedia.org/wiki/Elliptic-curve_cryptography (date of access: 20.05.2025). 12. Darrel Hankerson, Alfred J. Menezes, Scott A. Vanstone. Guide to elliptic curve cryptography. New York : Springer, 2004. 312 p. 13. NIST SP 800-57 Part 1 Rev. 5. Recommendation for key management. Replaces NIST SP 800-57 Part 1 Rev. 4 ; effective from 2020-05-01. Official edition. Gaithersburg : U.S. Department of Commerce, 2020. 85 p. 14. FIPS 186 5. Digital signature standard. Replaces FIPS 186 4 ; effective from 2023-02-03. Official edition. Gaithersburg : U.S. Department of Commerce / NIST, 2023. 15. RFC 7748. Elliptic Curves for Security. Effective from 2016-01-22. Official edition. 16. Android security vulnerability. Bitcoin.org. URL: https://bitcoin.org/en/alert/2013-08-11-android (date of access: 11.03.2025). 17. Paul C. Kocher. Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems. Advances in cryptology – CRYPTO ’96 (16th annual international cryptology conference) : Conference paper, Santa Barbara, California. 18. Учасники проектів Вікімедіа. Алгоритм Шора – Вікіпедія. Вікіпедія. URL: https://uk.wikipedia.org/wiki/Алгоритм_Шора (дата звернення: 27.05.2025). 19. NIST Releases First 3 Finalized Post-Quantum Encryption Standards. NIST. URL: https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards (date of access: 28.05.2025). 20. Weiterleitungshinweis. Google. URL: https://www.google.com/url?sa=i&url=https://www.cryptologie.net/article/360/how-to-backdoor-diffie-hellman-quick-explanation/&psig=AOvVaw1wnxH1lefXU9oZWEhO83ba&ust=1749841918811000&source=images&cd=vfe&opi=89978449&ved=0CBMQjhxqFwoTCKC35LDL7I0DFQAAAAAdAAAAABAK (date of access: 30.03.2025). 21. Hoffstein J. Pipher J. Silverman J. H. Introduction to Mathematical Cryptography. 2nd ed. NY, USA : Springer, 2010. 524 p. 22. Yesin, V., Karpinski, M., Yesina, M., Vilihura, V., Kozak, R., Shevchuk, R. (2023). Technique for Searching Data in a Cryptographically Protected SQL Database. Applied Sciences, 13(20), art. no. 11525, 1-21. doi: 10.3390/app132011525. 23. Skorenkyy, Y., Kozak, R., Zagorodna, N., Kramar, O., & Baran, I. (2021, March). Use of augmented reality-enabled prototyping of cyber-physical systems for improving cyber-security education. In Journal of Physics: Conference Series (Vol. 1840, No. 1, p. 012026). IOP Publishing. 24. Kuznetsov, O., Poluyanenko, N., Frontoni, E., Kandiy, S., Karpinski, M., & Shevchuk, R. (2024). Enhancing Cryptographic Primitives through Dynamic Cost Function Optimization in Heuristic Search. Electronics, 13(10), 1-52. doi: 10.3390/electronics13101825. 25. Деркач М. В., Мишко О. Є. Використання алгоритму шифрування AES-256-CBC для зберігання даних автентифікації автономного помічника. Наукові вісті Далівського університету. 2023. №24. 26. Гульчак Ю. П. Северин Л. І. Основи інженерної психології. Вінниця : ВНТУ, 2004. 105 с. 27. Брусенцов В. Г., Савченко С. О., Снігур В. І. Основи ергономіки. Харків : УкрДАЗТ, 2011. 141 с. 28. ДБН В.2.5-56:2014. Системи протипожежного захисту. Чинний від 2015-07-01. Вид. офіц. Київ, 2014. 29. Слуцька О. М., Скоробагатько Т. М., Скоробагатько Т. М. Необхідність удосконалення вимог до систем пожежної сигналізації. Пожежна безпека. 204. С. 70–78. 30. Навчально-методичний посібник до практичних заняття з дисципліни «Безпека життєдіяльності, основи охорони праці» для студентів освітнього ступеня ,,бакалавр" усіх спеціальностей та форм навчання / О. Я. Гурик та ін. Тернопіль : ТНТУ ім. Ів. Пулюя, 2025. 123 с. |
Content type: | Bachelor Thesis |
Appears in Collections: | 125 — Кібербезпека, Кібербезпека та захист інформації (бакалаври) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Shevchuk_Uliana_SB42_2025.pdf | 1,32 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
Admin Tools