Bits, Binary, and Hexadecimal
Computers process data in binary (0s and 1’s). Each 0 or 1 is called a ‘bit.’ Final SHA-256 hashes are made up of 256 bits. However, instead of 0s and 1s, hashes are typically written in hexadecimal form to save space. Each Hex number represents 4 binary digits.
Though it may look tedious, using binary instead of hexadecimal is key to understanding how SHA-256 works without hand waving away details. To make things look a bit nicer, binary is typically represented using black and white instead of 1 and 0 respectively.
Bit Math – Binary Addition
Bit math is a lot easier than it sounds. As you are only dealing with 0s and 1s, figuring 1+1 is trivial! It’s 10! =P
Let’s get into it. =)
These represent 0100 and 0101 respectively. Addition for binary works just the same as for regular numbers, the only difference is when you ‘carry over’. In normal numbers, you carry over the 1 when you add 1+9. The same thing happens with Binary except you start carrying over at 2 (adding 2 black squares) instead of at 10.
SHA-256 uses something called ‘modular math’. This is a high-level math concept that is remarkably simple in binary form. Addition ‘mod 24’ means that you do normal addition, but only care about the last 4 bits (full scale SHA-256 worries about the last 32).
It doesn’t matter if you add together two 32 bit long chains. We only ever care about the last 4.
Bit Logic – Basic Functions
There are 5 concepts of digital logic that go into SHA-256. They are: AND, XOR, NOT, Shift and Circular Shift. An AND function results in a 1 only if both inputs are a 1, a XOR results in a 1 only if both inputs are different, a NOT reverses all the bits, and Shifts… well… shift.
Shifts move all the bits to the right (the last bit is dropped) and add 0 bit to the front. A Circular Shift also moves the bits to the right, but the last bit is moved to the front instead of being dropped.