1
$\begingroup$

How does this code calculating the AES S-Box work? I don't understand the overall calculation procedure. Code is attached below:

function generate(irreducible_poly){
    try{
        p = parseInt(eval(irreducible_poly.replace(/x/g, '10')), 2);
    } catch(err){
        console.log('Irreducible Polynomial invalid');
        return;
    }

    let t = new Uint32Array(256);
    for (let i = 0, x = 1; i < 256; i ++) {
        t[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * p);
    }

    let Sbox = new Uint32Array(256);
    Sbox[0] = 0x63;
    for (let i = 0; i < 255; i ++) {
        let x = t[255 - i];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        Sbox[t[i]] = (x ^ 0x63) & 0xFF;
    }

    return Sbox;
}


// Inverse of Sbox
function inverse(sbox){
    let InvSbox = new Uint32Array(256);
    for (let i =0; i < 256; i++){
        InvSbox[i] = sbox.indexOf(i);
    }

    return InvSbox;
}
$\endgroup$
6

1 Answer 1

2
$\begingroup$

Big picture: this code needs to compute the inverse modulo binary irreducible polynomial $P$ of every non-zero binary polynomial $R$ of degree less than that of $P$. Towards this, it has selected a generating polynomial $G=1+x$, and tabulates $Q_i=G^i\bmod P$, which reaches all the desired $R$. The multiplicative inverse of $R=Q_i$ is $Q_{255-i}$.


This code evaluates the AES S-box and it's inverse as follows:

  1. (code block starting in try) It evaluates p = 0x11b = 283 that represents the binary polynomial $P=1+x+x^3+x^4+x^8$ as an integer: the value obtained when evaluating this polynomial for integer $x=2$. This common convention is used in AES to map binary polynomials to integers.

  2. (code block starting in let t) It computes table t[i] representing the binary polynomial $Q_i=(1+x)^i\bmod P$ per this convention. That $Q_i$ is computed per the recurrence $Q_{i+1}=Q_i\,(1+x)\bmod P$ with $Q_0=1$, translating¹ to t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p)) with t[0] = 1 under said convention.

    For example: $Q_0$ is the (binary) polynomial $1$, represented by t[0] = 1. $Q_1=1+x$, represented by t[1] = 3. $Q_2=(1+x)^2=1+x^2$, represented by t[2] = 5. $Q_7=(1+x)^7=1+x+x^2+x^3+x^4+x^5+x^6+x^7$, represented by t[2] = 0xff = 255. $Q_8=(1+x)^8\bmod P=(1+x^8)\bmod P=x+x^3+x^4$, represented by t[8] = 0x1a = 26.

  3. (code block starting in let Sbox) Tabulating $Q_i=(1+x)^i\bmod P$ was useful because $(1+x)^{255}\bmod P=1$, therefore $Q_{255-i}$ is the multiplicative inverse of $Q_i$. And $Q_i$ reaches all non-zero binary polynomials of degree $<8$ (that is $1+x$ is a generator). Therefore integer t[255 - i] represents the multiplicative inverse of the polynomial that integer t[i] represents. And when in the loop i goes from 0 to 254 that yields the multiplicative inverse of each of the 255 non-zero polynomials of degree $<8$. The loop then merely applies² the affine transformation specified in the rest of the definition of the AES S-box. The zero polynomial is special-cased.

    For example: when in the loop i = 8, t[i] is t[8] = 0x1a = 26 representing $Q_8=x+x^3+x^4$, and t[255-i] (going to x, unrelated to $x$) is t[247] = 0xfd = 253 representing the polynomial $Q_{247}=1+x^2+x^3+x^4+x^5+x^6+x^7$. That $Q_{247}$ is the multiplicative inverse of $Q_8$. By the definition of the AES S-box, there only remains to apply the affine transformation² to x, then set the result in Sbox[t[i]] = Sbox[26].

  4. (function inverse) The inverse table is computed by searching each entry in the table. That works but is inefficient. InvSbox[i] = sbox.indexOf(i); could be replaced by the straightforward and more efficient InvSbox[sbox[i]] = i;.


¹ Justification: in t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))

  • t[i] is an integer in $[0,2^8)$ and represents $Q_i$ of degree $<8$
  • t[i] << 1 is an even integer in $[0,2^9)$ and represents $Q_i\,x$.
  • t[i] >>> 7 is either 0 or 1. It's the coefficient of the term of order $x^7$ in $Q_i$.
  • (t[i] >>> 7) * p is correspondingly either 0 or 0x11b = 283, representing $0$ or $P$.
  • (t[i] << 1) ^ ((t[i] >>> 7) * p) correspondingly represents $(Q_i\,x)$ or $(Q_i\,x)+P$, and (by examination of the two cases) is an integer in $[0,2^8)$, thus represents a binary polynomial of degree $<8$, which thus is $(Q_i\,x)\bmod P$.
  • t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p)) is thus an integer in $[0,2^8)$ and represents $Q_i+(Q_i\,x)\bmod P)=Q_i\,(1+x)\bmod P=Q_{i+1}$, of degree $<8$.

In C, the standard likely-constant-time idiom for this expression would be (essentially with & - used instead of multiplication):
t[i+1] = t[i] ^ ((t[i] << 1) ^ (p & -(t[i] >> 7))).
Note: some overzealous C compilers will wrongly bark at the -, silence them.


² The statement x |= x << 8;duplicates the bits in variable x (representing the modular inverse of $Q_i$) so that subsequent right shifts become equivalent to rotation when it comes to the low-order 8 bits. The statement x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7); implements the circulant matrix multiplication. Then ^ 0x63 (representing polynomial $1+x+x^5+x^6$) is the constant addition, and & 0xFF keeps the low-order 8 bits (terms of degree $<8$), undoing the duplication.

$\endgroup$
6
  • 1
    $\begingroup$ $1+x$ is specifically used because $(1+x)^i \bmod P$ reaches all values (other than 0) for $i$ between 0 and 254; the technical term we use for this is that $1+x$ is a "generator" of this field (while the simpler term $x$ is not) $\endgroup$
    – poncho
    Commented Jan 31, 2022 at 16:42
  • $\begingroup$ so could you pleased explain it in your own way?? i need this algorithm for my thesis work. Actually I understand which part for what calculation, but it would be better for me if you explained it with one example rather then equation. Also; Sbox[t[i]] = (x ^ 0x63) & 0xFF; why FF used here could you pleased explain??? $\endgroup$
    – Aktar1990
    Commented Feb 1, 2022 at 8:31
  • $\begingroup$ @Aktar1990: I added numerical examples, as well as note 2 explaining the affine transformation, including the (x ^ 0x63) & 0xFF. For the Sbox[t[i]], it's explained in "3.". $\endgroup$
    – fgrieu
    Commented Feb 1, 2022 at 18:12
  • $\begingroup$ @fgrieu Do you have any complete coding for this AES S-Box with better explanation. I just want coding from you ,when i run it ,i get the output??do you have??do you know the time complexity and space complexity of AES S-Box?? $\endgroup$
    – Aktar1990
    Commented Feb 1, 2022 at 18:17
  • 1
    $\begingroup$ @Aktar1990: you chose this code and it's language. I have no better explanation of it, or code with similarly low time and space complexity: generate is reasonably close to optimal in the language at hand. Efficient code uses polynomial math and coding techniques that take some time and effort to grasp. But since you are on a related thesis, you should be capable of that. $\endgroup$
    – fgrieu
    Commented Feb 1, 2022 at 18:25

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.