2022-1 정보보호이론

created : 2022-04-17T23:59:34+00:00
modified : 2022-04-18T16:27:32+00:00

lectures

Chapter 1 Introduction

1.1. Security goals

1.2 Attacks

1.3. Services and Mechanisms

1.3.1. Security Services

Chapter 2. Mathematics of Cryptography

2.1 Integer Arithmetic

2.1.1. Set of Integers

2.1.2. Binary Operations

2.1.3. Integer Division

2.1.4. Divisbility

2.2. Modular Arithmetic

2.2.1. Modulo Operator

2.2.3. Congruence

2.2.4. Operation in $Z_n$

2.2.5. Inverses

2.2.6. Additive and Multiplication Tables

2.2.7. Different Sets

2.2.8. Two More sets

Chapter 3. Traidtional Symmetric-Key Ciphers

3.1. Introduction

3.1.1. Kerckhoff’s Principle

3.1.2. Cryptanalysis

3.2. Substitution ciphers (대치암호)

3.2.1. Monoalphabetic Ciphers

3.2.2. Polyalphabetic Ciphers

3.3. Transposition Ciphers (치환 암호)

3.3.1. Keyless Transposition Ciphers

3.3.2. Keyed Transposition Ciphers

3.3.3. Combining Two Approaches

3.4. Stream and block ciphers

3.4.1. Stream Ciphers

3.4.2. Block Ciphers

Chapter 6. Data Encryption Standard (DES)

6.1. Introduction

6.1.1. History

6.1.2. Overview

6.2. DES structure

6.2.1. Initial and Final Permutations

6.2.2. Rounds

6.2.3. Cipher and Reverse Cipher

mixer(leftBlock[32], rightBlock[32], RoundKey[48]) { copy(32, rightBlock, T1) function(T1, RoundKey, T2) exclusiveOr(32, leftBlock, T2, T3) copy(32, T3, leftBlock) }

swapper(leftBlock[32], rightBlock[32]) { copy(32, leftBlock, T) copy(32, rightBlock, leftBlock) copy(32, T, rightBlock) }

function(inBlock[32], RoundKey[38], outBlock[32]) { permute(32, 48, inBlock, T1, ExpansionPermutationTable) exclusiveOr(48, T1, RoundKey, T2) substitute(T2, T3, SubstituteTables) permute(32, 32, T3, outBlock, StraightPermutationTable) }


- Key Generation:
  - The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key.

### 6.3 DES Analysis
- Critics have used a strong manifier to analyze DES.
- Tests have been done to measure the strength of some desired properties in a block cipher.

#### 6.3.1. Properties
- Two desired properties of a block cipher are the (1)avalanche effect and the (2)completeness.
- To check the (1)avalanche effect in DES, let us encrypt two plaintext blocks (with the same key) that differ only in one bit and observe the differences in the number of bits in each round.
- Although the two plaintext blocks differ only in the rightmost bit, the ciphertext blocks differ in 29 bits. This means that chaning one bit of the plaintext creates a change of approximately 45 percent in hte ciphertext.
- Completeness effect means that each bit of the ciphertext needs to depend on many bits on the plaintext.

#### 6.3.2. Design Criteria
- Shannon, 1949
- Diffusion(확산) : ciphertext와 plaintext의 관계를 숨기는 것
- Confusion(혼돈) : ciphertext와 key의 관계를 숨기는 것
- Product cipher: Substitution과 Transposition(Permutation)을 결합하여 만든 cipher
- Feistel ciphers are a class of product cipher.

- S-Boxes 와 P-Boxes:
  - confusion과 diffusion을 잘 만들고 있다.
- Number of Rounds:
  - DES uses sixteen rounds of Feistel ciphers. After eight rounds, the ciphertext is throughly a random function of plaintext and key. DES with less than 16 rounds are more vulnerable to attacks.

#### 6.3.3. DES Weaknesses
- During the last few years critics have found some weaknesses in DES.
- Weaknesses in Key:
  - Key size (56bits) is too small: 2^56 keys
  - Weak keys exist.
- Key complement:
  - In the key domain (2^56), definitely half of the keys are complement of the other half. A key complement can be made by inverting (changing 0 to 1 or 1 to 0) each bit in the key. Does a key complement simplify the job of the cryptanalysis? It happens that it does. The attacker can use only half of the possible keys (2^55) to perform brute-force attack.
  - $$C=E(K, P) \rightarrow \bar C = E(\bar K, \bar P)$$

### 6.4 Multiple DES
- The major criticism of DES regards its key length. This means that we can use double or triple DES to increase the key size.

#### 6.4.1. Double DES
- The first approach is to use double DES(2DES)
- Use two different keys k1 and k2 (= 112 bits)
- Meet-in-the-Middle Attack:
  - However, using a known-plaintext attack called meet-in-the-middle attack proves that double DES improves this vulnerability slightly (to 2^57 tests), but not tremendously (to 2^112).
  - 즉 112 bit인데 57 bit 효과만 나타남

#### 6.4.2. Triple DES
- Triple DES with Three keys:
  - Triple DES with three keys is used by many applications such as PGP.
  - $$E_{k3}(D_{k2}(E_{k1}(P))) = C$$
  - $$D_{k1}(E_{k2}(D_{k3}(C))) = P$$

### 6.5. Security of DES
- DES, as the first important block cipher, has gone through much scrutiny. Among the attempted attacks, three are of interest: brute-force, differential cryptanalysis, and linear cryptanalysis.

## Chapter 4. Mathematics of Cryptography
### 4.1. Algebraic strucutres
- Cryptography requires sets of integers and specific operations that are defined for those sets. The combination of the set and the operations that are applied to the elements of the set is called an algebraic struture.

#### 4.1.1. Groups
- $<G, \cdot>$ is a group:
  - $G$ : a set elements
  - $\cdot$ : a binary operation
  - if it satisifes four properties (or axioms).
- A commutative (or abelian) group satisfies an extra property, commutativity.

- Closure(닫힘) : $a \cdot b \in G$ for any $a, b \in G$
- Associativity(결합) : $a \cdot (b \cdot c) = (a \cdot b) \cdot c$
- Commuativity(교환) : $a \cdot b = b \cdot a$ for any $a, b \in G$ (abelian group)
- Existence of identity(항등원) : there is $e \in G$ such that $a \cdot e = e \cdot a = a$ for all $a \in G$
- Existence of inverse(역) : there is $a' \in G$ such that $a \cdot a' = a' \cdot a = e$ for each $a \in G$

- Finite Group: the set has a finite number of elements.
- Order of group: $\vert G \vert$ = number of elements (집합의 크기)

#### 4.1.3. Field (체)
- A field, denoted by $<G, \cdot, \square>$, satisfies 11 properties:
  - G: set
  - $\cdot, \square$ : two binary operators
- $<G, \cdot>$ is an abelian group
- $<G, \square>$ is an abelian group
- Distribution(배분) : $a \square (b \cdot c) = (a \square b) \cdot (a \square c)$ for any $a,b,c \in G$

- Example :
  - $<R, +, *>$ is a field.
  - 정수들로 이루어진 field 필요. $GF(p), GF(2^n)$

- GF(p) field (Galois Field, p는 소수)
- $GF(p) = <Z_p, +, \times>$, p는 소수

### 4.2. $GF(2^n)$ Fields
- In cryptography, we often need to use four operations (addition, subtraction, ultiplicationh, and division). In other words, we need to use fields.

#### 4.2.1. Polynomials 다항식
- A polynomial of degree(차수) n-1 is
- $$f(x) = a_{n-1}x^{n-1} + a_{n-2} x^{n-2} + \cdots + a_1 x^1 + a_0 x^0$$
- where $x^i$ is called the i-th term and $a_i$ is called the coefficient of the i-th term.
- Addition and subtraction on polynomials are the same operation.

- Additive identity: 0
- Additive inverse: itself

- Polynomial multiplication:
  1. The coefficent multiplication is done is GF(2).
  2. The multiplying $x^i$ by $x^j$ results in $x^{i+j}$.
  3. The multiplication may create terms with degree more than $n-1$, which means the result needs to be reduced using a modulus polynomial (or irreducible polynomial).

- Multiplicative identity: 1
- Multiplicative inverse: use the extended Euclidean algorithm

#### 4.2.3. Summary
- The finite field GF(2^n) can be used to define four operations of addition, subtraction, multiplication and division over n-bit words.

## Chapter 7. Advanced Encryption Standard (AES)
### 7.1. Introduction
- The Advanced Encryption Standard (AES) is a symmetric-key block cipher published by the National Institute of Standards and Technology(NIST) in December 2001.

#### 7.1.1. History
- NIST: DES를 대체할 새 대칭 키 블록 암호 선정 절차
- 벨기에: Vincent Rijmen and Joan Daemen의 Rijndael 암호에 기반
- In February 2001, NIST announced that a draft of the Federal Information Processing Standard (FIPS) was available for public review and comment.
- Finally, AES was published as FIPS 197 in the Federal Register in December 2001.

#### 7.1.3. Rounds
- AES is a non-Feistel cipher that encrypts and decrypts a data block of 128 bits. It uses 10, 12, or 14 rounds. The key size, which can be 128, 192, or 256 bits, depends on the number of rounds.
- AES has defined three versions (AES-128, -192, -256), with 10, 12, and 14 rounds.
- Each version uses a different cipher key size (128, 192, or 256 bits), but the round keys are always 128 bits.

#### 7.1.4. Data Units
- 1 byte = 8bits
- 1 word = 4 bytes =32 bits
- 1 block = 4 words = 16 bytes = 128 bits

#### 7.1.5. Strucutre of Each Round
- AES-128 version: 10 rounds

Cipher(InBlock[16], OutBlock[16], w[0 … 43]) { BlockToState(InBlock, S)

S <- AddRoundKey(S, w[0…3]) for (round = 1 to 10) { S <- SubBytes(S) S <- ShiftRows(S) if (round != 10) S <- MixColumns(S) S <- AddRoundKey(S, w[4 * round, 4 * round + 3]) } StateToBlock(S, OutBlock); }


### 7.2. Transformations
- To provide security, AES uses four types of transformations:
  - substitution(SubBytes), permutation(ShiftRows), mixing(MixColumns), and key-adding(AddRoundKey)

#### 7.2.1. Substitution
- AES, like DES, uses substitution. AES uses two invertible transformations.
- SubBytes:
  - The first transformation, SubBytes, is used at the encryption site. To subsitute a byte, we interpret the byte as two hexadecimal digits.
  - SubBytes table
  - Transformation Using GF(2^8) Field
  - AES also defines the transformation algebraically using the GF(2^8) field with the irreducible polynomial ($x^8 + x^4 + x^3 + x + 1$)
  - $d = X \cdot s^{-1} \oplus y$
- InvSubBytes:
  - $s=(X^{-1} \cdot (d \oplus y))^{-1}$

#### 7.2.2. Permutation
- Another transformation found in a round is shifting, which permutes the bytes.
- ShiftRows:
  - In the encryption, the transformation is called ShiftRows.
- InvShiftRows:
  - In the decryption, the transformation is called InvShiftRows and the shifting is to the right.

#### 7.2.3. Mixing
- We need an interbyte transformation that changes the bits inside a byte, based on the bits inside the neighboring bytes.
- MixColumns:
  - The MixColumns transformation operates at the column level; it transforms each coulmn of the stae to a new column.

- InvMixColumns:
  - The InvMixColumns transformation is basically the same as the MixColumns transformation.
  - The MixColumns and InvMixColumns transformations are inverses of each other.

#### 7.2.4. Key Adding
- AddRoundKey:
  - AddRoundKey proceeds one column at a time. AddRoundKey adds a round key word with each state column matrix; the operation in AddRoundKey is matrix addition.
  - The AddRoundKey transformation is the inverse of itself.

### 7.3. Key Expansion
- To create round keys for each round, AES uses a key-expansion process. If the number of rounds is $N_r$, the key-expansion routine creates $N_r + 1$ 128-bit round keys from one single 128-bit cipher key.

#### 7.3.1. Key Expansion in AES-128
- RotWord(w) : one-byte circular left shift, i.e., [b0, b1, b2, b3] is transformed into [b1, b2, b3, b0]
- SubWord(w) : SubBytes transformation applied to four bytes

KeyExpansion([key_0 to key_{15}], [w_0 to w_{43}]) { for (i = 0 to 3) w_i <- key_{4i} + key_{4i+1} + key_{4i+2} + key_{4i+3}

for (i = 4 to 43) { if (i mod 4 != 0) w_i <- w_{i-1} \oplus w_{i-4} else { t <- SubWord(RotWord(w_{i-1})) \oplus RCon_{i/4} w_i <- t \oplus w_{i-4} } } }


- Each round key in AES depends on the previous round. The dependency, however, is nonlinear because of SubWord transformation. The addition of the round constants also guarantees that each round key will be different from the previous one.

### 7.4. Ciphers
- AES uses four types of transformations for encryption and decryption. In the standard, the encryption algorithm is referred to as the cipher and the decryption algorithm as the inverse cipher.

Cipher (InBlock[16], OutBlock[16], w[0…43]) { BlockToState(InBlock, S)

S <- AddRoundKey(S, w[0…3]) for (round = 1 to 10) { S <- SubBytes(S) S <- ShiftRows(S) if (round != 10) S <- MixColums(S) S <- AddRoundKey(S, w[4 * round, 4 * round + 3]) }

StateToBlock(S, OutBlock); } ```