信息安全概论课件-lecture03.ppt

1、Classical Cryptography,1. Introduction: Some Simple Cryptosystems,Outline,1 Introduction: Some Simple Cryptosystems The Shift Cipher The Substitution Cipher The Affine Cipher The Vigenre Cipher The Hill Cipher The Permutation Cipher Stream Ciphers 2 Cryptanalysis Cryptanalysis of the Affine Cipher C

2、ryptanalysis of the Substitution Cipher Cryptanalysis of the Vigenre Cipher Cryptanalysis of the Hill Cipher Cryptanalysis of the LFSR Stream Cipher,Introduction: Some Simple Cryptosystems,1 Introduction,Introduction: Some Simple Cryptosystems,Definition 1.1: A cryptosystem is a five-tuple (P,C,K,E,

3、D) satisfies P is a finite set of possible plaintexts C is a finite set of possible ciphertexts K, the keyspace, is a finite set of possible keys For each KK, there is an encryption rule eKE and a corresponding decryption rule dKD dK(eK(x)=x for every plaintext xP,Introduction: Some Simple Cryptosys

4、tems,Definition 1.2: a and b are integers, m is a positive integer congruence: ab (mod m) if m divides b-a Zm: the set 0,1,m-1 with 2 operations + and 10+20=4 in Z26 (10+20 mod 26=4) 1020=18 in Z26 (1020 mod 26=18),Introduction: Some Simple Cryptosystems, Shift Cipher Cryptosystem 1.1: Shift Cipher

5、P = C =K = Z26 K, x, y Z26 eK(x)=(x+K) mod 26 dK(y)=(y-K) mod 26,Introduction: Some Simple Cryptosystems,eg.: Suppose K=11 Plaintext: student Ciphertext: DEFOPZE,Introduction: Some Simple Cryptosystems, Substitution Cipher Cryptosystem 1.2: Substitution Cipher P=C=Z26 K: all possible permutations of

6、 the 26 symbols For each pK ep(x)=p(x) dp(y)=p-1(y) where p-1 is the inverse permutation to p,Introduction: Some Simple Cryptosystems,eg.: Plaintext: student Ciphertext: VMUSHSM,Introduction: Some Simple Cryptosystems, Affine Cipher Theorem 1.1: axb (mod m) has a unique solution xZm for every bZm if

7、f gcd(a,m)=1 Definition 1.3: Suppose a1 and m2 are integers a and m are relatively prime if gcd(a,m)=1 f(m): the number of integers in Zm that are relatively prime to m Theorem 1.2: Suppose,Introduction: Some Simple Cryptosystems,Definition 1.4: Suppose aZm a-1 mod m: the multiplicative inverse of a

8、 modulo m aa-1a-1a1 (mod m) Cryptosystem 1.3: Affine Cipher P = C = Z26 K=(a,b) Z26Z26 : gcd(a,26)=1 For K=(a,b)K ; x, yZ26 eK(x)=(ax+b) mod 26 dK(y)=a-1(y-b) mod 26,Introduction: Some Simple Cryptosystems,e.g.: Suppose K=(7,3) 7-1 mod 26 = 15 Plaintext: student Ciphertext: ZGNYFQG,eK(x)=(7x+3) mod

9、26,dK(y)=15(y-3) mod 26,Introduction: Some Simple Cryptosystems, Vigenre Cipher Cryptosystem 1.4: Vigenre Cipher m: a positive integer P = C = K = (Z26)m For a key K=(k1,k2,km) eK(x1,x2,xm)=(x1+k1,x2+k2,xm+km) dK(y1,y2,ym)=(y1-k1,y2-k2,ym-km),Introduction: Some Simple Cryptosystems,e.g.: Suppose m=4

10、 and K=(2,8,15,7) Plaintext: student Ciphertext: UBJKGVI,Introduction: Some Simple Cryptosystems, Hill Cipher Definition 1.5: Suppose A=(ai,j) is an mm matrix Ai,j: the matrix obtained from A by deleting the ith row and the jth column det A: the determinant of A m=1: det A=a1,1 m1: for any fixed i A

11、*=(a*i,j): the adjoint matrix of A a*i,j=(-1)i+jdet Aj,i,Introduction: Some Simple Cryptosystems,Theorem 1.3: Suppose K=(ki,j) is an mm invertible matrix over Zn K-1=(det K)-1K* e.g.: det K=117-83 mod 26=1 K-1=(det K)-1K*=,Introduction: Some Simple Cryptosystems,Cryptosystem 1.5: Hill Cipher M 2 is

12、an integer P = C = (Z26)m K = mm invertible matrices over Z26 For a key K eK(x)=xK dK(y)=yK-1 where K-1 is the inverse of K,Introduction: Some Simple Cryptosystems,e.g.: Plaintext: GOD (6 14 3) Ciphertext: WTJ (22 19 9),Introduction: Some Simple Cryptosystems, Permutation Cipher Cryptosystem 1.6: Pe

13、rmutation Cipher m is a positive integer P = C = (Z26)m K consist of all permutations of 1,m For a key(a permutation) p ep(x1,xm)=(xp(1),xp(m) where p-1 is the inverse permutation to p,Introduction: Some Simple Cryptosystems,e.g.: Suppose m=6 Plaintext: CYBERFORMULA Ciphertext: BRCFEYMLOAUR,Introduc

14、tion: Some Simple Cryptosystems, Stream Ciphers Block ciphers Plaintext string x =x1x2 (each xi is a plaintext) Ciphertext string y =y1y2 = eK(x1)eK(x2) Stream ciphers Plaintext string x =x1x2 Generate a keystream (by using some K) z =z1z2 Ciphertext string y =y1y2 = ez1(x1)ez2(x2) ,Introduction: So

15、me Simple Cryptosystems,Definition 1.6: A synchronous stream cipher is a tuple (P,C,K,L,E,D) with a function g P : a finite set of possible plaintexts C : a finite set of possible ciphertexts K : a finite set of possible keys L : a finite set called the keystream alphabet g: the keystream generator

16、Input: K g generates an infinite string z1z2,Introduction: Some Simple Cryptosystems,Definition 1.6 (cont.) For each zL, there is an encryption rule ezE and a corresponding decryption rule dZD dz(ez(x)=x for every plaintext xP,Introduction: Some Simple Cryptosystems,Vigenre Cipher can be defined as

17、a synchronous stream cipher K = (Z26)m P = C = L = Z26 ez(x)=(x+z) mod 26 dz(y)=(y-z) mod 26 Keystream z1z2 = k1k2.km k1k2.km k1k2.km ,Introduction: Some Simple Cryptosystems,Keystream can be produced efficiently in hardware using a LFSR (Linear Feedback Shift Register) k1 would be tapped as the nex

18、t keystream bet k2,km would each be shifted 1 stage to the left The new value of km would be this is “linear feedback“ (see Figure 1.2) This system is modulo 2,Introduction: Some Simple Cryptosystems,e.g.: in Figure 1.2,suppose K=(1,0,0,0) c0=1, c1=1, c2=0, c3=0 The keystream is 100010011010111,Figure 1.2,Introduction: Some Simple Cryptosystems,Non-synchronous stream cipher: Each keystream elem