The use of random/pseudorandom number generators with good cryptographic properties is critical for cryptographic applications, especially when these generators are used to generate key data. Using a generator whose outputs do not form a "perfect" random sequence significantly reduces the cryptographic properties of a cryptosystem. Specifically, the system becomes vulnerable to a directed brute-force attack, which allows one to recover the most probable key of a cryptographic algorithm, based on deviation of equiprobable distribution. However, developers of such generators typically focus on engineering, analytical, and statistical quality checks of the proposed generator, and pay virtually no attention to developing effective quality control methods for the generator throughout its lifecycle. This paper aims to fill this gap. Its goal is to develop and validate an effective (in terms of speed and quality) periodic verification of the correct operation of a random/pseudorandom number generator, ensuring its cryptographic properties are preserved. Such testing is necessary for the timely detection of generator operational deviations at the early stages of their occurrence, before their impact becomes critical. This paper develops a periodic generator quality check procedure, called second-level (the first-level verification is performed upon generator adoption). A set of statistical tests for performing this verification is proposed; it is shown that these tests identify various types of generator operational deviations and are independent. It also shows how the results of applying these tests to generator outputs should be processed. As an example of the use of a second-level verification, the results of its application to a standardized generator based on DSTU 7624:2014 "Kalina" are presented.
The
NIST
STS [1] statistical test suite, designed to verify the cryptographic qualities of random/pseudo-random number generators (RNGs/PRNGs), is a powerful and extremely important tool. It is mandatory when verifying a newly developed generator before its adoption, or after a major overhaul of a hardware generator [2].
However, in addition to a one-time inspection upon adoption, hardware generators require additional periodic control. Hardware RNG testing requires more complex approach than others classes of digital devices. This is due to the following factors. 1. In contrast to traditional approach to functionality verification, for hardware RNG it is impossible to organize verification according to the black box approach [3], or using known test input-output values, or like that.
2. The occurrence of a failure in hardware RNG functioning, causing incorrect output sequences, usually will not be immediately detected.
3. Hardware generators are significantly vulnerable to misuse or to use in inappropriate physical conditions [4], or to the deterioration of the quality of the physical source of randomness [5].
Thus, for hardware generation of random/pseudo-random sequences with a given level of security, it is necessary to perform periodic (once a day, a week, etc.) verifications of the correctness of its functioning, assessing the quality of the output sequences.
At the same time, periodic checking should not be as complicated and resource-consuming as the verification upon adoption. This is due to the fact that periodic checking is applied to such a RNG/PRNG, which, firstly, has good cryptographic properties, and secondly, has passed preliminary engineering checks for reliability of functioning. In addition, periodic checking should be applied to a working RNG/PRNG without stopping it, therefore it should occur almost in real time. the RNG/PRNG Verification Strategy defined in [1] and improved in [6]. As in lightweight cryptology, this analogue should, on the one hand, require significantly less time, and on the other hand, perform less detailed verification.
The structure of the article is the follows. In Section 2 we consider articles on the topic, analyze directions of their investigations. In the Section 3 the main results are given, namely: detailed description of tests proposed for second-level verification; justification of the tests independence; application of proposed second-level verification for standardized PRNG. We conclude with Section 4, summarizing the usage of our results and describing the possible direction of future investigations.
The vast majority of contemporary works, devoted to issues related to RNG/PRNG, can be divided into the following clusters by topic.
Thus, in [7] a number of methods for constructing high-quality RNG by harnessing the inherent noise properties of multistage ring oscillators and using fast Fourier transformation-based noise are proposed. The authors verify the statistical properties of their proposed RNG using a test suite [1] and obtain results confirming its cryptographic qualities.
The authors of [8] consider memristor TRNGs (True Random Number Generators) obtained using various entropy sources for producing high quality random numbers or sequences, analyze their strengths and weaknesses, and show that memristor TRNGs stand out due their simpler circuits and lower power consumption in comparison with CMOS (Complementary Metal-OxideSemiconductor)- based TRNGs.
The work [9] is devoted to the evaluation of the theoretical bound for the min-entropy of the output random sequence through the very efficient entropy accumulation using only bitwise XOR operations, under the condition that the inputs from the entropy source are independent. The obtained theoretical results were applied to the quantum random number generator that uses dark shot noise arising from image sensor pixels as its entropy source.
Chaos Based Cryptography Pseudo-Random Number Generator Template with Dynamic State Change is proposed in [10]. It is also analyzed using NIST STS tests [1]. Obtained results show that chaotic maps can be successfully used as a building blocks for cryptographic random number generators.
The work [11] deals with the method of Improving the Statistics Qualities of Pseudo Random Number Generators. The authors present a new non-linear filter design of PRNG that improves the output sequences of common pseudo random generators in terms of statistical randomness .
At last, [12] proposes a variety of randomness extraction methods to post-process the output of random number generators and evaluated their impacts on the statistical properties. The findings show that all proposed post-processing methods improved the statistical properties of RNG/PRNG.
In [13], the use of Neural Networks for the assessment of the quality and hence security of several Random Number Generators is considered. The authors focus both on the vulnerability of classical Pseudo Random Number Generators, such as Linear Congruential Generators and the RC4 algorithm, and extend their analysis to non-conventional data sources, such as Quantum Random Number Generators based on Vertical-Cavity Surface-Emitting Laser. Their findings reveal the potential of NNs to enhance the security of RNGs, along with highlighting the robustness of certain QRNGs, in particular the VCSEL-based (Vertical-Cavity Surface-Emitting Laser) variants.
The work [14] proposes a rough sets based analyzing system to analyze the quality of Pseudorandom Number Generator, while the design of generators is outside the scope of this paper.
The special of RNGs, namely Physical Prime Random Number Generator Based on Quantum Noise is considered in [15]. Such generators have not yet been explored, and in this work the authors experimentally implement and characterize a vacuum-based probabilistic prime number generation scheme with an error probability of about 3.5×10 .
The good example of such articles is [16], which reviews the performance and statistical quality of some well known algorithms for generating pseudo random numbers. For completeness, we should also mention such articles as [17], [18], [19].
However, as the study of these works showed, none of them considers the full process of functioning of the RNG/PRNG during its lifetime, in particular the issue of verifying the cryptographic qualities of the RNG/PRNG at different stages of its functioning.
In [5] and [20], the necessity to use three different types of RNG/PRNG quality verification was justified. The first-level verification is performed during the adoption process. The second-level verification is performed periodically at certain specified intervals to prevent usage of the RNG/PRNG with a slight (but dangerous) degradation of its cryptographic properties and to detect such degradation at an early stage. The third-level verification is a continuous verification aimed at instantly detecting significant failures in operation.
For the first level verification, an Improved Strategy for RNG/PRNG Quality Verification was proposed in [6 -3 simple tests (like chi-square and maximal series tests) which may detect significant deviations from equiprobable distribution, or significant symbol dependency, or different physical faults. But the question about the secondlevel (periodic) verification is still opened, and we are going to focus on it in this paper.
The object of this work is process of random/pseudorandom numbers and sequences generation.
The main purpose of it is to create an efficient second-level verification, which can be periodically applied to RNG/PRNG to verify correctness of its functioning. Here we understand fast procedure, which is able to detect different dangerous deviation in its work on their early stage, while these deviations become essentially dangerous.
For the second-level verification, it is sufficient to use a significantly smaller tests suite than for the first-level one. This is explained by the fact that at this stage it is not necessary to conduct a comprehensive analysis of the RNG/PRNG, but only to make sure that it functions correctly. But the technique for test results processing can be the same as in the Improved Strategy [6].
The requirements for the tests suite for the second level verification are as follows: • • • • tests should be independent; tests must be selected in a such way, that the obtained set contains tests that can check all major types of deviations from randomness, such as: violation of symbol equiprobability; presence of dependencies between symbols; presence of a symbol's dependence on its place in the sequence; etc.; tests should be quick and easy to perform; the number of tests should be as minimal as possible.
Based on the above requirements, a set of statistical tests will be proposed below, their choice will be justified, and what deviations each test detects will be shown. We will call this set of tests OPTIMA-5 according to the number of tests in the set. In order to make it possible to apply the Improved Strategy to the test results, an appropriate algorithm for calculating the P-value corresponding to the obtained statistic will be given for each test.
In what follows, we will use the hypothesis H0 from the RNG/PRNG is an implementation of a true random sequence, i.e. sequence of equiprobable, hypothesis H1 is complex and may be formulated as H0 is not true . The tests given below are aimed at testing the hypothesis H .
0
alphabet A = a1 ,...,aN of the size .
Then the random variable Let i in=1 be a sequence of independent random variables, equiprobably distributed on the 2 = N (Mi − npi )2 = N Mi2 − n ,
i=1 npi i=1 npi where pi = P l = ai , i N , l n , Mi is the number of symbols ai in the sequence i in=1 , will asymptotically have a 2 -distribution with -1 degrees of freedom.
2 =
N N
Mi2 − n .
n i=1 pi = N1 and
If
2 for a given significance level is calculated
from the formula F(2 ) = 1 − , where F ( x ) is a 2 -distribution function with -1 degrees of
freedom (the value of the distribution function is tabulated, see, for example, [21]).
(
2 2 approaches normal distribution with parameters N(x; 2(N −1) + 1, 1) , and the limit value of the statistic 2 for a given significance level may be found from the formula 2 = 1 ( 2(N −1) −1 + z )2 , where (z ) =1− and (x) is the standard 2 normal distribution function (the value of the distribution function is tabulated, see for example [22].
For example, for = 16 and =0.001, we have 2 =37.7; for N =2 and =0.01, we have
P-value calculation.
If N −1 30 , then the P-value corresponding to the calculated value of the statistic 2 = N N Mi2 − n is calculated as P2 = 1 − F( 2) , where F ( x ) is 2 -distribution function with n i=1 -1 degrees of freedom.
If N −1 30 , then the P-value corresponding to the calculated value of the statistic 2 = N N Mi2 − n is calculated with the next steps:
n i=1 - calculate the value z = 2 2 − 2(N −1) −1 ; - calculate the P-value from the equation P2 = 1− (z) , where (x) is the standard normal distribution function (the value of the distribution function is tabulated, see [22]).
n Let i i=1 be a sequence of independent random variables, equiprobably distributed on the alphabet A = a1 ,...,aN of the size .
n Then the sequence = 2 , where j = (2 j−1 ,2 j ) , consisting of non-overlapping bigrams, j j=1 is a sequence of independent random variables that take values in the alphabet A A of size N2 . Then the random variable
N (Mij − kpij )2 2 = i,j=1 kpij
N M2 = ij − k , i,j=1 kpij where pij = Pvl = (ai ,aj ) , k = n , Mij is the number of all bigrams (ai ,aj ) A A in the 2 sequence , will asymptotically have a 2 -distribution with N2 −1 degrees of freedom.
Under the condition of equiprobable distribution of variables i , the corresponding bigrams will also have equiprobable distribution, i.e. pij = 12 , therefore
N 2 = N2 N Mi2j − k .
k i,j=1
If N −1 30 , then the limit value of the statistic 2 for a given significance level is
calculated from the formula F(2 ) = 1 − , where F ( x ) is a 2 -distribution function with N2 −1
degrees of freedom.
(
2 2 approaches normal N(x; 2(N2 −1) +1, 1) , and the limit value of the statistic 2 for a given significance level may be found from the formula 2 = 1 ( 2(N2 −1) −1 + z )2 , where (z ) =1− and (x) is the standard normal distribution 2 function.
For example, for N = 16 and = 0.01 we have 2 = 309.781 ; for N =2 and =0.01, we have 2 = 6.63.
A sequence passed the test with a significance level if X2 X2 .
P-value calculation.
If N −1 30 , then the P-value corresponding to the calculated value of the statistic 2 = N2 N Mi2j − k is calculated as P2 = 1 − F(2) , where F ( x ) is 2 -distribution function with k i,j=1 N2 −1 degrees of freedom.
If N −1 30 , then the P-value corresponding to the calculated value of the statistic 2 = N N Mi2 − n is calculated with the next steps:
n i=1 - calculate the value Z = 2 2 − 2(N2 −1) −1 ; - calculate the P-value from the equation P2 = 1 − (Z) , where (x) is the standard normal distribution function (the value of the distribution function is tabulated, [22]).
The two tests described above check the equiprobability of distributions of symbols and bigrams. Note that the combination of these tests also checks pairwise symbol dependencies.
alphabet A of the size .
Then Let i in=1 be a sequence of independent random variables, equiprobably distributed on the n−1 Define a random variable G = I(i+1 i ) + 1 (the number of series in the sequence i in=1 ). n
i=1 n−1 n−1 N − 1
MGn = i=1 MI + 1 = (n − 1)(1 − N1 ) + 1 ; DGn = i=1 DI = (n − 1)( N2 ) .
G − MGn G = n
DGn
G − MGn → N(
= P n DGn
= 1− F(G ) + F(−G ) = 1 −F(G ) +1 −F(G ) = 2 −2F(G ) , where F(x) is the standard normal distribution function.
A sequence passed the test with a significance level if
(
P-value calculation.
G − MGn G , n
DGn from the equation PG = 2(1 − F(G)) , where F ( x ) is the function of the standard normal distribution.
The number of runs test checks the absence of dependencies between the symbols. For example, if the probability of changing the next symbol is greater than ½, then the number of series will be too large; otherwise, if this probability is small, too long series will appear, and the number of series will be small.
Let n
i i=1 be a sequence of independent random variables, equiprobably distributed on the alphabet A = a1 ,...,aN of the size .
n−1 Let us define a random variable R = iI( i = ) (the sum of the positions of the symbol v A i=1 i in=1 ). Then in the sequence
MR = niP(i = ) = n(n + 1) , DR = ni2DI( i = ) ,
i=1 2N i=1 since I(i = ) are independent random variables with variance and for sufficiently large n
DI(i = ) = MI2(i = ) −(MI(i = ))2 = MI(i = ) −(MI(i = ))2 = = MI(i = )(1 − MI(i = )) =
N −1
N2 ,
DR = i=n1 i2 NN−21 = NN−21 2n3 + 36n2 + n = NN−21 n(n −1)6(2n +1) NN−21 n33 .
Then
2 R − R − MR = DR (N3−N12)n3 Rn − n2+N1 2 n2 3nN Rn − n2+N1 2 .
A) are independent, so (for sufficiently large n) the R − MR
DR distribution of the quantity
can be considered as N(
If -1 30, then the distribution
2 2 approaches normal N(x; 2(N −1) + 1, 1) , and the limiting value of the statistic 2 for a given level of significance is found from the formula 2 = 1 ( 2(N −1) −1 + z )2 , where (z ) =1− , (x) is a function of the standard normal 2 distribution.
For example, for N = 16 and = 0.01 we have 2 = 30.58 ; for N = 16 and =0.001, we have 2 = 37.7
P-value calculation.
If N −1 30 , then the P-value corresponding to the calculated value of the statistic T = 3N N−1 R − n2+N1 2 is calculated as PT = 1 − F(T) , where F ( x ) is 2 -distribution function with n =0 n -1 degrees of freedom.
If N −1 30 , then the P-value corresponding to the calculated value of the statistic T = 3N N−1 R − n2+N1 2 is calculated with the next steps:
n =0 n - calculate the value z = 2T − 2(N − 1) − 1 ; - calculate the P-value as PT = 1 − (z) , where (x) is the standard normal distribution function (the value of the distribution function is tabulated).
This test checks the dependence of a symbol on its position in a sequence. For example, it can detect any periodic or monotonic trends.
Let i in=1 be a sequence of independent random variables, equiprobably distributed on the alphabet A of the size .
We assume that n = 2l (otherwise we discard the last symbol of the sequence).
Build an auxiliary sequence i = I2i−1 2i , i = 1,l , and calculate
2N q = P ( i = 0) = 1 + 1 , p = P ( i = 1) = 1 − 1 ,
2 2N 2 2N
M i = 1 − 1 , D i =
2 2N
1 − 1 , i = 1,l .
4 4N2
(
MIn = l 21 − 21N , DIn = l 41 − 4N12 .
I − MIn I = n
DIn has asymptotically standard normal distribution. Therefore, for the chosen significance level the next equality holds: I − MIn I = 2 − 2F(I ) ,
= P n
DIn where F(x) is the standard normal distribution function.
A sequence passed the test with a significance level if In − MIn I , where I is calculated DIn from the equation F(I ) = 1 − .
2 For example, for =0.01 we have I =2.58.
P-value calculation.
I − MIn is calculated as The P-value corresponding to the calculated value of the statistic I = n DIn PI = 2 (1 − F(I)) , where F ( x ) is the function of the standard normal distribution.
Like the series test, this test detects dependencies between symbols, but of a different nature.
It should be noted that, in general situation, a maximum length run test can be added to the above-described set of tests. However, for the second-level verification, it is unnecessary, since such a test is performed continuously according to the third-level verification.
To check the independence of the tests of this set, two methods were used: (i) using the normal distribution [23]; (ii) using Chernov's inequality [24], both with the significance level = 0.01 . The number of sequences which passed all tests is T = 296.
The significance level for checking hypothesis about independence is A = 0.0001 . The following results were obtained.
Independence verification using normal distribution: credential interval is calculated as W1 , W2 , where W1 = max 0, (1 − )5 − 4 W2 = min1, (1 − )5 + 4 (1 − )5 (1− (1− )5 ) = 0.9 , 300 (1 − )5 (1 − (1 − )5 )
= 1 .
300
As T W1 , W2 , the hypothesis about tests independence is accepted.
(
Independence verification using Chernov's inequality: credential interval is calculated as V1 , V2 , where
V = max0, − A = 193 and V2 = min1, + A = 300 , with = n(1 − )m , A = 1 As T V1 , V2 , the hypothesis about tests independence is accepted. 3 ln 2 . A
Hence, both methods make the same decision and we may consider these tests to be mutually independent. It should be noted that, in general situation, a maximum length run test can be added to the abovedescribed set of tests. However, for the second-level verification, it is unnecessary, since such a test is performed continuously according to the third-level verification.
To confirm the practical usage of the Improved Strategy for application in second-level PRNG verification, we applied the verification to the PRNG described in Appendix A of DSTU 9041:2020 [23]. Note that Improved Strategy was described in details in [6], therefore, we only note here that it verifies the following requirements:
- equiprobable distribution of P-values for each test (checked using limit chi-square distribution); - the proportion of sequences that passed each test (checked using limit normal distribution); - the number of sequences that passed all tests (checked using limit normal distribution).
All tests from OPTIMA-5 were applied to 300 sequences, obtained from PRNG mentioned above. Then for each test distribution of 300 corresponding P-values was checked using chi-square test with significance level A = 0.0001 . Next, for each test the proportion of adopted sequences were checked, using limit normal distribution to calculate the edges of credential interval with significance level A = 0.0001 . At last, the proportion of sequences passed all tests was checked, using limit normal distribution to calculate the edges of credential interval with significance level A = 0.0001 .
1. Distribution of P-values
In conditions, described above, the limit statistics for chi-square criterion is 33.71995. Based of obtained P-values, the next statistics were calculated (Table 1):
Final decision: PRNG from Appendix A of DSTU 9041:2020 is adopted with Improved Strategy.
The article proposed new technique for second-level verification of the cryptographic quality of RNG/PRNG, intended for key generation. The task of the second-level verification is to detect faults in RNG/PRNG before these faults become critical and dangerous from the cryptographic point of view. This second-level verification consists of 5 tests, which are detailed described in this work. For each test the simple algorithm to calculate corresponding P-value is given, because second-level verification uses the set of obtained P-values to make decision about RNG/PRNG quality. As part of justification of the set of tests, chosen for this verification, we proved that these tests are in dependent using two different methods: one is based on limit normal distribution, the second is based on Chernoff inequality. Both methods made decision about tests mutual independence.
To demonstrate practical usage of the second-level verification, we applied it to standardized PRNG, and obtained the expected result: PRNG was accepted.
As the follow direction of investigation, we consider justification of the value of time interval between second-level verifications, based on the nature of the generator, its characteristics, supposed variant of application and other factors.
The results of this work were obtained within the project 2023.04/0020 Development of methods and layout of the "DEMETRA" ARM for constant and periodic control of the functioning of cryptographic applications using statistical methods.
The authors have not employed any Generative AI tools.
[6] Kovalchuk, L., Nelasa, H., Rodinko, M., Bespalov, O. "A new extended strategy of processing of
statistical testing results" CEUR Workshop Proceedings, 2024, 3933, pp. 158 167, ISSN
16130073 Publisher CEUR-WS https://ceur-ws.org/Vol-3933/Paper_12.pdf
[7] Singh V, Hasan MS, Azeemuddin S. "A High-Quality Random Number Generator Using
Multistage Ring Oscillators and Fast Fourier Transform-Based Noise Extraction" Eng. 2024;
5(
Generators." Technical Report CSTN-122 (2011). [17] Deshmukh Shrutika, Damle Bhagyashree, Kottur Suhasini. "Review of Random Number Generation." International Journal of Current Trends in Engineering & Research (IJCTER) (2017) https://doi.org/10.13140/RG.2.2.21227.62248. [18] Crocetti, Luca, Pietro Nannipieri, Stefano Di Matteo, Luca Fanucci, and Sergio Saponara. "Review of Methodologies and Metrics for Assessing the Quality of Random Number Generators." Electronics 12, no. 3(2023): 723. https://doi.org/10.3390/electronics12030723 [19] Priyanka, Hussain Imran, Khalique Aqeel. "Random Number Generators and their
Applications: A Review". IJRECE VOL 7 (2019): 1777-1781.
[20] Bespalov O., Kovalchuk L., Klimenko T., "New methods for testing random/pseudo-random
sequence generators at different stages of their functioning" Èlektron. model. 2025, (
Turney. Revised on June 21, (2023). URL: https://www.scribbr.com/statistics/chi-squaredistribution-table/ [22] Standard Normal Distribution Table. Copyright © 2023 Rod Pierce URL: https://mathsisfun.com/data/standard-normal-distribution-table.html [23] DSTU 9041:2020 Information technologies. Cryptographic information security. Short message encryption algorithm based on twisted Edwards elliptic curves, 2020. URL: https://online.budstandart.com/ua/catalog/doc-page.html?id_doc=90523