1
$\begingroup$

I have been reading on the polynomial representation of the AES Sbox in the PDF “Essential Algebraic Structure Within the AES” by Murphy and Robshaw (www.isg.rhul.ac.uk/~sean/crypto.pdf) on page 7, that the affine transformation can be represented as $f(a) = \sum^7_{k=0} \lambda_ka^{2^k}$ where $(\lambda_0, \lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5, \lambda_6, \lambda_7)$ = (0x05, 0x09, 0xf9, 0x25, 0xf4, 0x01, 0xb5, 0x8f). Can me anybody tell how to compute this values $\lambda_0,\ldots,\lambda_7$ from the Matrix $L_A$ on page 7?

Best regards

$\endgroup$
  • $\begingroup$ possible duplicate of Polynomial representation of the affine part of the AES S-box $\endgroup$ – otus Sep 11 '14 at 14:16
  • $\begingroup$ No I don't think the link is answering my question, because they only uses the coefficients $\lambda_0, \ldots,\lambda_7$ of the paper and don't tell me how to compute from the matrix $\endgroup$ – user17203 Sep 11 '14 at 14:25
  • $\begingroup$ Yeah, I'll leave the related link there, but it isn't really a duplicate. $\endgroup$ – otus Sep 11 '14 at 14:57
1
$\begingroup$

One way to derive the values $\lambda_0, \lambda_1, ..., \lambda_7$ would be to formulate the eight simultaneous equations in GF(256):

$$\lambda_7 01^{128} + \lambda_6 01^{64} + \lambda_5 01^{32} + \lambda_4 01^{16} + \lambda_3 01^{8} + \lambda_2 01^{4} + \lambda_1 01^{2} + \lambda_0 01^{1} = Aff(01)$$ $$\lambda_7 02^{128} + \lambda_6 02^{64} + \lambda_5 02^{32} + \lambda_4 02^{16} + \lambda_3 02^{8} + \lambda_2 02^{4} + \lambda_1 02^{2} + \lambda_0 02^{1} = Aff(02)$$ $$\lambda_7 04^{128} + \lambda_6 04^{64} + \lambda_5 04^{32} + \lambda_4 04^{16} + \lambda_3 04^{8} + \lambda_2 04^{4} + \lambda_1 04^{2} + \lambda_0 04^{1} = Aff(04)$$ $$...$$ $$\lambda_7 80^{128} + \lambda_6 80^{64} + \lambda_5 80^{32} + \lambda_4 80^{16} + \lambda_3 80^{8} + \lambda_2 80^{4} + \lambda_1 80^{2} + \lambda_0 80^{1} = Aff(80)$$

(where $Aff$ is the affine transform, not counting the addition of the constant), and 80 is the GF(256) element represented by the bit pattern '10000000')

and solve this set of 8 linear equations in $\lambda_0, \lambda_1, ..., \lambda_7$

Both sides of these equations are linear; that is $(x^{2^k} + y^{2^k}) = (x+y)^{2^k}$ and $Aff(x) + Aff(y) = Aff(x+y)$, and so if find such a set $\lambda_0, \lambda_1, ..., \lambda_7$, that set will hold for a sum of any subset of (01, 02, 04, ..., 80); since that's the entire field $GF(256)$, we have:

$$\lambda_7 x^{128} + \lambda_6 x^{64} + \lambda_5 x^{32} + \lambda_4 x^{16} + \lambda_3 x^{8} + \lambda_2 x^{4} + \lambda_1 x^{2} + \lambda_0 x^{1} = Aff(x)$$

for all $x$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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