Дослідження та впровадження швидкого методу обчислення порядку еліптичної кривої

Автор(и)

  • Ivan Gorbenko Харківський національний університет ім. В. Н. Каразіна пл. Свободи, 4, м. Харків, Україна, 61022, Україна https://orcid.org/0000-0003-4616-3449
  • Roman Hanzia Харківський національний університет радіоелектроніки пр. Науки, 14, м. Харків, Україна, 61166, Україна https://orcid.org/0000-0001-7945-3683

DOI:

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

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

метод Сато, метод Харлі, порядок еліптичних кривих двійкове поле, слід Фробеніуса

Анотація

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

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

Ivan Gorbenko, Харківський національний університет ім. В. Н. Каразіна пл. Свободи, 4, м. Харків, Україна, 61022

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

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

Roman Hanzia, Харківський національний університет радіоелектроніки пр. Науки, 14, м. Харків, Україна, 61166

Аспірант

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

Посилання

  1. Horbenko, Yu. I., Hanzia, R. S. (2014). Analysis of the possibility of quantum computers and quantum computings for cryptanalysis of modern cryptosystems. Eastern-European Journal of Enterprise Technologies, 1 (9 (67)), 8–16. Available at: http://journals.uran.ua/eejet/article/view/19897/18759
  2. Hanzia, R. S., Horbenko, Yu. I. (2014). Analiz shlyakhiv rozvytku kryptohrafiyi pislya poyavy kvantovykh kompyuteriv. Visnyk Natsional'noho universytetu “L'vivs'ka politekhnika”: Kompyuterni systemy ta merezhi, 806, 40–48.
  3. Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26 (5), 1484–1509. doi: 10.1137/s0097539795293172
  4. Horbenko, I. D., Horbenko, Yu. I. (2012). Prykladna kryptolohiya. Kharkiv: Fort, 868.
  5. Schoof, R. (1995). Counting points on an elliptic curve over finite fields. Proc. Journees Arithmetiques, 93, 219–252.
  6. Skjernaa, B. (2003). Satoh’s algorithm in characteristic 2. Mathematics of Computation, 72 (241), 477–488. doi: 10.1090/s0025-5718-02-01434-5
  7. Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F. (Eds.) (2005). Handbook of Elliptic and Hyperelliptic Curve Cryptography. NW.: Chapman & Hall/CRC, 807. doi: 10.1201/9781420034981
  8. Vercauteren, F. (2003). Computing zeta functions of curves over finite fields. Katholieke Universiteit Leuven, 195.
  9. Satoh, T. (2000). The Canonical Lift of an Ordinary Elliptic Curve over a Finite Field and its Point Counting. J. Ramanujan Math. Soc., 15 (4), 247–270.
  10. Satoh, T., Skjernaa, B., Taguchi, Y. (2003). Fast computation of canonical lifts of elliptic curves and its application to point counting. Finite Fields and Their Applications, 9 (1), 89–101. doi: 10.1016/s1071-5797(02)00013-8
  11. Harley, R. (2002). Asymptotically optimal p-adic point-counting. E-mail to NMBRTHRY list. Available at: https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0212&L=NMBRTHRY&F=&S=&P=7824
  12. Gaudry, P. (2002). A Comparison and a Combination of SST and AGM Algorithms for Counting Points of Elliptic Curves in Characteristic 2. Lecture Notes in Computer Science, 311–327. doi: 10.1007/3-540-36178-2_20
  13. Lercier, R., Lubicz, D. (2003). Counting Points on Elliptic Curves over Finite Fields of Small Characteristic in Quasi Quadratic Time. Lecture Notes In Computer Science, 360–373. doi: 10.1007/3-540-39200-9_22
  14. Hanzia, R. S. (2016). Otsinka obchyslyuval'noyi skladnosti metodiv pidrakhunku kil'kosti tochok na eliptychniy kryviy. Systemy obrobky informatsiyi, 8, 92–99.
  15. Satoh, T. (2001). Asymptotically fast algorithm for computing the Frobenius substitution and norms over unramied extension of p-adic number fields. Department of Mathematics, Faculty of Science, Saitame University, 1–21.

##submission.downloads##

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

2017-04-21

Як цитувати

Gorbenko, I., & Hanzia, R. (2017). Дослідження та впровадження швидкого методу обчислення порядку еліптичної кривої. Eastern-European Journal of Enterprise Technologies, 2(9 (86), 11–21. https://doi.org/10.15587/1729-4061.2017.95194

Номер

Том 2 № 9 (86) (2017): Інформаційно-керуючі системи

Розділ

Інформаційно-керуючі системи

Ліцензія

Авторське право (c) 2017 Ivan Horbenko, Roman Hanzia

Creative Commons License

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

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

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