Get best of the week

Description of the basics of AES crypto conversion

Good day, Habr! About 3 months ago, the frontend developer interviewed and the very first question I was asked: “What is AES?” Well, as if I still had an amorphous idea about symmetrically block AES encryption, it was even used in one of the projects to encrypt personal data. But to know the rijndael algorithm and still be able to implement it in javascript, for me at that time it seemed like a difficult task. But! I was challenged and accepted.



Go to the tackle!

As a basis, I took the FIPS197 AES specification dated November 26, 2011.

In the IT field, some of the most famous encryption algorithms are:

  • symmetrical
  • asymmetric

Symmetric algorithms are those algorithms that have one secret key for encryption and the same key for decryption. The advantage of this algorithm is the encryption speed. Disadvantages - the need for a secure channel to transmit this key for decryption.

In turn, symmetric algorithms are divided into two types:

  • blocky
  • streaming

Block ones have the ability to encrypt data in blocks, that is, a predetermined finite number of bytes. This implies the possibility of parallelizing block encryption, that is, to encrypt large amounts of data at the same time, while reducing the time resource.

Stream encrypt character by character.

Advantages for asymmetric algorithms are its secure key storage. Asymmetric - those algorithms that have two keys:

  • publicKey
  • privateKey

publicKey is the key for encryption. Not subject to decryption, which means there is no need for its transfer.
privateKey - the key to decrypt.

The disadvantages of asymmetric algorithms are its relatively slow encryption performance.

Rijndael is a symmetric block encryption algorithm with the ability to resize blocks and private keys from 128 to 256 bits with a difference of 32 bits. It uses linear-substitution transformations and consists of 10, 12 or 14 rounds depending on the key length.
AES - rijndael with a key of 128 bits and a data block of 16 bytes.

Presumably you are familiar with the theory of the following terms:

  • binary number system
  • decimal number system
  • bits
  • bytes
  • XOR (^)

If not, then it doesn’t matter. Read my article "Image Processing ReactJS - NodeJS» or take a look at the examples snipettov reactjs.su

Mathematical concepts in rijndael:


  • The field GF (2⁸) is a finite number of elements, the result of which is the nth natural degree of a prime number. Within the framework of GF (2⁸), arbitrary operations of addition, subtraction, product, division are performed. The field GF (2⁸) is definite.
  • . Rijndael [00000000₂; 11111111₂]. , x. , , :

    a(x)=a₇x⁷ +a₆x⁶ +a₅x⁵ +a₄x⁴ +a₃x³ +a₂x² +a₁x +a₀x;

    , a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀ {0, 1}, :
    87 = 01010111 ( );
    : x⁶ + x⁴ + x² + x + 1;
  • . , , 1 . rijndael m(x):
    m(x)= x⁸ + x⁴ + x³ + x + 1;
  • . XOR, : 1 ^ 1 = 0 ^ 0 = 0; 1 ^ 0 = 0 ^ 1 = 1, :

    , a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀;
    B, b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀;

    A = 87 = 01010111; B = 131 = 10000011;
    A ^ B = a₇, a₆, a₅, a₄, a₃, a₂, a₁, a₀ ^ b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀ = 11010100;
  • . GF(2⁸) ( | -x | = x ) 8, :

    87 x 131 :
    (x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁷ + x⁷ + x⁵ + x³ + x² + x + x⁶ + x⁴ + x² + x + 1.
    . (.4):

    x⁷ + x⁷ = x⁷(1 + 1) = x⁷(1 ^ 1) = x⁷0 = 0;
    (x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1) = x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1.

    m(x) = x⁸ + x⁴ + x³ + x + 1 ( ), rijndael , 8, . . , . :

    (x⁶ + x⁴ + x² + x + 1)(x⁷ + x + 1)/(x⁸ + x⁴ + x³ + x + 1) =
    (x¹³ + x¹¹ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + x³ + 1)/(x⁸ + x⁴ + x³ + x + 1) = |Result| = x⁷ + x⁶ + 1


:


  1. keyExpansion() — ;
  2. addRoundKey() — ;
  3. subBytes() — state;
  4. shiftRows() — state;
  5. mixColumns() — state;
  6. invMixColumns() — mixColumns;
  7. invShiftRows() — shiftRows;
  8. invSubBytes() — subBytes;

AES :


  1. state
    - . [0; 255] ( ASCII Unicode). n- 16 . state ( 4 = [ [], [], [], [] ] ), 16 , 16 :

  2. keyExpansion();
    AES, state. . XOR Rcon.

    Rcon — XOR. keyExpansion() XOR’ Rcon . — 11. 10 .

    let rCon = [
  [ 0x00, 0x00, 0x00, 0x00 ],
  [ 0x01, 0x00, 0x00, 0x00 ],
  [ 0x02, 0x00, 0x00, 0x00 ],
  [ 0x04, 0x00, 0x00, 0x00 ],
  [ 0x08, 0x00, 0x00, 0x00 ],
  [ 0x10, 0x00, 0x00, 0x00 ],
  [ 0x20, 0x00, 0x00, 0x00 ],
  [ 0x40, 0x00, 0x00, 0x00 ],
  [ 0x80, 0x00, 0x00, 0x00 ],
  [ 0x1b, 0x00, 0x00, 0x00 ],
  [ 0x36, 0x00, 0x00, 0x00 ],
];
  3. addRoundKey();

    state , . addRoundKey XOR’ state, . ’XOR’ state , :




  4. 10 , 10 . 9 4 :

    • subBytes();
    • shiftRows();
    • mixColumns();
    • addRoundKey();

    10- :

    • subBytes();
    • shiftRows();
    • addRoundKey();

  5. subBytes();

    state S-box:



    State hex , : 01010011 -> 0101 | 0011 -> 53h



    53h edh

    S-box
    const sBox = [
  0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
  0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
  0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
  0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
  0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
  0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
  0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
  0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
  0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
  0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
  0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
  0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
  0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
  0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
  0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
  0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16,
];


  6. shiftRows();

    3- :


  7. mixColumns();

    . a(x) = {03}x³ + {01}x² + {01}x + {02}. state a(x). :







AES :


  1. keyExpansion();


  2. 10 , .

    9 4 , , :

    • addRoundKey();
    • invMixColumns();
    • invShiftRows();
    • invSubBytes();

    10-:

    • addRoundKey();
    • invShiftRows();
    • invSubBytes();

  3. addRoundKey();

    , Rcon
  4. invMixColumns ();

    The invMixColumns function performs the multiplicatively inverse multiplication operation according to the rules of multiplying the algorithm by the constant function a⁻¹ (x) of a particular state column:




  5. invShiftRows ();

    Inverse transformation shiftRows () - cyclic shift to the right:


  6. invSubBytes ();

    Inversion subBytes () - the reverse replacement of state bytes, which is obviously represented in hex according to the fixed inverse S-box table:



Bibliography:

  1. Specification for the AES
  2. Advanced Encryption Standard (AES)
  3. Pole Galois
  4. Cyclic codes
  5. Textbook for high schools A.N. Stepanov - Computer Science Course - Information Data Security
  6. Snippets

More articles:


All Articles