Cryptography Flashcards

Flashcards for reviewing key vocabulary from the Cryptography lecture notes.

Cryptography

Secure transmission, storage, and usage of data in insecure environments by encryption.

Cryptanalysis

Analysis of cryptosystems and attacks against them with the aim to evaluate and strengthen them.

Cryptology

Cryptography + Cryptanalysis.

Cracking

Unauthorized access to computer systems.

Cipher

An algorithm for performing encryption/decryption.

Ciphertext

Encrypted version of a plaintext message.

Set

An unordered collection of elements without repetition.

Cardinality

The number of elements in the set.

Divisor

A number m is a divisor of n if n = km for some integer k.

Zm

The set of integers modulo m.

Function

A mapping between two sets where f(x) = y; A is the domain, B is the codomain.

Injection

A function where no two different inputs have the same output.

Binary Operation

A function ↖ : A → A ⇐ A, where a ↖ b = c.

Monoid

A set G with a binary operation ↖ : G → G ⇐ G that satisfies closure, associativity, and has a neutral element.

Group

A monoid (G, ↖) which fulfills the axiom, that for each a ⇒ G, there exists an inverse a↑1 ⇒ G such that a ↖ a↑1 = e.

Z*m

The largest subset of Zm that forms a group under multiplication · (mod m).

Greatest Common Divisor (GCD)

For two integers n, m, the largest positive integer that divides both n and m.

Symmetric Cryptosystems

Given the encryption/decryption key is private, the actual encryption and decryption functions E, D can still be public.

Public vs Private Information

The goal that the plaintext should be kept private, where the released ciphertext is public.

Kerckhoff's Principle

In particular, always assume that the adversary knows the cryptosystem used. Only the key is secret.

Ciphertext-only Attack

The adversary intercepts ciphertexts and tries to gain information on the plaintexts or keys.

Brute-force Attack

The adversary attempts decryption with every possible key until they succeed.

Known-plaintext Attack

The adversary knows a few plaintext-ciphertext pairs.

Chosen-plaintext Attack

The adversary can choose plaintexts and obtain the ciphertexts without having access to the key.

Chosen-ciphertext Attack

The adversary is able to decrypt some ciphertexts without having access to the key.

Chosen-text Attack

Plaintexts and ciphertexts can be chosen and encrypted/decrypted freely.

Endomorph Cryptosystem

A cryptosystem S = (M, C, K, D, E) with M = C is called endomorph.

Idempotent Cryptosystem

An endomorph cryptosystem S is idempotent if S applied twice is just another instance of S (with a different key).

Order of Finite Groups

Let G be a finite group. The order of G, |G|, is defined as the number of elements in G.

Order of Individual Elements in a Group

min{k ↔ 1 | ak = 1}.

Generator of G

An element g → G of order ordG(g) = |G|.

Cyclic

If G has a generator.

Discrete Logarithm

The unique exponent k → {0, 1,…, |G| ⇐ 1} with gk = a.

Polynomial Rings

R[x] is the ring of polynomials over x with coefficients in ring R.

Quotient Rings

Finite rings of polynomials called R[x]/p(x) where p(x) ↑ R[x] is called an ideal.

Prime

For any ring elements a, b if p divides a · b then p must divide either a or b.

Irreducible Element

Any non-zero, non-unit which is not a product of any two non-units.

Integral Domains

Rings that have the property that if a · b = 0 then either a or b must be zero.

Greatest Common Divisors

If m, n ↑ N are integers, the largest a ↑ N such that a | m and a | n.

Euclidean Domain

A GCD domain that is able to implement a terminating Euclid’s algorithm.

Knowledge of a key pair (e, n),(d, n) with ed ≡ 1 is enough to factor n

Is enough to factor n.

Breaking RSA

The task of knowing e, n, y to compute x where xe ≡ y (mod n).

Malleability

Replacing ciphertext y with ciphertext sey leads to the modified plaintext (sey)d ≡ (sexe)d ≡ sx mod n, so the attacker can apply a deterministic change.

Product Ciphers

Let S1 = (M1, C1, E1, D1, K1) and S2 = (M2, C2, E2, D2, K2) be two cryptosystems with C1 = M2. Then we define the product cryptosystem of S1 and S2 as S1 → S2 = (M1, C2, E, D, K1 → K2) with E(k1, k2; x) = E2(k2, E1(k1, x)), D(k1, k2; y) = D1(k1, D2(k2, y)) for all x ↑ M1, y ↑ C2 and (k1, k2) ↑ K1 → K2.

Abelian Groups

A group (G, ↔) is commutative or Abelian if for all a, b ↑ G we have a ↔ b = b ↔ a.

Rings

A set R with two binary operations +, · defined on it.

Unit

Any element that has a multiplicative inverse.

Feistel Ciphers

Feistel ciphers are a class of cryptographic schemes that differ in their “round function”.

Fields

A ring (F; +, ·), which fulfils the axioms, that (R, +) is an Abelian group with neutral element 0 and (R \ {0}, ·) is an Abelian group with neutral element 1.

Finite Fields

This field can be extended to a field of size pn for each number n → 1.

Local Substitution (SubBytes)

Non-linear computation of inverses in F(28).

Global Substitutions (Mix Columns)

Linear matrix multiplication

Global Permutations (Shift Rows)

Repeated Execution.

Order of the Multiplicative Group Z

We denote Z*m = {a ∈ Zm | gcd(a, m) = 1}.

Collision

Collision pair for h.

Compute a Pre-Image

Is hard for h, then h is called a one-way hash function.

Week Collision Resistant

Compute a second preimage.

Strong Collision Resistant

Compute a collision.

Birthday Attack

There is a collision pair for h with probability.

Signing the method directly

RSA digital signature: signature: (x, y), verifying: Does x = ye mod n hold?

Perfect security

If for all plaintexts x ∈ M and all ciphertexts y

A unitary matrix U ∈ Cn×n matrix s.t. U†U = UU† = I

Unitary transformation.

Wave-particle duality

Sub-atomic particles behave both as particles and as waves and are modelled using wave functions.

Quantisation

Quantum systems can only assume discrete, quantized values of energy, momentum etc.

Superposition

A quantum system can be in multiple different states simultaneously, called a superposition state.

Entanglement

Quantum particles can become entangled and a change in one state can effect an instant change in the other.

Uncertainty

The precise measurement of both the position and velocity of a quantum particle is impossible.

Factorisation as Period Finding Problem

Find a period r > 0 of the function f(x) = ax mod n, i.e. find r > 0 such that ar ≡ 1 mod n.

Quantum Fourier Transform

A quantum register of q qbits, represented using Q = 2q basis vectors |j〉 as |x〉 = ΣQ−1j=0 xj |j〉, we define the quantum Fourier transform x ↝ y as y = QFT|x〉, where:yk =1/√Q ΣQ−1j=0 xj εjq k , k = 0, 1,…, Q − 1, xj, yk ∈ Cwhere εq = e2πi/Q.

Known-Plaintext Attack

If in addition to the ciphertext the adversary also knows a few plaintext ciphertext pairs.

Chosen-Plaintext Attack

If the adversary gets even more power: He can choose plaintexts and obtain the ciphertext without having access to the key.

Chosen-Ciphertext Attack

If the adversary is able to decrypt some ciphertexts without having access to the key.