May 14, 2020 23:00:00

'SHA-256 Animation' that allows you to intuitively understand the calculation process of the hash function 'SHA-256' with animation

Encryption of digital certificates and

block chains are made up of ' hash functions ' that calculate a hash value that is a completely different value from the input value. Engineer Greg Walker has released the program ' Sha-256 Animation ' that can display the process of calculating the hash value of ' Sha-256 ' which is a typical hash function by animation.

GitHub-in3rsha / sha256-animation: Animation of the SHA-256 hash function in your terminal.
https://github.com/in3rsha/sha256-animation

The following is a movie that actually runs the program.

When observing how the hash value is generated with `` SHA-256 Animation '' it looks like this-YouTube


I used Ubuntu 18.04 this time to run the program.

Since SHA-256 Animation is a program written in Ruby, execute the following command to install the execution environment in advance.

[code] sudo apt install ruby [/ code]

Clone the program from GitHub.

[code] git clone https://github.com/in3rsha/sha256-animation.git[/code]

When I entered the cloned directory, the programs were located.

Let's calculate the hash value of the string 'abc' using 'sha256.rb' of SHA-256 Animation.

Somehow the calculation has started.

After waiting for about 1 minute, the hash value of 'abc' was displayed at the end.

The GitHub page where SHA-256 Animation is published also explains how to calculate the hash value by SHA-256.

SHA-256 will perform four basic operations on input values. Each operation is implemented by the SHA-256 Animation program. The first operation is a binary right shift, which shifts the binary numbers represented by 0 and 1 to the right by the specified number. It is said to be implemented by 'shr.rb' in SHA-256 Animation.

The second operation is bit rotation. A right shift discards digits that overflow the digit, whereas a bit rotation shifts digits that overflow the digit from the left. It is explained that it is implemented in 'rotr.rb' in SHA-256 Animation.

The third operation is

exclusive OR (XOR) . XOR returns 0 if both bits are 0 or both are 1, and 1 if both are 0 and 1. It is said to be implemented by 'xor.rb' in SHA-256 Animation.

The fourth operation is normal addition, but in order to obtain a 32-bit value, the value after addition is divided by 2 32, and the

remainder operation is performed to find the remainder . SHA-256 Animation explains that it is implemented by 'add.rb'.

SHA-256 combines these operations and implements four functions. In the σ0 function implemented as 'sigma0.rb' in SHA-256 Animation, the input value is rotated 7 digits to the right, the value rotated 18 digits to the right, and the value shifted 3 digits to the right is XORed, It will return the calculation result.

The sigma1 function implemented in 'sigma1.rb' returns the value obtained by rotating the input value by 17 digits to the right, the value rotated by 19 digits to the right, and the value obtained by rotating 10 digits to the right by XOR operation.

The Σ0 function is implemented in 'usigma0.rb', and it returns the value obtained by XORing the input value rotated by 2 digits to the right, the value rotated by 13 digits to the right, and the value rotated by 22 digits to the right. thing.

It is explained that the Σ1 function implemented in 'usigma1.rb' returns a bit string that is the result of XORing the input value rotated 6 digits to the right, the value rotated 11 digits to the right, and the value rotated 25 digits to the right. I am.

There are two main SHA-256 functions. Choice function and Majority function. The Choice function is implemented by 'ch.rb', and for three input values x, y, and z, the bit of y is selected when x is 1, and the bit of z is selected when x is 0. It is said that the bit string arranged in step is calculated.

It is explained that the Majority function implemented by 'maj.rb' compares the number of 0's and 1's in each bit of x, y, and z and calculates the value in which the larger one is arranged. For example, if x is 1, y is 1, and z is 0, 1 is returned.

'Constants.rb' of SHA-256 Animation is a program for calculating constants used in SHA-256. In SHA-256, the

cube root of the first 64 prime numbers arranged in ascending order is multiplied by 2 32, and these constants are irrational numbers . It is convenient for you. The 64 constants are named K0-K63 in order.

You can get the hash value from a 32-bit binary number with the programs so far, but there is still an operation to convert a character string into a 32-bit bit string. In SHA-256 Animation, in 'message.rb', first, the input character string is inquired with the

ASCII code table, and it is explained that the bit string is created by concatenating the values converted from decimal numbers in the code table to binary numbers. It has been.

Since SHA-256 calculates the hash value by dividing the input for each 512 bits, it is necessary to

pad the size of the bit string calculated in 'message.rb' to be a multiple of 512. In SHA-256 Animation, set the bit immediately after the input bit string to 1, pad with 0 up to 448 bits, and pad the remaining 64 bits with the size of the input bit string to prevent collision of hash values. It is said that there is.

If the input value can be padded, the operation to cut the input value after padding every 512 bits is performed by 'blocks.rb'. This one block is called 'message block'.

Finally, the 512-bit message block is converted into a 64-bit string with a size of 32 bits, and numbers W0 to W63 are assigned to each. Of the 64 bit strings, the first 16 are the message blocks cut as they are for every 32 bits and are performed by 'schedule.rb'.

The remaining 48 bit strings are created by 'expansion.rb' starting from the 16 bit strings cut from the message block with 'schedule.rb'. In 'expansion.rb', the bit string that is the number two bits before the number of the bit string to be generated is input to the σ1 function, the bit string that is seven numbers before, and the bit string that is 15 bits before is input to the σ0 function It is explained that the previous bit string is added to calculate the value.

The operation of 'schedule.rb' and 'expansion.rb' is expressed in a formula like this.

Finally, we will calculate the hash value from here. The original value of the hash value is calculated by calculating the square root of the first 8 prime numbers arranged in ascending order by 'initial.rb', and multiplying the decimal part by 2 32 to convert it to a binary number ah Use a bit string consisting of. It seems that this operation is also to make the hash value more robust.

Compress 64 values calculated from the input string, 64 constants from 'constants.rb', and 8 constants from 'initial.rb'. The compressed value is temporarily stored in variables named T1 and T2. The compression to T1 is performed by 't1.rb', and the Σ1 function and Choice function explained so far are used.

When expressing the compression method of 't1.rb' with a mathematical expression, it looks like this.

Another variable, T2, is calculated by 't2.rb', and the Σ0 function and Majority function are used.

It is said that the processing of 't2.rb' is expressed as a mathematical expression as follows.

Using T1 and T2 generated in this way, compression is performed recursively. The value obtained by adding T1 and T2 is set to 'a' of eight constants and T1 is set to 'e', and the 64 bit string consisting of W0 to W63 calculated from the input character string and 'constants' .rb ”is used to calculate T1 and T2 by using the 64 constants K0 to K63 calculated from the prime numbers in order. You can check the animation by clicking the image.

In this example, the size of the message to be processed is 512 bits, which is the same as the block size of SHA-256, so the compression process ends once, but if the message size is larger than 512 bits, one It is explained that the hash value calculated by compression for the previous message block is set to the first eight hash values 'a to h' and the compression process is repeated.

The 8 bit string calculated at the end is converted to hexadecimal number and concatenated in order to complete a 256-bit hash value. This process is done by 'final.rb'.

If you understand the explanation above and watch the movie again, the animation may seem more interesting.