Chapter 1 Introduction
1.1. Security goals
 Confidentiality : 기밀성, 비밀성:
 most common aspect of information security
 protect our confidential information
 guard aginst those malicious actions that endanger the confidentiality of the information
 Integrity: 무결성:
 information needs to be changed constantly
 changes need to be done only by authorized entities and through authorized mechanisms
 Availability: 가용성:
 information needs to be available to authorized entities
1.2 Attacks
 Attacks Threatening Confidentiality:
 Snooping: unauthorized access to or interception of data. 도청, 엿보기
 Traffic analysis: to obtain some other type of information by monitoring. 통신량 분석
 Attacks Threatening Integrity:
 Modification: attacker intercepts the message and changes it. Insertion, deletion attack 변조
 Masquerading or spoofing: attacker impersonates somebody else. 신원(명의)도용
 Replaying: attacker obtains a copy of a message sent by a user and later tries to replay it. 다시 사용하기
 Repudiation: 부인, 부정:
 sender of a message denies that she has sent it.
 receiver of a message denies that he has received it
 Attacks Threatening Availability:
 Denial of service (DoS): slows down or totally interrupts the service of a system.
1.3. Services and Mechanisms
 ITUT(International Telecommunication Union:Telecommunication Standardization Sector, 국제전기통신연합) provides some security services and seom mechanisms to implement those services. Security services and mechanisms are closely related because a mechanism or combination of mechanisms are used to provide a service.
1.3.1. Security Services
 Data confidentiality: 메시지 전체 혹은 일부에 대한 기밀성을 유지하는 수단
 Data integirty: modification, insertion, deletion 예방하는 수단
 Authentication: peer entity 인증, data origin 인증하는 수단
 Nonrepudiation: proof of origin, proof of delivery 보장하는 수단
 Access control: unauthorized access 방지하는 수단
Chapter 2. Mathematics of Cryptography
2.1 Integer Arithmetic
 In integer arithmetic, we use a set and a few operations. You are familiar with this set and the corresponding operations, but they are reviewed here to create a background for modular arithmetic.
2.1.1. Set of Integers
 The set of integers, denoted by $Z$, contains all integral numbers (with no fraction) from negative infinity to positive infinity
 \[Z = \{..., 2, 1, 0, 1, 2, ...\}\]
2.1.2. Binary Operations
 In cryptography, we are interesed in three binary operations applied to the set of integers. A binary operation takes two inputs and creates one output.
2.1.3. Integer Division
 In integer arithmetic, if we divide $a$ by $n$ ($a/n$), we can get $q$ and $r$. The relationship between these four integers can be shown as
 \[a = q \times n + r\]
 $n$ : positive
 $r$ : nonnegative
2.1.4. Divisbility
 If $a$ is not zero and we let $r=0$ in the division relation, we get
 \[a = q \times n\]
 If the remainder is zero, $n \mid a$ (n divides a)
 If the remainder is not zero, $n \not \mid a$ (n does not divide a)
 Properties:
 Property 1 : if $a \mid 1$, then $a = \pm 1$
 Property 2 : if $a \mid b$ and $b \mid a$, then $a = \pm b$
 Property 3 : if $a \mid b$ and $b \mid c$, then $a \mid c$.
 Property 4 : if $a \mid b$ and $a \mid c$, then $a \mid (m \times b + n \times c)$, where $m$ and $n$ are arbitrary integers
 Facts 양의 양수만을 고려하였을때:
 The integer 1 has only one divisor, itself.
 Any positive integer has at least two divisors, 1 and itself(but if can have more).
 GCD(Greatest Common Divisor):
 The greatest common divisor of two positive integers is the largest integer that can divide both integers.
 Euclidean Algorithm:
 Fact 1. $gcd(a, 0) = a$
 Fact 2. $gcd(a, b) = gcd(b, a % b), \text{ for } a \ge b > 0$.
r_1 < a; r_2 < b; (initialization) while (r_2 > 0) { q < r_1 / r_2; r < r_1  q * r_2; r_1 < r_2; r_2 < r; } gcd(a, b) < r_1
 Extended Euclidean Algorithm:
 Given two integers $a$ and $b$, we often need to find other two integers, $s$ and $t$, such that
 \[s \times a + t \times b = gcd(a, b)\]
 The extended Eculidean algorithm can calculate the $gcd(a, b)$ and at the same time calculate the value of $s$ and $t$.
r_1 < a; r_2 < b; s_1 < 1; s_2 < 0; t_1 < 0; t_2 < 1; while (r_2 > 0) { q < r_1 / r_2; r < r_1  q * r_2; r_1 < r_2; r_2 < r; s < s_1  q * s_2; s_1 < s_2; s_2 < s; t < t_1  q * t_2; t_1 < t_2; t_2 < t; } gcd(a, b) < r_1; s < s_1; t < t_1;
2.2. Modular Arithmetic
 The division relationship ($a=q \times n + r$) discussed in the previous section has two inputs ($a$ and $n$) and two outputs ($q$ and $r$). In modular arithmetic, we are intereseted in only one of the outputs, the remainder $r$.
2.2.1. Modulo Operator
 The modulo operator is shown as mod. THe second input($n$) is called the modulus. The output $r$ is called the residue
2.2.3. Congruence
 To show that two integers are congruent, we use the congruence operator ($\equiv$):
 $2 \equiv 12 (\text{ mod } 10)$
2.2.4. Operation in $Z_n$
 The three binary operations that we discussed for the set $Z$ can also be defined for the set $Z_n$. The result may need to be mapped to $Z_n$ using the mod operator.
 \[Z_n = \{ 0, 1, 2, ..., (n1)\}\]
 Properties:
 Property 1 : $(a + b) \text{ mod } n = [(a \text{ mod } n) + (b \text{ mod } n)] \text{ mod } n$
 Property 2 : $(a  b) \text{ mod } n = [(a \text{ mod } n)  (b \text{ mod } n)] \text{ mod } n$
 Property 3 : $(a \times b) \text{ mod } n = [(a \text{ mod } n) \times (b \text{ mod } n)] \text{ mod } n$
2.2.5. Inverses
 Additive Inverse:
 In $Z_n$, two numbers $a$ and $b$ are the additive inverse of each other if
 \[(a + b) \text{ mod } n = 0\]
 In $Z_n$, two numbers $a$ and $b$ are the additive inverse of each other if
 Multiplicative Inverse:
 In $Z_n$, two numbers $a$ and $b$ are the multiplicative inverse of each other if
 \[(a * b) \text{ mod } n = 1\]
 An integer $b$ in $Z_n$ has a multiplicative inverse:
 if and only if $gcd(n, b) = 1$
 n과 b가 서로소(n and b are relatively prime)
 In $Z_n$, two numbers $a$ and $b$ are the multiplicative inverse of each other if
2.2.6. Additive and Multiplication Tables
2.2.7. Different Sets
 We need to use $Z_n$ when additive inverses are needed; we need to use $Z_n^*$
2.2.8. Two More sets
 Cryptography often uses two more sets: $Z_p$ and $Z_p^*$. p is a prime number
 \[Z_p = Z_p^* \cup \{ 0 \}\]
Chapter 3. Traidtional SymmetricKey Ciphers
3.1. Introduction
3.1.1. Kerckhoff’s Principle
 Based on Kerckhoff’s principle, one should always assume that the adversary, Eve, knows the encryption/decryption algorith. The reisistance of the cipher to attack must be based only one the secrecy of the key.
 Shanon : The enemy knows the system.
3.1.2. Cryptanalysis
 As cryptography is the science and art of creating secret codes, Cryptanalysis is the science and art of breaking those codes.
3.2. Substitution ciphers (대치암호)
 A substitution cipher replaces one symbol with another. Subsitution ciphers can be categorized as either monoalphabetic ciphers or polyalphabetic ciphers.
3.2.1. Monoalphabetic Ciphers
 In monoalphabetic substitution, the relationship between a symbol in the plaintext to a symbol in the ciphertext is always onetoone.
 Additive Cipher(= Caesar cipher) 덧셈 암호:
 The simplest monoalphabetic cipher is the additive cipher. This cipher is sometimes called a shift cipher and sometimes a Caesar cipher, but the term additive cipher better reveals it mathematical nature.
 \[C = (P + k) \text{ mod } 26\]
 \[P = (C  k) \text{ mod } 26\]
 Historically, additive ciphers are called shift ciphers. Julius Caesar used an additive cipher to communicate with his officers. For this reason, additive ciphers are sometimes referred to as the Caesar cipher. Caesar used a key of 3 for his communications.
 Statistical Attack
 Multiplicative Ciphers
 \[C = (P \times k) \text{ mod } 26\]
 \[P = (C \times k^{1}) \text{ mod } 26\]
 Affine Ciphers (덧셈 곱셈 혼합)
 \[T = (P \times k_1) \text{ mod } 26\]
 \[C = (T + k_2) \text{ mod } 26\]
 \[T = (C  k_2) \text{ mod } 26\]
 \[P = (T \times k_1^{1}) \text{ mod } 26\]
 Monoalphabetic Substitution Cipher:
 Because additive, multiplicative, and affine ciphers have small key domains, they are very vulnerable to bruteforce attack.
 A better solution is to create a mapping between each plaintext character and the corresponding ciphertext character. Alice and Bob can agree on a table showing the mapping for each character.
3.2.2. Polyalphabetic Ciphers
 In polyalphabetic substitution, each occurrence of a character may have ad ifferent substitute. The relationship between a character in the plaintext to a character in the ciphertext is onetomany.
 Autokey Ciphers:
 \[k = (k_1, P_1, P_2, ...)\]
 \[C_i = (P_i + k_i) \text{ mod } 26\]
 \[P_i = (C_i  k_i) \text{ mod } 26\]
 Playfair Cipher : 영국 1차 세계 대전 사용
 5 x 5 의 Secret Key 존재
 J 는 잘 안쓰기 때문에 i와 같은 칸 차지
 두 글자씩 암호:
 같은 글자가 연속으로 나오면 미리 약속한 글자를 삽입
 같은 row : 각 글자의 오른쪽 글자 대치
 같은 column : 각 글자의 아래 글자 대치
 그 외 : 직사각형에서 같은 row의 반대편 글자로 대치
 Vigenere Cipher : 비지네르 프랑스 수학자:
 secret key 가 문자열이고, 이를 돌아가면서 키로 사용
 Hill Cipher:
 secret key 가 m x m 정사각 행렬
 글자수가 안맞으면 끝에 z(약속된 문자) 삽입
 복호화는 secret key 의 역행렬을 사용한다.
 OneTime Pad:
 One of the goals of cryptography is perfect secrecy. A study by Shannon has shown that perfect secrecy can be achieved if each plaintext symbol is encrypted with a key randomly chosen from a key domain. This idea is used in a cipher called onetime pad, invented by Vernam.
3.3. Transposition Ciphers (치환 암호)
 A transposition cipher does not substitute one symbol for another, instead it changes the location of the symbols.
3.3.1. Keyless Transposition Ciphers
 Split odd and even
 example. meet me at the park > memateaketethpr
3.3.2. Keyed Transposition Ciphers
 The key used for encryption and decryption is a permutation key, which shows how the character are permuted.
 For example, key = (3 1 4 5 2)
3.3.3. Combining Two Approaches
 keyless + keyed
3.4. Stream and block ciphers
 The literature divides the symmetric ciphers into two broad categories: stream ciphers and block ciphers.
 Although the definitions are normally applied to modern ciphers, this categorization also applies to traditional ciphers.
3.4.1. Stream Ciphers
 Call the plaintext stream P, the ciphertext stream C, and the key stream K.
 $P=P_1P_2P_3…$, $C=C_1C_2C_3…$, $K=(k_1, k_2, k_3, …)$
3.4.2. Block Ciphers

In a block cipher, a group of plaintext symbols of size $m (m> 1)$ are encrypted together creating a group of ciphertext of the same size. A single key is used to encrypt the whole block even if the key is made of multiple values.

Playfair cipher, Hill cipher
Chapter 6. Data Encryption Standard (DES)
6.1. Introduction
 The Data Encryption Standard (DES) is a symmetrickey block cipher published by the National Institute of Standards and Technology (NIST).
6.1.1. History
 1973, NIST 미국 표준 대칭 키 암호 공모
 IBM의 Lucifer 당선. DES라 부름
 DES 1975 미국 표준 발표.
 현재 : 표준 탈락
6.1.2. Overview
 DES is a block cipher.
 symmetrickey cipher(대칭키 암호)
 동일 plaintext라고 key에 따라 다른 ciphertext가 생성
6.2. DES structure
 The encryption process is made of two permutations(Pboxes), which we call initial and final permutations, and sixteen Feistel rounds.
6.2.1. Initial and Final Permutations
 1~64 정수들의 permutation
 규칙적
 IP와 FP는 서로 역 permutation
6.2.2. Rounds
 $L_i = R_{i  1}$

$R_i = f(R_{i1}, K_i}) \oplus L_{i1}$
 DES Function:
 The heart of DES is the DES function. The DES function applies a 48bit key to the rightmost 32 bits to produce a 32bit output.
 Expansion Pbox:
 Since $R_{i1}$ is a 32bit input and $K_i$ is a 48bit key, we first need to expand $R_{i1}$ to 48bits.
 Although the relationship between the input and output can be defined mathematically, DES uses Table.
 XOR:
 After the expansion permutation, DES uses the XOR operation on the expanded right section and the round key.
 Note that both the right section and the key are 48bits in length.
 Also note that the round key is used only in this operation.
 SBoxes (substitutionbox, 48bits > 32bits):
 The Sboxes do the real mixing (confusion). DES uses 8 Sboxes, each with a 6bit input and a 4bit output.
 불규칙적
 Straight Pbox(Permutation box):
 불규칙적
6.2.3. Cipher and Reverse Cipher
 Using mixers and swappers, we can create the cipher and reverse cipher, each having 16 rounds.
 To achieve this goal, one approach is to make the last round (round 16) different from the others; it has only a mixer and no swapper.

cipher와 reverse cipher는 같은 코드 사용
 Pseudocode for DES cipher ``` Cipher (plainBlock[64], RoundKeys[16, 48], cipherBlock[64]) { permute(64, 64, plainBlock, inBlock, InitialPermutationTable) split(64, 32, inBlock, leftBlock, rightBlock) for (round = 1 to 16) { mixer(leftBlock, rightBlock, RoundKeys[round]) if (round != 16) swapper(leftBlock, rightBlock) } combine(32, 64, leftBlock, rightBlock, outBlock) permute(64, 64, outBlock, cipherBlock, FinalPermutationTable) }
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 roundkey generator creates sixteen 48bit keys out of a 56bit 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.
 SBoxes 와 PBoxes:
 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 bruteforce 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)
 MeetintheMiddle Attack:
 However, using a knownplaintext attack called meetinthemiddle 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: bruteforce, 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(차수) n1 is
 $$f(x) = a_{n1}x^{n1} + a_{n2} x^{n2} + \cdots + a_1 x^1 + a_0 x^0$$
 where $x^i$ is called the ith term and $a_i$ is called the coefficient of the ith 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 $n1$, 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 nbit words.
## Chapter 7. Advanced Encryption Standard (AES)
### 7.1. Introduction
 The Advanced Encryption Standard (AES) is a symmetrickey 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 nonFeistel 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 (AES128, 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
 AES128 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 keyadding(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 keyexpansion process. If the number of rounds is $N_r$, the keyexpansion routine creates $N_r + 1$ 128bit round keys from one single 128bit cipher key.
#### 7.3.1. Key Expansion in AES128
 RotWord(w) : onebyte 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_{i1} \oplus w_{i4} else { t < SubWord(RotWord(w_{i1})) \oplus RCon_{i/4} w_i < t \oplus w_{i4} } } }
 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); }
## Chapter 9. Mathematics of Cryptography
### 9.1. Primes
 Asymmetrickey 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 PhiFunction
 $\phi(n)$ : Euler's phifunction:
 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^{p1} \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
Divisibility_Test(n) { r < 2 while (r < sqrt (n)) { if (r  n) return “a composite” r < r + 1 } return “a prime” }
 수행시간 : $n_b$ = no. of bits of n
#### 9.2.2. Probabilistic Algorithms
 Fermat test
repeat k times: pick a randomly from [2, n2] if a^{n1} mod n != 1, then return “composite” return “prime”
 Square Root Test:
 If n is a prime, then $sqrt 1$ mod n = {1, n1}
 MillerRabin Test: Fermat test + Square Root test:
MillerRabin(n, a)
find m and k such that n  1 = m * 2^k T < a^m mod n if (T = 1 or n  1) return “prime”
for (i=1 to k1) T < T^2 mod n if (T=1) return “composite” if (T=n1) return “prime”
return “composite”
#### 9.2.3. Recommended Primality Test
 Today, one of the most popular primality test is combination of the divisibility test and the MillerRabin 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 MillerRabin 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 publickey 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. AsymmetricKey (PublicKey) Cryptography
### 10.1 Introduction
 Symmetric and publickey 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.
 Symmetrickey cryptography : sharing secrecy
 publickey 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 publickey 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 publickey cryptogrpahy does not eliminate the need for symmetrickey cryptography.
 Symmetrickey: faster. Good for encryption of large messages
 Publickey: slow, but needed for authentication, digital signature, and key exchange.
#### 10.1.4. Trapdoor OneWay Function
 The main idea behind publickey cryptogaphy is the concept of the trapdoor oneway function
 OneWay 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 Oneway Function:
 Given $y$ and $a$ trapdoor (secret), $x$ can be computed easily $x=f^{1}(y)$.
 Every publickey cryptography depends on a trapdoor oneway function.
### 10.2. RSA Cryptosystem
 The most common publickey 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:
 Chosenciphertext:
 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. mbit message M이 mbit가 안되면 padding하여 m bit로 만든다.
2. random number r of k bits 생성
3. G(r) 계산. G는 public oneway 함수(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 oneway 함수(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 publickey 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 p2$
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 p1$, $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 asymmetrickey 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 + a2 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 fixedlength 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:
for i = 1 ~ k: create M_i compute t = h(M_i) if (t == y) return M_i return failure
 $$k \ge 0.69 \times N = 0.69 \times 2 ^n$$
 Collision Attack
for i = 1 ~ k: create M_i compute y_i = h(M_i) for j = 1 ~ i  1: if (y_i == y_j) return M_i and M_j return failure ```
 $k \ge 1.189 \times N^{1/2} = 1.18 \times 2^{n / 2}$
11.3 Message Authentication
 A message digest does not authenticate the sender of the message. To provide message authentication, Alice needs to provide proof that it is Alice sending the message and not an impostor. The digest created by a cryptographic hash function is normally called a modification detection code (MDC). What we need for message authetnication is a message authentication code (MAC)
11.3.1. Modification Detection Code (MDC)
 MDC: 메시지의 integrity 보장
 Alice에게 Bob에게 메시지를 보내려할 때 메시지가 전송 중에 변하지 않았음 을 보장하려면 MDC를 만드록, 메시지와 MDC를 상대에게 보냄.
11.3.2. Message Authentication Code (MAC)
 메시지의 integirty 와 data origin authentication을 동시에 보장하려면 MDC> MAC(message authentication code)으로 바꿈

둘의 차이점: MAC은 Alice와 Bob 사이에 비밀 사전 공유
 MAC 의 종류
 HMAC : hash함수를 이용
 CMAC : CBCMAC (대칭키 암호를 이용)
 전용 MAC함수를 따로 개발
Chapter 12. Cryptographic Hash Functions
12.1 Introduction
 A cryptographic hash function takes a message of arbitrary length and creates a message digest of fixed length.
11.1.1. Iterated Hash Function
 MerkleDamagard Scheme:
 $H_0$: 초기값(미리 정해진 값)
 $H_i = f(H_{i1}, M_i), 1 \le i \le t$
 $H_t = h(M)$
 $f$ : compression function
 $n$ : block 크기
 $m$ : message digest 길이
12.1.2. Two Groups of Compression Functions
 $f$ 함수 : made from scratch(새로 개발):
 Message Digest(MD) : MD2, MD4, MD5  Rivest 개발
 Secure Hash Algorithm (SHA) : SHA2, SHA512 미국 표준
 $f$ 함수 : based on block ciphers:
 Whirlpool
12.2 SHA512

SHA512 is the version of SHA with a 512bit message digest. This version, like the others in the SHA family of algorithms ,is based on the merkleDamgard scheme.(by NSA and NIST)

With a message digest of 512 bits, SHA512 expected to be resistant to all attacks, including collision attacks.
Chapter 13. Digital Signature
 Conventional Signatures:
 A person signs a document to show that it originated from her or was approved by her.
 The signature is a proof to the recipient that the document comes from the correct entity.
 Digital Signatures:
 When Alice sends a message to Bob, Bob needs to check the authenticity of the sender; he needs to be sure that the message comes from Alice and not Eve.
 Bob can ask Alice to sign the mssage electronically. The electornic signature can prove the authenticity of Alice as the sender.
13.1. Comparision
 Let us begin by looking at the differences between conventional signatures and digital signatures.
13.1.1 Inclusion
 A conventional signature is included in the document; it is part of the document.
 But when we sign a document digitally, we send th signature as a separate document.
13.1.2. Verification Method
 For a conventional signature, wehn the recipient receives a document, she compares the signature on the document with the signature on file.
 For a digital signature, the recipient receives the message and the signature. The recipient needs to apply a verification techinique to the combination of the message and the signature to verify the authenticity.
13.1.3. Relationship
 For a conventional signature, there is normally a onetomany relationship between a signature and documents.
 For a digital signature, there is a onetoone relationship between a signature and a message.
13.1.4. Duplicity
 In conventional signature, a copy of the signed document can be distinguished from the original one on file.
 In digital signature, there is no such distinction unless there is a factor of time one the document.
13.2. Process
 The sender uses a signing algorithm to sign the message. The message and teh signature are sent to the receiver. The receiver receives the message and the signature and applies the verifying algorithm to the combination. If the result is true, the message is accepted; otherwise, it is rejected.
13.2.1. Need for Keys
 A digital signature needs a publickey system.
 The signer signs with her private key;
 the verifier verifies with the signer’s public key.
 공개 키 암호의 두가지 용도:
 암호복호(기밀성 유지): the private and public keys of the receiver 사용
 디지털서명(저자 확인) : the private and public keys of the sender 사용
13.2.2. Signing the Digest
 공개키 암호시스템: 긴 메시지에서 속도 느림.
 메시지 대신 메시지 다이제스트에 서명
13.3 Services
 message confidentiality, message authentication, message integrity, and nonrepudiation.
 A digital signature can directly provide the last tree; for message confidentiality we still need encryption/decryption.
13.3.1. Message Authentication
 message authentication (or dataorigin authentication)
 메시지 인증: 메시지의 저자(보낸 사람) 확인
13.3.2. Message Integrity
 메시지와 디지털 서명은 1대1 관계
 미시지가 바뀌면 그에 따라 디지털서명도 바뀌어야 함
 디지털 서명을 새로 만드려면 개인 키 필요
13.3.3. Nonrepudiation
 디지털 서명을 서명자가 부인할 수 없음
13.3.4. Confidentiality
 디지털 서명은 기밀성을 제공하지 못한다.
 기밀성 보장은 반드시 암복호화가 적용된 다른 레이어를 통해서 제공되야한다.
13.5. Digitial Signature Schemes
 Several digital signature schemes have evolved during the last few decades. Some of them have been implemented.
13.6. Variations and Application
13.6.1. Variations
 Time Stamped Signatures:
 시간 정보를 포함한 서명(replay attack 방지)
 Blind Signatures:
 문서 내용을 보여주지 않고 서명하기
Chapter 14. Entity Authentication
14.1. Introduction
 Entity authentication is a technique designed to let one party prove the identity of another party. AN entity can be a person, a process, a client, or a server. The entity whose identity needs to be proved is called the claimant; the party that tries to prove the identity of the claimant is called the verifier.
14.1.1. Message Versus Entity Authentication
 Two differences between message authentication (dataorigin authentication), and entity authentication:
 Message authentication might not happen in real time; entity authentication does. When Bob authenticates the message, Alice may or may not be present in the communication process. MAC, 디지털 서명의 경우 In Entity authentication, Alice needs to be online and to take part in the process. Only after she is authenticated message can be communicated between them.
 Message authentication simply authenticates one message; the process needs to be repeated for each new message. Entity authentication authenticates the claimant for the entire duration of a session.
14.1.2. Verification Categories
 Something known:
 Password, PIN, secret key, private key
 Something possessed:
 ID card, Passport
 Something inherent:
 Fingerprint, voice, handwriting
14.2. Passwords

The simplest and old method of entity authentication is the passwordbased authentication, where the password is something that the claimant knows.
 Hashing the password
 Dictionary Attack:
 Salting the password
14.3. ChallengeResponse
 In password authentication, the claimant proves her identity by demonstrating that she knows a secret, the password. In challengereponse authentication, the claimant proves that she knows a secret without sending it.
14.3.1. Using a SymmetricKey Cipher
 일방향 인증:
 verifier가 평문을 보냄, claimant는 이를 암호화 해서 보내고 verifier는 대칭키로 이를 해제함으로써 claimant가 key를 알고있다고 판단.
 양방향 인증:
 verifier가 평문을 보냄, claimant가 생성한 평문과 받은 평문을 붙여서 암호화 해서 보냄. 이를 verifier가 복호화후 평문의 순서를 바꿔 암호화하여 전송
 상호 인증
14.3.3. Using a PublicKey Cipher
14.4. ZeroKnowledge
 In zeroknowledge authentication, the claimant does not reveal anything that might endanger the confidentiality of the secret. The claimant proves to the verifier that she knows a secret, without revealing it. The interactions are so designed that they cannot lead to revealing or guessing the secret.
 Cave Example, Two balls and the colorblind friend