CM30173: Cryptography

Flashcards for reviewing key voabulary terms in Cryptography.

Cryptography

The techniques, tools, and pitfalls of cryptography (including authentication etc.)

Confidentiality (Cryptography)

Keeping information a secret from those not authorized to have it.

Data Integrity (Cryptography)

Ensuring information has not been altered by those not authorized to do so.

Authentication (Cryptography)

Confirmation of the identity of an entity.

Message Authentication

Confirmation of the source of information.

Signature (Cryptography)

A way of binding information to an entity.

Certification

Endorsement of information by a trusted entity.

Non-repudiation

Preventing an entity from denying previous actions or commitments.

Revocation

Retracting certification or authorization.

Cryptosystem

An encryption system is a five-tuple (P, C, K, E, D), where P is a finite set of possible plaintexts, C is a finite set of possible ciphertexts and K is a finite set of possible keys called the keyspace. And, For each key k ∈ K there is an encryption rule ek ∈ E, ek : P → C and a corresponding decryption rule dk ∈ D, dk : C → P such that dk(ek(x)) = x for all plaintext elements x ∈ P.

Substitution Cipher

P = C = Z26, K is the set of all permutations of the 26 symbols 0, 1, . . . , 25. For each permutation π ∈ K eπ(x) = π(x) and dπ(y) = π −1(y) where π −1 is the inverse permutation.

Shift Cipher

A special case of the substitution cipher that allow only those permutations that “shift” the alphabet by a specific offset. The offset is the key 0 ≤ k ≤ 25.

Vigenère Cipher

P = C = (Z26)m where m ∈ Z, m > 0. K is the set of keys k = (k1, k2, . . . , km). For each key k we have ek(x1, x2, . . . , xm) = (x1 + k1, x2 + k2, . . . , xm + km) and dk(y1, y2, . . . , ym) = (y1 − k1, y2 − k2, . . . , ym − km) (operations are modular 26, that is, in Z26).

Permutation Cipher

P = C = (Z26)m, m ∈ Z, m > 0. K is the set of permutations of {1, . . . , m}. For each permutation π (the key) we have eπ(x1, . . . , xm) = (xπ(1), . . . xπ(m)) and dπ(y1, . . . , ym) = (yπ−1(1), . . . , yπ−1(m)) where π −1 is the inverse permutation.

Brute Force Attack

An exhaustive search of a keyspace involves trying all possible decryption keys.

Kerckhoffs’ desiderata

A set of six design principles for ciphers.

Computational Security

A cryptosystem is computationally secure if the best algorithm for breaking it requires a computational effort which is greater than the computational resources of the assumed attacker.

Provable Security

For some cryptosystems that provide confidentiality we can provide evidence that the system is secure by proving a theorem of the form: If the cryptosystem can be broken then we can efficiently solve problem A.

Unconditional Security

A cryptosystem is said to be unconditionally secure if an attacker with infinite computational resources cannot break the system.

One-time Pad

The Vernam cipher is referred to as a one-time pad if the key stream k1k2k3 . . . is Randomly chosen and Never used again.

Product Cipher

Combines two or more components with the intention of producing a cipher that is more secure than the basic parts of which it is made.

Iterated Block Cipher

A block cipher is made up from: A key schedule of Nr round keys: (k1, k2, . . . , kNr), derived, using a fixed public algorithm, from the key k and A round function f which takes a round key and a current state, The encryption (and decryption) functions consist of repetition of the round function Nr times.

Substitution-Permutation Network

Let l, m, Nr be positive integers. πS : {0, 1}l → {0, 1}l is an S-box, πP : {1, . . . , lm} → {1, . . . , lm} is a permutation, P = C = {0, 1}lm, K ⊆ ({0, 1}lm)Nr+1 is the set of all key schedules that can be derived from an initial key k. For a key schedule (k1, . . . , kNr+1) we encrypt using an iterated cipher composed of sub- stitution, permutation and x-or operations.

Differential Cryptanalysis

A chosen plaintext attack using plaintexts chosen in pairs x, x∗ such that x ⊕ x∗ = x′, a particular plaintext difference. x′ is chosen such that, with high probability, during encryption, a particular state difference will occur at the input to the last round of S-boxes.

Linear Cryptanalysis

A known plaintext attack. Using probabilistic analysis we find biased linear approximations for the S-boxes. Construct a linear approximation, with a large bias, of the SPN (excepting the final round) in terms of plaintext bits and state bits. For each candidate key we partially decrypt each ciphertext and see if the linear approx- imation holds for state, incrementing a counter for the key if it does. The candidate key with largest bias (from |input pairs|/2) should contain the targeted key bits.

Feistel Cipher

An iterated cipher in which the state on round i is divided into two halves of equal length: Li and Ri . The round function g has the form g(Li−1, Ri−1, ki) = (Li, Ri) and is computed: Li = Ri−1 and Ri = Li−1 ⊕ f(Ri−1, ki) for some function f.

Weak Key

A key k for which ek(ek(x)) = x for all x.

Semi-weak Key Pair

A pair of keys k1, k2 is semi-weak if ek1 (ek2 (x)) = x for all x.

Message Digest Code (MDC)

An unkeyed hash function.

Message Authentication Code (MAC)

Keyed hashes.

Public-Key Cryptosystem

A cryptosystem (P, C, K, E, D) where For every k ∈ K, ek is the inverse of dk, For every k ∈ K and for every x ∈ P or y ∈ C, ek(x) and dk(y) are easy to compute, It is computationally infeasible (for almost all k ∈ K) to derive dk from ek, For every k ∈ K it is feasible to compute ek and dk from k

One-way Function

A function f : X → Y such that for all x ∈ X it is easy to compute f(x) but for (almost) all y ∈ Y it is computationally infeasible to find an x such that f(x) = y.

Trap-door One-way Function

A one-way function f : X → Y such that given some additional trap-door information it becomes feasible, for all y ∈ Y to find x ∈ X such that y = f(x).

Euler phi-function

The number of integers less than n and relatively prime to n is denoted φ(n).

Splitting

Algorithms which split n, that is, find 1 < a < n, 1 < b < n such that n = ab. a and b are said to be non-trivial factors of n.

Strong Prime

p prime is strong if p − 1 has a large prime factor (denoted r), p + 1 has a large prime factor, r − 1 has a large prime factor.

Coppersmith’s Theorem

Let p be a monic polynomial of degree d in one variable modulo an integer n of unknown factorisation. Then one can find, in time polynomial in (log n, d), all integers x0 such that p(x0) ≡ 0 (mod n) and |x0| ≤ n1/d .

Order of a Group

The number of elements in the group. If the order of a group is finite it is called a finite group.

Order of an Element

Let G be a finite group. The order of an element g ∈ G is the smallest positive integer m such that gm = 1.

Cyclic Group

Let G be a finite group of order m. G is said to be a cyclic group if there exists an element α ∈ G having order equal to m. α is called a generator of G.

Primitive Element Modulo p

An element α ∈ Z∗ p with order p − 1 modulo p is called a primitive element modulo p.

Discrete Logarithm in Z∗ p

Let p be prime and let α ∈ Z∗ p be a primitive element modulo p. If β ∈ Z∗ p such that αa ≡ β (mod p) then a is called the discrete logarithm of β and is denoted logα β.

Computational Diffie-Hellman Problem (CDH)

Given p prime, α a primitive element modulo p and two elements β, γ ∈ Z∗ p find δ ∈ Z∗ p such that logα δ ≡ logα β × logα γ (mod p). That is, given αa and αb, find αab .

Signature Scheme

A signature scheme is a five-tuple (P, A, K, S, V) where P, a finite set of possible messages, A, a finite set of possible signatures, K, a keyspace, the finite set of possible keys. For each key k there is a signing algorithm sigk : P → A and a corresponding verifi- cation algorithm verk : P × A → {t, f} such that for all messages x and all signatures y: verk(x, y) = t if y = sigk(x) f if y != sigk(x)

Public Key Infrastructure (PKI)

A secure system that is used to manage and control certificates.

Certificate Path

A path from a trusted CA to a given certificate. Each certificate in the path is signed by the owner of the previous certificate in the path.

Cross Certification

When one CA signs the certificate of another CA. This can be used to connect the root CAs of multiple PKIs to form networked PKIs.