# 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

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

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.

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

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

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