Paper 2022/1134
An improved method for predicting truncated multiple recursive generators with unknown parameters
Abstract
Multiple recursive generators are an important class of pseudorandom number generators which are widely used in cryptography. The predictability of truncated sequences that predict the whole sequences by the truncated high-order bits of the sequences is not only a crucial aspect of evaluating the security of pseudorandom number generators but also serves an important role in the design of pseudorandom number generators. This paper improves the work of Sun et al on the predictability of truncated multiple recursive generators with unknown parameters. Given a few truncated digits of high-order bits output by a multiple recursive generator, we adopt the resultant, the Chinese Remainder Theorem and the idea of recovering $p$-adic coordinates of the coefficients layer by layer, and Kannan's embedding technique to recover the modulus, the coefficients and the initial state, respectively. Experimental results show that our new method is superior to that of the work of Sun et al, no matter in terms of the running time or the number of truncated digits required.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. Designs, Codes and Cryptography
- Keywords
- Multiple recursive generators Truncated prediction Lattice reduction The resultant
- Contact author(s)
-
hbing_yu @ 163 com
qunxiong_zheng @ 163 com
jguobi @ bupt edu cn
nairwx @ gmail com
497591946 @ qq com
2670505187 @ qq com
xidian_chengrong @ 163 com
wanglin4math @ outlook com
bssun @ stu xidian edu cn - History
- 2022-08-31: approved
- 2022-08-31: received
- See all versions
- Short URL
- https://ia.cr/2022/1134
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1134,
author = {Han-Bing Yu and Qun-Xiong Zheng and Yi-Jian Liu and Jing-Guo Bi and Yu-Fei Duan and Jing-Wen Xue and You Wu and Yue Cao and Rong Cheng and Lin Wang and Bai-Shun Sun},
title = {An improved method for predicting truncated multiple recursive generators with unknown parameters},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/1134},
year = {2022},
url = {https://eprint.iacr.org/2022/1134}
}