Some Simple Cryptosystems .ppt

1、Kyungpook National UniversityInformation Security Lab.Some Simple Cryptosystems 2012.06.26.(Tue)Yuan Xiyuanxi_Kyungpook National UniversityInformation Security Lab./27Outline1,The contents that I simply understanding of the Cryptography2,The Shift Cipher3,The Substitution Cipher4,The Vigenere Cipher

2、5,The Hill Cipher 6,The Permutation Cipher7,Stream Cipher2 2Kyungpook National UniversityInformation Security Lab./271,The contents that I Simply understanding of the Cryptography1.Cryptography is a method which can hide the communicating words and documents when they spread by medium.Notice：The doc

3、uments are unreadable documents or they maybe just a gibberish,when they spread by medium.But the people who accept the documents,they must have a key,or key sets.Then,they can use key to decode ciphertext with the given injective functions.3 3Kyungpook National UniversityInformation Security Lab./2

4、71,The contents that I Simply understanding of the Cryptography4 4Kyungpook National UniversityInformation Security Lab./271,The contents that I Simply understanding of the Cryptography3.Encryption operation:5 5plaintext ciphertext mediumKyungpook National UniversityInformation Security Lab./271,The

5、 contents that I Simply understanding of the Cryptography4.Decryption operation:6 6ciphertext plaintext mediumKyungpook National UniversityInformation Security Lab./272,The shift cipher1.What is the shift cipher?The shift cipher is based on modulararithmetic.First,we give letter a integer type value

6、.Then we can understand shift cipher as that plus a number(K)on the assigned letter.7 7Kyungpook National UniversityInformation Security Lab./272,The shift cipher2.Modular arithmeticDefinition:Suppose a and b are integers,and m is a positive integer.Then we write a b(mod m)if m divides b-a.The phras

7、e a b(mod m)is called a congruence,and it is read as“a is congruent to b modulo m.”The integer m is called the modulus.8 8Kyungpook National UniversityInformation Security Lab./272,The shift cipher2.Modular arithmetic some properties of modular arithmetic:1,addition is closed.for any a,b ,a+b .2,add

8、ition is commutative.for any a,b ,a+b=b+a.3,addition is commutative.for any a,b ,(a+b)+c=a+(b+c).4,0 is an additive identity.for any a ,a+0=0+a=a.5,the additive inverse of any a is m-a,a+(m-a)=(m-a)+a=0 for any a 6,multiplication is closed,for any a,b ,ab .9 9Kyungpook National UniversityInformation

9、 Security Lab./272,The shift cipher2.Modular arithmetic 7,multiplication is commutative,for any a,b ,ab=ba.8,multiplication is associative,for any a,b,c ,(ab)c=a(bc).9,1 is a multiplication identity,for any a ,a*1=1*a=a.10,the distributive property is satisfied,for any a,b,c ,(a+b)c=(ac)+(bc)and a(b

10、+c)=(ab)+(ac).1010Kyungpook National UniversityInformation Security Lab./272,The shift cipherShift cryptosystem:let=,for 0K25,define:(x)=(x+K)mod 26 and (y)=(y-K)mod 26 (x,y ).1111Kyungpook National UniversityInformation Security Lab./273,The Substitution cipherWhat is the substitution cipher?To put

11、 it simply,the substitution cipher is use a new letter to substitute for another letter of plaintext.1212Kyungpook National UniversityInformation Security Lab./273,The Substitution cipherSubstitution cryptosystem:Let P=C=,K consists of all possible permtation of the 26symbols 0,1,2,.,25,for each eac

12、h permutation K,define:(x)=(x),and define:(y)=(y),Where is the inverse permutation to .1313Kyungpook National UniversityInformation Security Lab./273,The Substitution cipherFor instance:(x):(y):1414P:abcdefghC:XNYAHPOGijklmnopqZQWBTSFLRrstuvwxyzCVMUEKJDIC:ABCDEFGHP:dlryvoheIJKLMNOPQzxwptbgpjRSTUVWXY

13、ZqnmuskaciKyungpook National UniversityInformation Security Lab./273,The Affine cipherWhat is the substitution cipher?The affine cipher is a special case of substitution cipher.in the affine cipher,we restrict the encryption function to function of the form:e(x)=(ax+b)mod 26,a,b .Then we find a issu

14、e which it is necessary to ask when an affine function is injective.1515Kyungpook National UniversityInformation Security Lab./273,The Affine cipher1.Theorem:The congruence axb(mod m)has a unique solution x ,for every b if only if gcd(a,m)=1.1616Kyungpook National UniversityInformation Security Lab.

15、/273,The Affine cipher2.The number of possible keys.Eular-function:Suppose a1 and m2 are integers.If gcd(a,m)=1,then we say that a and m are Relatively prime.The number of integers inThat are relatively prime to m is often denoteby(m)(this function is called the Euler-function)1717Kyungpook National

16、 UniversityInformation Security Lab./273,The Affine cipherThe proof of Eular-function:Now,please look at the blackboard:1818Kyungpook National UniversityInformation Security Lab./273,The Affine cipher3.Affine cryptosystem Let P=C=,and let K=(a,b)X :gcd(a,26)=1.For K=(a,b)K,define:(x)=(ax+b)mod26And

17、(y)=(y-b)mod26(x,y ).1919Kyungpook National UniversityInformation Security Lab./273,The Affine cipher2020Kyungpook National UniversityInformation Security Lab./274,The vigenre cipherWhat is the vigenre cipher?This cipher is named after Blaise de Vigen-re,who lived in sixteenth century.We can associa

18、te each key K with an alphabetic string of length m,called a keyword.The vigenere cipher encryprs m alphabetic character at a time,each plaintext alement is equivalent to m alphabetic characters.2121Kyungpook National UniversityInformation Security Lab./274,The vigenre cipher1.Property of the vigene

19、re cipher The vigenre cryptosystems is a polyalph-abetic cryptosystem.2222Kyungpook National UniversityInformation Security Lab./274,The vigenre cipher2,Vigenre cipher cryptsystem Let m be a positive integer.Define P=C=K=.For a key,K=,we define:and where all operation are performed in .2323+)Kyungpo

20、ok National UniversityInformation Security Lab./275,The hill cipherWhat is the hill cipher?The hill cipher is a polyalphabetic cryptosys-tem.Let m be a positive integer.and define P=C=,The idea is to take m linear combi-nation of the m alphabetic characters in one plaintext element,thus producing th

21、e m alph-betic characters in one ciphertext element.2424Kyungpook National UniversityInformation Security Lab./275,The hill cipher1,Hill cipher cryptsystem Let m2 be an integer.Let P=C=,and let K=m*m invertible matrices over .For a key K,we define:and where all operations are performed in .2525Kyung

22、pook National UniversityInformation Security Lab./275,The hill cipher2,Definition:(The value of det A)Suppose that A=()is an m*m matrix,for 1im,1jm,define to be the matrix obtained from A by deleting the ith row and the jth column.The determinant of denoted det A.is the value ,if m=1,if m1,then det

23、A is computed recursively from the formula:Where i is any fixed integer between 1and m.2626Kyungpook National UniversityInformation Security Lab./275,The hill cipher3,Theorem:(for obtain the )Suppose K=()is an m*m matrix over such that det K is invertible in .Then =,where is the adjoint matirx of K.

24、2727 Kyungpook National UniversityInformation Security Lab./275,The hill cipher4,A corollary:suppose is a matrix having entries in ,and is invertible in .Then 2828Kyungpook National UniversityInformation Security Lab./276,The Permutation CipherWhat is the permutation cipher?Permutation cipher keep t

25、he plaintext char-acters unchanged.but alter their position by rearranging them using a permutation.2929Kyungpook National UniversityInformation Security Lab./276,The Permutation Cipher1,The principle of permutation cipher A permutation of a finite set X is a bijective function :XX.In other word,the

26、 function is one-to-one(injective)and onto(surjective).It follows that,for every xX,there is aunique emlement such that()=x.This is allows us to de-fine the inverse permutation,:XX by the rule (x)=,if and only if()=xThen is also a permutation of X.3030Kyungpook National UniversityInformation Securit

27、y Lab./276,The Permutation Cipher2,Permutation cipher cryptosystem Let m be positive integer.Let P=C=and let K consistof all permutations of 1,2,m,for a key(i.e.,a permutation),we define andWhere is the inverse permutation to .3131Kyungpook National UniversityInformation Security Lab./276,The Stream

28、 Ciphero What is the stream cipher?The basic idea is to generate a keystream z=,and use it to encrypt a plaintext string x=,according to the rule:.The simplest type of stream cipher is on in which the key-stream is constructed from the key,independent of the plaint-text string,using some specified a

29、lgorithm.And this type of stream cipher is called“synchronous”and can be defined for-mally as follows:3232Kyungpook National UniversityInformation Security Lab./276,The Stream Cipher1,Definition:A synchronous stream cipher is a tuple(P,C,K,L,E,D),together with a function g,such that the following co

30、-nditions are satisfied:1,P is a finite set of possible plaintext 2,C is a finite set of possible ciphertext 3,K,the keyspace,is a finite set of possible keys 4,L is a finite set called the keystream alphabet 5,g is the keystream generator.G takes a key as input,and generates an infinite string call

31、ed the key-stream,where L,for all i1.3333Kyungpook National UniversityInformation Security Lab./276,The Stream Cipher 6,For each zL,there is an encryption rule E and a corresponding decryption rule D.:P C are functionssuch that (x)=x for every plaintext element xP.3434Kyungpook National UniversityIn

32、formation Security Lab./276,The Stream Cipher2,The vigenere cipher can be defined as a syn-chronous stream cipher as follows:where K=.This generates the keys-treamfrom the key K=.3535Kyungpook National UniversityInformation Security Lab./276,The Stream Cipher3,Binary en-decrytion operations Stream c

33、ipher are often described in terms of binary alphab-ets,i.e,P=C=L=,In this situation,the encryption and de-Cryption operations are just addition modulo 2:(x)=(x+z)mod 2and (x)=(y+z)mod 23636Kyungpook National UniversityInformation Security Lab./276,The Stream Cipher4,Generating synchronous keystram

34、In order to,very efficiently obtain en-decryption in hardware,we can do the addition modulo 2 as exclusive-or operation.If use the formule:(1im)We can a periodic keystream having period -1.3737Kyungpook National UniversityInformation Security Lab./276,The Stream Cipher4,Generating synchronous keystr

35、amFor instance:Suppose m=4,and start with a binary key-m-tuple(1,1,0,0)so we can use the formule obtain the new and simple formule .According to the above,we can ensure that period is 15,and if we staring with c-m-tuple(1,0,0,0).The keystream is:100010011010111 100010011010111.3838Kyungpook National

36、 UniversityInformation Security Lab./276,The Stream Cipher5,Linear feedback shift register The linear feedback shift register(LFSR)is another keystream generator,we would use a shift register with m stages.The v-etor would be used to initialize the shift regist-er.At each time unit,the following ope

37、ration would be perfor-Med concurrently:1.would be tapped as the next keystream bit 2.would each be shifted one stage to the left 3.the new value of would be computed to be:3939Kyungpook National UniversityInformation Security Lab./276,The Stream Cipher5,Linear feedback shift register4040NewkeyKyung

38、pook National UniversityInformation Security Lab./276,The Stream Cipher6,Non-synchronous stream cipher The non-synchronous stream cipher is a stream cipher in w-hich each keystream element depends on previous plaintextor cipher text element as well as the key K.The simple type of non-synchronous str

39、eam cipher,knownas the Autokey cipher,the Autokey cipher is use plaintext to c-onstruct the keystream.And the Autokey cipher is insecure since.There are only 26 possible keys.The Autokey cryptosy-stem be given as follows:4141Kyungpook National UniversityInformation Security Lab./276,The Stream Cipher6,Non-synchronous stream cipher Autokey cryptosystem:Let P=C=K=L=,let =K,and define for alli2.For 0z25,define =(x+z)mod26and =(y-z)mod26(x,y ).4242Kyungpook National UniversityInformation Security Lab./274343Thank you for your listening!Thank you for your listening!