In this paper (Section 2.3.1, Pg.5), I came across the left_encode and right_encode functions, and I have some questions about the functions:
base256 encoding of an integer?enc8 effectively mean little-endian?enc8 bytes are concatenated, are they transformed back into a number or binary or...?
- What is meant by the base256 encoding of an integer?
It splits an integer $x$ into bytes, a byte is 8-bit that can represent 256 numbers. That is why actually $n$ is set as the smallest positive integer satisfying $2^{8n} > x$. The bytes are little-endian encoded.
- Do $x_1,x_2,\ldots, x_n$ all contain the same bytes, or do they contain different bytes split across them?
No, the x is split into bytes.
- Does enc8 effectively mean big-endian?
A byte has no little-endian or big-endian encodings. Here, it is just a byte encoding but in reverse. Second steps do the little-endian. In the end, all bits are reversed. See a bigger example below.
- After the enc8 bytes are concatenated, are they transformed back into a number or binary or...?
It is a byte array and in general in cryptographic implementations, the programming codes are processing with byte arrays. The output of the hash function will be byte to. It is up to you to convert into hex or base64.
A nice example from cryptologie.net
left_encode:
0001 0000 | 0011 0001 | 0111 1110 input
0111 1110 | 1000 1100 | 0000 1000 value reversed
1100 0000 | 0111 1110 | 1000 1100 | 0000 1000 length encoded. the size 3 in reverse
right_encode:
0001 0000 | 0011 0001 | 0111 1110 input
0111 1110 | 1000 1100 | 0000 1000 value reversed
0111 1110 | 1000 1100 | 0000 1000 | 1100 0000 length encoded
right_encode function too please?
$\endgroup$
The SHA-3 functions are defined over arbitrary bit strings as input, whose length in bits might not be a multiple of eight. Implementations are allowed to skip support for this and restrict themselves to bit sequences that fit into a neat number of bytes, and in fact routinely choose to do this.
After the enc8 bytes are concatenated, are they transformed back into a number or binary or...?
Nope, although the definitions take great care that you could do so, unambigously. This particular NIST SP defines constructions that involve concatenating multiple inputs. For example, the second clause of the definition of CSHAKE (for non-empty $N$ or non-empty $S$) is:
$$\mathrm{KECCAK}[256](\mathrm{bytepad}(\mathrm{encode\_string}(N) \| \mathrm{encode\_string}(S), 168) \| X \| 00, L)$$
And one of the key concerns in these definitions is that the resulting bitstrings be unambigously parseable—that you could, from any of the bitstrings and knowledge of the context in which it was used, unambigously recover the values of $X$, $L$, $N$ and $S$ that went into it. This isn't because there's a practical requirement to parse these values after you've concatenated them, but rather because the designers want the encoding to be an injective function—meaning that every distinct combination of inputs will encode to a different bit strings. The advantage of this is that we never have to worry that two distinct input combinations will "collide" and produce the same encoded string. (Note that if an attacker could find such an encoding collision that'd count as a break of the derived function!)
What is meant by the base256 encoding of an integer?
The same thing that's meant by a base-2, base-8, base-10 or base-16 encoding of an integer, except with base 256. The integer $m$ is represented by a sequence of digits $x_1, \dots, x_n$ such that
$$m = 256^0 x_0 + 256^1 x_1 + 256^2 x_2 + \cdots + 256^n x_{n-1}$$
Do $x_1, x_2, \dots, x_n$ all contain the same bytes, or do they contain different bytes split across them?
The $x_i$'s are not bytes, they're base-256 digits, abstractly. These are of course in a one-to-one relationship bytes, but the definition doesn't assume any specific representation of the digits—however they are represented, the $enc_8$ function is going to encode them into bitstrings.
Does enc8 effectively mean little-endian?
Kelakala answers this with "no" based on a definition where endianness is about byte order. Not an unreasonable point to make, but I think the important thing to remark is that, again, SHA-3 is defined over arbitrary bitstrings, and the definition of enc8 is making sure that the base-256 digits are getting encoded into 8-digit bitstrings where lesser significant bits first, which is the same idea as little-endianness, except over bits instead of bytes.
Remember how I said above that many SHA-3 implementations will skip support for input bitstrings that don't fit evenly into bytes? All this business here is about catering to such implementations:
