Security in Communications 学习笔记

发布于 29 天前  382 次阅读


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.
Symmetric cryptography is not affected too much by quantum computers (we “only” have
to increase the security level). But, all asymmetric cryptosystems which are based on integer factorization or the discrete logarithm problem are broken by a quantum computer!
  • Code-based cryptography and lattice-based cryptography are post-quantum secure. Decoding a random code is an NP-hard problem. Code-based cryptosystems are based on the hardness of decoding a random code. Lattice-based cryptosystems are based on hard problems in lattices.

2. Basic Concept of Linear Codes

(1) Finite Fields and Linear Codes

  • Prime Field

A finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules.

The most common examples of finite fields are given by the integers mod p when p is a prime number, called prime fields.

A primitive element of a finite field GF(p) is a generator of the multiplicative group of the field. In other words, α ∈ GF(p) is called a primitive element if each non-zero element of GF(p) can be written as α^i for some integer i. Every finite field has at least one primitive element α.

The smallest integer n s.t. α^n = 1 is the order of α, ord(α). If α is primitive, ord(α) = |GF|-1.

For all elements, a^|GF| = a.

  • Extension Fields

Let p be a prime and m>=1 an integer. Let f(x) ∈ GFp[x] be an irreducible polynomial of degree m. Then, the set of all polynomials in GFp[x] of degree less than m ( in total p^m polynomials) defines the finite extension field.

A primitive polynomial is the minimal polynomial of a primitive element of the finite field GF(p^m). This means that a polynomial of degree m with coefficients in GF(p) is a primitive polynomial if it has a root α in GF(p^m) such that {0, 1, α, α^2, α^3, …, α^(pm−2)} is the entire field GF(p^m).