[0:00]We are going to take the name of this YouTube channel, RedBlockBlue, as our input, pass it through the SHA-256 algorithm and give you the step-by-step process of how to get the 256-bit output. So first of all, we use ASCII to convert our input into pure binary form, because after all that is the only language that the computer understands. Capital R is matched to this 8-bit number, E to this 8-bit number, and D to this 8-bit number, and you get the idea. So we do that for each of the 12 characters in our input, and then we can just concatenate them all into one long 96-bit input. And we could write this as this long big string of zeros and ones, but we're going to tidy things up and order things in this way. So we have each row is 32 bits. Before we get to the calculation part, we'll have to do some preprocessing. So the purpose of why we're doing this is because we need the input to be a multiple of 512, and at the moment, it is of length 96. So we round up to the nearest multiple of 512. So in our case, we're going to just round up to 512, but if our input was 960, we would round up to 1024. So, the first thing we're going to do is we're going to append a single 1-bit to our input, that'll take us up to 97 bits. And then we're going to just keep adding 0 bits until we get 64 bits away from the nearest multiple of 512, so in our case, that's going to be 448. And the last 64 bits, which we have left, this is going to be used to encode the original length of our input, that is 96, into its 64-bit binary representation. And after we have done all this, our padded input will have a bit length that is a multiple of 512. So here is our original input, which is 96 bits. We add a singular 1-bit and keep adding zeros until we get to 448 bits. Now, the remaining 64 bits are used to represent the original length of the input, which was 96. And 96 written as a binary number is 1100000. Because we're using 64 bits to represent this, we have a load of zeros at the beginning. And then we have 1100000. So now we have our padded input of 512 bits. The next thing we do is split our padded input into 512-bit blocks. But because our padded input is only 512 bits, then we only have one block. So in our case, this capital N here is just equal to 1. So this is extremely simple. And so all we have to do now is split the 512-bit block input into 16 32-bit words. And luckily, we've already organized our bits into this format where we have each row representing 32 bits. So we can just label each row M0 to M15, and these are our 16 32-bit words.
[2:58]So here we're going to be setting some initial what they call hash values. And so what are these? Well, there are eight of them, and they're 32 bits each, giving 256 bits in total. So we're going to initialize these, and then we're going to do some stuff to them, and then we're going to end up merging them, and then that will be our 256-bit output. So where do these numbers come from? Well, we take the first 32 bits of the fractional parts of the square roots of the first eight prime numbers. And you may be thinking, why on Earth are we doing this? This is just to ensure that these are indeed random and there are no back doors into this algorithm. If you want to know what I mean by back door, then here is a video that I highly recommend watching. So the first prime number is two, and when we take its square root, we get something which looks a bit like this. And now what we're going to do is take the fractional part of that, and convert it into binary. Now let's get rid of the zero and the decimal point. And let's convert these zeros and ones into its hexadecimal format. And as you can see, we get H0. To get the other Hs, we just do the same thing with the other seven prime numbers. Some other constants we need to be aware of is K0 to K63. Now, these are derived by taking the first 32 bits of the fractional parts of the cube roots of the first 64 prime numbers. Which is a mouthful, to say the least. And I'm not going to go through how to derive them because it's the same as what we just did with the square root of 2, but here is all you need to know. Here is K0, for example. Here is K7, and here is K62. Now, we move on to the computational steps. So here we have a for loop. But as I've said, because this capital N for us is one, because our padded input is only of length 512. We only do one iteration through this for loop. So we have to prepare something called a message schedule, which is these WT things from W0 to W63. Now, each of these are 32 bits in length. The first 16 of which are just equal to M0 to M15. And then W16 up until W63 is given iteratively by this formula. This would be pretty easy to understand, except we don't know what these mean. So what is sigma0 and sigma1? Well, here it's defined but it looks very, very, very messy. So let's give a quick and easy example. Let's take a 32-bit input, let's call it X. First do a right rotation of 7 of X, which basically means we get each bit and we just move it over 7 bits. So this bit here, where the red arrow is pointing, gets moved to here, where the blue arrow is pointing. And we do the same for each and every bit, but these last seven bits. They have nowhere to go and so we loop them back around. And after we do that, we get this number. Now we do the same, we get a right rotation of 18 of X, and we get this number. And finally, we get to something called a right shift of 3, where we do the exact same as we have just done, but instead of looping those numbers around, we just set all of these to zero. So you can think of them as being pushed off a cliff or something, or however you want to think of it. And so the output of sigma0 of X is given as this. We have these three numbers, and we do bit-wise addition modulo 2. So to get the rightmost bit, we do 1 + 1 + 0, which is 2, which is 0 mod 2. The second is 0 + 1 + 0, which is 1, which is 1 mod 2, and we do the same over and over again, and we end up with this number. Sigma1 is the exact same, pretty much, but we do a right rotation of 17, followed by a right rotation of 19, followed by a right shift of 10. Then we do bit-wise addition modulo 2, and we get the output of sigma1. So back to where we were. Now let's take a concrete example and shove T = 16 into here. We have W16 = sigma1(W14) + W9 + sigma0(W1) + W0. W14 is just all zeros. W9 lives somewhere up here, which is all zeros. W1 is this thing, so we'll put that there, and W0 is this thing, so we'll put that by there. Sigma1 of all zeros. So, if you do a right rotation of 17, and then do a right rotation of 19, and then do a right shift of 10, and then add these bit-wise modulo 2, we not surprisingly get all zeros. And so we add to that another load of all zeros. And then we have sigma0 of something that's not all zeros, which is more interesting. So, we take a right rotation of 7, we take a right rotation of 18, and we take a right shift of 3, and we have these three numbers, and then we do bit-wise addition modulo 2, and this is our final output. So we'll put that here in orange. And then we just have this N here as well. What we're going to do now is addition modulo 2 to the 32. And the reason we're doing this modulo 2 to the 32 is to ensure that W16 here is 32 bits in length. So the first two terms are zero, so we can just ignore them. And if we add these two 32 bits on the right here, modulo 2 to 32, then we end up with this. And that is our W16. So let's put that up here with the rest of them. And I'm not going to go through W17 up to 63, but they are given in the exact same way iteratively using this formula. So this is all within the same for loop, remember. And so the next step, we initialize A through to H as H0 through to H7. Which sounds a bit messy here right now, but it will all make sense very, very shortly. We don't need these superscripts, as I've mentioned a couple of times already that our capital N is 1 and so we're not going to be looping through this for loop more than once. These were the values we had earlier for our Hs, and this is in hexadecimal format, so we'll convert all of them into binary so we can really understand what's going on here. And now we have a for loop, which we are going to go through. These last lines here are all very, very straightforward, and there's no need to go through that. But these first two lines look a bit more complicated. So, firstly, what is the first line? We have T1 = H, we know what H is. Capital Sigma1, we don't know what that is, but it's a function and it takes E as its input, we know what E is. CH, we don't know what that function is, but we pass EFG through that. And we add K0, which we know what that is, and we add W0, which we know what that is. So, these capital sigmas, sigma0 and 1, they're defined pretty much the same as their lowercase counterparts, but instead, they don't have a right shift value. They're just all right rotations followed by bit-wise addition modulo. Oh no. I should not say 2 to the 32, that should say 2, but I'm not going to change that now. And so, yes, for sigma0, we have 2, 13, 22. Sigma1, we have 6, 11, 25. And this CH function, the CH stands for choose. So this first parameter here, E plays an asymmetric role in this.
[10:07]We're going to use the bits from E to tell us out of the inputs F and G, which ones to take as our final output. So that may not make much sense, but here's an example. We have our first bit here, our leftmost bit as 0. This tells us to go to the third input. And so we take 0 as an output. The second bit of E is 1, and so this tells us to go to the second input and take an output of 0. And then the third bit of E is 0, and so we again go down here and take that as part of our output. And if you're going to ask me, hang on, wouldn't this make more sense if we had a 0 bit in our E, then we would go to F and a 1 bit we would go to G? That would make more sense to me also. I have no idea why they're doing it this way, but they are. After we do all that, we have this as our final output. So now we know what they all are. Here is H, here is sigma1 of E, well, there's E, and then we apply sigma1 to it and we get this. Here is CH of EFG, which we have just done. Here is K0, which, remember, it was this thing over here, highlighted in orange. And so we'll put that there, and we have W0, which we defined a few seconds ago or 30 seconds ago or something. And now we do addition modulo 2 to the 32 to ensure that T1 is of bit length 32, and we get this. This second part here, T2, what does that equal? T2 is capital sigma0 of A plus Maj ABC. What's going on here then? We know what sigma0 is. Maj stands for majority, and there's no asymmetric role being played here, unlike the choose function. So we look at the first column, and we see 010. So the majority of the bits are 0. We go to the second column, we see 100, so the majority of the bits are 0. The third, they're all 1, so the majority is 1, and we keep doing that, and we get this as our output. So let's take sigma0 A. Here is A, and once we do all the right rotations, and then the bit-wise addition modulo 2, we get this output. And if we take the majority of ABC bit-wise, we get this as I just showed, and here is our output for T2. Everything highlighted in that pink box over there is extremely simple to follow, because we're literally just all we're doing there is switching around some stuff and doing some simple addition. So that was it for T = 0. So we do the same for T = 1, all the way up to T = 63. So after we've run through this for loop, we'll have the values of A through to H is equal to these 32-bit numbers here. And then we update our Hs, and we do so by adding the ABCs, EFG, and Hs to our original H values. And once we update these H values, we get these eight 32-bit numbers. And now we're finished because as I said earlier, our padded input was only of length 512, and so we only had to go through the outer loop once. And so our final output is given as this. Now, all these double lines just mean shove all of these 32 bits together, merge them into one 256-bit number. So, the output of SHA-256 RedBlockBlue is this, which is the same thing we have here, but just written in hexadecimal format. And that is it. We are finished.
[14:52]Sub if you want to.
