Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Valentina Casola » 3.Basic Cryptography


Overview

  • Security Requirements
  • Classical Cryptography
    • Cæsar cipher
    • Vigènere cipher
    • DES
    • 3DES

Security Requirements (cont’d)

  • Confidentiality

Only the owner of the private key knows it, so text enciphered cannot be read by anyone except the owner of the private key

  • Authentication

Only the owner of the private key knows it, so text enciphered with private key must have been generated by the owner

  • Integrity

Enciphered letters cannot be changed undetectably without knowing private key

  • Non-Repudiation

Message enciphered with private key came from someone who knew it

Cryptosystem

Quintuple (E, D, M, K, C):

  • M set of plaintexts
  • K set of keys
  • C set of ciphertexts
  • E set of encryption functions e: M · K → C
  • D set of decryption functions d: C · K → M

Example: Cæsar cipher

  • M = { sequences of letters }
  • K = { i | i is an integer and 0 ≤ i ≤ 25 }
  • E = { Ek | k ∈  K and for all letters m,
  • Ek(m) = (m + k) mod 26 }
  • D = { Dk | k ∈  K and for all letters c,
  • Dk(c) = (26 + c – k) mod 26 }
  • C = M

Classical Cryptography

The sender and the receiver share a common (secret) key:

  • Keys may be the same, or trivial to derive from one another
  • Sometimes called symmetric cryptography

Two basic algorithm types:

  • Transposition ciphers
  • Substitution ciphers
  • Combinations are called product ciphers

Transposition Cipher

Rearrange letters in plaintext to produce ciphertext

Example (Rail-Fence Cipher)

  • Plaintext is HELLO WORLD
  • Rearrange as:

HLOOL
ELWRD

Ciphertext is HLOOL ELWRD

Substitution Ciphers

Change characters in plaintext to produce ciphertext
Example (Cæsar cipher)

  • Plaintext is HELLO WORLD
  • Change each letter to the third letter following it (X goes to A, Y to B, Z to C)

- Key is 3, usually written as letter ‘D’

Ciphertext is KHOOR ZRUOG

Character Frequencies


Statistical Analysis

f(c) frequency of character c in ciphertext;
p(x) is frequency of character x in English;
Φ(i) correlation of frequency of letters in ciphertext with corresponding letters in English, assuming key is i;
Φ(i) = Σ0 ≤ c ≤ 25 f(c)p(c – i) so here;
Φ(i) = 0.1p(6 – i) + 0.1p(7 – i) + 0.1p(10 – i) + 0.3p(14 – i) + 0.2p(17 – i) + 0.1p(20 – i) + 0.1p(25 – i).

Cæsar’s Problem

Key is too short

  • Can be found by exhaustive search;
  • Statistical frequencies not concealed well;
  • They look too much like regular English letters.

So make it longer

  • Multiple letters in key;
  • Idea is to smooth the statistical frequencies to make cryptanalysis harder.

Vigènere Cipher

Like Cæsar cipher, but use a phrase
Example

  • Message THE BOY HAS THE BALL
  • Key VIG
  • Encipher using Cæsar cipher for each letter:

key VIGVIGVIGVIGVIGV
plain THEBOYHASTHEBALL
cipher OPKWWECIYOPKWIRG

Relevant Parts of Tableau

Tableau shown has relevant rows, columns only
Example encipherments:
key V, letter T: follow V column down to T row (giving “O”).
Key I, letter H: follow I column down to H row (giving “P”).


Useful Terms

period: length of key

In earlier example, period is 3

tableau: table used to encipher and decipher

Vigènere cipher has key letters on top, plaintext letters on the left

polyalphabetic: the key has several different letters

Cæsar cipher is monoalphabetic

One-Time Pad

A Vigenère cipher with a random key at least as long as the message

  • Provably unbreakable;
  • Why? Look at ciphertext DXQR. Equally likely to correspond to plaintext DOIT (key AJIY) and to plaintext DONT (key AJDY) and any other 4 letters;
  • Warning: keys must be random, or you can attack the cipher by trying to regenerate the key
    • Approximations, such as using pseudorandom number generators to generate keys, are not random.

Overview of the DES

A block cipher:

  • encrypts blocks of 64 bits using a 64 bit key;
  • outputs 64 bits of ciphertext.

A product cipher:

  • basic unit is the bit;
  • performs both substitution and transposition (permutation) on the bits.

Cipher consists of 16 rounds (iterations) each with a round key generated from the user-supplied key.

DES phases


Initial Permutation IP


Inverse Permutation IP-1


Singol Iteration


Generation of Round Keys


Encipherment


The f Function


Deciphering DES


Controversy

Considered too weak

Diffie, Hellman said in a few years technology would allow DES to be broken in days.

  • Design using 1999 technology published

Design decisions not public

  • S-boxes may have backdoors

Key space DES = 256 ≈ 7,2056 ·1016

A PC with 500 Mhz that is able to test a key in a clock cycle, needs:
144.115.188 seconds ≈ 834 days ≈ 2 years and 3 months to test 255 ≈ 3,6 ·1016 keys.

Undesirable Properties

4 weak keys

  • They are their own inverses

12 semi-weak keys

  • Each has another semi-weak key as inverse

Complementation property
DESk(m) = c ⇒  DESk (m) = c
S-boxes exhibit irregular properties;
Distribution of odd, even numbers non-random;
Outputs of fourth box depends on input to third box.

DES modes

How to cipher text longer than 64 bit?

  • Electronic codebook chaining (ECB)
  • Cipher block chaining (CBC)
  • Cipher feedback (CFB)
  • Output feedback (OFB)

Electronic codebook chaining (ECB)

plaintext x = x1x2…xn (in n blocks of 64 bit).

Ciphered text y = y1y2…yn.


Cipher Block Chaining (CBC)

Plaintext x=x1x2…xn (in n blocks of 64 bit).

Ciphered text y = y1y2…yn.
Inizialization vector IV is public.


Cipher feedback (CFB)

Plaintext x=x1x2…xn (diviso in n blocchi di 64 bit).

Ciphered text y = y1y2…yn.


Double DES

Block lenght = 64 bit.
key (k, k´) of 56+56 = 112 bit.


Double DES


Triple DES

  • Block length = 64 bi
  • Key (k, k´) lenght 56+56 = 112 bit
  • Also called EDEk,k´ (acronym of Encrypt Decrypt Encrypt)
  • Adopted in standards X9.17 and ISO 8732

Deciphering Triple DED


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion