Padding-kk-bit state machine
The 136-byte output of the Padding-KK SM must first be translated to bits before it can be used as the Keccak-F SM’s input.
This is where the Padding-KK-Bit state machine comes into the picture.
The Padding-KK-Bit SM play the role of converting bytes to bits in both directions. It also serves as a bridge between the bit-wise operating Keccak-F SM and the byte-wise operating Padding-KK SM.
The Padding-KK-Bit SM is in charge of validating each action connected to the inputs and outputs of the Keccak-F permutation blocks in addition to being a two-way bytes-to-bits converter.
Design strategy¶
Here’s how this state machine facilitates operations between the Padding-KK SM and the Keccak-F SM.
A block of 136 rows of bytes in the Padding-KK SM corresponds to
First subdivision: Consists of
Second subdivision: Consists of the
Third subdivision: Consists of
Bytes to bits correspondence¶
This section elaborates how the Padding-KK-Bit SM handles the correspondence of bytes between state machines, and correct positioning of bits with respect to the powers of 2.
Starting with the first subdivision, the
-
The Padding-KK-Bit state machine has a column named
, which records all the bits associated with the decomposition of each of the bytes of the Padding-KK SM. -
In order to relate the byte to its bit decomposition between the two states machines, a register called
is added in both state machines as a bit-to-parent-byte identifier. -
Also, another register called
, is added for the sole purpose of sequentially constructing each byte from the bits. -
A factor register
is used to correctly place each bit in the parent, with respect to the powers of 2. -
Therefore, each complete byte is recorded at the last row of such a 9-row byte block of the
register. This row is flagged with a “1” in the same row of another register called . This ensures that is 0 in all rows except the last row of a 9-row byte block.
Example: Representation of two bytes¶
Here’s an example of how two bytes,
Note that
The following constraint applies to the
It is very important for
It is also necessary to ensure that
Validating transitions of bits¶
The challenge of breaking down bytes into bits has been the main focus up to this point. Here, it is intended to verify the bit transitions following the KECCAK-F operation, which is carried out for each block of 136 bytes. For this, a few columns are introduced.
-
: This register stores the input bit of the current KECCAK-F permutation block. -
: This register stores the output bit of the current KECCAK-F permutation block. -
: The same idea as in the Padding-KK state machine applies here. The register is constant within a block, and reflects that the output of the previous permutation KECCAK-F is connected to the current one. That is, it indicates that the previous 136-byte block belongs to the same string as the current block. -
: This register records “ ” in the very last row of each of the -row block corresponding to a 136-byte block of the Padding-KK SM, and everywhere else.
Below figure depicts a schema of how to relate the above columns with the KECCAK-F sponge construction.
Constraints for bit transitions¶
These constraints are needed to ensure correct transition between rows.
There is a need to make sure the
It is also mandatory to test whether
The register
Therefore,
A quick analysis shows the following,
-
If
is , then equals , which is precisely what needs to happen in the first KECCAK-F permutation block. -
But if
is , then equals , which is actually the of and .
Below table shows all the cases of the above computation.
Capacity connection in the 512 rows¶
The second subdivision of the Padding-KK-Bit SM’s
First, a new register called
This ensures that in each
Therefore, these equations guarantee that the capacity bits are not modified by any exterior bits.
Output calculations in the (256 + 1) rows¶
Now, the last part of the Padding-KK-Bit SM is to keep track of the last subdivision of each
Example: Storing 256-bit intermediate hash outputs¶
Consider the 256 bits,
Observe how factors
where
The
This concludes our design for creating the Padding-KK-Bit SM. What is left to be done is to connect both states machines and check the validity of the last hash.
Padding-KK SM and Padding-KK-Bit SM connection¶
This section describes how these two state machines, the Padding-KK SM and the Padding-KK-Bit SM, connect via Plookup.
First of all, observe that there’s a need to check whether the bytes received in one state machine are the same as those in the other. Also, corresponding sequential order of these bytes should be checked. The identifier register
The Padding-KK state machine has the
In particular,
Hence, the following Plookup is added: