How to calculate/generate the inverse S-box of Kuznyechik block cipher?

Question

Let's suppose I want to modify Kuznyechik block cipher by choosing a random S-box (taken from /dev/random for example).

How can I calculate/generate the inverse S-box?

Does anyone know the formula or algorithm used to do this?

Answer 1

Sagemath SBox Package is a friend of SBox learners/designers.

For an invertible SBox;

#         0  1  2  3  4  5  6  7       #index
S = SBox([0, 1, 3, 6, 7, 4, 5, 2])     #output
Sinv = S.inverse()
print(Sinv)

outputs

(0, 1, 7, 2, 5, 6, 3, 4)

Actually, the implementation of the inverse is not hard; just reverse the index-output relation. Remember, invertible SBox is just a permutation.

---

Note that the source code of SageMath SBox is here and as a good library it first controls the SBox is a permutation or not and returns an SBox oject;

        if not self.is_permutation():
            raise TypeError("S-Box must be a permutation")

        cdef Py_ssize_t i
        cdef list L = [self._S_list[i] for i in range(1 << self.m)]

        return SBox([L.index(i) for i in range(1 << self.m)],
                    big_endian=self._big_endian)

Answer 2

Assuming S-boxes are a permutation.

Here is example in Python:

S = (2, 0, 1)
inverse = [0] * len(S)

for i in range(len(S)):
    inverse[S[i]] = i

print(inverse)

Here is example in C:

unsigned int S[256] = {...};
unsigned int inverse[256];

for (int i = 0; i < 256; i++)
{
    inverse[S[i]] = i;
}