Today, pseudo-random number generators (PRNGs) are used in various systems and applications, including as key generators in stream ciphers, blockchain, game industry and others. The implementation of the latest information and communication technology (in particular, modern 5G networks) strengthens the requirements for privacy risk mitigation of critical data and forces the development of new methods and means for cryptographic security. In the paper, a computational model of PRNG was developed and studied. It allows to build efficient algorithms for privacy risk mitigation. Based on this model, software PRNGs have been developed and studied (speed and security parameters were verified). These will be useful for confidentiality ensuring and data privacy risk mitigation in modern 5G networks as well as blockchain technologies.
Today randomness is an important unit in many modern computer applications (especially
games, simulations, cryptography). Computers use a form of randomness known as pseudo
randomness, it means simulation of randomness. A pseudo random event looks random but is
completely predictable or deterministic (result of completely predictable mathematical
algorithm). Pseudo-random number generator (PRNG) can be used as key generator in stream
ciphers [
Analysis of related papers in this direction [
Most up-to-date cryptographic applications require random numbers, for example key
generation, cryptographic nonces, salts in certain signature schemes, including ECDSA,
RSASSA-PSS. The security and privacy of 5G is better than in 4G (Fig. 2) [
On the basis of analysis, as a prototype of computational model well-known PRNG Trivium [
1. Parameters n , t , e , k were specified and after their fixing new PRNG structure is forming (capacity of operations is changing). All operations are performing not on the bits but on the vectors of some size (bytes).
2. To improve non-linearity parameters substitution operation S (x) was specified. For any new formed PRNG new unique S (x) can be specified.
3. To generate pseudo-random sequences PRNG internal status vector Ei , key vector for sequence generation K and index of the current iteration of forming (generation) i are used.
4. For generation function Fgen stage of variables initialization was modified, the dynamic carry shift and substitution operations were specified.
5. For generation function Fgen usage of independent functions FA , FB , FC and FD was proposed, these functions depend on internal status vector of previous generation stage, key vector K and index of current iteration of generation i . Output of the functions FA , FB , FC and FD will be the data of necessary length (input and output data length will be different). For any new formed PRNG new unique functions FA , FB , FC and FD can be specified. In fact, these functions are independent byte-oriented PRNGs (without requirements for cryptographically security), they can work in parallel. For synchronization and optimization of sequence generation procedure the speed of sequence generation should be something like similar.
6. Final stage of sequence m forming and operation ordering were modified as well as the substitution operation was specified.
Various PRNGs can be constructed by modification / fixing parameters n , t , e , k as well all specifying functions FA , FB , FC , FD and operation S ( x) .
Computational model description
Let n, t ∈ Z+ , then for generation pseudo-random sequence M , M ∈ V with length N = n ⋅ t bits it is necessary to form t sequences with length n bit: , V N
N ∈ {0,1}N
M = ( m1, m2 , ..., mt−1, mt ) , mi ∈Vn , i =1, t .
Process of generation every mi , mi ∈Vn , i =1, t performs in the following manner: mi , Ei = Fgen ( Ei−1, K , i ) , i =1, t , where Ei is internal status vector of PRNG after generation i -th mi , Ei ∈Ve , e ∈ Z+ , E = IV , IV is initialization vector, IV ∈Ve , K is key vector for sequence generation, 0 K ∈Vk , k ∈ Z+ , Fgen is function of generation the sequence mi .
1) variables initialization; 2) sequence forming.
Stage 1 of function Fgen ( E, K , i ) performing. At the beginning the processing of internal status vector is performing E , E ∈Ve :
E
=S ( E ) <<< i , where x <<< y is operation of right dynamic carry shift of argument x on y bits, S ( x) is some substitution operation.
Next the internal status vector E of PRNG and key vector K are disintegrated on 4 components:
E = ( Ea , Eb , Ec , Ed ) , E ∈Ve , e = a + b + c + d , Ea ∈Va , Eb ∈Vb , Ec ∈Vc , Ed ∈Vd , a, b, c, d ∈ Z+ , K = ( Ka , Kb , Kc , Kd ) , K ∈V , k = a′ + b′ + c′ + d ′ ,
k
Ka ∈Va′ , Kb ∈Vb′ , Kc ∈Vc′ , Kd ∈Vd′ , a′, b′, c′, d ′ ∈ Z+ .
Vectors Ea , Eb , Ec , Ed and Ka , Kb , Kc , Kd will be used in the next stage of the function Fgen ( E, K , i ) .
Stage 2 of function Fgen ( E, K , i ) . On this stage the forming of sequence m , m ∈Vn is performing. For this objective 4 additional functions FA ( Ea , Ka , i ) , FB ( Eb , Kb , i ) , FC ( Ec , Kc , i ) і FD ( Ed , Kd , i ) are using, where F , F , FC and FD are functions, that have A B internal status vector and key vector as input data, and sequence with length n bits as output data. These functions can be constructed on the base of non-linear shift registers, block and stream symmetric ciphers, hash functions and others.
In this case, process of sequence m , m ∈Vn and new value of internal status vector E ,
Stage 1. Formation of additional vectors A , B , C і D and calculation of new values of vectors Ea , Eb , Ec , Ed :
Stage 2. Calculation of the new value internal status vector E , E ∈V : e Stage 3. Formation of the sequence m , m ∈V :
n A, Ea = FA ( Ea , Ka , i ) , A ∈Vn , Ea ∈Va , B, Eb = FB ( Eb , Kb , i ) , B ∈V , E ∈Vb ,
n b C, Ec = FC ( Ec , Kc , i ) , C ∈V , E ∈Vc ,
n c D, Ed = FD ( Ed , Kd , i ) , D ∈V , Ed ∈V .
n d
E = ( Eb , Ed , Ea , Ec ) .
AB = A <<< B , AB ∈V ,
n CD = C <<< D , CD ∈V ,
n BC = B + CD , BC ∈V ,
n AD =AB ⊕ D , AD ∈V ,
n m =AD ⊕ S ( BC ) , m ∈V , n where ⊕ і + are operations modulo addition 2 and 2n respectively, S ( x) is substitution operation.
Output of the function Fgen ( E, K , i ) will be vectors m , m ∈Vn and E , E ∈V : e ( m, E ) = Fgen ( E, K , i ) .
In this Section computational model of PRNG was described. Based on PRNG Trivium, this model includes internal status vector and key vector processing, dynamic carry shift and 4 nonlinear functions. It allows to construct effective PRNGs for privacy ensuring in modern communication networks (5G networks and others).
3.2.
On the basis of developed computational model 3 PRNGs 5Gen-1, 5Gen-2 and 5Gen-3 was constructed:
5Gen-1 was constructed with following set of parameters n = 128 , a = 128 , b = 100 , c = 111 , d = 173 , e = a + b + c + d = 512 , a′ = 128 , b′ = 128 , c′ = 128 , d ′ = 128 , k = a′ + b′ + c′ + d ′ = 512 . FA , FB , FC and FD are functions based on the non-linear shift register. As substitution S ( x) the operation S ( x) = ( s0 ( x31 ), ..., s0 ( x0 )) was used, where x j ∈ V16 , j = 0,31, S0 is the substitution on the set V16 .
Substitution S0 is constructed with parameters, presented in Table 1. 5Gen-2 was constructed with following set of parameters n = 256 , a = 138 , b = 120 , c = 116 , d = 138 , e = a + b + c + d = 512 , a′ = 128 , b′ = 128 , c′ = 128 , d ′ = 128 , k = a′ + b′ + c′ + d ′ = 512 . FA , FB , FC and FD are functions based on the non-linear shift register. As substitution S ( x) the operation S (x) = ( s7 ( x63 ) , ..., s0 ( x0 )) was used, where x j ∈ V8 , j = 0,63 , Sb is substitution on the set V8 , b = 0,7 (by the order 8 different substitution tables are using).
Substitution Si , i = 0, 7 is constructed with parameters, presented in Tables 2-9. Parameters for substitution table S1 construction for 5Gen-2 algorithm { 20, 40, 80, 1, 2, 4, 8, 10} 5Gen-3 was constructed with following set of parameters n = 128 , a = 128 , b = 128 , c = 128 , d = 128 , e = a + b + c + d = 512 , a′ = 128 , b′ = 128 , c′ = 128 , d ′ = 128 , k = a′ + b′ + c′ + d ′ = 512 . F , F , FC and FD are functions based on AES-128 algorithm. As
A B substitution S ( x) the operation S ( x) = ( s0 ( x63 ), ..., s0 ( x0 )) was used, where x j ∈ V8 , j = 0,63 , S0 − підстановка на множині V8 .
Substitution S0 is constructed with parameters, presented in Tables 10.
Statistical parameters of developed PRNGs were investigated using traditional techniques
NIST STS [
The statistical test is based on the verification of null hypothesis H0 – that the sequence under study is random. Alternative hypothesis H1 is also provided – the sequence under study is not random. Therefore, the generated sequence is examined by a set of tests, each of which concludes whether the hypothesis H0 is rejected or accepted. For each test, adequate randomness statistics are selected based on which the hypothesis H0 is further rejected or accepted. Theoretically, the distribution of statistics for the null hypothesis is calculated using mathematical methods. The critical value is then determined from such an exemplary distribution. When performing the test, the value of the test statistic is calculated, which is compared to the critical value. In case of exceeding the test critical value over the reference, hypothesis H1 is accepted, otherwise – hypothesis H0.
For the experiments, the following input parameters were selected for the use of NIST STS: 1. The length of the test sequence n=106 bit. 2. The number of sequences being tested m=100. 3. Significance level α = 0, 01 .
4. Number of tests q=188, among them: Frequency − 1, Block Frequency − 1, Cumulative Sums − 2, Runs − 1, Longest Run − 1, Rank − 1, FFT − 1, Non Overlapping Template − 148, Overlapping Template − 1, Universal − 1, Approximate Entropy − 1, Random Excursions − 8, Random Excursions Variant − 18, Serial − 2, Linear Complexity − 1.
The confidence interval rule was applied, the lower bound being 0.96015. For every algorithms 10 files with sequences (100 Mbit) and investigated by NIST STS technique.
The results of testing are presented on Fig. 3-5.
Also developed algorithms were investigated by DIEHARD technique (one of the best practice
and traditional approach in cryptography for measuring quality of PRNG and statistical security).
Results of testing for 5Gen-3 algorithms presented on Fig. 6 (other two algorithms 5Gen-1 and
5Gen-2 showed 100% results).
Results presented on Fig. 3-5 as well as detail experimental data (Table 11) show that developed
algorithms 5Gen-1, 5Gen-2 and 5Gen-3 have passed complex control by NIST STS technique
and show better results (in some cases) than existed and well-known algorithms [
Results presented on Fig. 6 show that developed algorithms have passed complex security control by DIEHARD technique as well as verified good quality of PRNG and statistical security of potential systems based on these algorithms [14-16].
For investigation developed PRNGs 5Gen-1, 5Gen-2, 5Gen-3 were realized as software tools using programming language С++. Given results were compared with results of well-known SNOW generator. Experimental study was carried out using work station Intel Core i3-3220 3.3GHz and files with different size. Average results are presented on the Table 12. As we can see from Table 12 speed of the developed algorithms are higher in comparison with SNOW till 21% outside two results of 5Gen-3 algorithm.
In this paper analysis of different approaches in PRNG creation and implementation was carried out. Two categories of PRNGs were defined (cryptographically secure and cryptographically insecure) as well cryptographic applications that require random numbers were defined (key generation, cryptographic nonces, salts in certain signature schemes). But there are many relevant tasks related with data privacy risk mitigation and confidentiality ensuring in 4G/5G that can be solved by advanced PRNG development and implementation.
Computational model of PRNG was developed. Based on PRNG Trivium, this model includes internal status vector and key vector processing, dynamic carry shift and 4 non-linear functions. It allows to construct effective PRNGs for data privacy risk mitigation in modern communication networks (5G networks and others).
On the basis of developed computational model 3 PRNGs 5Gen-1, 5Gen-2 and 5Gen-3 was constructed and realized as software tools. These PRNGs have passed complex statistical testing by NIST STS technique as well as speed parameters investigation (developed algorithms are higher in comparison with SNOW till 21%).
Additionally, developed algorithms were investigated by DIEHARD technique (one of the best practice and traditional approach in cryptography for measuring quality of PRNG and statistical security). These algorithms have passed complex security control by DIEHARD technique as well as verified good quality of PRNG and statistical security of potential systems based on these algorithms.
[12] J.M.Mcginthy, A.J.Michaels, Further Analysis of PRNG-Based Key Derivation Functions,
IEEE Access, vol. 7, 2019, pp. 95978-95986 [13] P.S.Paul, M.Sadia, M.S.Hasan, Design of a Dynamic Parameter-Controlled Chaotic-PRNG in a 65 nm CMOS process, IEEE 14th Dallas Circuits and Systems Conference (DCAS), 2020, pp. 1-4, doi: 10.1109/DCAS51144.2020.9330647 [14] Z.Hua, Y.Zhou, One-Dimensional Nonlinear Model for Producing Chaos, in IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 65, no. 1, 2018, pp. 235-246, Jan. doi: 10.1109/TCSI.2017.2717943 [15] M.Iavich, A.Gagnidze, G.Iashvili, S.Gnatyuk, V.Vialkova, Lattice based Merkle, CEUR
Workshop Proceedings, vol. 2470, 2019, pp. 13-16 [16] S.Ergün, Security analysis of a random number generator based on a double-scroll chaotic circuit”, 16th International Symposium on Communications and Information Technologies (ISCIT), 2016, pp. 123-126, doi: 10.1109/ISCIT.2016.7751605