CITS - Publications - Attacking Power Generators Using Unravelled Linearization: When Do We Output Too Much?
CITS » Forschung » Papers

Attacking Power Generators Using Unravelled Linearization: When Do We Output Too Much?

Mathias Herrmann, Alexander May

We look at iterated power generators $s_i = s_{i-1}^e \mmod N$ for a random seed $s_0 \in \Z_N$ that in each iteration output a certain amount of bits. We show that heuristically an output of $(1-\frac 1 e)\log N$ most significant bits per iteration allows for efficient recovery of the whole sequence. This means in particular that the Blum-Blum-Shub generator should be used with an output of less than half of the bits per iteration and the RSA generator with $e=3$ with less than a $\frac 1 3$-fraction of the bits.
@inproceedings{DBLP:conf/asiacrypt/HerrmannM09,  author    = {Mathias Herrmann and               Alexander May},  title     = {Attacking Power Generators Using Unravelled Linearization:               When Do We Output Too Much?},  booktitle = {ASIACRYPT},  year      = {2009},  pages     = {487-504},  ee        = {http://dx.doi.org/10.1007/978-3-642-10366-7_29},  crossref  = {DBLP:conf/asiacrypt/2009},  bibsource = {DBLP, http://dblp.uni-trier.de}}@proceedings{DBLP:conf/asiacrypt/2009,  editor    = {Mitsuru Matsui},  title     = {Advances in Cryptology - ASIACRYPT 2009, 15th International               Conference on the Theory and Application of Cryptology and               Information Security, Tokyo, Japan, December 6-10, 2009.               Proceedings},  booktitle = {ASIACRYPT},  publisher = {Springer},  series    = {Lecture Notes in Computer Science},  volume    = {5912},  year      = {2009},  isbn      = {978-3-642-10365-0},  ee        = {http://dx.doi.org/10.1007/978-3-642-10366-7},  bibsource = {DBLP, http://dblp.uni-trier.de}}