- 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

### 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

- 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.

## Chapter 9. Mathematics of Cryptography
### 9.1. Primes
- Asymmetric-key cryptography uses primes extensively. The topic of primes is a large part of any book on number theory.

#### 9.1.1. Definition
- Positive integers:
  - Number 1, Primes, Composites
  - A prime is divisible only by itself and 1.

#### 9.1.2. Cardinality of Primes
- Infinite Number of Primes
- Number of Primes:
  - $$\frac{n}{ln(n)} < \pi(n) < \frac{n}{ln(n) - 1.08366}$$
    - for large n
  - $$\pi(n) \approx \frac{n}{ln(n)}$$
    - for large n

#### 9.1.3. Checking for Primeness
- Given a number n, how can we determine if n is a prime?
- We need to see if the number is divisible by all primes less than $\sqrt n$
- We know that this method is inefficient, but it is a godo start.
- Any composite integer can be expressed as a product of prime numbers.

#### 9.1.4. Euler's Phi-Function
- $\phi(n)$ : Euler's phi-function:
  - number of positive integers that are both smaller than n and relatively prime to n.

- Properties:
  - $\phi(1) = 0$
  - $\phi(p) = p - 1$, if p is a prime.
  - $\phi(m \times n) = \phi(m) \times \phi(n)$, if m and n are relatively prime. $m \ge 2, n \ge 2$
  - $phi(p^e) = p^e - p^{e - 1}$, if p is a prime

#### 9.1.5. Fermat's Little Theorem
- First Version:
  - If $p$ is a prime and $a$ is an integer such that $p$ does not divide $a$, then:
  - $$a^{p-1} \text{ mod } p = 1$$

- Second Version:
  - if $p$ is a prime and $a$ is an integer, then:
    - $$a^p \text{ mod } p = a \text{ mod } p$$

- Multiplicative Inverse:
  - If $p$ is a prime and $0 < a < p$, then:
    - $$a^{-1} \text{ mod } p = a^{p - 2} \text{ mod } p$$

#### 9.1.6. Euler's THeorem
- If $a$ and $n$ are relatively prime, then:
  - $$a^{\phi(n)} \text{ mod } n = 1$$
  - n이 소수이면, Fermat's Little Theorem이 됨.

#### 9.1.7. Generatign Primes
- Mersenne Primes:
  - A number in the form $M_p = 2^p - 1$, $p$ prime, is called a Mersenne number and may or may not be a prime.

### 9.2. Primality Testing
- Finding an algorithm to correctly and efficiently test a very large integer and output a prime or a composite has always been a challenge in number theory, and consequently in cryptography. However, recent developments look very promising.

#### 9.2.1. Deterministic Algorithms

- 수행시간 : $n_b$ = no. of bits of n

#### 9.2.2. Probabilistic Algorithms
- Fermat test

- Square Root Test:
  - If n is a prime, then $sqrt 1$ mod n = {1, n-1}

- Miller-Rabin Test: Fermat test + Square Root test:

#### 9.2.3. Recommended Primality Test
- Today, one of the most popular primality test is combination of the divisibility test and the Miller-Rabin test.
  1. Choose an odd integer, n.
  2. Do the divisibility tests on primes 3,5,7,11,13,17,19,23.
  3. Choose a set of bases, say 10 bases.
  4. Do the Miller-Rabin test on each of these bases.:
    - If any of them failes, then go to step 1.
    - If the test passes for all 10 bases, then declare n as a prime.

### 9.3. Factorization
- Factorization has been the subject of continuous research in the past; such research is likely to continue in the future. Factorization plays a very important role in the security of several public-key cryptosystems.

#### 9.3.1. Fundamental Theorem of Arithmetic
- Any positive integer n can be written uniquely in a prime factorization form. $p_1, p_2, ... p_k$ are primes, and $e_1, e_2, ..., e_k$ are positive integers.:
  - $$n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$$

### 9.6. Exponentiation and Logarithm
- Fast Exponentiation

## Chapter 10. Asymmetric-Key (Public-Key) Cryptography
### 10.1 Introduction
- Symmetric and public-key cryptography will exist in parallel and continue to serve the community. We actually belive that they are complements of each other; the advantages of one can compensate for the disadvantages of the other.

- Symmetric-key cryptography : sharing secrecy
- public-key cryptography : personal secrecy

#### 10.1.1. Keys
- PUblic key cryptography uses two separate keys:
  - one private key and one public key

#### 10.1.2. General Idea
- Plaintext/Ciphertext:
  - Plaintext and ciphertext are treated as integers in public-key cryptography.
- Encryption/Decryption:
  - $C=f(K_{pulibc}, P), P = g(K_{private}, C)$

#### 10.1.3. Need for Both
- There is a very important fact that is cometimes misunderstood: The advent of public-key cryptogrpahy does not eliminate the need for symmetric-key cryptography.
- Symmetric-key: faster. Good for encryption of large messages
- Public-key: slow, but needed for authentication, digital signature, and key exchange.

#### 10.1.4. Trapdoor One-Way Function
- The main idea behind public-key cryptogaphy is the concept of the trapdoor one-way function
- One-Way Function: $y=f(x)$
  - $f$ is easy to compute. Given $x,y=f(x)$ can be easily computed.
  - $f^{-1}$ is difficult to compute. Given $y$, it is computationally infeasible to compute $x=f^{-1}(y)$

- Trapdoor One-way Function:
  - Given $y$ and $a$ trapdoor (secret), $x$ can be computed easily $x=f^{-1}(y)$.

- Every public-key cryptography depends on a trapdoor one-way function.

### 10.2. RSA Cryptosystem
- The most common public-key algorithm is the RSA cryptosystem, named for its inventors (Rivest, Shamir, and Adleman, 1977).

#### 10.2.1. Introduction
- Plaintext : $P$, $P$ is an integer and $P < n$
  - Encryption: $C=P^e \text{ mod } n$
- Ciphertext : $C$, $C$ is an integer and $C < n$:
  - Decryption: $P=C^d \text{ mod } n$
- $e,n$ : public key
- $d$ : private key

#### 10.2.2. Procedure
- RSA key generation 키 생성:
  1. 두 소수 p,q, 생성, p != q
  2. n = p * q 계산
  3. $\phi(n) = (p - 1)(q - 1)$ 계산
  4. $e$ 선택: $1 < e < \phi(n)$ 이고, $e$와 $\phi(n)$ 은 서로소
  5. $d = e^{-1} \text{ mod } \phi(n)$ 계산

- $p, q, \phi(n)$ 모두 폐기
- In RSA, $p$ and $q$ must be at least 512 bits; $n$ must be at least 1024 bits.

#### 10.2.4. Attacks on RSA
- Potential attacks on RSA:
  - Factorization:
  - Chosen-ciphertext:
  - Encryption exponent: Coppersmith, broasdcast, related messages, and short pad
  - Decryption exponent: Revealed and low exponent
  - Plaintext: SHort message ,cyclic, and unconcealed
  - Modulus: Common modulus
  - Implementation: Timing and power

- Factorization attack:
  - $n$ is so large that it is infeasible to factor it in a reasonable time.
  - If Eve can factor $n$ and obtaion $p$ and $q$, she can calculate $\phi(n) = (p - 1)(q - 1)$. She then calculates $d=e^{-1} \text{ mod } \phi(n)$ because $e$ is public.
  - There are many factorization algorithms, but none of them can factor a large integer with polynomial time complexity. $n$ must be at least 1024 bits.
  - RSA is secure as long as an efficient algorithm for factorization has not been found.
- RSA reommendations based on theoretical and experimental results:
  1. The number of bits for $n$ should be at least 1024.
  2. $p$ and $q$ must each be at least 512 bits
  6. n must not be shared.
  7. $e$ should be $2^{16} + 1$ or an integer close to this.
  8. If $d$ is leaked, we must change $n$ as well as both $e$ and $d$.

#### 10.2.6. OAEP
- Optimal asymmetric encryption padding
- Encryption:
  1. m-bit message M이 mbit가 안되면 padding하여 m bit로 만든다.
  2. random number r of k bits 생성
  3. G(r) 계산. G는 public one-way 함수(k bit를 m bit로 확대, k < m)
  4. $P_1 = M \bigoplus$ G(r)$ 계산. $P_1$ : masked message (m bit)
  5. $P_2 = H(P_1) \bigoplus r$. H는 another public one-way 함수(m bit를 k bit로 축소)
  6. $C=(P_1 \vert \vert P_2)^e \text{ mod } n$으로 암호

- Decryption:
  1. 복호 $P = C^d \text{ mod } n = P_1 \vert \vert P_2$. $P_1$와 $P_2$를 얻음.
  2. $r$ 얻음. $H(P_1) \bigoplus H(P_1) \bigoplus r = r$
  3. 마스크 없앰. $G(r) \bigoplus P_1 = G(r) \bigoplus M \bigoplus G(r) = M$
  4. M에서 padding을 없애면 원래 메시지 얻음

- Applications:
  - RSA is slow if the message is long.
  - RSA is useful for short messages.
  - RSA is used in digital signatures and others that often need to encrypt a small message without having access to a symmetric key.

### 10.4. ElGamal Cryptosystem
- Besides RSA and Rabin, another public-key cryptosystem is ElGamal. ElGamel is based on the discrete logarithm problem
- Discrete Logarithm (이산 대수):
  - $y= g^x \text{ mod } p$:
    - Given $p,g$ and $x$, it is easy to compute y.
    - Given $p, g$ and $y$, however, it is computationally infeasible to compute $x$.
- discrete logarithm problem $\approx$ factorization
- Key Geneartion:
  1. $p$ : 소수 생성
  2. $e_1$ 선택, $e_1$ 은 $<Z_p^*, \times>$의 primitive root
  3. $d$ 선택, $1 \le d \le p-2$
  4. $e_2=e_1^d \text{ mod } p$ 계산
- 공개키 : $e_1, e_2, p$
- 개인키 : $d$
- $e_1, e_2, p$를 알아도 $d$를 계산하는 것은 어려움
- Encryption:
  1. $r$ 랜덤 선택, $1 \le r \le p-1$, $r$ 비밀
  2. $C_1 = e_1^r \text{ mod } p$ 계산
  3. $C_2 = M e_2^r \text{ mod } p$ 계산
- $(C_1, C_2)$가 $M$의 암호문
- Decryption:
  1. $M = C_2 / C_1^d \text{ mod } p$ 계산
- RSA와 달리 특별한 정리 필요 없음.

### 10.5. Elliptic Curve Cryptosystems
- Although RSA and ElGamal are secure asymmetric-key cryptosystems, their security comes with a price, their large keys. Researchers have looked for alternatives that give the same level of security with smaller key sizes. One of these promising alternatives is the elliptic curve cryptosystem (ECC).

#### 10.5.1. Elliptic Curves over Real Numbers
- The general equiation for an elliptic curve is:
  - $$y^2 + b_1 xy + b_2 y = x^3 + a_1 x^2 + a-2 x + a_3$$
- Elliptic curves over real numbers use a special class of elliptic curves of the form:
  - $$y^2 = x^3 + ax + b$$:
    - where $4a^3 + 27b^2 \not = 0$
  - In this case, the curves have three distinct (real or complex) roots.

##### Point addition
- Case 1: 두개의 다른점
  - $$\labmda = (y_2 - y_1) / (x_2 - x_1)$$
  - $$x_3 = \lambda^2 - x_1 - x_2, y_3 = \lambda(x_1 - x_3) - y_1$$
- Case 2: 접선:
  - $$\lambda = (3x_1^2 + a) / (2 y_1)$$
  - $$x_3 = \lambda^2 - 2 x_1, y_3 = \lambda(x_1 - x_3) - y_1$$
- Case 3: 점과 자기역:
  - $P + (-P) = O$

#### 10.5.2. Elliptic Curves over GF(p)
- The coordinates of the points are over the GF(p) field with prime p.
  - $$y^2 \text{ mod } p = (x^3 + ax + b) \text{ mod } p$$
    - where $x,y,a$, and $b$ are in $Z_p$, and $(4a^3+27b^2) \text{ mod } p \not = 0$
- $E_p(a, b)$ consists of all points of $(x, y)$ that satisfies the equation, and $O$, the zero point.

- Finding an Inverse:
  - The inverse of a point $(x, y)$ is $(x, -y)$, where $-y$ is the additive inverse of $y \text{ mod } p$.

- Adding two points:
  - We use the elliptic group defined over real numbers, but calculations are done in GF(p).
  - Instead of subtraction and division, we use additive and multiplicative inverses.

#### 10.5.4. ECC Simulating ElGamal
- Generating Public and Private Keys:
  1. Choose $E_p(a, b)$ over $GF(p)$.
  2. Choose a point $e_1 = (x_1, y_1)$ in $E_p(a, b)$.
  3. Choose an integer $d$.
  4. Calculate $e_2 = (x_2, y_2) = d \times e_1$
  5. Announce $p,a,b,e_1$ and $e_2$ as public key, keep $d$ as private key.

- Encryption:
  - Select $P$, a point in $E_p(a, b)$, as plaintext.
  - Choose a random positive integer $r$.
  - Calculate a pair of points:
    - $$C_1 = r \times e_1, C_2 = P + r \times e_2$$

- Decryption:
  - $$P = C_2 - (d \times C_1)$$

- Easy to calculate $e_2$ from $d$ and $e_1$. $e_1$ and $e_2$ are public, but computationally difficult to calculate $d$ from $e_1$ and $e_2$.
- elliptic curve discrete logarithmic problem(ECDLP)

## Chapter 11. Message Integrity and Message Authentication
### 11.1 Message Integrity
- The cryptography systems that we have studied so far provide secrecy, or confidentiality, but not integrity. However, there are occasions where we may not even need secrecy but instead msut have integrity.
#### 11.1.1. Document and Fingerprint
- 문서(document)의 무결성(integrity) 보장
- 도장, 사인, 지장(finger print)

#### 11.1.2. Message and Message Digest
- Message : Digital Document
- Message Digest : finger print

#### 11.1.3. Difference
- Two pairs (document/fingerprint) and (message/message digest) are similar, with some differences.:
  - document and fingerprint: physically linked together.
  - message and message digest : can be unlinked separately.
- message digest needs to be safe from change.

#### 11.1.4. Checking Integrity

#### 11.1.5. Cryptographic Hash Function Criteria
- Cryptographic hash function h: for a message M, $y=h(M)$:
  1. $h$ can be applied to a message of any size
  2. $h$ produces a fixed-length output.
  3. Given $M$, it is easy to compute $y$.
  4. Given $y$, it is computationally difficult to find any message $M$ such that $h(M) = y$. : Primage resistance
  5. Given $M$ and $y=h(M)$, it is computationally difficult to find another message $M'(\not = M)$ such that $h(M') = y$. : Second preimage resistance
  6. It is computationally difficult to find a pair of messages $M$ and $M'(M \not = M')$ such that $h(M) = h(M')$ : Collision resistance

### 11.2. Random Oracle Model
- The Random Oracle Model, which was introduced in 1993 by Bellare and Rogaway, is an ideal mathmatical model for a cryptographic hash function.

#### 11.2.1. Pigeonhole Principle
- If $n$ pigeonholes are occupied by $n+1$ pigeons, then at least one pigeonhole is occupied by two pigeons. The generalized version of the pigeonhole principle is that if $n$ pigeonholes are occupied by $kn +1$ pigeons, then at least one pigeonhole is occupied by $k+1$ pigeons.

#### 11.2.2. Birthday Problems
- "likely" menas "with probability $\ge$ 1/2"
- Problem 1:
  - What is the minimum number of students, $k$, in a classroom such that it is likely that at least one student has a predefined birthday?
  - $$1 - \frac{1}{N} \approx e^{- \frac{1}{N}}$$
  - $$e^{-\frac{k}{N}} \le \frac{1}{2}$$
  - $$-\frac{k}{N} \le ln \frac{1}{2} = - ln 2$$
  - $$k \le ln 2 \times N \approx 0.69 \times N$$
  - $$ N = 365, k \ge 253$$
- Problem 2:
  - What is the minimum number of students, $k$, in a classroom such that it is likely that at least one student has the same birthday as the student selected by the professor?
- Problem 3:
  - What is the minmum number of students, $k$, in a classroom such that it is likely that at least two students have the same birthday?
  - $$1 - e^{-\frac{k^2}{2N}} \ge \frac{1}{2}$$
  - $$k \ge \sqrt{2 N \times ln 2} \approx 1.18 \times \sqrt N$$
  - $$N = 365, k = 23$$
- Problem 4:
  - Two classes, each with $k$ students. what is the minimum value of $k$ such that it is likely that at least one student from the first classroom has the same birthday as a student from the second classroom?

- Preimage Attack:

  - $$k \ge 0.69 \times N = 0.69 \times 2 ^n$$

- Collision Attack