# SHA3 the Left & Right Encode Functions

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:

1. What is meant by the base256 encoding of an integer?
2. Do $$x_1,x_2,\ldots,x_n$$ all contain the same bytes, or do they contain different bytes split across them?
3. Does enc8 effectively mean little-endian?
4. After theenc8 bytes are concatenated, are they transformed back into a number or binary or...?

1. 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.

1. 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.

1. 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.

1. 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

• Thanks so much!! Do you have any examples or reference for the right_encode function too please? – SamG101 Oct 23 '19 at 19:30
• Just append the encoding of the length to the right. That is the only difference. left -> prepend, right -> append – kelalaka Oct 23 '19 at 19:33

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}(\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:

• Integers re encoded into bit strings with lengths divisible by 8, so that byte-oriented implementations aren't forced to cope with arbitrary bitstrings;
• The encoding takes care to specify the individual ordering of each bit of the input, whereas byte-oriented implementations will not expose any such order.