Обгрунтування коректності та переваг методу факторизації Лєнстра на кривих Едвардса

Автор(и)

  • Lyudmyla Kovalchuk Інститут служби зовнішньої розвідки України вул. Бульварно-Кудрявська, 11, м. Київ, Україна, 04053, Україна https://orcid.org/0000-0003-2874-7950
  • Oleksij Bespalov Фізико-технічний інститут Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського” пр. Перемоги, 37, м. Київ, Україна, 03056, Україна https://orcid.org/0000-0001-7126-6752
  • Nataliia Kuchynska Інститут служби зовнішньої розвідки України вул. Бульварно-Кудрявська, 11, м. Київ, Україна, 04053, Україна https://orcid.org/0000-0002-6457-7525
  • Polina Seliukh Фізико-технічний інститут Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського” пр. Перемоги, 37, м. Київ, Україна, 03056, Україна https://orcid.org/0000-0002-0027-6037
  • Artem Zhylin Інститут спеціального зв’язку та захисту інформації Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського” вул. Верхньоключова, 4, м. Київ, Україна, 03056, Україна https://orcid.org/0000-0002-4959-612X
  • Vasyl Tsurkan Інститут спеціального зв’язку та захисту інформації Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського” вул. Верхньоключова, 4, м. Київ, Україна, 03056, Україна https://orcid.org/0000-0003-1352-042X

DOI:

https://doi.org/10.15587/1729-4061.2018.151090

Ключові слова:

криптосистема RSA, задача факторизації, методи факторизації, метод Лєнстра, криві Едвардса

Анотація

Розглядається задача факторизації, на якій базуються багато класичних асиметричних систем (RSA, Рабіна, інші) та криптографічно сильних генераторів псевдовипадкових послідовностей (BBS). Коротко описані методи, які послугували прообразами методу Лєнстра, та запропоновано метод факторизації чисел, який є аналогом методу Лєнстра на кривих Едвардса. Спочатку для обґрунтування коректності методу розроблено відповідний математичний апарат. Далі, з використанням цього апарату, побудовано аналог методу Лєнстра на кривих Едвардса та розроблено відповідний алгоритм факторизації чисел. Математично обґрунтовано коректність методу, коректність роботи алгоритму; отримано та строго доведено верхні аналітичні оцінки для його швидкодії та нижні оцінки імовірності успіху. Наведено та строго обґрунтовано переваги розробленого методу у порівнянні з класичним методом Лєнстра, який застосовує еліптичні криві у формі Вейєрштраса. Проведено порівняльний аналіз нового та класичного алгоритмів.

За результатами досліджень отримано строгі доведення того, що новий алгоритм на повних кривих Едвардса, у порівнянні з класичним, має переваги у швидкодії приблизно у 1.5 рази. Наведено експериментальні результати, які показують, що швидкодія зростає іще більше (до 30 відсотків), якщо замість повних кривих Едвардса використовувати скручені та квадратичні криві. Показано, що оцінка імовірності успіху нового методу зросте за рахунок появи нових умов, які приводять до успіху алгоритму та які не існують для класичного алгоритму Лєнстра на кривих Вейєрштраса.

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

Біографії авторів

Lyudmyla Kovalchuk, Інститут служби зовнішньої розвідки України вул. Бульварно-Кудрявська, 11, м. Київ, Україна, 04053

Доктор технічних наук, професор

Кафедра № 22

Oleksij Bespalov, Фізико-технічний інститут Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського” пр. Перемоги, 37, м. Київ, Україна, 03056

Аспірант

Кафедра математичних методів захисту інформації

Nataliia Kuchynska, Інститут служби зовнішньої розвідки України вул. Бульварно-Кудрявська, 11, м. Київ, Україна, 04053

Кандидат технічних наук

Кафедра № 24

Polina Seliukh, Фізико-технічний інститут Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського” пр. Перемоги, 37, м. Київ, Україна, 03056

Аспірант

Кафедра математичних методів захисту інформації

Artem Zhylin, Інститут спеціального зв’язку та захисту інформації Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського” вул. Верхньоключова, 4, м. Київ, Україна, 03056

Кандидат технічних наук

Кафедра безпеки державних інформаційних ресурсів

Vasyl Tsurkan, Інститут спеціального зв’язку та захисту інформації Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського” вул. Верхньоключова, 4, м. Київ, Україна, 03056

Кандидат технічних наук

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

Посилання

  1. Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W. et. al. (2010). Factorization of a 768-Bit RSA Modulus. Lecture Notes in Computer Science, 333–350. doi: https://doi.org/10.1007/978-3-642-14623-7_18
  2. Bouvier, C., Imbert, L. (2018). Faster cofactorization with ECM using mixed representations. IACR Cryptology ePrint Archive, 669.
  3. Lenstra, A. K. (2017). General Purpose Integer Factoring. Topics in Computational Number Theory Inspired by Peter L. Montgomery, 116–160. doi: https://doi.org/10.1017/9781316271575.006
  4. Lenstra, A. K., Lenstra, H. W. Jr. (1987). Algorithms in number theory. Technical Report 87-008. Chicago: University of Chicago.
  5. Lenstra, H. W. Jr. (1986). Elliptic curves and number-theoretic algorithms. Report 86-19. Amsterdam: Mathematisch Instituut, Universiteit van Amsterda.
  6. Lenstra, H. W. (1987). Factoring Integers with Elliptic Curves. The Annals of Mathematics, 126 (3), 649. doi: https://doi.org/10.2307/1971363
  7. Koblitz, N. (1994). A Course in Number Theory and Cryptography. Springer, 235. doi: https://doi.org/10.1007/978-1-4419-8592-7
  8. Solov'ev, Yu. P., Sadovnichiy, V. A., Shavgurlidze, E. T., Belokurov, V. V. (2003). Ellipticheskie krivye i sovremennye algoritmy teorii chisel. Moscow: Izhevsk, 192.
  9. Bernstein, D. J., Birkner, P., Lange, T., Peters, C. (2012). ECM using Edwards curves. Mathematics of Computation, 82 (282), 1139–1179. doi: https://doi.org/10.1090/s0025-5718-2012-02633-0
  10. Hisil, H., Wong, K. K.-H., Carter, G., Dawson, E. (2008). Twisted Edwards Curves Revisited. Lecture Notes in Computer Science, 326–343. doi: https://doi.org/10.1007/978-3-540-89255-7_20
  11. Gélin, A., Kleinjung, T., Lenstra, A. K. (2016). Parametrizations for Families of ECM-friendly curves. IACR Cryptology ePrint Archive. Available at: https://eprint.iacr.org/2016/1092.pdf
  12. Edwards, H. M. (2007). A normal form for elliptic curves. Bulletin of the American Mathematical Society, 44 (03), 393–423. doi: https://doi.org/10.1090/s0273-0979-07-01153-6
  13. Bernstein, D. J., Lange, T. (2007). Faster Addition and Doubling on Elliptic Curves. Lecture Notes in Computer Science, 29–50. doi: https://doi.org/10.1007/978-3-540-76900-2_3
  14. Pollard, J. M. (1974). Theorems on factorization and primality testing. Mathematical Proceedings of the Cambridge Philosophical Society, 76 (03), 521. doi: https://doi.org/10.1017/s0305004100049252
  15. Bessalov, A. V. (2017). Ellipticheskie krivye v forme Edvardsa i kriptografiya. Kyiv, 272.
  16. Bernstein, D. J., Birkner, P., Joye, M., Lange, T., Peters, C. (2008). Twisted Edwards Curves. Lecture Notes in Computer Science, 389–405. doi: https://doi.org/10.1007/978-3-540-68164-9_26
  17. Bessalov, A. V., Kovalchuk, L. V. (2015). Exact Number of Elliptic Curves in the Canonical Form, Which are Isomorphic to Edwards Curves Over Prime Field. Cybernetics and Systems Analysis, 51 (2), 165–172. doi: https://doi.org/10.1007/s10559-015-9709-x
  18. Bessalov, A. V., Dihtenko, A. A. (2013). Cryptographically resistant Edwards curves over prime fields. Applied Radio Electronics, 12 (2), 285–291.
  19. Bespalov, O. Yu., Kuchynska, N. V. (2017). Kryva Edvardsa nad kiltsem lyshkiv yak dekartiv dobutok kryvykh Edvardsa nad skinchenymy poliamy. Prikladnaya radioelektronika, 16 (3-4), 170–175.

##submission.downloads##

Опубліковано

2018-12-17

Як цитувати

Kovalchuk, L., Bespalov, O., Kuchynska, N., Seliukh, P., Zhylin, A., & Tsurkan, V. (2018). Обгрунтування коректності та переваг методу факторизації Лєнстра на кривих Едвардса. Eastern-European Journal of Enterprise Technologies, 6(4 (96), 6–14. https://doi.org/10.15587/1729-4061.2018.151090

Номер

Том 6 № 4 (96) (2018): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2018 Lyudmyla Kovalchuk, Oleksij Bespalov, Nataliia Kuchynska, Polina Seliukh, Artem Zhylin, Vasyl Tsurkan

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.