Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Pseudo-random Sequence Generation from Elliptic Curves over a Finite Field of Characteristic 2

,

DOI: http://dx.doi.org/10.15439/2016F94

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 991–998 ()

Full text

Abstract. In this paper, the randomness of binary sequences generated from elliptic curves over a finite field of characteristic 2 is studied. A scheme of construction based on the Chaos-Driven Elliptic Curve Pseudo-random Number Generator (C-D ECPRNG) is proposed. The generators based of this scheme are verified by using tests from the NIST Statistical Test Suite to analyze their statistical properties. An elliptic curve used in the numerical example is defined over $\mathbb{F}\_{2^{8}}$. The investigations which made for the generated series of two output sequences of the lengths of $2^{10}$ and $2^{20}$ bits shown that 14 generators working according to our general scheme exhibit good randomness properties. Next, the binary sequences generated by these 14 schemes were used for encrypting a $256 \times 256$ grayscale Lena image as an application example and the security analysis of the ciphered images was carried out.

References

  1. N. Koblitz, “Elliptic curve cryptosystems,” Mathematics of Computation, vol. 48, 1987, pp. 203–209.
  2. V. Miller, “Uses of elliptic curves in cryptography,” Advances in Cryptology-CRYPTO’85, vol. 218, Springer, Heidelberg, 1986, pp. 417–426, http://dx.doi.org/10.1007/3-540-39799-X_31
  3. A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic, Dordrecht 1993, http://dx.doi.org/10.1007/978-1-4615-3198-2
  4. N. Gura, A. Patel, A. Wander, H. Eberle and S.C. Shantz, “Comparing elliptic curve cryptography and RSA on 8-bit CPUs,” Cryptographic Hardware and Embedded Systems (CHES), vol. 3156, Springer, Heidelberg, 2004, http://dx.doi.org/10.1007/978-3-540-28632-5_9
  5. B. S. Kaliski, “One-way permutations on elliptic curves,” Journal of Cryptology 3, 1991, pp. 187–199, http://dx.doi.org/10.1007/BF00196911
  6. Z. Chen, S. Li and G. Xiao, “Construction of pseudo-random binary sequences from elliptic curves by using discrete logarithm,” In: G. Gong, et al. (eds.): SETA 2006. LNCS, vol. 4086, Springer, Heidelberg, 2006, pp. 285–294, http://dx.doi.org/10.1007/11863854_24
  7. S. V. Sathyanarayana, M. A. Kumar and K. N. H. Bhat, “Random binary and non-binary sequences derived from random sequence of points on cyclic elliptic curve over finite field GF(2m ) and their properties,” Information Security J.: A Global Perspective, vol. 19, 2010, pp. 84–94, http://dx.doi.org/10.1080/19393550903482759
  8. J. M. Bahi and C. Guyeux, Discrete Dynamical Systems and Chaotic Machines: Theory and Applications, CRC Press, Numerical Analysis and Scientific Computing, London 2013.
  9. R. L. Tataru, “Image hashing secured with chaotic sequences,” Proceedings of the 2014 Federated Conference on Computer Science and Information Systems (FedCSIS), IEEE, 2014, pp. 735–740, http://dx.doi.org/10.15439/2014F250
  10. D. Johnson, A. Menezes and S. Vanstone, “The Elliptic Curve Digital Signature Algorithm,” International Journal of Information Security, vol. 1, 2001, pp. 36–63, http://dx.doi.org/10.1007/s102070100002
  11. J. H. Silverman, The arithmetic of elliptic curves, Springer-Verlag, New York 2009, http://dx.doi.org/10.1007/978-0-387-09494-6
  12. D. Szalkowski and P. Stpiczynski, “Template Library for Multi-GPU Pseudorandom Number Recursion-based Generators,” Proceedings of the 2013 Federated Conference on Computer Science and Information Systems (FedCSIS), IEEE, 2013, pp. 515–519.
  13. T. Lange and I. E. Shparlinski, “Certain exponential sums and random walks on elliptic curves,” Canad. J. Math., vol. 57, 2005, pp. 338–350, http://dx.doi.org/10.4153/CJM-2005-015-8
  14. E. El Mahassni and I. E. Shparlinski, “On the distribution of the elliptic curve power generator,” Proc. 8th Conf. on Finite Fields and Appl., Contemp. Math., vol. 461, Amer. Math. Soc., Providence, RI, 2008, pp. 111–119.
  15. S. Hallgren, “Linear congruential generators over elliptic curves,” Preprint CS94-143, Dept. of Comp. Sci., Cornegie Mellon Univ., 1994.
  16. G. Gong, T.A. Berson and D.R. Stinson, “Elliptic curve pseudorandom sequence generators,” Selected areas in cryptography, vol. 1758, Springer, Berlin, 2000, http://dx.doi.org/10.1007/3-540-46513-8_3
  17. O. Reyad and Z. Kotulski, “On Pseudo-random Number Generators Using Elliptic Curves and Chaotic Systems,” J. Appl. Math. Inf. Sci., vol. 9, 2015, pp. 31-38, http://dx.doi.org/10.12785/amis/090105
  18. P. Beelen and J. Doumen, “Pseudorandom sequences from elliptic curves,” Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Springer, Berlin, 2002, http://dx.doi.org/10.1007/978-3-642-59435-9_3
  19. P. P. Deepthi and P. S. Sathidevi, “New stream ciphers based on elliptic curve point multiplication,” Computer Communications, vol. 32, 2009, pp. 25–33, http://dx.doi.org/10.1016/j.comcom.2008.09.002
  20. O. Reyad and Z. Kotulski, “Statistical Analysis of the Chaos-Driven Elliptic Curve Pseudo-random Number Generators,” In: Z. Kotulski, et al. (eds.) CSS 2014. CCIS, vol. 448, Springer, Heidelberg, 2014, pp.38–48, http://dx.doi.org/10.1007/978-3-662-44893-9_4
  21. J. Szczepanski and Z. Kotulski, “Pseudorandom number generators based on chaotic dynamical systems,” Open Systems & Information Dynamics, vol. 8, 2001, pp. 137–146, http://dx.doi.org/10.1023/A:1011950531970
  22. L. P. Lee and K. W. Wong, “A random number generator based elliptic curve operations,” Computers & Mathematics with Appl., vol. 47, 2004, pp. 217–226, http://dx.doi.org/10.1016/S0898-1221(04)90018-1
  23. E. B. Barker and J. M. Kelsey, “Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised),” US Department of Commerce, Technology Administration, National Institute of Standards and Technology, Computer Security Division, Information Technology Laboratory, 2007.
  24. J. A. Buchmann, Introduction to Cryptography, Undergraduate Texts in Mathematics, Springer-Verlag New York, 2004, http://dx.doi.org/10.1007/978-1-4419-9003-7
  25. S. C. Phatak and S. S. Rao, “Logistic map: A possible random-number generator,” Physical Review E vol. 51, 1995,pp. 3670–3678, http://dx.doi.org/10.1103/PhysRevE.51.3670
  26. A. Rukhin, J. Soto, J. Nechvatal, et al., “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications,” NIST Special Publication 800-22 with revisions, May 2001.
  27. T. Rachwalik, J. Szmidt, R. Wicik and J. Zablocki, “Generation of Nonlinear Feedback Shift Registers with special-purpose hardware,” IEEE Transl. Military Communications and Information Systems Conference (MCC), pp. 1–4, October 2012.
  28. S. Maria and K. Muneeswaran, “Key generation based on elliptic curve over finite prime field, “ Int. J. Elect. Sec. and Digital Forensics, vol. 4, 2012, pp. 65–81, http://dx.doi.org/10.1504/IJESDF.2012.045391
  29. O. Reyad and Z. Kotulski, “Image Encryption Using Koblitz’s Encoding and New Mapping Method Based on Elliptic Curve Random Number Generator,” In: A. Dzich, et al. (eds.): MCSS 2015. CCIS, vol. 566, Springer, Heidelberg, 2015, pp. 34–45, http://dx.doi.org/10.1007/978-3-319-26404-2_3
  30. S. V. Sathyanarayana, M. Aswatha Kumar and K. N. Hari Bhat, “Symmetric key image encryption scheme with key sequences derived from random sequence of cyclic elliptic curve points,” Int. J. Netw. Secur., vol. 12, 2011, pp. 137–150.
  31. A. Soleymani, M. J. Nordin, Z. M. Ali and L. Golafshan, “A Binary Grouping Approach for Image Encryption Based on Elliptic Curves over Prime Group Field,” IEEE Transl. 11th Malaysia International Conference on Communications (MICC), pp. 373–378, November 2013, http://dx.doi.org/10.1109/MICC.2013.6805857
  32. J. Payingat and P. P. Deepthi, “Pseudorandom Bit Sequence Generator for Stream Cipher Based on Elliptic Curves,” Mathematical Problems in Engineering, Hindawi Pub. Cor., vol. 2015, 2015, pp. 1–16, http://dx.doi.org/10.1155/2015/257904
  33. G. Zhang and Q. Liu, “A novel image encryption method based on total shuffling scheme,” J. Optics Communications, vol. 284, 2011, pp. 2775–2780, http://dx.doi.org/10.1016/j.optcom.2011.02.039
  34. Y. Wu, J. P. Noonan and S. Agaian, “NPCR and UACI Randomness Tests for Image Encryption,” IEEE Transl. J. of Selected Areas in Telecommunications (JSAT), pp. 31–38, April 2011.