Home   >   CSC-OpenAccess Library   >    Manuscript Information
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
Volume - 3   Issue - 3    |    Publication Date - June 2009  Table of Contents
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.
CITED BY (2)  
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 
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.
26.Pommerening, K. (2003). Prediction of linear congruential generators http: //www.staff.uni?mainz.de/pommeren/
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.
Berlekamp, E.R. 1968. Algebraic coding theory McGraw-Hill, New York, (1968).
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.
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.
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
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.
Boyar, J. (1989). Inferring sequences produced by pseudo-random number generators. Journal of theAssociation for Computing Machinery 36,129-141.
Bruce, S. (1994). Applied Cryptography: Protocols, Algorithms and Source Code in C John-Willey andSons, New York, 1994. ISBN: 0-471-5975602
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.
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
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.
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.
Deng, L. Y., and Lin, D. K. J. (2000). Random number generation for the new century. AmericanStatistician 54, 145-150.
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.
Haldir, R. (2004). How to crack a Linear Congruential Generator. http://www.reteam.org/papers/e59.pdf.
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.
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.
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.
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.
Lidl, R., and Niederreiter, H. (1994). Introduction to Finite Fields and Their Applications. RevisedEdition. Cambridge University Press, Cambridge, MA.
Marsaglia, G. (1968). Random Numbers fall mainly in the planes. Proceedings of the National Academy of sciencesVol. IT-15, January 1969
Massey, J.L. (1969). Shift-register synthesis and BCH decoding. IEEE Trans. on Inform. Theory, 61,25- 28.
Neal R. W. (1994). The Laws of Cryptography, online book http://www.cs.utsa.edu/wagner/lawsbookcolor/laws.pdf
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
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
Reeds, J.A (1977). Cracking Random Number Generator. Cryptologia, v.1, n. 1, 20- 26
Rivest, R., Shamir, A., and Adleman, L .(1978). A method for Obtaining Digital Signatures andPublic-Key Cryptosystems. Communications of the ACM, 21, 120-126.
Shamir, A. (1983). On the Generation of Crytographically Strong. ACM Transaction on Computer Sys-tems (TOCS), pp. 38-44, Volume1 Issue1. ISSN: 0734-2071
Stinson, D. (2006). Cryptography: Theory and Pratice 3rd edition CRC Press, Boca Raton, Florida, ISBN: 1-58488-508-4.
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 .
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


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS