Pseudo-random number generators based on discrete logarithm

Authors

  • Александр Андреевич Замула Kharkov National University of Radio Electronics ave. Lenina 14, Kharkov, Kharkiv, 61000, Ukraine
  • Денис Александрович Семченко Kharkov National University of Radio Electronics ave. Lenina 14, Kharkov, Kharkiv, 61000, Ukraine

DOI:

https://doi.org/10.15587/2312-8372.2013.18390

Keywords:

generator, discrete logarithm, pseudo-random number, cryptographic strength, algorithm, bit

Abstract

The mathematical model of pseudo-random number generator is given in the paper. The problems of discrete logarithm tasks solving and the concept of «hard bits» for discrete logarithm are considered in the paper. Constraints are imposed related to the absence of logarithm which can compute the discrete logarithm of y = gxmodp, where x ≤ 2c for polynomial time. The constraint is called the assumption on discrete logarithm with short с bit exponents (с – DLSE). As an example, the Sundaram- Patel’s generator is given, qualitative and quantitative characteristics of the generator resistance to the main types of attacks are proposed.

The paper gives the analysis of algorithms for generating pseudo-random numbers, such as the algorithm of Blum-Blum- Shub algorithm, Blum-Micali, Fortuna and Yarrow. Based on specified criteria, evaluation of algorithms is given, conclusions on the advantages and disadvantages of each algorithm are made.

Author Biographies

Александр Андреевич Замула, Kharkov National University of Radio Electronics ave. Lenina 14, Kharkov, Kharkiv, 61000

Professor, Ph.D., associate professor.

Department of Information Technology Security

Денис Александрович Семченко, Kharkov National University of Radio Electronics ave. Lenina 14, Kharkov, Kharkiv, 61000

PhD student

Department of Information Technology Security

References

  1. Blum, L. A Simple Unpredictable Pseudo-Random Number Generator [Text] / L. Blum, M. Blum and M. Shub // SIAM J. Computing. − May 1986. − № 15(2).
  2. Шнаер, Б. Прикладная криптография. Протоколы, алгоритмы и исходные тексты на языке С. [Текст] / Б. Шнаер. − 2-е изд. − 610 с.
  3. Schnorr, C. Security of Allmost ALL Discrete Log Bits. [Electronic recource] / C. Schnorr // Electronic Colloquium on Computational Complexity. Report TR98-033. − Available at http://www.eccc.uni-trier.de/eccc/.
  4. Blum, M. How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits [Text] / M. Blum and S. Micali // SIAM J.Computing. − November 1984. − № 13(4).
  5. Hastad, J. The Security of Individual RSA Bits [Text] / J. Hastad and M. NÄaslund // IEEE FOCS, 1998.
  6. Patel, S. An Efficient Discrete Log Pseudo Random Generator [Text] / S. Patel and G. Sundaram // CRYPTO'98, LNCS 1462, 1998.
  7. Hastad, J. The Discrete Logarithm Modulo a Composite Hides O(n) Bits [Text] / J. Hastad, A. Schrift and A. Shamir // JCSS. − 1993.− № 47.
  8. Long, D. The Discrete Log Hides O(log n) Bits [Text] / D. Long and A. Wigderson // SIAM J. Computing. −1988. − № 17.
  9. Pollard, J. Monte-Carlo Methods for Index Computation (mod p) [Text] / J. Pollard // Mathematics of Computation. − 1978. − № 32(143).
  10. Yao, A. Theory and Applications of Trapdoor Functions [Text] / A. Yao // IEEE FOCS, 1982.
  11. Blum, L., Blum, M. and Shub, M. (May 1986). A Simple Unpredictable Pseudo-Random Number Generator. SIAM J.Computing, 15(2).
  12. Schneier, B. Applied kriptografіya. Ed. 2, 610.
  13. Schnorr, C. Security of Allmost ALL Discrete Log Bits. Electronic Colloquium on Computational Complexity. Report TR98-033. Available at http://www.eccc.uni-trier.de/eccc/.
  14. Blum, M., Micali, S. (November 1984). How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM J.Computing, 13(4).
  15. Hastad, J., NÄaslund, M. (1998). The Security of Individual RSA Bits. IEEE FOCS.
  16. Patel, S., Sundaram, G. (1998). An Efficient Discrete Log Pseudo Random Generator. CRYPTO'98, LNCS 1462.
  17. Hastad, J., Schrift, A., Shamir, A. (1993). The Discrete Logarithm Modulo a Composite Hides O(n) Bits. JCSS, 47.
  18. Long, D., Wigderson, A. (1988). The Discrete Log Hides O(log n) Bits. SIAM J.Computing, 17.
  19. Pollard, J. (1978). Monte-Carlo Methods for Index Computation (mod p). Mathematics of Computation, 32(143).
  20. Yao, A. (1982). Theory and Applications of Trapdoor Functions. IEEE FOCS.

Downloads

Published

2013-10-30

How to Cite

Замула, А. А., & Семченко, Д. А. (2013). Pseudo-random number generators based on discrete logarithm. Technology Audit and Production Reserves, 5(1(13), 28–31. https://doi.org/10.15587/2312-8372.2013.18390

Issue

Vol. 5 No. 1(13) (2013): Texnology audit

Section

Technology audit

License

Copyright (c) 2016 Александр Андреевич Замула, Денис Александрович Семченко

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.