Pseudorandom bit generator based on Edwards curve isomorphic transformations
DOI:
https://doi.org/10.18372/2225-5036.21.9705Keywords:
pseudorandom bit generator, elliptic curve, Edwards curve, isomorphic transformations, isomorphic curvesAbstract
This article provides an improved standardized pseudorandom bit generator on elliptic curves through the use of additional functions to get an isomorphic transformation of the base elliptic curve. Isomorphic transformation is used for each point witch obtained after the scalar multiplication of the base point in the cyclic subgroup. In this way it is possible to use the whole set of elliptic curve isomorphic transformations and increase the number of generator internal states and, as a consequence, increase the resistance to recovery of pseudorandom sequence. The elliptic curve is used in the Edwards form, which reduces the computational cost in the generation of the pseudorandom sequence. The results of the analyses of the statistical security are confirmed its security. An improved pseudorandom bit generator can reduce the computational complexity of the algorithm and increase its capacity compared with a standardized algorithm.References
NIST Special Publication 800-90. Recom-mendation for Random Number Generation Using Deterministic Random Bit Generators (Revised) / Elaine Barker, John Kelsey // Computer Security Division Information Technology Laboratory National Institute of Standards and Technology. – March 2007.
Kaliski Jr. B. S. A pseudo-random bit generator based on elliptic logarithms / B. S. Kaliski Jr. // Advances in Cryptology: Proceedings of Crypto '86 (Lecture Notes in Computer Science, vol. 263), Springer-Verlag, New York, 1987, pp. 84-103.
Krawczyk H. How to predict cоngruential generators / H. Krawczyk // TECHNION – Israel Institute of Technology Computer Science Department. December 1988. – Р. 1-15.
Impagliazzo R. Pseudo-random generation from one-way functions / R. Impagliazzo, L. Levin, M. Luby // Proceedings of the 21st Annual ACM Symposium on Theory of Computing, ACM, New York, 1989, pp. 12-24.
Burton S. One-Way Permutations on Elliptic Curves / Burton S., Kaliski Jr. // Journal of Cryptology (1991) International Association for Cryptologic Research. 1991. – P.187-199.
Hallgren S. Linear congruential generators over elliptic curve. // Cornegie Mellon Univ., 1994, CS-94-M3. – P. 1-10.
Gong G. Elliptic curve pseudorandom sequence generators / G. Gong, T. A. Berson, D. R. Stinson // Selected Areas in Cryptography (Kingston, ON, 1999), Springer, 2000, p. 34-48.
Lange T. Certain exponential sums and random walks on elliptic curves / T. Lange, I. E. Shparlinski // Canadian Jornal of Mathematics 57. – 2005. – P. 338-350.
Gjøsteen K. Comments on Dual-EC-DRBG/NIST SP 800-90, Draft December 2005 / K. Gjøsteen // March 16, 2006.
Горбенко І.Д. Метод побудування випад-кових бітів на основі спарювання точок еліптичних
кривих / Горбенко І.Д., Шапочка Н.В., Погребняк К.А. // Прикладная радиоэлектроника. – 2010. – № 3. –С. 386-394.
Edwards H. A normal form for elliptic curves / H.M. Edwards // Bulletin of the American Mathematical Society 44 (July 2007). – P. 393 – 422. URL: http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html
Lange T. Binary Edwards curves / Lange T., R.R. Farashahi // Cryptographic Hardware and Embedded Systems – CHES 2008, 10th International Workshop, Washington, D.C., USA / Proceedings. Elisabeth Oswald and Pankaj Rohatgi ed. LNCS 5154, Springer. – 2008. – P.244-265. [Електр. ресурс]. – Режим доступу до ресурсу: cr.yp.to/newelliptic/edwards2-20080611.pdf
Chevardin V. A pseudorandom bit generator based on elliptic curve transformations / Chevardin V. E. // Радіоелектронні і комп’ютерні системи. – № 5 (57). – Х.: «ХАІ», 2012. – C. 48-50.
Бессалов А. Метод генерации псевдо-случайных последовательностей на основе изоморфных трансформаций эллиптической кривой / А.В. Бессалов, В.Е. Чевардин // Прикладная радиоэлектроника. – Т. 1, № 2. – 2012. – C. 234-237.
Чевардін В. Изоморфные трансформации эллиптической кривой над конечным полем / В.Є. Чевардін // Кибернетика и системный анализ. – Т. 49, № 3. – 2013. – С. 168-171.
