Feistel Cipher Structure

Horst Feistel devised the feistel cipher

1.based on concept of invertible product cipher

Partitions input block into two halves

1.process through multiple rounds which

2.perform a substitution on left data half

3.based on round function of right half & subkey

4.then have permutation swapping halves

Implements Shannon’s S-P net concept

Block Cipher Designbasic principles still like Feistel’s in 1970’s;number of rounds

1.more is better, exhaustive search best attack

function f :1. provides “confusion”, is nonlinear, avalanche 2. have issues of how S-boxes are selected

key schedule: 1. complex subkey creation, key avalanche

Differential Cryptanalysis

· one of the most significant recent (public) advances in cryptanalysis

· known by NSA in 70's cf DES design

· Murphy, Biham & Shamir published in 90’s

· powerful method to analyse block ciphers

· used to analyse most current block ciphers with varying degrees of success

· DES reasonably resistant to it, cf Lucifer

Linear Cryptanalysis

· another recent development

· also a statistical method

· must be iterated over rounds, with decreasing probabilities

· developed by Matsui et al in early 90's

· based on finding linear approximations

· can attack DES with 2⁴³ known plaintexts, easier but still in practise infeasible

Group

· a set of elements or “numbers”

· with some operation whose result is also in the set (closure)

Cyclic Groupa group is cyclic if every element is a power of some fixed element

Ringa set of “numbers” with two operations (addition and multiplication) which form: an abelian group with addition operation

if multiplication operation is commutative, it forms a commutative ring

if multiplication operation has an identity and no zero divisors, it forms an integral domain

Field a set of numbers with two operations which form: abelian group for addition abelian group for multiplication (ignoring 0) ring; have hierarchy with more axioms/laws group -> ring -> field

Modular Arithmetic define modulo operator “a mod n” to be remainder when a is divided by n use the term congruence for: a = b mod n when divided by n, a & b have same remainder eg. 100 = 34 mod 11

· is 'clock arithmetic'

· uses a finite number of values, and loops back from either end

· modular arithmetic is when do addition & multiplication and modulo reduce answer

· can do reduction at any point, ie

o a+b mod n = [a mod n + b mod n] mod n

Euclidean Algorithm

an efficient way to find the GCD(a,b)

uses theorem that:

GCD(a,b) = GCD(b, a mod b)

Euclidean Algorithm to compute GCD(a,b) is:

EUCLID(a,b)

1. A = a; B = b 2. if B = 0 return A = gcd(a, b)

3. R = A mod B 4. A = B 5. B = R 6. goto 2

Galois Fields

finite fields play a key role in cryptography

can show number of elements in a finite field must be a power of a prime pⁿ

known as Galois fields

denoted GF(pⁿ)

in particular often use the fields: GF(p) GF(2ⁿ)

Polynomial Arithmetic with Modulo Coefficients

when computing value of each coefficient do calculation modulo some value

forms a polynomial ring

could be modulo any prime

but we are most interested in mod 2

ie all coefficients are 0 or 1

eg. let f(x) = x³ + x² and g(x) = x² + x + 1

f(x) + g(x) = x³ + x + 1

f(x) x g(x) = x⁵ + x²

Origins

clear a replacement for DES was needed

have theoretical attacks that can break it

have demonstrated exhaustive key search

attacks

can use Triple-DES – but slow, has small blocks

US NIST issued call for ciphers in 1997

15 candidates accepted in Jun 98

5 were shortlisted in Aug-99

Triple-DES with Two-Keys

hence must use 3 encryptions

l would seem to need 3 distinct keys

but can use 2 keys with E-D-E sequence

l C = E_K1(D_K2(E_K1(P)))

l nb encrypt & decrypt equivalent in sec.

l if K1=K2 then can work with single DES

standardized in ANSI X9.17 & ISO8732

no current known practical attacks

Triple-DES with Three-Keys

although are no practical attacks on two-key Triple-DES have some indications

can use Triple-DES with Three-Keys to avoid even these C = E_K3(D_K2(E_K1(P)))

has been adopted by some Internet applications, eg PGP, S/MIME

Modes of Operation

· block ciphers encrypt fixed size blocks

o eg. DES encrypts 64-bit blocks with 56-bit key

· need some way to en/decrypt arbitrary amounts of data in practise

· ANSI X3.106-1983 Modes of Use(now FIPS 81)defines 4 possible modes

· subsequently 5 defined for AES & DES

· have block and stream modes

Поиск по сайту: