ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2022-22-4-674-680ntv-179Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEПостроение криптографических схем, основанных на эллиптических кривых над рациональными числамиBuilding cryptographic schemes based on elliptic curves over rational numbershttps://orcid.org/0000-0002-5544-2434ДавыдовВ. В.DavydovV. V.

Давыдов Вадим Валерьевич — преподаватель

sc 57203909696

Санкт-Петербург, 197101

Vadim V. Davydov — Lecturer

sc 57203909696

Saint Petersburg, 197101

vvdavydov@itmo.ruhttps://orcid.org/0000-0002-4084-8829ДакуоЖ.-М. Н.DakuoJ.-M. N.

Дакуо Жан-Мишель Никодэмович — студент,

Санкт-Петербург, 197101

Jean-Michelle N. Dakuo — Student

Saint Petersburg, 197101

jeandakuo@itmo.ruhttps://orcid.org/0000-0002-0856-2249ИогансонИ. Д.IogansonI. D.

Иогансон Иван Дмитриевич — инженер

Санкт-Петербург, 197101

Ivan D. Ioganson — Engineer

Saint Petersburg, 197101

ivan.ioganson@itmo.ruhttps://orcid.org/0000-0001-5494-7142ХуцаеваА. Ф.KhutsaevaA. F.

Хуцаева Алтана Феликсовна — инженер

Санкт-Петербург, 197101

Altana F. Khutsaeva — Engineer

Saint Petersburg, 197101

afkhutsaeva@itmo.ruУниверситет ИТМОРоссияITMO UniversityRussian Federation202214122024224674680Copyright © Давыдов В.В., Дакуо Ж.Н., Иогансон И.Д., Хуцаева А.Ф., 20242024Давыдов В.В., Дакуо Ж.Н., Иогансон И.Д., Хуцаева А.Ф.Davydov V.V., Dakuo J.N., Ioganson I.D., Khutsaeva A.F.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/179

Предмет исследования. Исследована возможность использования в криптографических схемах эллиптических кривых над полем рациональных чисел ненулевого ранга. Метод. Впервые предложено построение криптосистем, безопасность которых основана на сложности решения математической задачи о рюкзаке на эллиптических кривых над рациональными числами ненулевых рангов. Основные результаты. Описан новый подход использования эллиптических кривых для криптографических схем. Выполнен ряд экспериментов для оценки поведения высот точек эллиптических кривых бесконечного порядка. Представлена модель криптосистемы, стойкой к вычислениям на квантовом компьютере и основанной на использовании рациональных точек кривой бесконечного порядка. Проведено исследование криптографической стойкости и эффективности предлагаемой схемы. Реализована атака на поиск секрета в криптосистеме, показано, что сложность атаки экспоненциальна. Практическая значимость. Рассмотренное решение может быть применено при построении реальных криптографических схем и протоколов.

The possibility of using elliptic curves over the rational field of non-zero ranks in cryptographic schemes is studied. For the first time, the construction of cryptosystems is proposed the security of which is based on the complexity of solving the knapsack problem on elliptic curves over rational numbers of non-zero ranks. A new approach to the use of elliptic curves for cryptographic schemes is proposed. A few experiments have been carried out to estimate the heights characteristic of points on elliptic curves of infinite order. A model of a cryptosystem resistant to computations on a quantum computer and based on rational points of an infinite order curve is proposed. A study of the security and effectiveness of the proposed scheme has been carried out. An attack on the secret search in such a cryptosystem is implemented and it is shown that the complexity of the attack is exponential. The proposed solution can be applied in the construction of real cryptographic schemes as well as cryptographic protocols.

эллиптические кривыерациональные числаранг кривыхасимметричное шифрованиезадача о рюкзакеelliptic curvesrational numberscurve rankasymmetric encryptionknapsack problemРабота выполнена при поддержке программы «Приоритет 2030».This research was supported by Priority 2030 Federal Academic Leadership Program.ReferencesKoblitz N., Menezes A., Vanstone S. The state of elliptic curve cryptography // Designs, Codes and Cryptography. 2000. V. 19. N 2-3. P. 173–193. https://doi.org/10.1023/A:1008354106356Koblitz N., Menezes A., Vanstone S. The state of elliptic curve cryptography. Designs, Codes and Cryptography, 2000, vol. 19, no. 2-3, pp. 173–193. https://doi.org/10.1023/A:1008354106356Koblitz N. Elliptic curve cryptosystems // Mathematics of Computation. 1987. V. 48. N 177. P. 203–209. https://doi.org/10.1090/S0025-5718-1987-0866109-5Koblitz N. Elliptic curve cryptosystems. Mathematics of Computation, 1987, vol. 48, no. 177, pp. 203–209. https://doi.org/10.1090/S0025-5718-1987-0866109-5Washington L.C. Elliptic Curves: Number Theory and Cryptography. Chapman and Hall/CRC, 2008. 536 p.Washington L.C. Elliptic Curves: Number Theory and Cryptography. Chapman and Hall/CRC, 2008, 536 p.Silverman J.H. The Arithmetic of Elliptic Curves. New York: Springer, 2009. 513 p. (Graduate Texts in Mathematics; V. 106).Silverman J.H. The Arithmetic of Elliptic Curves. New York, Springer, 2009, 513 p. Graduate Texts in Mathematics, vol. 106.Mordell L. On the rational solutions of the indeterminate equation of the third and fourth degree // Proceedings Cambridge Philosophical Society. 1922. V. 21. P. 179–192.Mordell L. On the rational solutions of the indeterminate equation of the third and fourth degree. Proceedings Cambridge Philosophical Society, 1922, vol. 21, pp. 179–192.Weil A. L'arithmétique sur les courbes algébriques // Acta Mathematica. 1929. V. 52. N 1. P. 281–315. https://doi.org/10.1007/BF02592688Weil A. L'arithmétique sur les courbes algébriques. Acta Mathematica, 1929, vol. 52, no. 1, pp. 281–315. https://doi.org/10.1007/BF02592688Silverman J.H. Heights and elliptic curves // Arithmetic Geometry. New York, NY: Springer, 1986. P. 253–265. https://doi.org/10.1007/978-1-4613-8655-1_10Silverman J.H. Heights and elliptic curves. Arithmetic Geometry. New York, NY, Springer, 1986, pp. 253–265. https://doi.org/10.1007/978-1-4613-8655-1_10Klagsbrun Z., Sherman T., Weigandt J. The Elkies curve has rank 28 subject only to GRH // Mathematics of Computation. 2019. V. 88. N 316. P. 837–846. https://doi.org/10.1090/mcom/3348Klagsbrun Z., Sherman T., Weigandt J. The Elkies curve has rank 28 subject only to GRH. Mathematics of Computation, 2019, vol. 88, no. 316, pp. 837–846. https://doi.org/10.1090/mcom/3348Menezes A.J., Van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. CRC press, 2018. 810 p.Menezes A.J., Van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. CRC press, 2018, 810 p.Danzig T. Numbers: The Language of Science. Revised. Now York, Macmillan, 1933.Danzig T. Numbers: The Language of Science. Revised. Now York, Macmillan, 1933.Mathews G.B. On the partition of numbers // Proceedings of the London Mathematical Society. 1896. V. 1. N 1. P. 486–490. https:// doi.org/10.1112/plms/s1-28.1.486Mathews G.B. On the partition of numbers. Proceedings of the London Mathematical Society, 1896, vol. 1, no. 1, pp. 486–490. https://doi.org/10.1112/plms/s1-28.1.486Diffie W., Hellman M. New directions in cryptography // IEEE Transactions on Information Theory. 1976. V. 22. N 6. P. 644–654. https://doi.org/10.1109/TIT.1976.1055638Diffie W., Hellman M. New directions in cryptography. IEEE Transactions on Information Theory, 1976, vol. 22, no. 6, pp. 644–654. https://doi.org/10.1109/TIT.1976.1055638Noro K., Kobayashi K. Knapsack cryptosystem on elliptic curves // Cryptology ePrint Archive. 2009. P. 2009/091.Noro K., Kobayashi K. Knapsack cryptosystem on elliptic curves. Cryptology ePrint Archive, 2009, pp. 2009/091.Mazur B., Goldfeld D. Rational isogenies of prime degree // Inventiones Mathematicae. 1978. V. 44. N 2. P. 129–162. https://doi.org/10.1007/BF01390348Mazur B., Goldfeld D. Rational isogenies of prime degree. Inventiones Mathematicae, 1978, vol. 44, no. 2, pp. 129–162. https://doi.org/10.1007/BF01390348Lozano-Robledo Á. Elliptic curves, modular forms, and their L-functions // The Student Mathematical Library. 2011. V. 58. http://dx.doi.org/10.1090/stml/058Lozano-Robledo Á. Elliptic curves, modular forms, and their L-functions. The Student Mathematical Library, 2011, vol. 58. http://dx.doi.org/10.1090/stml/058

The authors declare that there are no conflicts of interest present.