How does a hashing algorithm work?

Hashing algorithms are an important weapon in any cryptographers toolbox. They are everywhere on the internet, mostly used to secure passwords, but also make up an integral part of most crypto currencies such as Bitcoin and Litecoin.

The main features of a hashing algorithm are that they are a one way function – or in other words you can get the output from the input but you can’t get the input from the output – just like elliptic curve cryptography where you can’t get the private key from the public key. The other property is that the same input creates the same output.

Most hashing algorithms, including the SHA and RIPEMD are all descended from the MD4 family. The MD4 hashing algorithm was developed by Ronald Rivest specifically to allow very easy software implementation. The MD4 algorithm and subsequent SHA algorithms use 32 bit variables with bitwise Boolean functions such as the logical AND, OR and XOR operators to work through from the input to the output hash.

So how does a hashing algorithm work – in this case a look at SHA1:

1 – Create five variables

H0 - 01100111010001010010001100000001
H1 - 11101111110011011010101110001001
H2 - 10011000101110101101110011111110
H3 - 00010000001100100101010001110110
H4 - 11000011110100101110000111110000

2- Then choose a word to hash. In this case we will choose the word “CRYPTO”

3- Convert the word to ASCII – “American Standard Code for Information Interchange”. Each letter has a number assigned to it.

CRYPTO – 67-82-89-80-84-79

4- Convert ASCII code to binary –

CRYPTO – 01000011-01010010-01011001-01010000-01010100-01001111

5- join characters and add 1 to the end.

CRYPTO – 0100001101010010010110010101000001010100010011111

6- Add zeros to make the message equal to 448 mod 512 – (modular arithmetic just like a clock except with 512 hours). So a 48 bit message with the added one will need to have 399 zeros added to the end, and if the message was 64 characters (or 512 bits) long you would need 447 zeros.

0100001101010010010110010101000001010100010011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

7- Add the original message length into the 64 bit field left over after the 448 modular arithmetic. The message is 48 characters long which expressed in binary is 110000. So the below is added to the end of the message in part six.

0000000000000000000000000000000000000000000000000000000000110000

8- Break the message up into sixteen sections of 32 characters/bits.

01000011010100100101100101010000
01010100010011111000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000110000

9- Transform the 16 x 32 character bit words into 80 words using a step loop function. First select four words for the first run through the loop which are strings 1,3,9 &14 from step 8.
The next time through the loop we will use words 2,4,10,15 from stage 8.
The next process is to XoR the words together. Xoring is just a basic computational function that gives the output of q only if the two inputs both have a 1 in that position – if they don’t the output is zero.

The function is ((14 XOR 9) XOR 3) XOR 1) which is:

00000000000000000000000000000000

XOR

01000011010100100101100101010000

Is

01000011010100100101100101010000

10- perform a left rotate on the numbers – i.e. move the left most digit to the right.

So

01000011010100100101100101010000

Becomes

10000110101001001011001010100000

This process is then repeated until there are 80 words, or strings of 32 bits.

10- The next step is to run a set of functions over the words in a specific order operating off the five variables that were set in step 1. The functions combine AND, OR & NOT operators combined with left shifts.

The end result is that you are left with five variables of:

H0 – 01000100101010010111000100110011
H1- 01010000111001010011100001011000
H2-11110000010110000100011000111101
H3-01001011111101111111000111100101
H4-01000010110110011100101001001011

11- Convert the H variables into hex:

H0- 44a97133
H1- 50e53858
H2- f058463d
H3 - 4bf7f1e5
H4 - 42d9ca4b

12- Join the variables together to give the hash digest:

44a9713350e53858f058463d4bf7f1e542d9ca4b

This is the basic process behind hashing – simply convert a number into binary then perform a set of simple functions that operate through basic standard transistor and bus processes such as AND, XOR, NOT, Rotate &OR. This is part of the reason that ASIC, or application specific chips can be designed that optimise hashing. In the case of SHA-256 chips have been specifically designed to optimise the iterations throughout the steps to increase the speed of creating a hash from an input. In the case of mining this means you can calculate more hashes per second by iterating through the nonce and extra nonce parameters and have a higher probability of winning the block reward.

RELATED ARTICLES:

What is the Bitcoin Transactions?
source: http://theriseofthebitcoins.blogspot.com/2016/02/what-is-bitcoin-transaction.html

How does the bitcoin network actually work?
source: http://theriseofthebitcoins.blogspot.com/2016/02/how-does-bitcoin-network-actually-work.html

Bitcoin Transactions – The Scriptsig and Scriptpubkey source: http://theriseofthebitcoins.blogspot.com/2016/02/bitcoin-transactions-scriptsig-and.html

What are the Bitcoin Transaction types?source: http://theriseofthebitcoins.blogspot.com/2016/02/what-is-bitcoins.html

The BitcoiNews Online Updates!

Tuesday 16 February 2016

How does a hashing algorithm work?

How does a hashing algorithm work?

No comments:

Post a Comment

Like & Share

Pages

Contributors