Дослідження стійкості криптосистем побудованих на складності знаходження дискретного логарифму

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.