Home > CSC-OpenAccess Library > Manuscript Information

This is an Open Access publication published under CSC-OpenAccess Policy.

Design of Cryptographically Strong generator By Transforming Linearly Generated Sequences

Matthew Nwokejizie Anyanwu, Lih-Yuan Deng, Dasgupta Dipankar

Pages - 186 - 200 | Revised - 05-08-2009 | Published - 01-09-2009

MORE INFORMATION

KEYWORDS

Linear Congruential Generator, Multiple Recursive Generator, Random Number generator, Strong (Secure) generators and classical generator

ABSTRACT

Random numbers have been used extensively in many simulation applications like Monte Carlo Integration
or computer modeling. But recently security applications have increased the need for strong(secure) random
number generation like automatic password generation, encryption algorithms, on-line gambling etc. Thus
random number generation has become a challenging and an interesting task. Most classical random number
generators, generate sequences that are either linear or predictable hence not suitable for cryptographic and
security applications. Others generate sequences that even though they are secure they are not cryptographically
strong and above all are slow in execution. Also recent advances in random number generation like
the construction of Multiple Recursive Generator(MRG) with large orders, Fast Multiple Recursive Generator(
FMRG) and DX(system of multiple recursive generators proposed by Deng and XU(2003)) generators
does not generate a strong random number sequences. Though MRGs have extremely long period of length
with good empirical performance, its recurrence equation can be solved given a small set of its generated
sequence, this implies that MRGs and FMRGs are not strong cryptographic generators. We propose an
algorithm that will transform linear sequences generated by both classical LCG, MRGs, FMRGs and DX
generators and make them cryptographically strong generators by hiding the entire sequence generated by
the generators, thus it will be difficult for cryptanalyst to predict or infer the generator sequence if even the
partial sequence or the parameters or knowledge of the algorithm used in the transformation of the generators
are known.

1 | J. Kar and B. Majhi, “An Efficient Password Security of Multi-Party Key Exchange Protocol Based on ECDLP”, International Journal of Computer Science and Security (IJCSS), 3(5), pp. 405 – 413, 2009. |

2 | S. J. Aboud, “Secure E-payment Protocol”, International Journal of Security (IJS), 3(5), pp. 85 – 92, 2009. |

1 | Google Scholar |

2 | Academic Journals Database |

3 | ScientificCommons |

4 | Academic Index |

5 | CiteSeerX |

6 | refSeek |

7 | iSEEK |

8 | Socol@r |

9 | ResearchGATE |

10 | Libsearch |

11 | Bielefeld Academic Search Engine (BASE) |

12 | Scribd |

13 | WorldCat |

14 | SlideShare |

15 | PDFCAST |

16 | PdfSR |

17 | Chinese Directory Of Open Access |

1 | Alexi, W., Chor, B. Z.,Goldreich, O. and Schnorr, C.P. (1988). RSA and Rabin Functions: Certain Parts Are as Hard as the Whole Proceedings of the 25th IEEE Symposium on the Foundations of Computer Science 449-457. |

2 | Berlekamp, E.R. 1968. Algebraic coding theory McGraw-Hill, New York, (1968). |

3 | Blum, M., and Micali, S. (1982). How to generate cryptographically strong sequences of pseudo-randombits.In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science. IEEE, New York. pp. 112- l 17 |

4 | Blum, L., Blum, M., and Shub, M. (1983). A simple secure pseudo-random number generator. InAdvances in Cryptography: Proceedings of CRYPTO 82. Plenum Press, New York, 61-78. |

5 | Blum, L., Blum, M., and Shub, M. (1986). A simple unpredictable pseudo-random number generator. SIAM Journal on Computing, Volume 15, Issue 2, pp. 364-383 . ISSN:0097-5397. |

6 | Boyar, J. (1982). Inferring sequences generated by a linear congruence. Proceedings of the 23rd AnnualIEEE Symposium on the Foundations of Computer Science pages 153-159. |

7 | Boyar, J. (1989). Inferring sequences produced by pseudo-random number generators. Journal of theAssociation for Computing Machinery 36,129-141. |

8 | Bruce, S. (1994). Applied Cryptography: Protocols, Algorithms and Source Code in C John-Willey andSons, New York, 1994. ISBN: 0-471-5975602 |

9 | Deng, L. Y., and Lin, D. K. J. (2000). Random number generation for the new century. AmericanStatistician 54, 145-150. |

10 | Deng, L. Y. and Xu, H. Q. (2003). A System of High-dimensional, Efficient, Longcycle and Portable Uniform Random Number Generators, ACM Transactions on Modeling and Computer Simulation, Vol. 13, No. 4, pages 299-309. |

11 | Deng, L. Y. (2004). Generalized Mersenne prime number and its application to random number generation, in Monte Carlo and Quasi-Monte Carlo Methods 2002 (H. Niederreiter, ed.), Springer-Verlag, 167-180. |

12 | Deng, L. Y. (2005). Efficient and Portable Multiple Recursive Generators of Large Order, ACM Transactions on Modeling and Computer Simulation(TOMACS), Volume 15, Issue 1 PP.1-13. ISSN: 1049-3301 |

13 | Deng, L. Y. (2008). Issues on Computer Search for a Large Order Multiple Recursive Generators, in Monte Carlo and Quasi-Monte Carlo and Quasi-Monte Cralo Methods 2006(S. Heinrich, A. Keller and H. Niederreiter, ed.) Springer-Verlag, 251-261. |

14 | Frieze, A.M., Kannan, R.and Lagarias, J.C. (1984). Linear Congruential Generators do not Produce Random Sequences. 25th Annual Symposium on Foundations of Computer Science, pp. 480-484. |

15 | Hastad, J. and Shamir, A. (1985). The cryptographic security of truncated linearly related variables. In Proceedings of the 17th ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York. 356- 362. |

16 | Haldir, R. (2004). How to crack a Linear Congruential Generator. http://www.reteam.org/papers/e59.pdf. |

17 | Hugo, K. (1999). How to Predict Congruential Generators. In Proceedings on Advances in cryptology(Santa Barbara California USA). 138-153. ISBN: 0-387-97317-6. |

18 | Lehmer, D. H. (1951). Mathematical methods in large-scale computing units. Proceedings of the Second Symposium on Large Scale Digital Computing Machinery, Harvard University Press, Cambridge, MA, 141-146. |

19 | 19. L Ecuyer, P. (1997). Uniform Random Number Generation: A Review. Proceedings of the 29th conference on Winter Simulation conference, Atlanta Gergia USA 127-134. |

20 | L Ecuyer, P., Blouin, F., and Couture R. (1993). A search for good multiple recursive linear random number generators. ACM Transactions on Modeling and Computer Simulation, 3, 87-98. |

21 | Lidl, R., and Niederreiter, H. (1994). Introduction to Finite Fields and Their Applications. RevisedEdition. Cambridge University Press, Cambridge, MA. |

22 | Marsaglia, G. (1968). Random Numbers fall mainly in the planes. Proceedings of the National Academy of sciencesVol. IT-15, January 1969 |

23 | Massey, J.L. (1969). Shift-register synthesis and BCH decoding. IEEE Trans. on Inform. Theory, 61,25- 28. |

24 | Neal R. W. (1994). The Laws of Cryptography, online book http://www.cs.utsa.edu/wagner/lawsbookcolor/laws.pdf |

25 | Park, K. and Miller, K. 1988. Random Numbers Generators: Good Ones are Hard to Find. Communication of the ACMvol. 31.No.10, pp 1192-1201 |

26 | 26.Pommerening, K. (2003). Prediction of linear congruential generators http: //www.staff.uni?mainz.de/pommeren/ |

27 | Raja,G and Hole, P.H. (2007). Use of the Shrinking Generator in Lightweight Cryptography for RFIDhttp://www.autoidlabs.org/uploads/media/AUTOIDLABS-WPSWNET- 024.pdf |

28 | Rivest, R., Shamir, A., and Adleman, L .(1978). A method for Obtaining Digital Signatures andPublic-Key Cryptosystems. Communications of the ACM, 21, 120-126. |

29 | Reeds, J.A (1977). Cracking Random Number Generator. Cryptologia, v.1, n. 1, 20- 26 |

30 | Shamir, A. (1983). On the Generation of Crytographically Strong. ACM Transaction on Computer Sys-tems (TOCS), pp. 38-44, Volume1 Issue1. ISSN: 0734-2071 |

31 | Stinson, D. (2006). Cryptography: Theory and Pratice 3rd edition CRC Press, Boca Raton, Florida, ISBN: 1-58488-508-4. |

32 | Takashi, K., Li-Ming, W. and Niro, Y. (1996). On a nonlinear congruential pseudorandom number generator Mathematics of Computation, Volume 65, Issue 213, 227 - 233, ISSN: 0025-5718 . |

33 | Tausworthe, R.C. (1965). Random numbers generated by linear recurrence modulo two Mathematics ofComputation, 19: 201-209. |

Mr. Matthew Nwokejizie Anyanwu

- United States of America

manyanwu@memphis.edu

Dr. Lih-Yuan Deng

University of Memphis - United States of America

Dr. Dasgupta Dipankar

University of Memphis - United States of America