## Chapter 1 Classical Cryptography

### 1 Security

#### (1) Goals

- Confidentiality(nobody except the communicating parties can
**read**information)

-> use encryption algorithms

- Integrity(nobody except the communicating parties can
**change**parts of the information)

-> use hash functions

- Authenticity(authorized partner)

-> use signatures(asymmetric) or MAC(Message Authentication Codes)(symmetric)

#### (2) Kerkhoff's Principle

A cryptosystem should be secure even if everything about the system, except the secret key, is public knowledge. (KeyGen(), Enc() and Dec() can be known)

#### (3) Perfect Secrecy & Computational Security

- Perfect Secrecy / Information-theoretic security:

No information about the plaintext should be leaked from the ciphertext.

Pr[M=m|C=c] = Pr[M=m] or I (M;C)=0

- In practice,
**computational security**is enough:

Any attack on the cryptosystem should be complex enough so that it cannot be done in a certain time (measured by the **security level**)

#### (4) Security Level

The security level measures computational security. If there exists an attack with **complexity** 2^l to recover the secret key or the message, the security level is said to have l bit.

The key size gives an upper bound on the security level. For example, assume there are 2145 possible keys, but an attack with complexity 2108 exists. => The key size is 145 bit and the system has 108 bit security.

#### (5) Notations

- semantic security: Pr[A(lamda, c) = m_i] <= 0.5 + negl(lamda)

- Indistinguishability(IND): An attacker cannot distinguish which
**self-chosen**message m was encrypted given c

- Chosen-Plaintext-Attack(CPA): Gives power which plaintext m will get encrypted and attacked. : Gives power which ciphertexts c can be decrypted. 攻击者拥有加密机的访问权限，可构造所选一定数量的明文所对应的密文

- Chosen-Ciphertext-Attack(CCA): 攻击者掌握对解密机的访问权限，可构造任意密文所对应的明文

### 2 Symmetric Cryptography

Symmetric encryption: both parties have access to the same secret key and use it for encryption and decryption.

- Usually, in symmetric cryptography, the key size equals the security level.

**Deterministic**Cryptosystems are not IND-CPA secure.

#### (1) Stream Cipher

Directly combines (e.g. xor) a plaintext stream of arbitrary length with a key stream of the same length. The **key stream** is generated using a fixed-length secret key and a public keystream generator algorithm.

#### (2) Block Cipher

A block cipher is a deterministic algorithm (specified by the secret key k of size s) that maps plaintext blocks (of fixed length n) to ciphertext blocks (of same length n)

#### (3) Historical Ciphers

- Shift Cipher(Caesar Cipher)

- Substitution Cipher(map each letter into another letter -> 26! = 2^88 secret keys)

Each plaintext in Shift Cipher and Substitution Cipher is **always** encrypted to the same letter, so **letter** **statistics** can be used to break the cipher.

- Polyalphabetic Substitution Cipher(e.g. with five key letters, (26!)^5 = 2^441 secret keys)

- Viginere Cipher (a polyalphabetic substitution cipher with five key letters 26^5 = 2^23 secret keys)

#### (4) Modern Cipher

- Advanced Encryption Standard(AES, a binary block cipher)

The length of the key influences the sub-keys as well as the number of rounds.

- Hash Function("fingerprints" of messages, a small change to the message leads to a completely different hash value)

Hash function is a **deterministic** **non-injective** mapping that maps data of arbitrary length to a fixed length. All output hash values occur with the same probability.

Hash functions should be collision-resistant: given h(x), it is hard to find y such that h(y)=h(x). Given h(x), it is infeasible to find x.

All output hash values occur with the same probability.

### 3 Asymmetric (Public-Key) Encryption

Asymmetric encryption / public key cryptosystems use two keys:

a public key for encryption and a private key for decryption. Usually, PKCs are used to exchange the secret key of symmetric cryptosystems.

- Classical public-key encryption is based on mathematical hard problem: factoring large numbers(RSA) or discrete algorithm(ELGamal).

#### (1) RSA

e: select a number e so that gcd((p-1)(q-1),e)=1

d: use the extended euclidean algorithm to compute ed = 1 mod (p-1)(q-1), d = d mod (p-1)(q-1).

From the complexity of factoring, we get:

- RSA with key size s=1024 has 80 bit security.

- RSA with s=2048 has 112 bit security.

- RSA with s=3072 has 128 bit security.

- Plain RSA is not IND-CPA secure.

#### (2) Diffie-Hellman Key Exchange

The underlying hard problem is the discrete logarithm problem: let p be prime and a be a primitive element of Fp, for every number A, there is **exactly one b** in {0, ..., (p-2)} such that A=a^b mod p. b is the discrete logarithm of A and is hard to calculate.

- Diffie-Hellman key exchange can be used to exchange secret keys over insecure channels:

Alice and Bob agree on a public pair (p,a).

Alice chooses randomly b in {2, ..., (p-2)} and keeps it secret. She calculates A=a^b mod p and sends it to Bob.

Bob chooses randomly c in {2, ..., (p-2)} and keeps it secret. He calculates B=a^c mod p and sends it to Bob.

The secret key is **a^bc mod p**.

## Chapter 2 Post-Quantum Cryptography & Code-Based Cryptosystems

### 1. Post-Quantum Cryptography

- Grover’s quantum algorithm can efficiently find the unique root of a polynomial => key size of symmetric systems has to be doubled.

- Post-quantum secure PKCs should be based on NP-hard problems and not be breakable by polynomial attacks on quantum computers.

- RSA, EIGamal and Elliptic-Curve cryptography are
**NOT post-quantum secure**. Shor’s quantum algorithm can efficiently find any positive integer's prime factorization. Similar algorithm to solve the discrete logarithm problem exists.

## Comments | NOTHING