Matthew van Eerde's web log

  • Matthew van Eerde's web log

    Expressing a function f: GF(2⁸) → GF(2⁸) as a polynomial using a Lagrange polynomial

    • 0 Comments

    I talked about Rijndael in a couple of previous posts: Generating the Rijndael S-box, Efficient multiplication and division in GF(28), Sieving irreducible monic polynomials over a finite field, Addition and multiplication table for GF(22).

    I'm going to talk some more about it today.

    The Rijndael non-linear S-box S(x) is a composition of two invertible functions f(g(x)). Last time we showed how to generate these, and their inverses, as 256-entry tables.

    As Daemen and Rijmen point out, any function from a finite field to itself can be expressed as a polynomial. In fact, given a tabular form of the function, it is possible to generate the Lagrange polynomial and then simplify.

    They also give the polynomial for S(x):

    SRD[x] = 05·x255 + 09·x253 + F9·x251 + 25·x247 + F4·x239 + 01·x223 + B5·x191 + 8F·x127 + 63

    Well, let's check this.
    And while we're at it, let's find the polynomials for g(x), f(x) and even S-1(x) too.
    First of all, let's start with the Lagrange polynomial.

    Given a table of entries { (00, y00), (01, y01), ..., (ff, yff) }, there is a polynomial L(x) which gives the same output, namely:

    L(x) = Σi ∈ { 00, 01, ..., ff } yi pi(x)
    where pi(x) = Πj ∈ { 00, 01, ..., ff }, ji (x - j) / (i - j)

    Can we simplify this?
    Yes. Note that (i - j)-1 term varies over all the non-zero elements of the finite field. Since this is a field, every non-zero element has an inverse, which might or might not be itself.
    If the inverse is not itself, we can pair the two inverse elements together, and we get 01, which is the multiplicative identity, so we can ignore it.
    What are we left with? The product of those non-zero elements which are their own inverses.
    In the case of GF(28), there is only one such element, namely 01.
    Great! We can ignore the (i - j)-1 terms altogether:

    L(x) = Σi ∈ { 00, 01, ..., ff } yi Πj ∈ { 00, 01, ..., ff }, ji (x - j)

    What is this? A sum of 256 different polynomials.
    Each of these summands is a product of 255 polynomials of degree 1, and so is a polynomial of degree 255.
    But in GF(28), x255 = 01 for all x. So each of the summands is actually a polynomial of degree 254, or less.
    So the sum is also a polynomial of degree 254, or less; terms with an exponent >= 255 go away and just contribute to lower-order terms.

    Great. We have { (00, y00), (01, y01), ..., (ff, yff) } for f, g, S, and S-1. Let's plug them in and see what happens!

    I wrote a Perl script to do this; the script is attached. Here's the output. (It's quite slow; it takes about two and a half minutes to run.)

    g(x) = 01 x^254

    f(x) =
     63 + 05 x + 09 x^2 + f9 x^4 + 25 x^8 + f4 x^16 + 01 x^32 + b5 x^64 +
     8f x^128

    S(x) =
     63 + 8f x^127 + b5 x^191 + 01 x^223 + f4 x^239 + 25 x^247 + f9 x^251 + 09 x^253 +
     05 x^254

    S^(-1)(x) =
     52 + f3 x + 7e x^2 + 1e x^3 + 90 x^4 + bb x^5 + 2c x^6 + 8a x^7 +
     1c x^8 + 85 x^9 + 6d x^10 + c0 x^11 + b2 x^12 + 1b x^13 + 40 x^14 + 23 x^15 +
     f6 x^16 + 73 x^17 + 29 x^18 + d9 x^19 + 39 x^20 + 21 x^21 + cf x^22 + 3d x^23 +
     9a x^24 + 8a x^25 + 2f x^26 + cf x^27 + 7b x^28 + 04 x^29 + e8 x^30 + c8 x^31 +
     85 x^32 + 7b x^33 + 7c x^34 + af x^35 + 86 x^36 + 2f x^37 + 13 x^38 + 65 x^39 +
     75 x^40 + d3 x^41 + 6d x^42 + d4 x^43 + 89 x^44 + 8e x^45 + 65 x^46 + 05 x^47 +
     ea x^48 + 77 x^49 + 50 x^50 + a3 x^51 + c5 x^52 + 01 x^53 + 0b x^54 + 46 x^55 +
     bf x^56 + a7 x^57 + 0c x^58 + c7 x^59 + 8e x^60 + f2 x^61 + b1 x^62 + cb x^63 +
     e5 x^64 + e2 x^65 + 10 x^66 + d1 x^67 + 05 x^68 + b0 x^69 + f5 x^70 + 86 x^71 +
     e4 x^72 + 03 x^73 + 71 x^74 + a6 x^75 + 56 x^76 + 03 x^77 + 9e x^78 + 3e x^79 +
     19 x^80 + 18 x^81 + 52 x^82 + 16 x^83 + b9 x^84 + d3 x^85 + 38 x^86 + d9 x^87 +
     04 x^88 + e3 x^89 + 72 x^90 + 6b x^91 + ba x^92 + e8 x^93 + bf x^94 + 9d x^95 +
     1d x^96 + 5a x^97 + 55 x^98 + ff x^99 + 71 x^100 + e1 x^101 + a8 x^102 + 8e x^103 +
     fe x^104 + a2 x^105 + a7 x^106 + 1f x^107 + df x^108 + b0 x^109 + 03 x^110 + cb x^111 +
     08 x^112 + 53 x^113 + 6f x^114 + b0 x^115 + 7f x^116 + 87 x^117 + 8b x^118 + 02 x^119 +
     b1 x^120 + 92 x^121 + 81 x^122 + 27 x^123 + 40 x^124 + 2e x^125 + 1a x^126 + ee x^127 +
     10 x^128 + ca x^129 + 82 x^130 + 4f x^131 + 09 x^132 + aa x^133 + c7 x^134 + 55 x^135 +
     24 x^136 + 6c x^137 + e2 x^138 + 58 x^139 + bc x^140 + e0 x^141 + 26 x^142 + 37 x^143 +
     ed x^144 + 8d x^145 + 2a x^146 + d5 x^147 + ed x^148 + 45 x^149 + c3 x^150 + ec x^151 +
     1c x^152 + 3e x^153 + 2a x^154 + b3 x^155 + 9e x^156 + b7 x^157 + 38 x^158 + 82 x^159 +
     23 x^160 + 2d x^161 + 87 x^162 + ea x^163 + da x^164 + 45 x^165 + 24 x^166 + 03 x^167 +
     e7 x^168 + 19 x^169 + e3 x^170 + d3 x^171 + 4e x^172 + dd x^173 + 11 x^174 + 4e x^175 +
     81 x^176 + 91 x^177 + 91 x^178 + 59 x^179 + a3 x^180 + 80 x^181 + 92 x^182 + 7e x^183 +
     db x^184 + c4 x^185 + 20 x^186 + ec x^187 + db x^188 + 55 x^189 + 7f x^190 + a8 x^191 +
     c1 x^192 + 64 x^193 + ab x^194 + 1b x^195 + fd x^196 + 60 x^197 + 05 x^198 + 13 x^199 +
     2c x^200 + a9 x^201 + 76 x^202 + a5 x^203 + 1d x^204 + 32 x^205 + 8e x^206 + 1e x^207 +
     c0 x^208 + 65 x^209 + cb x^210 + 8b x^211 + 93 x^212 + e4 x^213 + ae x^214 + be x^215 +
     5f x^216 + 2c x^217 + 3b x^218 + d2 x^219 + 0f x^220 + 9f x^221 + 42 x^222 + cc x^223 +
     6c x^224 + 80 x^225 + 68 x^226 + 43 x^227 + 09 x^228 + 23 x^229 + c5 x^230 + 6d x^231 +
     1d x^232 + 18 x^233 + bd x^234 + 5e x^235 + 1b x^236 + b4 x^237 + 85 x^238 + 49 x^239 +
     bc x^240 + 0d x^241 + 1f x^242 + a6 x^243 + 6b x^244 + d8 x^245 + 22 x^246 + 01 x^247 +
     7a x^248 + c0 x^249 + 55 x^250 + 16 x^251 + b3 x^252 + cf x^253 + 05 x^254

    Daemen and Rijmen's polynomial rendition of S(x) is confirmed.

    Also note how simple g(x) is, and how complex S-1(x) is.

    Finally, I must confess that none of this is actually useful. The tabular form is much more convenient for applications. This is just a fun theoretical exercise.

    (Well, I had fun.)

  • Matthew van Eerde's web log

    Generating the Rijndael S-box

    • 0 Comments

    I talked about Rijndael in a couple of previous posts: Efficient multiplication and division in GF(28), Sieving irreducible monic polynomials over a finite field, Addition and multiplication table for GF(22).

    I'm going to talk some more about it today.

    One of the more interesting steps used in the Rijndael transformation is the non-linear S-box. This is a function S(a) that takes an element of GF(28) (which could be represented as a byte) and returns another one. It is invertible but non-linear.

    The spec defines S(a) in terms of two other invertible functions g(a) and f(a). In particular S(a) = f(g(a)). It follows that S-1(a) = g-1(f-1(a)).

    g(a) is the non-linear piece, and is quite simple:
    g(00) is defined as 00.
    g(a) = a-1 for all other a in GF(28). In particular, if a = 03b, then g(a) = 03255 - b.
    This is clearly invertible; in fact, it is its own inverse.

    Daemen and Rijmen seem to have been almost embarrassed by the simplicity of g so they introduced f. To quote from section 3.4.1:

    By definition, g has a very simple algebraic expression. This could allow algebraic manipulations that can be used to mount attacks such as interpolation attacks. Therefore, we built the S-box as the sequence of g and an invertible affine transformation f.

    I don't know if I buy the "simplicity" argument. It seems to me that if Rijndael, without f, is robust, then it's robust. And if you add f to a non-robust scheme, I don't understand how that makes it robust; I do see that it complicates analysis, but that seems like a drawback rather than an advantage.

    But I'll play along for now. What is f?

    b = f(a) is defined using the following matrix multiplication over GF(2) (each entry can be represented as a bit; a row or column as a byte.) Multiplication can be implemented as bitwise AND, and addition by bitwise XOR.

    In particular, note that f(00) = 63. So S(00) = f(g(00)) = f(00) = 63. So S-1(63) = 00.

    The reference implementation in the book uses hardcoded 256-byte lookup tables for S(a) and S-1(a). I wrote a Perl script which generates these lookup tables and prints them out. This script is attached.

    Here's its output, which matches the listing in the book:

    >perl -w s-box.pl
                              S(xy)
       | x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xa xb xc xd xe xf
    ---+------------------------------------------------
    0y | 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
    1y | ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
    2y | b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
    3y | 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
    4y | 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
    5y | 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
    6y | d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
    7y | 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
    8y | cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
    9y | 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
    ay | e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
    by | e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
    cy | ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
    dy | 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
    ey | e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
    fy | 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

                            S^(-1)(xy)
       | x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xa xb xc xd xe xf
    ---+------------------------------------------------
    0y | 52 09 6a d5 30 36 a5 38 bf 40 a3 9e 81 f3 d7 fb
    1y | 7c e3 39 82 9b 2f ff 87 34 8e 43 44 c4 de e9 cb
    2y | 54 7b 94 32 a6 c2 23 3d ee 4c 95 0b 42 fa c3 4e
    3y | 08 2e a1 66 28 d9 24 b2 76 5b a2 49 6d 8b d1 25
    4y | 72 f8 f6 64 86 68 98 16 d4 a4 5c cc 5d 65 b6 92
    5y | 6c 70 48 50 fd ed b9 da 5e 15 46 57 a7 8d 9d 84
    6y | 90 d8 ab 00 8c bc d3 0a f7 e4 58 05 b8 b3 45 06
    7y | d0 2c 1e 8f ca 3f 0f 02 c1 af bd 03 01 13 8a 6b
    8y | 3a 91 11 41 4f 67 dc ea 97 f2 cf ce f0 b4 e6 73
    9y | 96 ac 74 22 e7 ad 35 85 e2 f9 37 e8 1c 75 df 6e
    ay | 47 f1 1a 71 1d 29 c5 89 6f b7 62 0e aa 18 be 1b
    by | fc 56 3e 4b c6 d2 79 20 9a db c0 fe 78 cd 5a f4
    cy | 1f dd a8 33 88 07 c7 31 b1 12 10 59 27 80 ec 5f
    dy | 60 51 7f a9 19 b5 4a 0d 2d e5 7a 9f 93 c9 9c ef
    ey | a0 e0 3b 4d ae 2a f5 b0 c8 eb bb 3c 83 53 99 61
    fy | 17 2b 04 7e ba 77 d6 26 e1 69 14 63 55 21 0c 7d

    And here's the interesting part, the implementation of g(a) and f(a):

    sub g($) {
        my ($a) = shift;

        # g(0) we define to be 0
        return 0 unless $a;

        # otherwise g(a) = a^(-1)
        # a = (x + 1)^loga
        # so a^(-1) = (x + 1)^(-loga) = (x + 1)^(255 - loga)
        my $loga = $log_xplusone_of[$a];
        my $logb = 255 - $loga;
        $logb -= 255 if $logb >= 255;

        return $xplusone_to[$logb];
    }

    # f(a) = b is defined as follows:
    #
    # [ b7 ]   ( [ 1 1 1 1 1 0 0 0 ] [ a7 ] )   [ 0 ]
    # [ b6 ]   ( [ 0 1 1 1 1 1 0 0 ] [ a6 ] )   [ 1 ]
    # [ b5 ]   ( [ 0 0 1 1 1 1 1 0 ] [ a5 ] )   [ 1 ]
    # [ b4 ] = ( [ 0 0 0 1 1 1 1 1 ] [ a4 ] ) + [ 0 ]
    # [ b3 ]   ( [ 1 0 0 0 1 1 1 1 ] [ a3 ] )   [ 0 ]
    # [ b2 ]   ( [ 1 1 0 0 0 1 1 1 ] [ a2 ] )   [ 0 ]
    # [ b1 ]   ( [ 1 1 1 0 0 0 1 1 ] [ a1 ] )   [ 1 ]
    # [ b0 ]   ( [ 1 1 1 1 0 0 0 1 ] [ a0 ] )   [ 1 ]
    #
    # where the + is XOR
    sub f($) {
        my ($a) = @_;

        # start with the addition
        my $b = 0x63; # 0b01100011;

        # do the matrix multiplication
        # one matrix column at a time
        for (
            my ($c, $i) = (0x8f, 0x80); # 0b10001111, 0b10000000
            $i;
            $c = rotate_byte_right($c), $i >>= 1
        ) {
            # i is used to select a bit out of the a column
            # c is the matrix column which is multiplied by that bit
            # the resulting product influences the eventual b column

            # printf("%02x %02x\n", $c, $i);

            # if this bit in the a column is 0, all of the products are 0, so don't bother
            next unless $a & $i;

            # this bit in the a column is 1
            # so XOR b with the matrix column
            $b ^= $c;
        }

        return $b;
    }
Page 1 of 1 (2 items)

April, 2014