How does the SHA256 algorithm work…in detail? (part 1/2)

SHA-256 (Secure Hash Algorithm) is the name of a “cryptographic hash function”. SHA-256 is part of an , with the same goal: to create a hash that is resistant to collisions, the calculation of which only works in one direction and has a fixed length. In the following article, I describe the steps the algorithm takes to create a hash.

In the first part we take care of the preparations, in the second part it goes to the actual algorithm. The source code is on Github.

What will you learn?

In addition to creating a SHA-256, you will be familiar with the handling of binary numbers and binary arithmetic operations such as XOR, AND, etc. However, I assume that there is a basic understanding of binary numbers, the focus is on the algorithm. 10 should stand in your head either for the ten or one two. (Or also twelve, if you like the duo decimal system.)

Foreword

If you lower this to a maximum amateur description, the following happens with a crytological hash function: An output text of any length is processed in such a way that a result text (the hash) with the same length is always created. It is almost impossible to calculate the output text from the hash. In addition, you can almost certainly assume that each output text creates a different hash. If I change only one character, it affects the original text drastically. Such an algorithm is therefore predestined to be attached to texts, i.e. messages. This is why we also speak of a checksum.

And that is the foundation of a technology that is making more and more talks in the recent past: the blockchain, the basis for cryptocurrencies such as Bitcoin. With the blockchain, and even that only amateurly broken down, the entries of the “cash book” are securely against manipulation, because the change of a historical value (e.g. booking process) would inevitably result in a drastic change in the checksums generated from it. To take the blockchain apologist out of the wind out of the sails, I quote Fefe, meaning: It is also easier. I use Bitcoin here only as a buzzword, for marketing reasons. :]

But to motivate you to read on, an important note:

The algorithm is used to calculate the next records of the blockchain. Strictly speaking, a certain hash is setting, which is to be calculated (the notorious mining). The reward for the correct calculation is Bitcoins. The problem: This calculation is very, very complex, because as already written above: it only works in one direction. The miners therefore have to make unspeakable many calculations in order to calculate a target value. And the miner who carries out the calculation the fastest is also rewarded for it. So if you’re looking forward to optimizing the algorithm, you can get out big in the mining business. That sounds like a challenge, doesn’t it? ;)

Source: https://peakd.com/german/-marcus0alameda/dagobert-gold-bitcoin-perfect assembly

Disclaimer: I have recreated the whole algorithm in Python. Python is certainly not the best option to calculate SHA-256 from performance view and dealing with binary or hexadecimal values is somewhat uncomfortable. Thanks to Jupyter, Python is most likely to describe a complex algorithm step-by-step.

Introduction

Before we get involved with the loops, we need to take care of a few functions that we will use later to mix through binary numbers a little.

In the following, I renounce the prefixes of the number system, such as 0b binary, to keep the text clear. I assume that the following is known: 0 -> False and 1

Note 2: In the context of SHA-256, one word (dual word) corresponds to exactly 32 bits. In general, 1 Word corresponds to 2 bytes of 16 bits.

The Explicit Or (XOR)

The explicit mean or (either-or) is an elementary logical, bitwise operator. The outcome of the operation is only true if exactly a state is true (in comparison, the result of the “simple” OR is true, by the way, if at least one operand is true or both).

So two values are processed as follows:

XOR: only if exactly one value is true (1), the corresponding position is true in the result (1)

The implementation in Python is done with the circumflex :

110 to 100
010

The logical and (AND)

The AND operator is also quite common and comparatively simple. Analogous to XOR, the result is true when exactly both (or all) operands are true.

AND: Only if both values of a single area are true, the passage is true in the result

The implementation in Python is done with the commercial and :

110 & 100
100

The Negation (Nope?)

Now it becomes strange: There is also an operator for this: The bitwise operator negation revolves values around. 0 becomes 1, from 1 will be 0.

The negation reverses values bitwise. No more but no longer not less.

The implementation in Python is done with the tilde à my favourite character!

110
001

The Shift Operation

The shift function is an elementary binary computing operation in which the individual places of a binary value are moved to the left or right. The vacancies on the other side will be filled with 0.

Shift to the left around a place, from 6 to 12

And now there is hopefully a positive kink in the learning curve: If you look closely, you will not notice something and let me assure you, it’s not a coincidence: 12 is the product of 6 and 2. This indicates an interesting side effect: A shift comes to a multiplication or. Division with 2 equal. A shift around several digits corresponds to a multiplication with a potency to the base 2 exists. Sounds complicated, therefore an example:

Instead of 139 * 2, you can shift the binary representation of 139, so 10001011, to 17 digits to the left. The result: 1000101100000000000000000. Count after, right of 1 one there are now 17 zeros.

In Python, the binary shift with the double arrow is implemented:

110 >> 1 
011110 to 2
€ 000

The Rotate function

Rotate means that one shifts the values of a (binary) number in one direction. And this is best explained by an example. The following number series should be rotated by one counter to the left. The number on the left side falls out and we turned on the right. The other numbers move one position to the left.

Rotate of a binary value by one place to the left, from 6will 5

This works in both directions and with any number of places. The corresponding function (Kudos an action looks like this):

def rotate(value, rotations, width à 32):    
if int(rotations) ! ! abs(int(rotations):        
rotations à width + int(rotations)    
return (int(value) - (width - (rotations%width)) | (int(value) >> (rotations % width))) & ((1 Ã width) - 1)

The Sigma Functions

A total of four so-called Sigma functions are used. 0 and 1 (the small sigma) respectively. (Σ1the large sigma, many known as the sum character). All functions are called with a binary value and return this binary value in a modified form.

(sigma0) is as follows:

• the initial value is rotated by 7 digits to
• the initial value is rotated by 18 digits to
• the initial value is shifted by 3 digits to the right

This results in three different values, which are linked to each other. The function for this in Python:

def sigma0(word):    
part1 Ã bin(rotate(int(word, 2), 7, 32))    
part2 Ã bin(rotate(int(word, 2), 18, 32))    
part3 - bin(int(word, 2) >> 3)    
return bin(int(part1, 2) Ã int(part2, 2) Ã int(part3, 2))[2:].zfill(32)

Important mote : I work with bin() and in(s, 2), to make the output and input legible and above all comprehensible. I also ensure that the binary representation does not need 0b. This benefits the purpose of learning, since the binary operations on decimal values are more difficult to understand. With zfill(32) (zero fill) the binary value to the left is expanded by so many zeros to always comprise 32 digits. In some cases, this facilitates the overview, on the other hand, this also meets a length specification later. The upper function can also be simplified as follows:

def rotate(value, rotations, width = 32):
    if int(rotations) != abs(int(rotations)):
        rotations = width + int(rotations)
    return (int(value) << (width - (rotations%width)) | (int(value) >> (rotations % width))) & ((1 << width) - 1)

It looks very similar to Ã1 (sigma1):

• the initial value is rotated by 17 digits to the right
• the initial value is rotated by 19 digits to the right
• the initial value is shifted by 10 digits to the right

This results in three different values, which are linked to each other. The function for this in Python:

def sigma0(word):
    part1 = bin(rotate(int(word, 2), 7, 32))
    part2 = bin(rotate(int(word, 2), 18, 32))
    part3 = bin(int(word, 2) >> 3)
    return bin(int(part1, 2) ^ int(part2, 2) ^ int(part3, 2))[2:].zfill(32)

Now to Ã0 (Sigma0). Here too, no great overshoots, here now without shift:

• the initial value is rotated by 2 digits to the right
• the initial value is rotated by 13 digits to the right
• the initial value is rotated by 22 digits to the right

Here, too, the respective results are final XOR. So in Python:

def upper_sigma0(word):
    part1 = bin(rotate(int(word, 2), 2, 32))
    part2 = bin(rotate(int(word, 2), 13, 32))
    part3 = bin(rotate(int(word, 2), 22, 32))
    return bin(int(part1, 2) ^ int(part2, 2) ^ int(part3, 2))[2:].zfill(32)

Let’s come to the last participant in our illustrious Greek round: Ã1 (Sigma1Sigma1):

• the initial value is rotated by 6 digits to the right
• the initial value is rotated by 11 points to the right
• the initial value is rotated by 25 digits to the right

And in the end the XOR link again. Python:

def upper_sigma1(word):
    part1 = bin(rotate(int(word, 2), 6, 32))
    part2 = bin(rotate(int(word, 2), 11, 32))
    part3 = bin(rotate(int(word, 2), 25, 32))
    return bin(int(part1, 2) ^ int(part2, 2) ^ int(part3, 2))[2:].zfill(32)

Election and majority

Let us stay with the Greeks and switch to politics: The election and the majority, English: choose and majority.

Choose is a slightly more complex function that processes three binary values, bitwise. The function goes through the respective digits (x) of the first input value and checks:

• If x 1 then take y
• If x 0 then take z

Y and z stand for the respective positions of the second and third input values. How can this be solved programmatically? So:

def choose(word1, word2, word3):
    bin_word1 = (int(word1, 2))
    bin_word2 = (int(word2, 2))
    bin_word3 = (int(word3, 2))
    return bin((bin_word1 & bin_word2) ^ (~bin_word1 & bin_word3))[2:].zfill(32)

First, value 1 and value 2 are logically linked AND-linked. Then the negation of value 1 is linked to a value of 3 AND-. The two subtotals are finally hunted by XOR.

Majority simply checks for each location of the three input values, which is more common, 1 or 0. This looks like this in Python — here I can’t explain the logical operations again, it’s simply linked XOR and AND:

def majority(word1, word2, word3):
    bin_word1 = (int(word1, 2))
    bin_word2 = (int(word2, 2))
    bin_word3 = (int(word3, 2))
    return bin((bin_word1 & bin_word2) ^ (bin_word1 & bin_word3) ^ (bin_word2 & bin_word3))[2:].zfill(32)

Prime numbers?

To cover another popular field of arithmetic, let us talk about prime numbers briefly. Prime numbers are mystical. And thus just right for our earthly plan to optimize mining.

SHA-256 uses prime numbers as the basis for the algorithm. Which does not mean that the result would be transparent.

We start with the first 64 prime numbers and build a set of constants from it. Of course in bit form.

[2, 3, 5, 7, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 71, 71, 79, 83, 89, 97, 101, 103, 107, 107, 109, 127, 131, 137, 139, 149, 151, 157, 163, 163, 173, 179, 181, 191, 191, 191, 191, 197, 211, 191, 199257, 263, 269, 271, 277, 281, 283, 293, 307, 311]

But these are now also properly taken by the lack. I cannot understand why this is necessary. From my point of view, it does not matter what constants one are used, since they are always the same (which is why constant, this time from the Latin one). So there is no big secret about that.

The third root is drawn from the 64 prime numbers. Then the natural part is removed (proach everything before the decimal point) and the result is multiplied by 232 (aka 4,294,996,296, which by the way also corresponds to the number of available IPv4 addresses — the 2nd positive buckling in today’s learning curve?). As you have learned above and hopefully not forgotten yet, the multiplication with 2'32 is not really so complex in the bitu universe.

In any case, the result is rounded off to a natural number, i.e. all decimal places removed. If you repeat this for the remaining 63 prime numbers, you get a well-formed list of 64 entries, which look something like this, using the example of the notorious prime number 2:

010000101000100010111110011000

Or as a hex value:

0x428a2f98

And in the decimal number system:

1.116.352.408

The function for this is as follows:

result_constants = []
for prime_number in first_64_prime_numbers:
    cube_root = prime_number ** (1./3.)
    frac_part = cube_root - floor(cube_root)
    product = frac_part * (2**32)
    floored_product = floor(product)
    result_constants.append(bin(floored_product)[2:].zfill(32))

This is what we call result constant, because this list is the beginning of our final output. We pick up this list well and because the work with prime numbers is so liberating, we are organizing a similar circus for the first 8 prime numbers. With one difference: This time the square root serves as the basis:

compression_constants = []
for prime_number in first_8_prime_numbers:
    square_root = prime_number ** (1./2.)
    frac_part = square_root - floor(square_root)
    product = frac_part * (2**32)
    floored_product = floor(product)
    compression_constants.append(bin(floored_product)[2:].zfill(32))

By the way, the names have a meaning, which I later add.

Epilog

The preparations are thus completed and we can devote ourselves to the actual algorithm in the second part.