Secret linear congruential generators are not cryptographically secure
Author:
- Jacques SternJSJacques Stern
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 421-426
Abstract
This paper discusses the predictability of the sequence given by outputing a constant proportion α of the leading bits of the numbers produced by a linear congruential generator. First, we make the assumption that the modulus of the generator is the only known parameter and we prove that, almost surely, a significant proportion of the bits can be predicted from the previous ones, once the generator has been used K times successively where K is O(√log m). Next, we assume that all parameters of the generator are secret and we show how repeated observations of sequences of outputs of length K will probably allow an opponent to cryptanalyze the full sequence.Keywords
This publication has 5 references indexed in Scilit:
- Reconstructing Truncated Integer Variables Satisfying Linear CongruencesSIAM Journal on Computing, 1988
- Polynomial time algorithms for finding integer relations among real numbersLecture Notes in Computer Science, 1986
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982
- Inferring a sequence generated by a linear congruence1982
- How to generate cryptographically strong sequences of pseudo random bits1982