Bitcoin Forum
November 10, 2024, 06:25:02 PM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: Down to Earth explanation of SHA256?  (Read 2802 times)
Reclaim3r (OP)
Full Member
***
Offline Offline

Activity: 139
Merit: 100


View Profile
August 05, 2014, 11:43:24 PM
 #1

I know the question has been asked of how SHA256 works, but pouring over all the documentation, a lot of it seems to be extremely difficult to comprehend.
I understand how the padding and preprocessing works, but I was interested in finding a...shall I say..easier to comprehend answer.
If there isn't any, that's okay.
Relnarien
Sr. Member
****
Offline Offline

Activity: 399
Merit: 257


View Profile
August 06, 2014, 05:17:17 AM
 #2

In simplest terms, SHA256 is a hashing algorithm. Hashing is essentially changing the bits so that Message A translates easily to Message B but not the other way around. You can liken hashing to encryption in the sense that they are both aimed at securing communication between two parties, but hashing is NOT encryption. If you encrypt something, you can always get back the original message as long as you know the algorithm used. If you hash something, you will never get back the original message without cycling through a subset of all possibilities.

As for the actual algorithm used by SHA256, that's more of a technical explanation, which I'm assuming you've already read about. If not, Wikipedia lists the full algorithm, if I remember correctly.
Reclaim3r (OP)
Full Member
***
Offline Offline

Activity: 139
Merit: 100


View Profile
August 06, 2014, 06:18:46 PM
 #3

In simplest terms, SHA256 is a hashing algorithm. Hashing is essentially changing the bits so that Message A translates easily to Message B but not the other way around. You can liken hashing to encryption in the sense that they are both aimed at securing communication between two parties, but hashing is NOT encryption. If you encrypt something, you can always get back the original message as long as you know the algorithm used. If you hash something, you will never get back the original message without cycling through a subset of all possibilities.

As for the actual algorithm used by SHA256, that's more of a technical explanation, which I'm assuming you've already read about. If not, Wikipedia lists the full algorithm, if I remember correctly.

Thank you for the quick explanation  Smiley
I was actually more interested in the compression algorithm that SHA256 uses in its Merkle-Damgard construct.
From all I can tell, it just uses a bunch of Rotation operations. I'm not very good with math considering that my real age ( not the one on my profile ) is...different.
I've been trying to "distill" it into simpler terms but help would be greatly appreciated  Grin

Thanks!
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
August 06, 2014, 08:06:14 PM
Last edit: August 07, 2014, 01:03:30 AM by rarkenin
 #4

Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia in my descriptions.

In a rotation, all bits are shifted around a certain number of spaces. For example, rotating
Code:
abcdefghij
right 3 bits yields
Code:
hijabcdefg

where a,b,c,d,e,f,g,h,i,j are bits. Basically, each bit is moved over some spaces, and bits on the end are moved around to the beginning after being "shifted off".

The ">>>" symbols used in crypto to describe Σ-zero and Σ-one steps of SHA are these rotations exactly.

Simiarly, bitwise operations such as XOR exist. They handle each bit separately using the following tables:

Code:
A | B | A AND B | A OR B | A XOR B
==================================
0 | 0 |    0    |    0   |     0
0 | 1 |    0    |    1   |     1
1 | 0 |    0    |    1   |     1
1 | 1 |    1    |    1   |     0

For example, (E∧F)⊕(⌐E∧G) means:

(E AND F) XOR ((NOT E) AND G)

which means to take NOT E, AND it with G, and then XOR that with the result of ANDing E and F.

Addition modulo 2^32, shown as red boxes on the diagram on Wikipedia, means that the two inputs are added (carrying as with regular addition), just in binary. If the result overflows 32 bits, then we ignore the overflow. For example:

Code:
 *                                (see note)
 1111    1111111                  (carry)
  10110100110110111101110001011000
+ 11011010101101100000000000000001
----------------------------------
= 10001111100100011101110001011001(result)

While usually the leftmost 1 in the carry (marked with a *) would be brought down, it is considered overflow in this case and ignored, since it falls as the 33rd digit. Only 32 bits are retained, since the compression function works with 32-bit-length data. Our result is thus 10001111100100011101110001011001 and not 110001111100100011101110001011001.

As a summary, SHA-2 (SHA256 being a member of the SHA-2 family) compresses a 256-bit length of data by first splitting it into 8 blocks, and then performing the following operations (where A-H are input blocks and A' through H' are output blocks):

A'= W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+ma(A,B,C)+Σ0(A)
B' = A
C' = B
D' = C
E' = W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+D
F' = E
G' = F
H' = G

ch(E,F,G) is (E∧F)⊕(⌐E∧G)
ma(A,B,C) is (A∧B)⊕(A∧C)⊕(B∧C)
Σ0(A) is (A>>>2) ⊕ (A>>>13) ⊕ (A>>>25)
Σ1(E) is (E>>>6) ⊕ (E>>>11) ⊕ (E>>>25)

Hopefully this makes sense. If not, feel free to ask and I'll try to clarify.
Reclaim3r (OP)
Full Member
***
Offline Offline

Activity: 139
Merit: 100


View Profile
August 06, 2014, 09:15:08 PM
 #5

Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia in my descriptions.

In a rotation, all bits are shifted around a certain number of spaces. For example, rotating
Code:
abcdefghij
right 3 bits yields
Code:
hijabcdefg

where a,b,c,d,e,f,g,h,i,j are bits. Basically, each bit is moved over some spaces, and bits on the end are moved around to the beginning after being "shifted off".

The ">>>" symbols used in crypto to describe Σ-zero and Σ-one steps of SHA are these rotations exactly.

Simiarly, bitwise operations such as XOR exist. They handle each bit separately using the following tables:

Code:
A | B | A AND B | A OR B | A XOR B
==================================
0 | 0 |    0    |    0   |     0
0 | 1 |    0    |    1   |     1
1 | 0 |    0    |    1   |     1
1 | 1 |    1    |    1   |     0

For example, (E∧F)⊕(⌐E∧G) means:

(E AND F) XOR ((NOT E) AND G)

which means to take NOT E, AND it with G, and then XOR that with the result of ANDing E and F.

Addition modulo 2^32, shown as red boxes on the diagram on Wikipedia, means that the two inputs are added (carrying as with regular addition), just in binary. If the result overflows 32 bits, then we ignore the overflow. For example:

Code:
 *                                (see note)
 1111    1111111                  (carry)
  10110100110110111101110001011000
+ 11011010101101100000000000000001
----------------------------------
= 10001111100100011101110001011001(result)

While usually the leftmost 1 in the carry (marked with a *) would be brought down, it is considered overflow in this case and ignored, since it falls as the 33rd digit. Only 32 bits are retained, since the compression function works with 32-bit-length data. Our result is thus 10001111100100011101110001011001 and not 110001111100100011101110001011001.

As a summary, SHA-2 (SHA256 being a member of the SHA-2 family) compresses a 256-bit length of data by first splitting it into 8 blocks, and then performing the following operations (where A-H are input blocks and A' through H' are output blocks):

A'= W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+ma(A,B,C)+Σ0(A)
B' = A
C' = B
D' = C
E' = W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+D
F' = E
G' = F
H' = G

ch(E,F,G) is (E∧F)⊕(⌐E∧G)
ma(A,B,C) is (A∧B)⊕(A∧C)⊕(B∧C)
Σ0(A) is (A>>>2) ⊕ (A>>>13) ⊕ (A>>>25)
Σ1(E) is (E>>>6) ⊕ (E>>>11) ⊕ (E>>>25)

Hopefully this makes sense. If not, feel free to ask and I'll try to clarify.

You are a godsend  Grin!!
Thank you so much! I would have loved to give you some BTC but I'm broke as of now  Sad

I did have a few quick questions.
1.) I'm familiar with the fancy E ( Sigma, I should say ) but how exactly does it apply?
2.)What exact is the "ch" and "ma"?

I'd like to state that I'm only 14. I'm attempting to digest this. Your explanation would probably make a great deal of sense to someone with a higher understanding.
I'll make sure to save your BTC address and this post so I can donate to you when I get my hands on some moolah  Grin
So I'd also like to apologize beforehand if I seem extremely dim  Tongue
jonnybravo0311
Legendary
*
Offline Offline

Activity: 1344
Merit: 1024


Mine at Jonny's Pool


View Profile WWW
August 06, 2014, 09:28:12 PM
 #6

Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia in my descriptions.

In a rotation, all bits are shifted around a certain number of spaces. For example, rotating
Code:
abcdefghij
right 3 bits yields
Code:
hijabcdefg

where a,b,c,d,e,f,g,h,i,j are bits. Basically, each bit is moved over some spaces, and bits on the end are moved around to the beginning after being "shifted off".

The ">>>" symbols used in crypto to describe Σ-zero and Σ-one steps of SHA are these rotations exactly.

Simiarly, bitwise operations such as XOR exist. They handle each bit separately using the following tables:

Code:
A | B | A AND B | A OR B | A XOR B
==================================
0 | 0 |    0    |    0   |     0
0 | 1 |    0    |    1   |     1
1 | 0 |    0    |    1   |     1
1 | 1 |    1    |    1   |     0

For example, (E∧F)⊕(⌐E∧G) means:

(E AND F) XOR ((NOT E) AND G)

which means to take NOT E, AND it with G, and then XOR that with the result of ANDing E and F.

Addition modulo 2^32, shown as red boxes on the diagram on Wikipedia, means that the two inputs are added (carrying as with regular addition), just in binary. If the result overflows 32 bits, then we ignore the overflow. For example:

Code:
 *                                (see note)
 1111    1111111                  (carry)
  10110100110110111101110001011000
+ 11011010101101100000000000000001
----------------------------------
= 10001111100100011101110001011001(result)

While usually the leftmost 1 in the carry (marked with a *) would be brought down, it is considered overflow in this case and ignored, since it falls as the 33rd digit. Only 32 bits are retained, since the compression function works with 32-bit-length data. Our result is thus 10001111100100011101110001011001 and not 110001111100100011101110001011001.

As a summary, SHA-2 (SHA256 being a member of the SHA-2 family) compresses a 256-bit length of data by first splitting it into 8 blocks, and then performing the following operations (where A-H are input blocks and A' through H' are output blocks):

A'= W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+ma(A,B,C)+Σ0(A)
B' = A
C' = B
D' = C
E' = W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+D
F' = E
G' = F
H' = G

ch(E,F,G) is (E∧F)⊕(⌐E∧G)
ma(A,B,C) is (A∧B)⊕(A∧C)⊕(B∧C)
Σ0(A) is (A>>>2) ⊕ (A>>>13) ⊕ (A>>>25)
Σ1(E) is (E>>>6) ⊕ (E>>>11) ⊕ (E>>>25)

Hopefully this makes sense. If not, feel free to ask and I'll try to clarify.

You are a godsend  Grin!!
Thank you so much! I would have loved to give you some BTC but I'm broke as of now  Sad

I did have a few quick questions.
1.) I'm familiar with the fancy E ( Sigma, I should say ) but how exactly does it apply?
2.)What exact is the "ch" and "ma"?

I'd like to state that I'm only 14. I'm attempting to digest this. Your explanation would probably make a great deal of sense to someone with a higher understanding.
I'll make sure to save your BTC address and this post so I can donate to you when I get my hands on some moolah  Grin
So I'd also like to apologize beforehand if I seem extremely dim  Tongue
Kid, if you're following this at 14, you're doing better than 99% of the people out there.  I don't think "extremely dim" comes anywhere near the picture, never mind into it.

Jonny's Pool - Mine with us and help us grow!  Support a pool that supports Bitcoin, not a hardware manufacturer's pockets!  No SPV cheats.  No empty blocks.
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
August 06, 2014, 09:53:25 PM
 #7

You are a godsend  Grin!!
Thank you so much! I would have loved to give you some BTC but I'm broke as of now  Sad

I did have a few quick questions.
1.) I'm familiar with the fancy E ( Sigma, I should say ) but how exactly does it apply?
2.)What exact is the "ch" and "ma"?

I'd like to state that I'm only 14. I'm attempting to digest this. Your explanation would probably make a great deal of sense to someone with a higher understanding.
I'll make sure to save your BTC address and this post so I can donate to you when I get my hands on some moolah  Grin
So I'd also like to apologize beforehand if I seem extremely dim  Tongue

Sorry for the slow reply.

The sigma, ch, and ma are defined at the bottom of my first post here:

ch(E,F,G) is (E∧F)⊕(⌐E∧G)
ma(A,B,C) is (A∧B)⊕(A∧C)⊕(B∧C)
Σ0(A) is (A>>>2) ⊕ (A>>>13) ⊕ (A>>>25)
Σ1(E) is (E>>>6) ⊕ (E>>>11) ⊕ (E>>>25)

They are just fairly complex functions of some of the subblocks (for example you calculate ch by taking blocks E,F, and G and using them in the formula (E∧F)⊕(⌐E∧G). The ∧ is AND taken one bit at a time (so separate bits do not affect each other), the ⌐ is not taken one bit at a time (flip all bits, basically), and ⊕ is XOR, bit by bit, as I described it at the top of my post.

That being said, I'm extremely happy that someone around my age is interested in this, and is managing to go into such depth.
Reclaim3r (OP)
Full Member
***
Offline Offline

Activity: 139
Merit: 100


View Profile
August 06, 2014, 10:55:46 PM
 #8

You are a godsend  Grin!!
Thank you so much! I would have loved to give you some BTC but I'm broke as of now  Sad

I did have a few quick questions.
1.) I'm familiar with the fancy E ( Sigma, I should say ) but how exactly does it apply?
2.)What exact is the "ch" and "ma"?

I'd like to state that I'm only 14. I'm attempting to digest this. Your explanation would probably make a great deal of sense to someone with a higher understanding.
I'll make sure to save your BTC address and this post so I can donate to you when I get my hands on some moolah  Grin
So I'd also like to apologize beforehand if I seem extremely dim  Tongue

Sorry for the slow reply.

The sigma, ch, and ma are defined at the bottom of my first post here:

ch(E,F,G) is (E∧F)⊕(⌐E∧G)
ma(A,B,C) is (A∧B)⊕(A∧C)⊕(B∧C)
Σ0(A) is (A>>>2) ⊕ (A>>>13) ⊕ (A>>>25)
Σ1(E) is (E>>>6) ⊕ (E>>>11) ⊕ (E>>>25)

They are just fairly complex functions of some of the subblocks (for example you calculate ch by taking blocks E,F, and G and using them in the formula (E∧F)⊕(⌐E∧G). The ∧ is AND taken one bit at a time (so separate bits do not affect each other), the ⌐ is not taken one bit at a time (flip all bits, basically), and ⊕ is XOR, bit by bit, as I described it at the top of my post.

That being said, I'm extremely happy that someone around my age is interested in this, and is managing to go into such depth.

Slow? That has to be one of the fastest replies I've seen!
Ah, thank you very much for clarifying that! Makes so much sense.
You won't believe how many days of my summer vacation I've burned trying to understand how SHA256 works so thanks for the help  Grin
If you have a Bitshares account, I'd be willing to give you a few.
Reclaim3r (OP)
Full Member
***
Offline Offline

Activity: 139
Merit: 100


View Profile
August 06, 2014, 11:00:09 PM
 #9

Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia in my descriptions.

In a rotation, all bits are shifted around a certain number of spaces. For example, rotating
Code:
abcdefghij
right 3 bits yields
Code:
hijabcdefg

where a,b,c,d,e,f,g,h,i,j are bits. Basically, each bit is moved over some spaces, and bits on the end are moved around to the beginning after being "shifted off".

The ">>>" symbols used in crypto to describe Σ-zero and Σ-one steps of SHA are these rotations exactly.

Simiarly, bitwise operations such as XOR exist. They handle each bit separately using the following tables:

Code:
A | B | A AND B | A OR B | A XOR B
==================================
0 | 0 |    0    |    0   |     0
0 | 1 |    0    |    1   |     1
1 | 0 |    0    |    1   |     1
1 | 1 |    1    |    1   |     0

For example, (E∧F)⊕(⌐E∧G) means:

(E AND F) XOR ((NOT E) AND G)

which means to take NOT E, AND it with G, and then XOR that with the result of ANDing E and F.

Addition modulo 2^32, shown as red boxes on the diagram on Wikipedia, means that the two inputs are added (carrying as with regular addition), just in binary. If the result overflows 32 bits, then we ignore the overflow. For example:

Code:
 *                                (see note)
 1111    1111111                  (carry)
  10110100110110111101110001011000
+ 11011010101101100000000000000001
----------------------------------
= 10001111100100011101110001011001(result)

While usually the leftmost 1 in the carry (marked with a *) would be brought down, it is considered overflow in this case and ignored, since it falls as the 33rd digit. Only 32 bits are retained, since the compression function works with 32-bit-length data. Our result is thus 10001111100100011101110001011001 and not 110001111100100011101110001011001.

As a summary, SHA-2 (SHA256 being a member of the SHA-2 family) compresses a 256-bit length of data by first splitting it into 8 blocks, and then performing the following operations (where A-H are input blocks and A' through H' are output blocks):

A'= W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+ma(A,B,C)+Σ0(A)
B' = A
C' = B
D' = C
E' = W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+D
F' = E
G' = F
H' = G

ch(E,F,G) is (E∧F)⊕(⌐E∧G)
ma(A,B,C) is (A∧B)⊕(A∧C)⊕(B∧C)
Σ0(A) is (A>>>2) ⊕ (A>>>13) ⊕ (A>>>25)
Σ1(E) is (E>>>6) ⊕ (E>>>11) ⊕ (E>>>25)

Hopefully this makes sense. If not, feel free to ask and I'll try to clarify.

You are a godsend  Grin!!
Thank you so much! I would have loved to give you some BTC but I'm broke as of now  Sad

I did have a few quick questions.
1.) I'm familiar with the fancy E ( Sigma, I should say ) but how exactly does it apply?
2.)What exact is the "ch" and "ma"?

I'd like to state that I'm only 14. I'm attempting to digest this. Your explanation would probably make a great deal of sense to someone with a higher understanding.
I'll make sure to save your BTC address and this post so I can donate to you when I get my hands on some moolah  Grin
So I'd also like to apologize beforehand if I seem extremely dim  Tongue
Kid, if you're following this at 14, you're doing better than 99% of the people out there.  I don't think "extremely dim" comes anywhere near the picture, never mind into it.

Well, never underestimate any individuals ability to accomplish his/her goal  Wink
I'm not exactly your typical 14 year old. I don't spend my summers like most teens do.
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
August 06, 2014, 11:19:43 PM
 #10

If you're on Bitcointalk in the summer, you're like most of us here, myself included.
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
August 06, 2014, 11:34:19 PM
 #11

If you have a Bitshares account, I'd be willing to give you a few.

I don't use BitShares, but thanks for the offer!
Reclaim3r (OP)
Full Member
***
Offline Offline

Activity: 139
Merit: 100


View Profile
August 06, 2014, 11:52:38 PM
 #12

If you're on Bitcointalk in the summer, you're like most of us here, myself included.

That's good news  Smiley
Silly question, but is there anyway to just show the start of a post?
I hate being able to see all my stuff in one place, I just want the head of the topics and the ensuing posts.
Might complain about this Meta.

So, any other down to earth explanations for all the X11 algos  Cheesy ?

I might ask around, try to see if I can piece everything together.
I've wanted to make an X11 FPGA and if it successfully outperforms a GPU miner, maybe gain some basic capital for batch samples and some more for the final thing.
But that's a LONG way off. I still have to learn Verilog/VHDL!
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
August 07, 2014, 12:09:40 AM
 #13

X11/X13 are basically combinations of other hash algorithms (blake, bmw, groestl, jh, keccak, skein, luffa, cubehash, shavite, simd, echo). It would take a much larger bitstream, much larger netlist, and more blocks/gates/macrocells than SHA-256, and possibly not fit (especially at place-and-route) into small and medium-sized FPGAs. What model are you targeting with X11?

Edit: I'm not sure there's functionality to see parts of posts, but you can see a list of topics that you've posted in, that have new replies at the updated topics page.

Edit 2: In terms of FPGAs, you'll be happy to know that there's support for all of the basic functions performed within an FPGA, at a schematic/logic, or a VHDL level. Shifts and rotations are simply cross-connecting of wires in a diagonal stripe pattern, addition modulo 2^32 is done with 1 half adder, and 32 full adders, of which the top one discards its carry out. And/or/xor/not are simply on-silicon gates that are made available to you. You could try optimizations such as (in some cases) boolean algebra might reduce the number of gates by letting you combine some operations on some lines. Also, knowing the compression function (for SHA-2 at least), you can also not waste buffers on shifting blocks B,C,D,F,G,H around, as they'll get shifted a few times before being used in functions.
Reclaim3r (OP)
Full Member
***
Offline Offline

Activity: 139
Merit: 100


View Profile
August 07, 2014, 12:24:56 AM
 #14

X11/X13 are basically combinations of other hash algorithms (blake, bmw, groestl, jh, keccak, skein, luffa, cubehash, shavite, simd, echo). It would take a much larger bitstream, much larger netlist, and more blocks/gates/macrocells than SHA-256, and possibly not fit (especially at place-and-route) into small and medium-sized FPGAs. What model are you targeting with X11?

Edit: I'm not sure there's functionality to see parts of posts, but you can see a list of topics that you've posted in, that have new replies at the updated topics page.

Edit 2: In terms of FPGAs, you'll be happy to know that there's support for all of the basic functions performed within an FPGA, at a schematic/logic, or a VHDL level. Shifts and rotations are simply cross-connecting of wires in a diagonal stripe pattern, addition modulo 2^32 is done with 1 half adder, and 32 full adders, of which the top one discards its carry out. And/or/xor/not are simply on-silicon gates that are made available to you. You could try optimizations such as (in some cases) boolean algebra might reduce the number of gates by letting you combine some operations on some lines. Also, knowing the compression function (for SHA-2 at least), you can also not waste buffers on shifting blocks B,C,D,F,G,H around, as they'll get shifted a few times before being used in functions.

I remember seeing a post somewhere on the Darkcoin forums where they were collaborating to find a way but the performance just wasn't worth it. I'll try and dig around. I hope you don't mind if I PM you the rest of the details ( unless you prefer to post it all here ).

Thanks for the optimization and FPGA tips! I'm still trying to finish learning C coding before my Dad's gonna get me my own FPGA. But afterwards, I can probably convince him to get me one of the more high-end FPGA's.
BCFrictionless
Member
**
Offline Offline

Activity: 87
Merit: 10


View Profile
August 07, 2014, 12:45:06 AM
 #15

This is an interesting read here  Smiley
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
August 07, 2014, 12:54:40 AM
 #16

I remember seeing a post somewhere on the Darkcoin forums where they were collaborating to find a way but the performance just wasn't worth it. I'll try and dig around. I hope you don't mind if I PM you the rest of the details ( unless you prefer to post it all here ).

Thanks for the optimization and FPGA tips! I'm still trying to finish learning C coding before my Dad's gonna get me my own FPGA. But afterwards, I can probably convince him to get me one of the more high-end FPGA's.

Of course, PM is welcome at any time. I have access to about 15 lower-end Spartan 3e FPGAs occasionally, as well as one at home, so I could do testing of at least single algos from X11.
wolfYella
Newbie
*
Offline Offline

Activity: 48
Merit: 0


View Profile
August 07, 2014, 01:28:20 AM
 #17

Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia in my descriptions.

In a rotation, all bits are shifted around a certain number of spaces. For example, rotating
Code:
abcdefghij
right 3 bits yields
Code:
hijabcdefg

where a,b,c,d,e,f,g,h,i,j are bits. Basically, each bit is moved over some spaces, and bits on the end are moved around to the beginning after being "shifted off".

The ">>>" symbols used in crypto to describe Σ-zero and Σ-one steps of SHA are these rotations exactly.

Simiarly, bitwise operations such as XOR exist. They handle each bit separately using the following tables:

Code:
A | B | A AND B | A OR B | A XOR B
==================================
0 | 0 |    0    |    0   |     0
0 | 1 |    0    |    1   |     1
1 | 0 |    0    |    1   |     1
1 | 1 |    1    |    1   |     0

For example, (E∧F)⊕(⌐E∧G) means:

(E AND F) XOR ((NOT E) AND G)

which means to take NOT E, AND it with G, and then XOR that with the result of ANDing E and F.

Addition modulo 2^32, shown as red boxes on the diagram on Wikipedia, means that the two inputs are added (carrying as with regular addition), just in binary. If the result overflows 32 bits, then we ignore the overflow. For example:

Code:
 *                                (see note)
 1111    1111111                  (carry)
  10110100110110111101110001011000
+ 11011010101101100000000000000001
----------------------------------
= 10001111100100011101110001011001(result)

While usually the leftmost 1 in the carry (marked with a *) would be brought down, it is considered overflow in this case and ignored, since it falls as the 33rd digit. Only 32 bits are retained, since the compression function works with 32-bit-length data. Our result is thus 10001111100100011101110001011001 and not 110001111100100011101110001011001.

As a summary, SHA-2 (SHA256 being a member of the SHA-2 family) compresses a 256-bit length of data by first splitting it into 8 blocks, and then performing the following operations (where A-H are input blocks and A' through H' are output blocks):

A'= W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+ma(A,B,C)+Σ0(A)
B' = A
C' = B
D' = C
E' = W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+D
F' = E
G' = F
H' = G

ch(E,F,G) is (E∧F)⊕(⌐E∧G)
ma(A,B,C) is (A∧B)⊕(A∧C)⊕(B∧C)
Σ0(A) is (A>>>2) ⊕ (A>>>13) ⊕ (A>>>25)
Σ1(E) is (E>>>6) ⊕ (E>>>11) ⊕ (E>>>25)

Hopefully this makes sense. If not, feel free to ask and I'll try to clarify.

You are a godsend  Grin!!
Thank you so much! I would have loved to give you some BTC but I'm broke as of now  Sad

I did have a few quick questions.
1.) I'm familiar with the fancy E ( Sigma, I should say ) but how exactly does it apply?
2.)What exact is the "ch" and "ma"?

I'd like to state that I'm only 14. I'm attempting to digest this. Your explanation would probably make a great deal of sense to someone with a higher understanding.
I'll make sure to save your BTC address and this post so I can donate to you when I get my hands on some moolah  Grin
So I'd also like to apologize beforehand if I seem extremely dim  Tongue
Kid, if you're following this at 14, you're doing better than 99% of the people out there.  I don't think "extremely dim" comes anywhere near the picture, never mind into it.
There are probably people with advanced degrees that would not be able to follow this explanation.
Dabs
Legendary
*
Offline Offline

Activity: 3416
Merit: 1912


The Concierge of Crypto


View Profile
August 08, 2014, 02:36:39 PM
 #18

Here's my "down to earth" explanation:

SHA256 is a way of turning a really long message and DIGESTING it so it comes out much shorter. This process is one way.

In other words, you can get the SHA256 of a very long email message, and compress it to 32 bytes (or 64 hexadecimal characters) that will not change.

As a simplified example, if I use this formula: 3 + 5 + 1 = 9. But if you just say 9, how do you know what the original formula was? Was it 2 + 4 + 3?

SHA256 is also considered "cryptographically secure" unlike other hash methods such as your credit card number check digit, or even CRC32.

For every exact message, there is only one SHA256 digest possible. For all practical purposes, for every SHA256 result you see published, there is only one real original message. Theoretically there are an infinite number of messages (known as collisions) that can result in that particular SHA256 result, but the odds make it unlikely.

Cubic Earth
Legendary
*
Offline Offline

Activity: 1176
Merit: 1020



View Profile
August 09, 2014, 05:21:35 PM
 #19

SHA256 = A deterministic food processor
YarkoL
Legendary
*
Offline Offline

Activity: 996
Merit: 1013


View Profile
August 10, 2014, 08:51:16 PM
 #20


As a summary, SHA-2 (SHA256 being a member of the SHA-2 family) compresses a 256-bit length of data by first splitting it into 8 blocks, and then performing the following operations (where A-H are input blocks and A' through H' are output blocks):

A'= W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+ma(A,B,C)+Σ0(A)
B' = A
C' = B
D' = C
E' = W(t)+K(t)+H+ch(E,F,G)+Σ1(E)+D
F' = E
G' = F
H' = G

ch(E,F,G) is (E∧F)⊕(⌐E∧G)
ma(A,B,C) is (A∧B)⊕(A∧C)⊕(B∧C)
Σ0(A) is (A>>>2) ⊕ (A>>>13) ⊕ (A>>>25)
Σ1(E) is (E>>>6) ⊕ (E>>>11) ⊕ (E>>>25)

Hopefully this makes sense. If not, feel free to ask and I'll try to clarify.

Can you give also a dumbed-down explanation of W(t) and K(t) for me?
I looked at the wiki article, and there it says that they have something
to do with a "message schedule" but I didn't get what it means.

“God does not play dice"
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!