SHA-3 uses Padding, so the original message has a certain length.

In the case of SHA-3-512 each block has the size of 576, so any message must be padded, such that it is a multiple of the blocksize 576.

I know the rule that the padding is done via the formula

p(m)=P10*1

where P is a predetermined bit-String and the * is a placeholder, where an amount of 0 is inserted, such that the condition is met.

Now here comes the question: What happens, when we want to put a message of 575 bit into the algorithm? Obviously we are 1 bit short of the required length, and the padding rule is at least 3 bit long. What happens in that case?

What happens, when we want to put a message of 575 bit into the algorithm? Obviously we are 1 bit short of the required length, and the padding rule is at least 3 bit long. What happens in that case?

In that case, we just extends padding until it hits the next multiple-of-576 boundary; in this case, this means the padding is 577 bits long (and crosses the block boundary).

The padding rule $$pad10*1$$, whose output is a $$1$$, followed by a (possibly empty) string of $$0$$s, followed by a $$1$$.

The padding rule, pad, is a function that produces padding, i.e., a string with an appropriate length to append to another string. In general, given a positive integer $$x$$ and a non-negative integer $$m$$, the output $$pad(x, m)$$ is a string with the property that $$m + len(pad(x, m))$$ is a positive multiple of $$x$$. Within the sponge construction, $$x = r$$ and $$m = len(N)$$, so that the padded input string can be partitioned into a sequence of $$r-bit$$ strings.

Where $$r$$ is the block size or the rate. The $$r$$ can be calculated by $$r = 1600 - 2\cdot r$$

The below algorithm is the padding algorithm of SHA3 and internally determines the number of required zeros.

• Input: positive integer $$x$$; non-negative integer $$m$$.
• Output: string $$P$$ such that $$m + len(P)$$ is a positive multiple of $$x$$.
• Steps:
1. Let $$j = (– m – 2) \bmod x$$.
2. Return $$P = 1 \mathbin\| 0^j \mathbin\| 1$$.

• A message with 575-bit size;

What happens, when we want to put a message of 575 bit into the algorithm? Obviously we are 1 bit short of the required length, and the padding rule is at least 3 bit long. What happens in that case?

Call the algorithm pad10*1(x, m) with 575 ( pad10*1(576, 575) ), then $$j = (-575 -2) \bmod 576 =575$$ So the number of 0's is 575.

The padded message is $$m\mathbin\|1\,\underbrace{00\ldots00}_{575-zeroes}\,1$$

The total padding size is 577 which requires an extra block since the $$r=576$$.

• Note: this is answer was written to extend poncho's answer in detail. – kelalaka Jun 28 '20 at 7:15