Cryptanalysis on Two Kinds of Number Theoretic Pseudo-Random Generators Using Coppersmith Method
Pseudo-random number generator (PRNG) is a type of algorithm that generates a sequence of random numbers using a mathematical formula, which is widely used in computer science, such as simulation, modeling applications, data encryption, et cetera. The efficiency and security of PRNG are closely rela...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2025-01-01
|
| Series: | IET Information Security |
| Online Access: | http://dx.doi.org/10.1049/ise2/5569393 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849254678014984192 |
|---|---|
| author | Ran Zhang Jingguo Bi Lixiang Li Haipeng Peng |
| author_facet | Ran Zhang Jingguo Bi Lixiang Li Haipeng Peng |
| author_sort | Ran Zhang |
| collection | DOAJ |
| description | Pseudo-random number generator (PRNG) is a type of algorithm that generates a sequence of random numbers using a mathematical formula, which is widely used in computer science, such as simulation, modeling applications, data encryption, et cetera. The efficiency and security of PRNG are closely related to its output bits at each iteration. Especially, we have recently found that linear congruential generator (LCG) is commonly used as the underlying PRNG in short message service (SMS) app, fast knapsack generator (FKG), and programming languages such as Python, while the quadratic generator plays an important role in Monte Carlo method. Therefore, in this paper, we revisit the security of these two number-theoretic pseudo-random generators and obtain the best results for attacking these two kinds of PRNGs up to now. More precisely, we prove that when the mapping function of LCG and the quadratic generator is unknown, if during each iteration, generators only output the most significant bits of vi, one can also recover the seed of PRNG when enough consecutive or nonconsecutive outputs are obtained. The primary tool of our attack is the Coppersmith method which can find small roots on polynomial equations. Our advantage lies in applying the local linearization technique to the polynomial equations to make them simple and easy to solve and applying the analytic combinatorics method to simplify the calculation of solution conditions in the Coppersmith method. Experimental data validate the effectiveness of our work. |
| format | Article |
| id | doaj-art-b61cef521823402e9a61640550cc376b |
| institution | Kabale University |
| issn | 1751-8717 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj-art-b61cef521823402e9a61640550cc376b2025-08-20T03:56:04ZengWileyIET Information Security1751-87172025-01-01202510.1049/ise2/5569393Cryptanalysis on Two Kinds of Number Theoretic Pseudo-Random Generators Using Coppersmith MethodRan Zhang0Jingguo Bi1Lixiang Li2Haipeng Peng3Information Security CenterInformation Security CenterInformation Security CenterInformation Security CenterPseudo-random number generator (PRNG) is a type of algorithm that generates a sequence of random numbers using a mathematical formula, which is widely used in computer science, such as simulation, modeling applications, data encryption, et cetera. The efficiency and security of PRNG are closely related to its output bits at each iteration. Especially, we have recently found that linear congruential generator (LCG) is commonly used as the underlying PRNG in short message service (SMS) app, fast knapsack generator (FKG), and programming languages such as Python, while the quadratic generator plays an important role in Monte Carlo method. Therefore, in this paper, we revisit the security of these two number-theoretic pseudo-random generators and obtain the best results for attacking these two kinds of PRNGs up to now. More precisely, we prove that when the mapping function of LCG and the quadratic generator is unknown, if during each iteration, generators only output the most significant bits of vi, one can also recover the seed of PRNG when enough consecutive or nonconsecutive outputs are obtained. The primary tool of our attack is the Coppersmith method which can find small roots on polynomial equations. Our advantage lies in applying the local linearization technique to the polynomial equations to make them simple and easy to solve and applying the analytic combinatorics method to simplify the calculation of solution conditions in the Coppersmith method. Experimental data validate the effectiveness of our work.http://dx.doi.org/10.1049/ise2/5569393 |
| spellingShingle | Ran Zhang Jingguo Bi Lixiang Li Haipeng Peng Cryptanalysis on Two Kinds of Number Theoretic Pseudo-Random Generators Using Coppersmith Method IET Information Security |
| title | Cryptanalysis on Two Kinds of Number Theoretic Pseudo-Random Generators Using Coppersmith Method |
| title_full | Cryptanalysis on Two Kinds of Number Theoretic Pseudo-Random Generators Using Coppersmith Method |
| title_fullStr | Cryptanalysis on Two Kinds of Number Theoretic Pseudo-Random Generators Using Coppersmith Method |
| title_full_unstemmed | Cryptanalysis on Two Kinds of Number Theoretic Pseudo-Random Generators Using Coppersmith Method |
| title_short | Cryptanalysis on Two Kinds of Number Theoretic Pseudo-Random Generators Using Coppersmith Method |
| title_sort | cryptanalysis on two kinds of number theoretic pseudo random generators using coppersmith method |
| url | http://dx.doi.org/10.1049/ise2/5569393 |
| work_keys_str_mv | AT ranzhang cryptanalysisontwokindsofnumbertheoreticpseudorandomgeneratorsusingcoppersmithmethod AT jingguobi cryptanalysisontwokindsofnumbertheoreticpseudorandomgeneratorsusingcoppersmithmethod AT lixiangli cryptanalysisontwokindsofnumbertheoreticpseudorandomgeneratorsusingcoppersmithmethod AT haipengpeng cryptanalysisontwokindsofnumbertheoreticpseudorandomgeneratorsusingcoppersmithmethod |