Improvement of hash function based on life game

0 lead said

       Hash The function is in 20 century 50 Technology introduced in the s , It maps an arbitrary length message to a fixed length message digest .Hash Function was first used to detect random errors due to noise in message transmission , Later, it was mainly used to detect human errors or fabricated messages in message transmission . be based on Hash The application of function message authentication is developing rapidly , Widely used, including message authentication 、 Password check 、 software protection 、 Construction of encryption algorithms and other fields .
        The game of life is English mathematician John · Horton · Conway is in 1970 Cellular automata invented in , Each grid in the game of life follows simple rules , The following rules ：
1． The state of each cell is determined by the last state of the cell and its surrounding eight cells ;
2. If a cell has 3 One cell for life , The cell is living , That is, if the cell was originally dead , Turn to life , If it was a living , Keep the same ;
3. If a cell has 2 One cell for life , Then the state of life and death of the cell remains the same ;
4. In other cases , The cell is dead , That is to say, if the cell was originally living , Turn to death , If it was death , Keep the same .

1 Based on the game of life hash function

        The game of life has simple rules , Interaction between each cell unit , Showing extremely complex forms . The final evolution of the game depends on the initial conditions and rules of the game .
Use the game of life to test a piece of data hash operation , The algorithm is described as follows ：
① Select canvas size ;
② Set the rules ;
③ Solve operations beyond the boundary , It can be calculated according to its corresponding boundary , For example, the cells on the left boundary , The operation of determining life and death is carried out by the surrounding cells and their corresponding cells on the boundary , You can also give up , Or other rules ;
④ Determine the number of cycles ;
⑤ Make sure you want to select hash Number of digits of the value ;
⑥ Processing and converting data ;
⑦ obtain hash value .
        Its original rules cannot be used here , Because the original rules will soon lose all the data , So here , The rules need to be changed .

2 About the relevant calculation of the algorithm

        One way ：
        Here, take the original rule as an example to calculate , A living lattice , There are two situations , First , This lattice makes a living , And the last status of the surrounding grid is 2 raw 6 die , So there is 28 In this case ; perhaps , The last status of the grid around this grid is 3 raw 5 die , So there is 56 In this case .
        A lattice for death , There are two situations , First , This grid is dead , And the last status of the surrounding grid is 2 raw 6 die , So there is 28 In this case ; perhaps , The last status of the grid around this grid is not 3 raw 5 Dead and the last state of this grid is alive , So there is 172 In this case ; also , The last status of this grid is dead , And the last status of the surrounding grid is 2 raw 6 die , So there is 28 In this case .
        Because the last state of this grid is lost , And this is just a grid , Therefore, the absolute unidirectionality is guaranteed .

3 Performance analysis and algorithm simulation

Experimental analysis of the above algorithm ：
① take 200 That's ok 300 Column canvas ;
② Take the rules as the improvement of the original life game rules , There is 2 A or 4 Make a living in a grid , Then this lattice will not change , There is 3 Make a living in a grid , Then this grid makes a living , The rest of the cases are dead ;
③ Solve operations beyond the boundary , Operation according to its corresponding boundary , Turn the canvas into a closed loop ;
④ Then take a set of data , Here we take random numbers , One 30 That's ok 30 Columns of the matrix , For intuitive performance , Convert binary to 1 Take black ,0 Take white , The display is shown in the picture figure1;

figure1
⑤ Determine the number of cycles , Here is to show the stable results , Take a larger number of times , take 600 Time ;
⑥ Make sure you want to select hash Number of digits of the value , As a demonstration , Take the whole canvas here ;
function
⑦ obtain hash value , The visual display is shown in the figure figure2.

figure2

4 Statistical analysis of chaos and diffusion properties

        The second row and the second column of the data in the above example are divided into 1 Change it to 0, The visual display is shown in the figure figure3

figure3
        You can see that the color of the second row and the second column changes to white , Proceed again hash, obtain hash value , The visual diagram is shown in the figure figure4.

figure4
        To hide the redundancy of plaintext information ,Shannon Put forward the concept of chaos and diffusion , That is, encryption system requires full and uniform use of ciphertext space . Try to make clear text correspondence Hash Values are not relevant , For binary representation of information , Each bit can only be 0 or 1 Two possible , So ideal Hash The diffusion effect of is caused by the slight change of initial value Hash value 50% Transformation of . From the above Hash The experiment shows that , The data changes by one bit , The degree of change reaches 48.735%, near 50%, It has good chaos and diffusion .

4 improvement

        You can simply take a small piece of the entire canvas as hash Worth the end result , You can also change two dimensions into three dimensions or higher . The size of the input information can be determined by the size of the canvas , This will hash Function becomes a flexible function , In order to meet the needs of different occasions .

5 Conclusion

        By changing the rules of the game of life , Play life with hash Function combination , Through the image to better show hash The process of .