CS152-lecture-20210611

Fields #

A field is

  • A collection of \( F \) objects
  • Two binary operations \( \times \) and \( + \) closed on \( F \) .
  • \( F \) contains multiplicative identity 1 where \( (1 \times y) = y \) for all \( y \) in \( F \) .
  • \( F \) contains additive identity 0 where \( (0 + y) = y \) for all \( y \) in \( F \) .
  • For each \( y \) in \( F \) , there exists a \( z \) in \( F \) such that \( (y + z) = 0 \) (additive inverse).
  • For each \( y \) in \( F \) , except 0, there exists a \( z \) in \( F \) such that \( (y \times z) = 1 \) (multiplicative inverse).
  • Associative, commutative, distributive laws work as expected

Shorthands

  • \( a^{-1} \) is \( a \) ’s multiplicative inverse
  • \( -a \) is \( a \) ’s additive inverse
  • \( a-b \) is short for \( a + - b \)
  • \( a / b \) is short for \( a \times b^{-1} \)

Field examples #

  • \( \mathbb{R} \) with standard addition and multiplication form a field (real numbers).
  • \( \mathbb{Q} \) with standard addition and multiplication form a field (rational numbers).
  • \( \mathbb{Z} \) with standard addition and multiplication doesn’t form a field (integers).
    • \( a^{-1} \) doesn’t exist for most \( a \)
  • \( \mathbb{Z}_p \) forms a field with \( p \) prime and addition and multiplication \( \mod p \) .
    • \( p \) must be prime to make sure every element has a multiplicative inverse.
Theorem: If \( p \) is prime, then there is a field of size \( p^n \) for each \( n > 0 \).

\( \mathbb{Z}_p \) is not convenient for high-speed processing: \( \mod p \) is expensive and standard data type don’t hold a prime number of values.

Since 2 is prime, there is a field of size \( 2^n \) for all \( n > 0 \) . This is promising because all data types can hold power-of-two different values.

Galois Fields #

Evariste Galois died age 20 in a duel, 1821

The set of all bit sequences of length \( n \) form a field called \( GF(2^n) \) . Because of the above theorem, there is a guarantee to have a field in a size of \( 2^n \) . We will use \( GF(256) \) for this class.

GF(256) = {00000000, 00000001, 00000010, ..., 11111111}

Addition

  • Interpret the bits as coefficients of a degree 7 polynomial with variable \( x \)
  • Add the two polynomlials to keep coefficients 0 or 1, mod each coefficient by 2
  • Concat the coefficients of the resulting degree 7 polynomial
    • Shortcut, xor’ing the two bytes produces the same result

Multiplication

  • Interpret the bits as coefficients of a degree 7 polynomial with variable \( x \)
  • Multiply the two polynomials, to keep coefficients 0 or 1, mod each coefficient by 2
  • Mod the result by \( x^8 + x^4 + x^3 + x^1 + x^0 \)
  • Concat the coefficients of the resulting degree 7 polynomial
    • No shortcut, multiplication is expensive

GF(256) example #

Addition in \( GF(256) \) ,

\[\begin{aligned} 00001001 + 10000001 &= x^3 + x^0 + x^7 + x^0 \\ &= x^7 + x^3 + 2x^0 \\ &\text{mod coefficients by 2} \\ &= x^7 + x^3 \\ &= 10001000 \end{aligned}\]

Multiplication in \( GF(256) \) ,

\[\begin{aligned} 00001001 \times 10000001 &= (x^3 + x^0)(x^7 + x^0) \mod x^8 + x^4 + x^3 + x^1 + x^0 \\ &= x^{10} + x^7 + x^3 + x^0 \mod x^8 + x^4 + x^3 + x^1 + x^0 \\ &= x^7 + x^6 + x^5 + x^2 + x^0 \\ &= 11100101 \end{aligned}\]
Note: We are modding by the given polynomial above.

Padding #

Recall that our block cipher modes of operation use blocks of size \( b \) . The more common scenario ends with a block that is less than the size of \( b \) . So we can use padding to help the mode of operation.

In CTR mode, since its producing a key stream, they do not require padding. Stream ciphers do not require padding.

image_2021-06-11-17-30-48

In the other modes, ECB and CBC, we need our input to be a multiple of \( b \) in order for it to work. In a non-stream cipher, to ensure a size that is a multiple of \( b \) , it has to go through a padding process.

image_2021-06-11-17-33-01

These padding functions need

  • unpad is the inverse of pad
  • \( P' \) is a multiple of \( b \)
  • efficiency

10* padding #

  • append a 1 bit, then
  • append enough 0 to next multiple of \( b \)

So if \( b = 16 \) ,

b  = 16
p  = 1111 0000 1111         // needs padding to be 16 bits
p' = 1111 0000 1111 1000    // padded

So how do we distinguish between padded and not? We decide to always pad even if it already is a multiple of \( b \) .

So

b  = 16
p  = 1111 0000 1111 0000
p' = 1111 0000 1111 0000 1000 0000 0000 0000
Note: Whenever we do ECB/CBC, we will always apply padding to avoid ambiguity with the receiver.

To unpad

  • We will decrypt the ciphertext to get \( P' \)
  • Remove all 0 and strip the rightmost 1
b  = 16
p' = 1111 0000 1111 0000 1000 0000 0000 0000
// strip zeros from right of p'
p' = 1111 0000 1111 0000 1
// strip 1 from right of p' to get p
p  = 1111 0000 1111 0000

If we’re at \( b - 1 \) bits,

p  = 1111 1111 1111 111     // one away from 16
p' = 1111 1111 1111 1111    // adding the 1 made it a multiple of b
                            // no 0s needed