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 algorithm
    Input: a security parameter 1n
    Output: a public key pair
    Public key k
    Corresponding private key k’
  • Encrypt(k, m) is a deterministic or probabilistic encryption algorithm
    Input: a public key k and a plaintext message m
    Output: a ciphertext c (i.e., c = Encrypt(k, m))
  • Decrypt(k’,c)is a deterministic decryption algorithm
    Input: a private key k’ and a ciphertext c
    Output: 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

  • A ring ⟨S, ∗1, ∗2⟩ in which ⟨S \ {e1}, ∗2⟩ is a group
    • ⟨S \ {e1}, ∗2⟩
      A group is that every nonidentity element (with respect to ∗1) must have an inverse element (with respect to ∗2)

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