4
$\begingroup$

The substitution-value of input byte $\mathtt{C2}$ is $S[\mathtt{C2}]=\mathtt{2F}$. This comes from applying the Euclidean algorithm to $A(x)A^{-1}(x)\equiv 1\pmod{p(x)}$, where $A(x) = x^7+x^6+x$ (from $\mathtt{C2}$) and $p(x) = x^8+x^4+x^3+x+1$ (the $AES$ irreducible polynomial). On finding remainder $r=1$ we apply the extended Euclidean algorithm to find $A(x)^{-1}=x^5+x^3+x^2+x+1$ or $\mathtt{2F}$ as expected.

However, this is a lot of work by hand. I am not a programmer but I have managed to write $AES$ in Excel. I would like to change the irreducible polynomial for another suitable one, but I would then need to create a corresponding $S-box$ and doing this by hand is a lot of work. So my questions are:

  1. Is there an online program that can do these calculations?
  2. Is there a quick way to do it in Excel?
  3. Since the irreducible polynomial will be different from the original, how do I find the matrix for the corresponding affine transform?

Thank you for any help or advice.

$\endgroup$
  • $\begingroup$ You'd have to construct an explicit isomorphism between the two fields, which is probably as much work, if not more. What about using a precomputed table? $\endgroup$ – knbk Nov 28 '17 at 13:27
1
$\begingroup$

I would like to change the irreducible polynomial for another suitable one

Suitable in what way? Are you trying to make a cipher with improved hardware performance or resource usage? Trying to increase the security of the cipher? Any change would result in a similar cipher but would no longer be AES.

1: I believe Sage can perform the calculation if you can write the correct script, and I believe they have an online version

2: not easily, you need to generate multiple tables, then do all the math. I can do it quickly in VB6, and Excel uses a VB type script language, but it may not be comprehensive enough to get it done, and since it would not be compiled, it would be slower, and you would still need to write a substantial amount of code

3: you have to choose it. The affine transform in AES was chosen based on the polynomial so that the s-box would meet certain criteria, you could simply brute force all of them (there are about 65000) and choose the best result. That is the last step, and the most computationally expensive, doing it in excel would take an absurd amount of time, probably years.

$\endgroup$
  • $\begingroup$ I see. Well how about a specific example? In this paper pdfs.semanticscholar.org/db08/… on page 7 they have used $p(x) =x^8+x^4+x^3+x^2+1$ and replaced the matrix in the affine transform to $R$. (1) Is there an $S-box$ table for this (and$S^{-1}$)? And (2) How were the rows of $R$ created? In the usual $AES$ they are rotated but this is not the case here. $\endgroup$ – Red Book 1 Nov 29 '17 at 4:32
  • $\begingroup$ @RedBook1 I believe in that example they calculated the required additional transformations so that a different polynomial can be used, but the cipher will still output valid ciphertexts $\endgroup$ – Richie Frame Nov 29 '17 at 5:19
  • $\begingroup$ Okay, but is there an S-box table available for this p(x)? $\endgroup$ – Red Book 1 Nov 29 '17 at 11:55
  • $\begingroup$ I found the online Sage sagecell.sagemath.org but I cannot understand where all the polynomials are coming from. A simple example based on the original question with $AES$ original would be very helpful. I should be able to work it out from there. $\endgroup$ – Red Book 1 Dec 1 '17 at 9:46
  • $\begingroup$ @RedBook1 my example in answer 1 should do it $\endgroup$ – Richie Frame Dec 1 '17 at 18:40
1
$\begingroup$

Whatever the irreducible polynomial $p(x)$ chosen, for any non-zero $A(x)$ it holds that $A^{255}(x)\equiv1\pmod{p(x)}$, thus $A^{-1}(x)\equiv A^{254}(x)\pmod{p(x)}$. This gives a convenient way to compute the desired modular inverse, alternative to the extended Euclidean algorithm.

We can perform that computation by starting from $A(x)$ and alternatively multiplying modulo $p(x)$ by the current result or by $A(x)$, computing $A(x)$ to the 2, 3, 6, 7, 14, 15, 30, 31, 62, 63, 126, 127, 254th power; for a total of 13 multiplications.

In fact, we can get down to 11 multiplications, by computing $A(x)$ to the 2, 3, 6, 12, 24, 48, 51, 63, 126, 127, 254th power; see Shortest Addition Chains.

Either method is easy in any programming language including Excel, once we have the multiplication modulo $p(x)$ right.

$\endgroup$
  • 1
    $\begingroup$ where it is going to get messy is when computing the affine transform $\endgroup$ – Richie Frame Dec 29 '17 at 0:22
  • $\begingroup$ @fgrieu I posted the question on AskSage and received this answer: ask.sagemath.org/question/40008/… $\endgroup$ – Red Book 1 Dec 29 '17 at 10:46

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.