Cryptography Tutorials - Herong's Tutorial Examples - v5.42, by Herong Yang
AES MixColumns() Procedure Algorithm
A detailed description of the MixColumns() procedure algorithm is provided. The MixColumns() procedure performs a matrix multiplication of a given 'state' with a static matrix. The MixColumns() procedure is used in the AES encryption process.
The MixColumns() - The MixColumns() procedure performs a matrix multiplication of a given 'state' with a static matrix. The MixColumns() procedure is key procedure used in the AES encryption process.
Here is the algorithm that the MixColumns() procedure should follow:
Procedure Name: MixColumns(state) Input: state: A 4x4 byte array Algorithm: | | |0x02 0x03 0x01 0x01| | | | | |0x01 0x02 0x03 0x01| | | |state| = |0x01 0x01 0x02 0x03| ● |state| | | |0x03 0x01 0x01 0x02| | | Note that "●" represents a matrix multiplication defined as: |a1| |0x02 0x03 0x01 0x01| |b1| |a2| |0x01 0x02 0x03 0x01| |b2| |a3| = |0x01 0x01 0x02 0x03| ● |b3| |a4| |0x03 0x01 0x01 0x02| |b4| is equivalent to: a1 = 0x02●b1 ⊕ 0x03●b2 ⊕ 0x01●b3 ⊕ 0x01●b4 a2 = 0x01●b1 ⊕ 0x02●b2 ⊕ 0x03●b3 ⊕ 0x01●b4 a3 = 0x01●b1 ⊕ 0x01●b2 ⊕ 0x02●b3 ⊕ 0x03●b4 a4 = 0x03●b1 ⊕ 0x01●b2 ⊕ 0x01●b3 ⊕ 0x02●b4 where "⊕" is the binary XOR operation, and "●" is Rijndael's GF (Galois Field) multiplication.
Rijndael's GF multiplication used above can be defined as:
If we express bytes "a" and "b" in a polynomial form: a = 2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0 b = 2^7*b7⊕2^6*b6⊕2^5*b5⊕2^4*b4⊕2^3*b3⊕2^2*b2⊕2^1*b1⊕2^0*b0 then: c = a ● b = ((2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^7*b7 ⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^6*b6 ⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^5*b5 ⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^4*b4 ⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^3*b3 ⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^2*b2 ⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^1*b1 ⊕ (2^7*a7⊕2^6*a6⊕2^5*a5⊕2^4*a4⊕2^3*a3⊕2^2*a2⊕2^1*a1⊕2^0*a0)*2^0*b0 ) ⓜ 0x011b
Now we have only one last operation to understand, the GF modulo, "ⓜ", which can be defined as:
If we say: c = a ⓜ b then should have: a = b●d ⊕ c c < b
Here is an example of Rijndael's GF multiplication:
0x57 ● 0x83 = (2^6 ⊕ 2^4 ⊕ 2^2 ⊕ 2^1 ⊕ 2^0) ● (2^7 ⊕ 2^1 ⊕ 2^0) = ((2^13 ⊕ 2^11 ⊕ 2^9 ⊕ 2^8 ⊕ 2^7) ⊕ (2^7 ⊕ 2^5 ⊕ 2^3 ⊕ 2^2 ⊕ 2^1) ⊕ (2^6 ⊕ 2^4 ⊕ 2^2 ⊕ 2^1 ⊕ 2^0) ) ⓜ 0x011b = ((2^13 ⊕ 2^11 ⊕ 2^9 ⊕ 2^8 ⊕ 2^6 ⊕ 2^5 ⊕ 2^4 ⊕ 2^3 ⊕ 2^0) ) ⓜ 0x011b = 0x2b79 ⓜ 0x011b = 0xc1 The last step can approved by: 0x2b79 = 0x011b●0x28 ⊕ 0xc1 = (2^8 ⊕ 2^4 ⊕ 2^3 ⊕ 2^1 ⊕ 2^0)●(2^5 ⊕ 2^3) ⊕ (2^7 ⊕ 2^6 ⊕ 2^1) = (2^13 ⊕ 2^9 ⊕ 2^8 ⊕ 2^6 ⊕ 2^5) ⊕ (2^11 ⊕ 2^7 ⊕ 2^6 ⊕ 2^4 ⊕ 2^3) ⊕ (2^7 ⊕ 2^6 ⊕ 2^0) = 2^13 ⊕ 2^11 ⊕ 2^9 ⊕ 2^8 ⊕ 2^6 ⊕ 2^5 ⊕ 2^4 ⊕ 2^3 ⊕ 2^0 = 0x2b79
Here is a demonstration on how to calculate 0x2b79 ⓜ 0x011b manually in binary mode:
Express the dividend in binary format: 0x2b79 = 0b10101101111001 Express the divisor in binary format: 0x011b = 0b100011011 Do the manual calculation: 101000 <- quotient divisor ---------------- 100011011 | 10101101111001 <- dividend ⊕ 100011011 ---------------- 100000011001 ⊕ 100011011 -------------- 11000001 <- remainder Convert the remainder to hexadecimal format: 0b11000001 = 0xc1 We get the result: 0x2b79 ⓜ 0x011b = 0xc1
Table of Contents
►Introduction to AES (Advanced Encryption Standard)
What Is AES (Advanced Encryption Standard)?
AES, or Rijndael, Encryption Algorithm
►AES MixColumns() Procedure Algorithm
Example Vector of AES Encryption
AES Standard Decryption Algorithm
AES Equivalent Decryption Algorithm
DES Algorithm - Illustrated with Java Programs
DES Algorithm Java Implementation
DES Algorithm - Java Implementation in JDK JCE
DES Encryption Operation Modes
PHP Implementation of DES - mcrypt
Blowfish - 8-Byte Block Cipher
Secret Key Generation and Management
Cipher - Secret Key Encryption and Decryption
RSA Implementation using java.math.BigInteger Class
Introduction of DSA (Digital Signature Algorithm)
Java Default Implementation of DSA
Private key and Public Key Pair Generation
PKCS#8/X.509 Private/Public Encoding Standards
Cipher - Public Key Encryption and Decryption
OpenSSL Introduction and Installation
OpenSSL Generating and Managing RSA Keys
OpenSSL Generating and Signing CSR
OpenSSL Validating Certificate Path
"keytool" and "keystore" from JDK
"OpenSSL" Signing CSR Generated by "keytool"
Migrating Keys from "keystore" to "OpenSSL" Key Files
Certificate X.509 Standard and DER/PEM Formats
Migrating Keys from "OpenSSL" Key Files to "keystore"