1
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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)$ $\endgroup$
    – kelalaka
    Commented Sep 15, 2019 at 9:13
  • $\begingroup$ 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. $\endgroup$
    – user69015
    Commented Sep 15, 2019 at 10:36
  • $\begingroup$ @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 $\endgroup$
    – ackbar03
    Commented Sep 16, 2019 at 2:59

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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 $\endgroup$
    – Henno Brandsma
    Commented Sep 15, 2019 at 14:43
  • $\begingroup$ @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! $\endgroup$
    – ackbar03
    Commented Sep 16, 2019 at 2:49
  • $\begingroup$ 'one-to-one', 'bijection' and 'permutation' mean the same thing ^^ $\endgroup$
    – LeoDucas
    Commented Sep 16, 2019 at 16:08
  • $\begingroup$ @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. $\endgroup$
    – Snoop Catt
    Commented Sep 18, 2019 at 6:08
  • $\begingroup$ @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$) $\endgroup$
    – Snoop Catt
    Commented Sep 18, 2019 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.