Question

In SHA-512, the size of the original message is 1650 bits. What is the number of padding bits?

Answer 1

SHA-512 Pre-Processing

Answer is 270 bits [398 bits if you count the 128-bit block too]. Read on for the full explanation. Or, scroll down to the Short Method section to directly see how to solve the question if you already know all the concepts.

$\rule{320}{1}$

The Secure Hash Algorithm - 512 bits is a Hashing Algorithm to generate a 512 bit hash value of any given message of size upto $2^{128}$ bits.

It is one of the different algorithms specified in the Secure Hash Standard (SHS). The official documentation for the SHS is the FIPS PUB 180-4 [Federal Information Processing Standards Publication 180-4]. It is maintained by the National Institute of Standards and Technology [NIST].

$\rule{320}{1}$

Overview of SHA-512

The first step is Pre-Processing of the message. For SHA-512, the message must be padded so that its length is a multiple of 1024 bits.

After the Message is Padded, various constant values and different functions are used to manipulate the message and generate the Hash value. The specifics of the SHA-512 Constants and Hashing Functions can be found in the FIPS PUB 180-4.

For the purpose of this question, we must understand the first step: Pre-Processing.

$\rule{320}{1}$

Pre-Processing Messages in SHA-512

We denote the message by $M$.

Suppose the length of this message in bits, is $\ell$.

The final message length after pre-processing should be a multiple of 1024 bits.

The Pre-Processing Steps are as follows:

• Append the bit "1" to the end of the message.
• Now, append $k$ "0" bits to the end of the message, where $k$ is the smallest non-negative solution to $\ell + k+1 \equiv 896\ mod\ 1024$.
• After this, express the message length $\ell$ in binary in a 128-bit block and append this block at the end.

For example, consider a message $\tt Hi!$

So, $M = \tt Hi!$

We first express the message in binary by using the ASCII values for each character.

$\begin{aligned}\tt &H &\to\quad &(72)_{10} &= (01001000)_2 \\ \tt &i &\to\quad &(105)_{10} &= (01101001)_2 \\ \tt &! &\to\quad &(33)_{10} &= (00100001)_2\end{aligned}$

Each character is expressed as an 8-bit binary block, using the ASCII Values. The numbers 10 and 2 in subscript represent the Decimal and Binary ASCII Values respectively.

Now, we have the message $M$ in binary.

$M = 01001000\ 01101001\ 00100001$

The Message Length $\ell$ is 24. It is 24 bits long.

Now, we append the bit "1" to the message, and now we need the smallest solution of $k$ for

$\ell + k+1 \equiv 896\ mod\ 1024 \\\\\implies 24+k+1\equiv 896\ mod\ 1024 \\\\\implies k+25\equiv 896\ mod\ 1024 \\\\ \implies k = 896-25 = 871 \\\\ \implies k = 871$

So, we append 871 "0" bits. After this, we need the 128 bit block of $\ell = 24$ expressed in binary.

$(24)_{10} = (11000)_2 = \underbrace{(000\dots 011000)}_{\text{128 bits}}_2$

[We just append the required number of "0" bits to the beginning of binary form of $\ell$ to make it a 128 bit block.]

Hence, the final padded message would become:

$\boxed{\underbrace{01001000}_{\text{H}}\ \underbrace{01101001}_{\text{i}}\ \underbrace{00100001}_{!}\ 1\ \overbrace{00\dots 00}^{871}\ \overbrace{00\dots 0\underbrace{11000}_{\ell = 24}}^{128}}$

$\rule{320}{1}$

The Answer:

We have a message of the length $\ell = 1650$ bits.

We append "1" at the end. Now, we need the smallest solution of $k$ for:

$\ell + k + 1 \equiv 896\ mod\ 1024 \\\\\implies 1650+k+1 \equiv 896\ mod\ 1024\\\\\implies k+1651 \equiv 896\ mod\ 1024 \\\\\implies k = (1\times 1024)+896 - 1651 \\\\\implies k = 269$

So, we append 269 "0" bits towards the end of the message.

After that, we append the 128 bit block of $\ell = 1650$ expressed in binary.

$(1650)_{10} = (11001110010)_{2} = \overbrace{00\dots 011001110010}^{128}$

Hence, the final padded message is:

$\boxed{\text{(1650 bit message)}\ 1\ \overbrace{00\dots 0}^{269}\ \overbrace{00\dots 0\underbrace{11001110010}_{\ell=1650}}^{128}}$

So, The number of padding bits is $1+269 = \bold{270}$ bits.

Hence, Answer is 270 bits. If we include the 128 bit block, answer will be 398 bits.

$\rule{320}{1}$

Short Method:

The final message length must be a multiple of 1024 bits.

Now, we know that we compulsorily append "1" and a 128-bit-block of the message length $\ell$ expressed in binary.

The rest of the message length is accomplished by appending "0" bits in between the "1" bit and the 128-bit-block.

So, suppose we need to append $k$ zeros. Then, $\ell + 1 + k + 128$ must be a multiple of 1024.

Here, $\ell+1+128 = 1650+1+128 = 1779$

For 1779, the closest greater multiple of 1024 is 2048.

So, $k = 2048-1779 = 269$

Hence, the number of padding bits would be $1 + 269 = 270$. Thus, The Answer is 270 bits. [398 bits if we include the 128 bit block as well]

Answer 2

Answer:

Explanation:

270