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
 
 
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