Generalized information domain (GID) is the space of all kinds of digital information stored in digital equipment or transferred over the Internet that can be expressed by binary code. With the development of the information technology and the Internet, GID is so large that it can be seen as an infinite space to some extent. In this paper, we denote the generalized information file as GIF which refers to the file in GID. Because of the diversity of users in cultural background, career, interests, habits and so on, the user’s choice of GIF from GID can be seen as random behavior and an entropy source that is easy to get without any other facility. Zhang et al.^[29] proposed a random number generator based on discrete trajectory transform in the generalized information domain (RGDG). In RGDG, they first reconstruct the GIF and user input using shift operation with restriction condition to get the data stream which has good statistical properties and appropriate length denoted by background (BG). Then, a discrete trajectory extraction (DTE) method is proposed to extract the random number from BG. A system random source called initial value IV = {t,r,u} where t is system time, r is a system random number, and u is the user’s personalized input that is introduced. IV is used to calculate the extraction position and the extracted data is used in updating the IV in a feedback mechanism. Experimental results showed that RGDG had superior randomness and passed the NIST statistical test with a high ratio. However, we found that RGDG spends most of the time on calculating extraction positions. To speed up RGDG and preserve its good property at the same time, we propose an accelerated scheme based on drift factor (DF) in this paper, called RGDG-DF. DF is 32-bit vector used in the process of calculating extraction positions in Section 2.3.

According to Ref. [29], GIFs usually have bad statistics properties such as low information entropy, high correlation coefficient, etc. To generate random number sequences, we also reconstruct GIF first to get a sequence with an appropriate length and good statistics properties which is called BG.

The reconstruction process includes n rounds. We note GIF as RB₀ (reconstruction block) and the result of the ith round of reconstruction as where is an 8-bit data. In each round, the reconstruction process can be presented as follows:

In Eq. (3), a counter vector C = {c_k} (k = 0,1,…,255) is introduced, where c_k records the frequency of code k during the extraction process of each round and c_min = min{c_k} (k = 0,1, …,15). At the beginning of each round, C will be reset to zero. The restriction condition is used to control the frequency distribution of each code of RBⁱ to be balanced. The restriction factor q₁ is used to control the degree of the balance level. If q₁ gets smaller, the restriction condition becomes more critical and the frequency distribution of the code sequence is more balanced. It is proved in Ref. [29], if l_i > 255 × q₁, each code of RBⁱ exits and the frequency difference of any two codes is no more than q₁. After n rounds of reconstruction, we obtain a sequence RBⁿ and note it as BG = {b_i}, where b_i ∈ {0,1, …,255} (i = 0,1,2, …,l_n − 1).

BG cannot be used as random sequence directly because it has some regular pattern, not random. Therefore, an extraction method is used to generate random number sequences. The process of generating random number sequences SK and trajectory sequence PK from BG can be presented as (SK,PK) = f (BG,IV,D), where f is the extraction function. In each extraction operation, four bits of data are extracted from BG and added into the final random sequence based on some restriction condition. We introduced another counter vector denoted by where c_k records the frequency of code k during the extraction process, C′ is initialized as zero and

The extraction process is given as follows.

Step 1 Set IV = {ST,SI,UI}. ST is system time generated by the computer system and SI is system unique identifier such as hard disk number of the machine. UI depends on user’s input, such as a number, a sentence, etc. The size of ST and SR is four bytes in standard configuration.

Step 2 Hash transformation of IV. Choose an irreversible, strong, collision-free hash function to transform IV to a vector AI = (x₀,x₁, …,x_m). The size of x_i (i = 0,1, …,m) is 32 bits.

Step 3 Calculate the extraction position, trajectory address (ta) using

Step 4 (Only in the first round) Initialize DF. Start at position ta (by bit) of BG and sequentially get 32 bits data noted ω to initialize DF using formula

Step 5 Calculate ta using DF by formula

Step 6 Extract random number. Start at position ta (by bit) of BG and sequentially get four bits data noted M. If M cannot satisfy the restriction condition (i): then let ta = ta + 1 and get four bits data sequentially again. Repeat this process until we get a data M satisfying condition (i).

Step 7 Update DF using formula

Step 8 Repeat Steps 5–7 four times and obtain M four times. Then go to Step 9 until we obtain sequence of requested length.

Step 9 Get new AI. AI = (x₀,x₁, …,x_m) is seen as a 32 × m-bit-long sequence. Left shift four bit of AI and add four bits data M from Step 6 into the rightmost four bit of AI then get the new AI. Then go to Step 3.

Repeat Steps 3–9 until we get sequence SK of requested length. Another sequence SK′ can be generated similarly. In addition, we record the ta sequence denoted by PK which will be used in the permutation part of the image encryption process.

In RGDG, analysis results show that the computation of Eq. (4) is time-consuming, taking about 60% of the whole time. This is because that equation (4) uses plenty of multiplications. To improve the efficiency of RGDG, in RGDG-DF, a 32-bit vector DF is introduced in Steps 4–7. In Step 4, DF is initialized by random data from BG and is different every time. Calculating ta using DF and the previous ta as in Step 6 mainly uses the addition operation which is more time-saving than Eq. (4). In Step 7, the extracted data M is used to update DF in a feedback mechanism which makes the extraction process more complex. Figure 1 shows the distribution of trajectory address (ta) and the changing process of DF sequence. We can see that ta has a balanced distribution in BG sequence and the changing process of DF is a random process like white noise.

Fig. 1.

	Figure Option ViewDownloadNew Window
	Fig. 1. (a) Distribution of ta sequence on BG (500000 bits), (b) changing process of DF.

RGDG-DF has key K = {GIF, (S,L),D}, parameters q₁ and q₂. The suggested value ranges of parameters are summarized as below.

Step 1 Generate a random byte c₀ and three random sequences PK, SK′, and SK as described in Section 2.

Step 2 Pre-diffusion. Compute the pixel value of the middle cipher image by the following formula:

Step 3 Permutation. (I) Sort PK = (pk₁,pk₂,…,pk_M×N) and obtain

Step 4 Diffusion. Compute the pixel value of the cipher image by the following formula:

The decryption process is similar to the encryption process and is the inverse of the encryption process.

Step 1 Generate a random byte c₀ and three random sequences PK, SK′, and SK as described in Section 2.

Step 2 Generate P-box T using the same method as Step 2 in the encryption process.

Step 3 Get from the cipher image using the formula

Step 4 Perform the reverse operation using P-box T and obtain the middle cipher image from where

Step 5 Obtain plain image P = (p₁,p₂},…,p_M×N) from by

In our scheme, we propose a new shuffle method shown in Eq. (9) which has a simple inverse shown in Eq. (12). Equation (12) only uses the P-box T and does not need to calculate the inverse permutation sequence. This makes the decryption process more efficient.

We choose 10 groups of different keys and parameters as shown in Tables 1 and 2 to generate 100 random sequences of 1000000 bits for each group and test them using NIST special publication 800-22,^[30] a statistical package consisting of 15 tests for random and pseudo-random number generators for cryptographic applications. The results are shown in Table 3.

Table 1.

Table 1.

Table 1. Ten groups of keys and parameters for the NIST tests. Groups 1–5. . No. 1 2 3 4 5 GIF IE11-Windows6.1.exe (1.98 MB) Baboon.bmp(256 × 256) (257 KB) (q1,q2) (26,26) (30,70) (35,35) (40,60) (45,45) n 3 4 3 4 5 S (1,2,3)×2400 (1,2,3,4)×600 (1,2,3)×1000 (1,2,3,4)×1200 (1,2,3,4,5)×1400 L (1,2,3)×44000 (1,2,3,4)×30000 (1,2,3)×20000 (1,2,3,4)×18000 (1,2,3,4,5) ×12000 D (2151, 4302, 6453) (16291, 30042, 43793, 57544) (1989, 3978, 5967) (3989, 7978, 11967, 15956) (12021, 24042, 36063, 48084, 60105) AI (41,18467, 6334) (234,30031, 11744,4443) (77,5628, 6232) (68,6151, 18175, 22398) (77,5628, 6232,29052,1558)

Table 1. Ten groups of keys and parameters for the NIST tests. Groups 1–5. .

Table 2.

Table 2.

Table 2. Ten groups of keys and parameters for the NIST tests. Groups 6–10. . No. 6 7 8 9 10 GIF fips1402annexa.pdf (89.8 KB) ReadMe.htm (966 B) (q1,q2) (50,50) (55,55) (60,40) (65,65) (65,70) n 3 4 5 3 4 S (1,2,3)×2000 (1,2,3,4)×44 (1,2,3,4,5) ×333 (1,2,3)×1800 (1,2,3,4) ×4200 L (1,2,3)×40000 (1,2,3,4) ×44000 (1,2,3,4,5 ×36000) (1,2,3)×90000 (1,2,3,4) ×100000 D (6024,12048, 18072) (6024,12048, 18072,24096) (8691,14842, 20993,27144,33295) (14894,28518, 42142) (32299,34856, 37413,39970,42527) AI (90,15854, 12153) (103,26079, 18073,24951) (123,25034, 26954,5491,14890) (228,8535, 8784) (159,12194, 26852,8043,30046)

Table 2. Ten groups of keys and parameters for the NIST tests. Groups 6–10. .

Table 3.

Table 3.

Table 3. Results of the NIST statistical test (at the 1% level). . Statistical test Average pass ratio% Frequency 100.00 Block frequency 99.30 Cumulative sums (FORWARD) 100.00 Cumulative sums (REVERSE) 100.00 Runs 100.00 Longest run 99.70 Rank 99.00 FFT 98.80 Non overlapping template 99.80 (template = 000000001) Overlapping template 99.60 Universal 98.20 Approximate entropy 99.00 Random excursions (x = −1) 99.30 Random excursions variant (x = −1) 99.50 Serial 98.20 Linear complexity 99.50

Table 3. Results of the NIST statistical test (at the 1% level). .

From Tables 1–3, it can be seen that RGDG-DF has passed the test suit with a high ratio in different configurations. In some tests, i.e., the frequency test, cumulative sums (FORWARD), cumulative sums (REVERSE), and runs, the pass ratio is even 100%. This shows that RGDG-DF has superior randomness.

Key space size is the total number of different keys which can be used in the encryption. A good encryption algorithm should be sensitive to the secret keys, and the key space should be large enough to make brute-force attack impossible.

In our algorithm, GIF together with parameters (S,L), D denoted by K = {GIF, (S,L),D} can be seen as generalized key compared with traditional symmetric cryptography. This generalized key is different from the traditional key of a modern cryptography system such as DES, AES in three ways: (i) the length or size of K is not fixed, (ii) the key space is infinite, (iii) K can be stored in the facility of both sides of the communication and does not need to be transferred in a long time. GIF can be any digital file from the GID so its space is infinite theoretically. As mentioned before, we suggest that the size of GIF should range from 0.5 KB to 10 MB. Suppose the size of GIF is 1KB, then the space of GIF is 2^1024×8 = 2⁸¹⁹². (S,L) = {(s_i,l_i)}, (i = 1,2,…,n), where s_i and l_i are 32-bits integer and n ∈ [3,7]. Suppose n = 3, then the space of (S,L) is 2^32×2×3 = 2¹⁹². D = (d₀,d₁,…,d_m), (i = 0,1, …,m), where d_i is 32-bits long. If m = 4, then the space of D is 2^32×5 = 2¹⁶⁰. Thus, the key space of our algorithm is at least 2^8192+192+160 = 2⁸⁵⁴⁴ which is so huge that it can prevent brute-force attack.

For experimental analysis, IV remains unchanged in Subsection 4.3–4.5 and the corresponding AI is given in Table 4. Key K₀ = {GIF₀, (S₀,L₀),D₀} and parameters used in Subsections 4.3–4.5 are also shown in Table 4.

Table 4.

Table 4.

Table 4. Key K0 and parameters. . GIF0 S0 L0 D0 AI0 q1 q2 Baboon.bmp (1,2,3,4)×400 (1,2,3,4)×60000 (4982,9895, 14808,19721) (381,22190, 29200,5949) 47 47

Table 4. Key K0 and parameters. .

4.3.2. Correlation analysis

Correlation between pixels is an important intrinsic feature of an image. To resist statistical analysis, a good encryption algorithm should remove the high correlation of the plain image. We select all the pairs of two-adjacent pixels in vertical, horizontal, and diagonal directions from the plain image and the cipher image, and calculate the coefficient by

where x and y are gray-scale values of two adjacent pixels in the image and N is the total number of pixels.

We test the correlation coefficients of adjacent pixels in the plain image “Lenna” and its cipher image and the result is listed in Table 5. It shows that the correlation coefficients of adjacent pixels in the cipher image are negligible around zero. Moreover, we choose 1000 pairs of two horizontally adjacent pixels and their correlation is shown in Fig. 3. These results substantiate that the proposed algorithm has removed the strong correlation among neighboring pixels of the plain image.

Fig. 2.

	Figure Option ViewDownloadNew Window
	Fig. 2. (a) Plain image, (b) cipher image, (c) histogram of the plain image, and (d) histogram of the cipher image.

Table 5.

Table 5.

Table 5. Correlation coefficients of two adjacent pixels in the plain image and cipher image. . Direction Plain image Our algorithm Ref. [18] Ref. [19] Ref. [25] Horizontal 0.939918 0.000369102 0.0014 0.0035 –0.000848277 Vertical 0.969235 0.000636604 0.0171 0.00247 0.00370914 Diagonal 0.937176 0.000996246 0.0054 0.00107 –0.000188985

Table 5. Correlation coefficients of two adjacent pixels in the plain image and cipher image. .

Fig. 3.

	Figure Option ViewDownloadNew Window
	Fig. 3. Correlations of two horizontally adjacent pixels: (a) correlation of the plain image and (b) correlation of the cipher image.

4.3.3. Information entropy analysis

The information entropy is an important feature of the randomness and the information entropy H(s) of a message source s can be calculated as

where p(s_i) denotes the probability of symbol s_i. For a true random 256 gray-scale image, the entropy should be 8. The entropy of cipher images of three plain images “Lenna”, “Baboon”, and “Pepper” is shown in Table 6. The entropy values of the cipher images are very close to the theoretical value eight which means the information leakage in the encryption process is negligible. The results of the proposed algorithm and three existing algorithms^[18,19,25] are shown in Table 7.

Table 6.

Table 6.

Table 6. Entropy value for the cipher images. . Plain image Entropy value Lenna 7.99793 Baboon 7.99929 Pepper 7.99922

Table 6. Entropy value for the cipher images. .

Table 7.

Table 7.

Table 7. Entropy value for cipher images of “Lenna”. . Cipher image Entropy value Ref. [18] 7.9974 Ref. [19] 7.9973 Ref. [25] 7.99748 Proposed 7.99793

Table 7. Entropy value for cipher images of “Lenna”. .

In order to measure the different ranges between two images, we use NPCR (number of pixels change range) and UACI (unified average changing intensity),

4.4.1. Key sensitivity analysis

Key sensitivity is an essential feature for any good cryptosystem which guarantees the security of the cryptosystem against the brute-force attack to some extent. In the proposed algorithm, the generalized key K = {GIF, (S,L),D} is composed of several parts so we run several tests for each part of the key K separately. We randomly change one bit of GIF 1000 times to get 1000 slightly different GIFs and keep (S,L), D unchanged. We encrypt image “Lenna” using K₀ and these 1000 keys and calculate the average NPCR and UACI of the cipher images using Eqs. (19) and (20). There are 29 results that NPCR = 0, UACI = 0. This is because the effective GIF is related to (s₁,l₁) and the only changed bit may not belong to the effective GIF. However, the effective GIF is large enough to resist the brute force attack. The average results of the 971 groups are shown in Table 8. Similarly, change one value of (S₀,L₀) by adding or minusing 1 separately and get a series keys. We encrypt image “Lenna” using K₀ and these keys and calculate the average NPCR and UACI of the cipher images. The average results are shown in Table 8. IV = {ST,SI,UI} sent with the cipher image is not part of the key, but is the unique variable of the encryption algorithm and when the key is fixed, IV is the main factor of the approximately one-time pad manner. Therefore, a tiny change in the IV should cause a substantial change in the cipher image. AI = (x₀,x₁, …,x_m) is the hash transformation result of IV. For simplification, we test the sensitivity of AI instead of IV. We choose AI₀ = (x₀,x₁, …,x_m) and K₀ to encrypt plain image “Lenna” and then encrypt the same image with the same K₀ and other slightly different AIs. The NPCR and UACI between the cipher images are given in Table 8.

Table 8.

Table 8.

Table 8. NPCR and UACI between cipher images with key K0 and slightly different keys. . K NPCR% UACI% GIF 99.6086 33.50182 (S,L) 99.60309 33.50534 D 99.62176 33.49288 AI 99.60233 33.5227

Table 8. NPCR and UACI between cipher images with key K0 and slightly different keys. .

4.4.2. Plaintext sensitivity

In order to resist differential attack, a tiny change in the plain image should cause a substantial change in the cipher image. Given a 256 gray-scale plain image P of size 256×256 and get a P′ which only has a single pixel difference in a random position (i, j), where i, j = 0,1, …,255,

Encrypting P and P′ obtains the cipher images C and C′, then we calculate NPCR and UACI using Eqs. (19) and (20). We test 3 groups of plain images, randomly repeat this process 100 times and get the average NPCR and UACI shown in Table 9, respectively, which are very close to their expectation.

Table 9.

Table 9.

Table 9. NPCR and UACI between cipher images with slightly different plain images. . Plain image NPCR% UACI% Lenna 99.5737 33.4789 Baboon 99.60791 33.44112 Pepper 99.61115 33.46517

Table 9. NPCR and UACI between cipher images with slightly different plain images. .

We have used Microsoft Visual Studio 2010 to run RGDG,^[29] RGDG-DF, encryption and decryption programs in a personal computer with an Intel Core i3 CPU 2.53 GHz, 2 GB memory and 250 GB hard-disk capacity, and the operation system is Microsoft Windows 7. The average speed of RGDG-DF is 8.29 M/s and the average speed of RGDG is 5.78 M/s. The average time of encryption/decryption on 256 gray-scale images of size 512 × 512 is 150 ms. Considering the speed of the Internet transmission, our algorithm can well satisfy the practical situation.

Compared with that in Ref. [29], we add a random value SI in the initial value IV. It can be deduced that when encrypting any two images, IVs must be different. ST is system time generated by computer system so when encrypting images at different times the STs are different. SI is system unique identifier such as hard disk number, mainboard number, etc. When encrypting the two images at the same time then they must be at different machines so that SIs are different. It is easy to notice that Eq. (4) is an injection of A = (a₀,a₁, …,a_m). Therefore, in a practical situation, different IVs usually result in different random streams. Thus, every encryption uses different keystreams and this encryption method is an approximately one-time pad. Therefore, the attacks proposed in Refs. [15], [16], and [28] become ineffective to this new scheme. The proposed scheme can easily resist the known plain text and the chosen plain text attacks.

Key management includes key storage, key backup/recovery, and key period. In our scheme, the key K = {GIF, (S,L),D} can be seen as a generalized key compared with traditional symmetric cryptography. The process of the communication in practical usage is shown in Fig. 4. The key K only needs to be settled by both sides of the communication in the first time and can be stored at the machine of both sides. No secret key needs to be exchanged during the encryption process. IV and the cipher image are sent to the receiver on a public channel. Therefore, our scheme can tremendously reduce the risk of key leakage. For example, the sender and receiver choose the newest installation package of iTunes as GIF. The key {(S,L),D} is exchanged on a safety channel. GIF can pretend to be an ordinary file in the computer and does not need to be stored securely. In addition, the backup GIF can be found on the Internet anytime which is very convenient. The period of ST is 2³²/(60 × 60 × 24 × 365) = 136 year (when the time unit is seconds). When a longer period is needed, a larger ST such as 64 bits could be applied, so in a quite long time, both the sender and receiver do not need to change the key for safety which saves sources from key distribution and exchange.

Fig. 4.

	Figure Option ViewDownloadNew Window
	Fig. 4. Communication of the sender and receiver.