# Why is $S(y) = y^{2^8-2} = y^{254}$ a one-to-one function and a permutation on $GF(2^8)$

I'm taking a course on cryptography and I have some confusions concerning the materials in our notes. Say we have the field $$GF(2^8)$$, we create a substitution algorithm (the S Box in AES) so we need a bijective function that maps from $$GF(2^8)$$ onto itself.

The total number of one-to-one functions is 256! because $$| GF(2^8)| = 256$$ and we can find a mapping by permutating all elements within the set.

We use the mapping function $$S(y) = y^{2^8-2} = y^{254}$$ which is a permutation on $$GF(2^8)$$

Why is this a permutation? How do we show this?

It is also mentioned in other notes such as here: SubBytes Transform circuit for AES Cipher (Version 1.0)

that

$$S(y) = y^{-1}$$ for all $$y \neq 0$$ and $$y^{255} = 1$$

I don't understand why however.

Just to summarize, I don't understand why $$S(y) = y^{2^8-2} = y^{254}$$ is a one-to-one function and a permutation on $$GF(2^8)$$ and why $$S(y) = y^{-1}$$ for all $$y \neq 0$$

Could someone help explain the details behind? Thanks!

• Hint: assume that it is not one-to-one. Then there are two $x,y\in GF(2^8)$ and $x \neq y$ such that $S(x)=S(y)$ then $(x-y)^{254} = 0$ can you see now? Now lok at $y \cdot S(y)$ – kelalaka Sep 15 '19 at 9:13
• The multiplicative group of $\mathrm{GF}(2^8)$ has $2^8 - 1 = 255$ elements. By Lagrange's theorem, we have that $y^{255} = 1$ for $y\neq 0$, so $y^{254} = y^{-1}$. Then the function $y\mapsto y^{254}$ sends $0$ to $0$ and it's not hard to see why we get a bijective function. – user69015 Sep 15 '19 at 10:36
• @kelalaka thanks for the hint but could you elaborate a bit on this approach? As I understand $S(x-y) \neq S(x) - S(y)$. The equality only holds if $S(y) = y^{p^n}$ where $p=2$ in our scenario and for any $n$. This can also be confirmed by expanding $S(x-y)=(x-y)^{254}=x^{254} + _{254}C_1 x^{253}(-y) + _{254}C_2 x^{252}(-y)^2 + _{254}C_3 x^{251}(-y)^3 + ... + (-y)^{254}$ and checking that $_{254}C_2 = 32131 \neq 0 \pmod n$. Also I understand $S(y)$ was intentionally chosen to be non-linear. Maybe I'm not getting the gist of your suggestion – ackbar03 Sep 16 '19 at 2:59

Fact 1: the order of the field $$GF(2^8)$$ is $$2^8$$, hence the order of its multiplicative group $$GF(2^8)^{\times} := GF(2^8) \setminus \{0\}$$ is $$2^8-1 = 255$$.

Fact 2: For a group $$G$$ of order $$q$$, any element $$g \in G$$, when raised to the power of $$q$$ is equal to 1: mathematically put, $$g^q =1$$.

Fact 3: for any element in a group there exists a unique inverse. An inverse to $$g$$ is an element (denoted by $$g^{-1}$$) that satisfies $$g \cdot g^{-1} = 1$$. In other words, the function $$g \mapsto g^{-1}$$ is one-to-one.

In our case, any element $$g \in GF(2^8)^{\times}$$ satisfies $$g^{255} = 1$$. Another, useful way to write this is that for any $$g$$ we have $$g \cdot g^{254} =1$$. Since $$g \cdot g^{254}= g^{255} = 1$$ we have that $$g^{254}$$ is equal to $$g^{-1}$$.

We conclude that the function $$g \mapsto g^{254}$$ is equal to the function $$g \mapsto g^{-1}$$ which is one-to-one, hence it is a permutation of the group $$GF(2^8)^{\times}$$.

I'd be happy to elaborate on any unclear part.

• To clarify: the map is a bijection on the non-zero elements, and $0$ is mapped to itself, so the total map is still a bijection. @ackbar03 – Henno Brandsma Sep 15 '19 at 14:43
• @Chipotle thanks so much for this! This clarifies it a lot. I am still confused however why $S(y) = y^{254}$ can be viewed as a permutation of the group $GF(2^8)$. Is the permutation on the coefficients of the polynomial $y$? Why does raising it to the power of 254 effectively permutate it? I understand that permutations are one-to-one functions but don't really understand why this one-to-one function is a permutation. Thanks a lot! – ackbar03 Sep 16 '19 at 2:49
• 'one-to-one', 'bijection' and 'permutation' mean the same thing ^^ – LeoDucas Sep 16 '19 at 16:08
• @ackbar03 Indeed, one-to-one function and permutation are the same thing. I think it would be helpful to review the definitions in Wikipedia. To recap the argument above: $y \mapsto y^{254}$ is equal to the function $y \mapsto y^{-1}$, which is a one-to-one function by the existence and uniqueness of an inverse element. – Snoop Catt Sep 18 '19 at 6:08
• @ackbar03 Also, you might be wondering, if these two functions are the same, why not just define $S(y) := y^{-1}$ in the first place. This is for computational reasons: the way to compute the inverse of an element in a group $G$, is actually to raise it to the power of ($|G|-1$) – Snoop Catt Sep 18 '19 at 6:12