|
Title: Down to Earth explanation of SHA256? Post by: Reclaim3r on August 05, 2014, 11:43:24 PM 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. Title: Re: Down to Earth explanation of SHA256? Post by: Relnarien on August 06, 2014, 05:17:17 AM 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. Title: Re: Down to Earth explanation of SHA256? Post by: Reclaim3r on August 06, 2014, 06:18:46 PM 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 :) 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 ;D Thanks! Title: Re: Down to Earth explanation of SHA256? Post by: rarkenin on August 06, 2014, 08:06:14 PM Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia (http://en.wikipedia.org/wiki/SHA-2#Hash_standard) in my descriptions.
In a rotation, all bits are shifted around a certain number of spaces. For example, rotating Code: abcdefghij 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 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) 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. Title: Re: Down to Earth explanation of SHA256? Post by: Reclaim3r on August 06, 2014, 09:15:08 PM Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia (http://en.wikipedia.org/wiki/SHA-2#Hash_standard) in my descriptions. In a rotation, all bits are shifted around a certain number of spaces. For example, rotating Code: abcdefghij 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 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) 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 ;D!! 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 ;D So I'd also like to apologize beforehand if I seem extremely dim :P Title: Re: Down to Earth explanation of SHA256? Post by: jonnybravo0311 on August 06, 2014, 09:28:12 PM Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia (http://en.wikipedia.org/wiki/SHA-2#Hash_standard) in my descriptions. In a rotation, all bits are shifted around a certain number of spaces. For example, rotating Code: abcdefghij 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 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) 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 ;D!! 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 ;D So I'd also like to apologize beforehand if I seem extremely dim :P Title: Re: Down to Earth explanation of SHA256? Post by: rarkenin on August 06, 2014, 09:53:25 PM You are a godsend ;D!! 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 ;D So I'd also like to apologize beforehand if I seem extremely dim :P 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. Title: Re: Down to Earth explanation of SHA256? Post by: Reclaim3r on August 06, 2014, 10:55:46 PM You are a godsend ;D!! 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 ;D So I'd also like to apologize beforehand if I seem extremely dim :P 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 ;D If you have a Bitshares account, I'd be willing to give you a few. Title: Re: Down to Earth explanation of SHA256? Post by: Reclaim3r on August 06, 2014, 11:00:09 PM Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia (http://en.wikipedia.org/wiki/SHA-2#Hash_standard) in my descriptions. In a rotation, all bits are shifted around a certain number of spaces. For example, rotating Code: abcdefghij 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 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) 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 ;D!! 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 ;D So I'd also like to apologize beforehand if I seem extremely dim :P 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. Title: Re: Down to Earth explanation of SHA256? Post by: rarkenin on August 06, 2014, 11:19:43 PM If you're on Bitcointalk in the summer, you're like most of us here, myself included.
Title: Re: Down to Earth explanation of SHA256? Post by: rarkenin on August 06, 2014, 11:34:19 PM 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! Title: Re: Down to Earth explanation of SHA256? Post by: Reclaim3r on August 06, 2014, 11:52:38 PM If you're on Bitcointalk in the summer, you're like most of us here, myself included. 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 :D ? 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! Title: Re: Down to Earth explanation of SHA256? Post by: rarkenin on August 07, 2014, 12:09:40 AM 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 (https://bitcointalk.org/index.php?action=unreadreplies). 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. Title: Re: Down to Earth explanation of SHA256? Post by: Reclaim3r on August 07, 2014, 12:24:56 AM 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 (https://bitcointalk.org/index.php?action=unreadreplies). 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. Title: Re: Down to Earth explanation of SHA256? Post by: BCFrictionless on August 07, 2014, 12:45:06 AM This is an interesting read here :)
Title: Re: Down to Earth explanation of SHA256? Post by: rarkenin on August 07, 2014, 12:54:40 AM 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. Title: Re: Down to Earth explanation of SHA256? Post by: wolfYella on August 07, 2014, 01:28:20 AM Most operations in SHA-256 are bitwise operations--xor, rotation, etc. I'll be referencing Wikipedia (http://en.wikipedia.org/wiki/SHA-2#Hash_standard) in my descriptions. In a rotation, all bits are shifted around a certain number of spaces. For example, rotating Code: abcdefghij 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 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) 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 ;D!! 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 ;D So I'd also like to apologize beforehand if I seem extremely dim :P Title: Re: Down to Earth explanation of SHA256? Post by: Dabs on August 08, 2014, 02:36:39 PM 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. Title: Re: Down to Earth explanation of SHA256? Post by: Cubic Earth on August 09, 2014, 05:21:35 PM SHA256 = A deterministic food processor
Title: Re: Down to Earth explanation of SHA256? Post by: YarkoL on August 10, 2014, 08:51:16 PM 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. Title: Re: Down to Earth explanation of SHA256? Post by: rarkenin on August 10, 2014, 09:04:43 PM 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:
Code: 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 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 Code: (w[i-15]>>>7) xor (w[i-15]>>>18) xor (w[i-15] >>3) Code: (w[i-2]>>>17) xor (w[i-2]>>>19) xor (w[i-2]>>10) Code: w[i-16] + s0 + w[i-7] + s1 >>> is a right rotation (elements pushed off the right are reinserted at the left) >> is a right shift (no reinsertion at the left) Title: Re: Down to Earth explanation of SHA256? Post by: YarkoL on August 11, 2014, 11:32:43 AM 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. Title: Re: Down to Earth explanation of SHA256? Post by: rarkenin on August 11, 2014, 05:24:56 PM To be honest, I have no idea why it is a secure hash algorithm. I just know what is done to calculate a hash.
|