Topic: Down to Earth explanation of SHA256? (Read 2800 times)

To be honest, I have no idea why it is a secure hash algorithm. I just know what is done to calculate a hash.

Thank you for the great, accessible dissection.
Now the next step is to understand why it is put together
like that... I suppose that the governing principle in the
arrangement of these operations is to enable the trapdoor property:
easy to verify,
hard to invert.

k is just a constant array that is defined as the first 32 bits of the fractional parts of the cube roots of the first 64 primes from 2 to 311:


W is dynamically modified as follows:

1) W starts as an array or 64 32-bit words. Each chunk is copied into the first 16 words of this array. The rest of it doesn't matter, as it will get filled in the next step.
2) Elements 0-15 of w are filled. Let's fill in elements 16-63:
2a) Let's say we're filling in the i-th element. We calculate s0 as 2b) We calculate s1 as 2c) We set the i-th element to be
>>> is a right rotation (elements pushed off the right are reinserted at the left)
>> is a right shift (no reinsertion at the left)

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.

SHA256 = A deterministic food processor

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.

There are probably people with advanced degrees that would not be able to follow this explanation.

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.

This is an interesting read here 

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.

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.

That's good news  
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   ?

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!

I don't use BitShares, but thanks for the offer!

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

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

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 
If you have a Bitshares account, I'd be willing to give you a few.

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.

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.

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

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 
So I'd also like to apologize beforehand if I seem extremely dim 

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
right 3 bits yields

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:


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:


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.