ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Saes tables

?
?
P
president_crg

The document provides supplemental information on the mix column function used in the AES cipher. It explains the arithmetic performed in GF(24) and expresses the mix column multiplication in terms of polynomials. Specifically, it shows how each nibble of an output column is a function of the polynomial multiplication and division of the corresponding nibble polynomials in the input column modulo x4 + x + 1.

1 of 6
Download to read offline
A PPENDIX E More on Simplified AES E.1 ARITHMETIC IN GF(24).........................................................................................2 E.2 THE MIX COLUMN FUNCTION ...........................................................................4 William Stallings Copyright 2006 Supplement to Cryptography and Network Security, Fourth Edition Prentice Hall 2006 ISBN: 0-13-187316-4 http://williamstallings.com/Crypto/Crypto4e.html
8/5/05 E.1 ARITHMETIC IN GF(24 ) Table E.1 shows the addition and multiplication tables in GF(24 ) modulo x4 + x + 1. For example, consider the product (4 ? C) = (0100 ? 1100). In terms of polynomials, this is the product [x2 ! (x3 + x2 )] mod (x4 + x + 1) = (x5 + x4 ) mod (x4 + x + 1). Because the degree of the polynomial to the right of the mod operator is greater than or equal to the modulus, a division is required to determine the remainder: x + 1 x4 + x + 1 x5 + x4 x5 + x2 + x x4 + x2 + x x4 + x + 1 x2 + 1 In binary, the remainder is expressed as 0101, or 5 in hexadecimal. Thus (4 ? C) = 5, which agrees with the multiplication table in Table E.1. E-2
8/5/05 Table E.1 Arithmetic in GF(24 ) modulo x4 + x + 1 (a) Addition + 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 2 3 4 5 6 7 8 9 A B C D E F 1 1 0 3 2 5 4 7 6 9 8 B A D C F E 2 2 3 0 1 6 7 4 5 A B 8 9 E F C D 3 3 2 1 0 7 6 5 4 B A 9 8 F E D C 4 4 5 6 7 0 1 2 3 C D E F 8 9 A B 5 5 4 7 6 1 0 3 2 D C F E 9 8 B A 6 6 7 4 5 2 3 0 1 E F C D A B 8 9 7 7 6 5 4 3 2 1 0 F E D C B A 9 8 8 8 9 A B C D E F 0 1 2 3 4 5 6 7 9 9 8 B A D C F E 1 0 3 2 5 4 7 6 A A B 8 9 E F C D 2 3 0 1 6 7 4 5 B B A 9 8 F E D C 3 2 1 0 7 6 5 4 C C D E F 8 9 A B 4 5 6 7 0 1 2 3 D D C F E 9 8 B A 5 4 7 6 1 0 3 2 E E F C D A B 8 9 6 7 4 5 2 3 0 1 F F E D C B A 9 8 7 6 5 4 3 2 1 0 (b) Multiplication 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 0 2 4 6 8 A C E 3 1 7 5 B 9 F D 3 0 3 6 5 C F A 9 B 8 D E 7 4 1 2 4 0 4 8 C 3 7 B F 6 2 E A 5 1 D 9 5 0 5 A F 7 2 D 8 E B 4 1 9 C 3 6 6 0 6 C A B D 7 1 5 3 9 F E 8 2 4 7 0 7 E 9 F 8 1 6 D A 3 4 2 5 C B 8 0 8 3 B 6 E 5 D C 4 F 7 A 2 9 1 9 0 9 1 8 2 B 3 A 4 D 5 C 6 F 7 E A 0 A 7 D E 4 9 3 F 5 8 2 1 B 6 C B 0 B 5 E A 1 F 4 7 C 2 9 D 6 8 3 C 0 C B 7 5 9 E 2 A 6 1 D F 3 4 8 D 0 D 9 4 1 C 8 5 2 F B 6 3 E A 7 E 0 E F 1 D 3 2 C 9 7 6 8 4 A B 5 F 0 F D 2 9 6 4 B 1 E C 3 8 7 5 A E-3
8/5/05 E.2 THE MIX COLUMN FUNCTION The mix column function operates on each column individually. Each nibble of a column is mapped into a new value that is a function of both nibbles in that column. The transformation was defined in Appendix 5B as follows: "1 4%"s0,0 s0,1% "s0,0 ( s0,1% ( $4 1'$ s =$ # &# 1,0 s1,1 ' # s1,0 & ( s1,1 ' ( & We can recast this in terms of polynomials as follows. The value 1 corresponds to the polynomial 1 ! the value 4 (binary 100) corresponds to the polynomial x2 . Thus, we have: and "1 x 2 %"s 0,0 s 0,1 % "s ( 0,0 s( % 0,1 $x 2 1 '$ s1,0 ' = $ s( s1,1 & # 1,0 s1,1 ' ( & # &# Remember that multiplication is performed modulo x4 + x + 1. Using the polynomial formulation! allows us to develop a simple explanation of the arithmetic involved. Referring back to the representation of the state matrix in Figure 5.9a, we can recast the mix column multiplications as follows: "1 x 2 %" b0 x 3 + b1 x 2 + b2 x + b3 b8 x 3 + b9 x 2 + b10 x + b11 % $x 2 $ ' # 1 '#b4 x 3 + b5 x 2 + b6 x + b7 & b12 x 3 + b13 x 2 + b14 x + b15 & ! E-4
8/5/05 Let's perform the multiplication of the first row of the left-hand matrix with the first column of the right-hand matrix to get the entry in the upper left-hand corner of the target matrix; that is, the polynomial value for S'0,0. We have s" 0,0 = (b0 x3 + b1 x2 + b2 x + b3 ) + (x2 ) (b4 x3 + b5 x2 + b6 x + b7 ) = b4 x5 + b5 x4 + (b0 " b6 )x3 + (b1 " b7 )x2 + b2 x + b3 ! It can easily be shown that: x5 mod (x4 + x + 1) = (x2 + x) x4 mod (x4 + x + 1) = (x + 1) The reader is invited to do the polynomial division to demonstrate these equalities. Using these results, we have: s " = b4(x2 + x) + b5(x + 1) + (b0 " b6)x3 + (b1 " b7)x2 + b2x + b3 0,0 = (b0 " b6 )x3 + (b1 " b4 " b7 )x2 + (b2 " b4 " b5 )x + (b3 " b5 ) ! Expressed in terms of bits, the four bits of S'0,0 are s " = [(b0 " b6), (b1 " b4 " b7), (b2 " b4 " b5), (b3 " b5)] 0,0 Similarly, we can show that: ! E-5
8/5/05 s1,0 = [(b2 " b4), (b0 " b3 " b5), (b0 " b1 " b6), (b1 " b7)] " s " = [(b8 " b14), (b9 " b12 " b15), (b10 " b12 " b13), (b11 " b13)] 0,1 ! s1,1 = [(b10 " b12), (b8 " b11 " b13), (b8 " b9 " b14), (b9 " b15)] " ! ! E-6

More Related Content

Saes tables

  • 1. A PPENDIX E More on Simplified AES E.1 ARITHMETIC IN GF(24).........................................................................................2 E.2 THE MIX COLUMN FUNCTION ...........................................................................4 William Stallings Copyright 2006 Supplement to Cryptography and Network Security, Fourth Edition Prentice Hall 2006 ISBN: 0-13-187316-4 http://williamstallings.com/Crypto/Crypto4e.html
  • 2. 8/5/05 E.1 ARITHMETIC IN GF(24 ) Table E.1 shows the addition and multiplication tables in GF(24 ) modulo x4 + x + 1. For example, consider the product (4 ? C) = (0100 ? 1100). In terms of polynomials, this is the product [x2 ! (x3 + x2 )] mod (x4 + x + 1) = (x5 + x4 ) mod (x4 + x + 1). Because the degree of the polynomial to the right of the mod operator is greater than or equal to the modulus, a division is required to determine the remainder: x + 1 x4 + x + 1 x5 + x4 x5 + x2 + x x4 + x2 + x x4 + x + 1 x2 + 1 In binary, the remainder is expressed as 0101, or 5 in hexadecimal. Thus (4 ? C) = 5, which agrees with the multiplication table in Table E.1. E-2
  • 3. 8/5/05 Table E.1 Arithmetic in GF(24 ) modulo x4 + x + 1 (a) Addition + 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 1 2 3 4 5 6 7 8 9 A B C D E F 1 1 0 3 2 5 4 7 6 9 8 B A D C F E 2 2 3 0 1 6 7 4 5 A B 8 9 E F C D 3 3 2 1 0 7 6 5 4 B A 9 8 F E D C 4 4 5 6 7 0 1 2 3 C D E F 8 9 A B 5 5 4 7 6 1 0 3 2 D C F E 9 8 B A 6 6 7 4 5 2 3 0 1 E F C D A B 8 9 7 7 6 5 4 3 2 1 0 F E D C B A 9 8 8 8 9 A B C D E F 0 1 2 3 4 5 6 7 9 9 8 B A D C F E 1 0 3 2 5 4 7 6 A A B 8 9 E F C D 2 3 0 1 6 7 4 5 B B A 9 8 F E D C 3 2 1 0 7 6 5 4 C C D E F 8 9 A B 4 5 6 7 0 1 2 3 D D C F E 9 8 B A 5 4 7 6 1 0 3 2 E E F C D A B 8 9 6 7 4 5 2 3 0 1 F F E D C B A 9 8 7 6 5 4 3 2 1 0 (b) Multiplication 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 A B C D E F 2 0 2 4 6 8 A C E 3 1 7 5 B 9 F D 3 0 3 6 5 C F A 9 B 8 D E 7 4 1 2 4 0 4 8 C 3 7 B F 6 2 E A 5 1 D 9 5 0 5 A F 7 2 D 8 E B 4 1 9 C 3 6 6 0 6 C A B D 7 1 5 3 9 F E 8 2 4 7 0 7 E 9 F 8 1 6 D A 3 4 2 5 C B 8 0 8 3 B 6 E 5 D C 4 F 7 A 2 9 1 9 0 9 1 8 2 B 3 A 4 D 5 C 6 F 7 E A 0 A 7 D E 4 9 3 F 5 8 2 1 B 6 C B 0 B 5 E A 1 F 4 7 C 2 9 D 6 8 3 C 0 C B 7 5 9 E 2 A 6 1 D F 3 4 8 D 0 D 9 4 1 C 8 5 2 F B 6 3 E A 7 E 0 E F 1 D 3 2 C 9 7 6 8 4 A B 5 F 0 F D 2 9 6 4 B 1 E C 3 8 7 5 A E-3
  • 4. 8/5/05 E.2 THE MIX COLUMN FUNCTION The mix column function operates on each column individually. Each nibble of a column is mapped into a new value that is a function of both nibbles in that column. The transformation was defined in Appendix 5B as follows: "1 4%"s0,0 s0,1% "s0,0 ( s0,1% ( $4 1'$ s =$ # &# 1,0 s1,1 ' # s1,0 & ( s1,1 ' ( & We can recast this in terms of polynomials as follows. The value 1 corresponds to the polynomial 1 ! the value 4 (binary 100) corresponds to the polynomial x2 . Thus, we have: and "1 x 2 %"s 0,0 s 0,1 % "s ( 0,0 s( % 0,1 $x 2 1 '$ s1,0 ' = $ s( s1,1 & # 1,0 s1,1 ' ( & # &# Remember that multiplication is performed modulo x4 + x + 1. Using the polynomial formulation! allows us to develop a simple explanation of the arithmetic involved. Referring back to the representation of the state matrix in Figure 5.9a, we can recast the mix column multiplications as follows: "1 x 2 %" b0 x 3 + b1 x 2 + b2 x + b3 b8 x 3 + b9 x 2 + b10 x + b11 % $x 2 $ ' # 1 '#b4 x 3 + b5 x 2 + b6 x + b7 & b12 x 3 + b13 x 2 + b14 x + b15 & ! E-4
  • 5. 8/5/05 Let's perform the multiplication of the first row of the left-hand matrix with the first column of the right-hand matrix to get the entry in the upper left-hand corner of the target matrix; that is, the polynomial value for S'0,0. We have s" 0,0 = (b0 x3 + b1 x2 + b2 x + b3 ) + (x2 ) (b4 x3 + b5 x2 + b6 x + b7 ) = b4 x5 + b5 x4 + (b0 " b6 )x3 + (b1 " b7 )x2 + b2 x + b3 ! It can easily be shown that: x5 mod (x4 + x + 1) = (x2 + x) x4 mod (x4 + x + 1) = (x + 1) The reader is invited to do the polynomial division to demonstrate these equalities. Using these results, we have: s " = b4(x2 + x) + b5(x + 1) + (b0 " b6)x3 + (b1 " b7)x2 + b2x + b3 0,0 = (b0 " b6 )x3 + (b1 " b4 " b7 )x2 + (b2 " b4 " b5 )x + (b3 " b5 ) ! Expressed in terms of bits, the four bits of S'0,0 are s " = [(b0 " b6), (b1 " b4 " b7), (b2 " b4 " b5), (b3 " b5)] 0,0 Similarly, we can show that: ! E-5
  • 6. 8/5/05 s1,0 = [(b2 " b4), (b0 " b3 " b5), (b0 " b1 " b6), (b1 " b7)] " s " = [(b8 " b14), (b9 " b12 " b15), (b10 " b12 " b13), (b11 " b13)] 0,1 ! s1,1 = [(b10 " b12), (b8 " b11 " b13), (b8 " b9 " b14), (b9 " b15)] " ! ! E-6