### Cryptology

From greek

"krypto's," standing for "hidden"

"lo'gos," standing for "word", "reason", or "plan"

### Cryptography

From greek

"krypto's," standing for "hidden"

"gra'phein," standing for "write"

Mathematical science that deals with transforming data to render its meaning unintelligible (i.e., to hide its semantic content), prevent its undetected alteration, or prevent its unauthorized use

### Cryptanalysis

Mathematical science that deals with analysis of a cryptographic system in order to gain knowledge needed to break or circumvent the protection that the system is designed to provide

### Steganography

Methods of hiding the existence of a message or other data

### Algorithm

An algorithm is a well-defined computational procedure that takes a variable input and generates a corresponding output.

Deterministic

Its behaviour is completely determined by the input

Probabilistic (or randomized)

Its behaviour is not completely determined by the input

### Protocol

A distributed algorithm in which two or more entities take part.

### Security

Unconditional (Information-theoretic)

The adversary is not able to solve the task even with infinite computing power

Probability theory, Information theory

Known unconditional secure crypto-systems

Conditional (Computational)

If the adversary is theoretically able to solve the task, but it is computationally infeasible

Computational complexity theory

No known computationally secure crypto-systems

Existence not formally proven

Easy

The computation can be done efficiently

Hard

The computation is not known to be feasible in an efficient way

Is not impossible that such an algorithm exists; it is just not known

### Kerckhoffs' Principle

A cryptographic system should be designed so as to be secure when the adversary knows all details of the system, except for the values explicitly declared to be secret, such as a secret cryptographic key

### One way functions

It is theoretically not even known whether one-way functions really exist

### Cryptographic Hash Function

A hash function h : Σ∗in → Σnout is cryptographic if it is one way or collision resistant

### Symmetric Encryption System

Employs private key cryptography

Five components:

- A plaintext message space M
- A ciphertext space C
- A keyspace K
- A family E = {Ek :k∈K} of encryption functions Ek :M→C;
- A family D = {Dk :k∈K} of decryption functions Dk :C→M.

For every key k ∈ K and every message m ∈ M, the functions Dk and Ek must be inverse to each other (i.e., Dk(Ek(m)) = Ek(Dk(m)) = m).

### Asymmetric Encryption System

Employs public key cryptography

Consist of three efficiently computable algorithms:

- Generate(1n) is a probabilistic key generation algorithmInput: a security parameter 1nOutput: a public key pairPublic key kCorresponding private key k’
- Encrypt(k, m) is a deterministic or probabilistic encryption algorithmInput: a public key k and a plaintext message mOutput: a ciphertext c (i.e., c = Encrypt(k, m))
- Decrypt(k’,c)is a deterministic decryption algorithmInput: a private key k’ and a ciphertext cOutput: a plaintext message m (i.e., m = Decrypt(k’ , c))

### Algebraic Structures

Consists of

- A nonempty set S
- One or more binary operations

### Semigroup

- Algebraic structure ⟨S, ∗⟩
- Nonempty set S

- Associativity axiom: ∀a,b,c ∈ S: a∗(b∗c)=(a∗b)∗c

(Associative binary operation ∗) - Closure Axiom: ∀a,b ∈ S: a∗b ∈ S

(S is closed)

### Monoid

- Semigroup
- Identity axiom: ∃a unique identity element e ∈ S such that ∀a ∈ S: a ∗ e = e ∗ a = a
- Has identity element respect to *

### Group

- Monoid
- Inverse axiom: ∀ a ∈ S : ∃ a unique inverse element a’ ∈ S such that a∗a’ = a’∗a = e
- Every element of S has and inverse element in S

### Abelian (Commutative) Group

- Group
- ⟨S,∗⟩ is commutative if ∗ is commutative
- a ∗ b = b ∗ a for all a, b ∈ S

### Subgroup

- Group
- A subset H of a group G is a subgroup of G if
- Is closed under the operation of G
- Also forms a group

### Ring

- Algebraic structure ⟨S, ∗1, ∗2⟩
- A set S
- Two associative binary operations ∗1 and ∗2
- ⟨S, ∗1⟩ is a commutative (Abelian) group with identity element e1
- ⟨S, ∗2⟩ is a monoid with identity element e2
- The operation ∗2 is distributive over the operation ∗1

### Field

### Homomorphism

- A mapping f : A → B
- A and B be two algebraic structures
- A homomorphism of A into B:
- Preserves the operations of A

- If ◦ is an operation of A and * an operation of B:
- f (x ◦ y) = f (x) * f (y) must hold for all x, y ∈ A

### Isomorphism

- A homomorphism f : A → B is an isomorphism if
- Is injective (“one to one”)
- A and B are isomorphic
- A ~= B

### Automorphism

An isomorphism f : A → A

### Complexity Theory

- Provide mechanisms for classifying computational problems
- according to the resources needed to solve them
- The classification should not depend on a particular computational model
- should measure the intrinsic difficulty of the problem
- The computational may include time, storage space, random bits, number of processors, etc.
- typically the main focus is time, and sometimes space