代写 CSCI361Computer Security

100%原创包过,高质代写&免费提供Turnitin报告--24小时客服QQ&微信：120591129

代写 CSCI361Computer Security

nCSCI361

Computer Security

nClassical cryptology

nOutline

nWhat is cryptology?

–Cryptography.

–Cryptanalysis.

nCommunication model.

nSecret-key cryptography.

nEarly ciphers:

–Caesar.

–Monoalphabetic.

nStatistical cryptanalysis.

nCryptology

nFrom the Greek words:

–kryptos meaning “hidden”

–logos meaning “word”

Cryptology is the art/science of secure communication. It splits into…

nCryptography: Designing algorithms to ensure security: i.e. confidentiality, integrity and authenticity.

nCryptanalysis: Analysing security algorithms with the aim of breaching security.

nThe basic secrecy channel

nThe channel can be a communication channel or a storage channel.

nSender (A for Alice) wants to send a message X to the Receiver (B for Bob), through this channel, such that the opponent/enemy/intruder O (O for Oscar) cannot access X.

nAlice applies a transformation, known as encryption, to X, referred to as the plaintext, to produce a garbled message Y, referred to as the ciphertext (or cryptogram).

nBob applies another transformation, known as decryption, to Y to obtain the plaintext again.

nKey dependence

nThe transformations are not fixed, they are key dependent. The key K controls the transformation and is known only by Alice and Bob. The key is secret.

nEncryption and decryption are sometimes referred to as enciphering and deciphering, respectively.

nNote that if a transformation does not depend on a key, it is referred to as encoding, with the inverse transformation being referred to as decoding.

–Morse code.

–ASCII code.

nSecret-key cryptography

nIn secret key cryptography the participants all have only secret key information.

nBasically this means there is no role, other than as an attacker, for anybody who doesn’t hold a secret key of some sort.

nWe shall later look at public-key cryptography, where persons without secret-keys can play a role (other than an attacker) in the cryptosystem.

nSymmetric and asymmetric encryption

nIn classical cryptography the encryption and decryption keys are the same, this is an example of a symmetric encryption scheme.

nIn asymmetric encryption the encryption and decryption keys are different, this is the case in public-key encryption.

nWe emphasise that the terms symmetric and private are not equivalent. It is possible to have private asymmetric key systems (not necessarily encryption), although we shall not be discussing such in this course.

nKirchoff’s Law

nThis is the main assumption of cryptology.

The cryptanalyst knows all the details of the encryption and decryption transformations, except for the value of the secret key or keys.

nSome possible attacks

nOscar is trying to decrypt a particular ciphertext, and possibly (although it is harder in general) to figure out the key.

nCiphertext only: Oscar knows Y. Alice and Bob don’t want Oscar to figure out what either X or K is.

nKnown plaintext: Oscar knows some X-Y pairs. Alice and Bob don’t want Oscar to figure out what K is, or the correspondence between other X-Y pairs.

nChosen plaintext: Oscar is allowed to choose some plaintexts (X’s), and receives the corresponding ciphertexts (Y’s).

nChosen ciphertext: Oscar is allowed to choose some ciphertexts (Y’s), and receives the corresponding plaintexts (X’s).

nSome combination of these.

nEpochs in cryptology

nNon-scientific cryptography: from antiquity until 1949.

Cryptology was more an “art” than a science.

nScientific cryptography starts with Shannon's paper :

Communication theory of secrecy systems (1949).
This was based on Shannon’s 1948 paper in which he had founded information theory.

nCryptologic research really took off in 1976 with the paper New directions in cryptography, by Diffie & Hellman.

They showed that secret communication is possible without a shared key.

nEarly ciphers

nStudying some early ciphers is useful because the empirical principles developed through their use are applied in the design and analysis of modern ciphers.

nCaesar cipher: (Julius Caesar 2000 years ago).

–Every letter is replaced by the letter “three to the right” in the alphabet, where this operation is cyclic. AàD, BàE, … XàA, YàB, ZàC

–For example: CABBAGE à FDEEDJH

–The generalised Caesar (or shift) cipher allowed the 3 to be replaced by an value between 1 and 25 inclusive.

nMonoalphabetic ciphers

nAlso known as simple substitution ciphers, each letter of the plaintext alphabet is replaced with an element of the ciphertext alphabet.

nThe substitution alphabet is the key.

nConsider that the plaintext and ciphertext alphabets are both the English alphabet.

nExample: Consider the plaintext and ciphertext alphabets to be the set of binary strings of length 3.

nPlaintext: 100 101 111

nCiphertext: 010 100 011

nUnique decryption: One-to-one.

nIn order for decryption to be unique, we need one-to-one mappings. Consider…

nDecryption: a bad day, a dad day, a bab day, a dab day, a bad bay, a dad bay, a bab bay, a dab bay.

nSecurity: Monoalphabetic ciphers

nTo decipher a ciphertext we need to know the substitution alphabet (key), or at least the subset of the key corresponding to those symbols which appear in the ciphertext.

nOne can use an exhaustive key search, to find the full key. This means use each key to decipher the ciphertext and accept the one that produces a meaningful plaintext.

nFor an alphabet of size N, the number of possible keys is N!.

nThe key is N elements long.

nFor the English alphabet there are 26!»4*10^(26) keys.

nWeak keys

nNot every substitution alphabet is suitable.

nFor example, a possible substitution which doesn’t hide the message very well at all is:

nIn most ciphers there are some weak keys.

nProperties of keys

nKeys must be easy to remember, a long random string is difficult to remember.

nThe key set must be large enough so that exhaustive key search is not easy.

nTo reduce the number of keys we may restrict ourselves to an indexed subset of all possible substitutions and use the index to identify the substitution that is used.

nIn this case the cipher algorithm is the collection of substitutions, and the key is the index.

nAdditive and multiplicative ciphers are examples of such indexed constructions.

nAdditive ciphers

nAlso known as translation ciphers, the substitution alphabet is obtained by shifting the plaintext alphabet by a fixed value. The amount of the shift is the key.

nFor example with the key of 3 we have

代写 CSCI361Computer Security

which is the substitution alphabet for the Caesar cipher.

nModular addition for additive ciphers

nAdditive ciphers can be described by modular addition.

nPlaintext character X, ciphertext character Y, shift (key) Z. Each of X,Y,Z is an element of the set {0,1,2,3,…,25} and they are related by Y = X Å Z, where Å denotes addition modulo 26. There are 26 keys, so bits are needed to represent the key.

nThis is a key space, hence exhaustive key search is a feasible attack against additive ciphers.

nMultiplicative Ciphers

nThe plaintext alphabet will again be taken as the set {0,1,…,25}.

nThe ciphertext alphabet can be determined using modular multiplication. We multiply each plaintext alphabet by a constant value, which is the key for this cipher.

nUsing similar notation to that for additive ciphers we write

Y = X Ä Z
where Ä represents multiplication modulo 26.

nNot all possible numbers for the key Z will result in a one-to-one mapping. The set of keys is therefore a subset of {0,1,…,25}.

nConsider Z=2

1 Ä 2 = 2 b à c
14 Ä 2 = 2 o à c

nFor all even numbers, and 13, the mapping not one-to-one. Hence the number of keys is 12, we need only 4 bits to represent the key.

nAgain exhaustive key search can easily break the cipher (find the secret key).

nAffine ciphers

nTo increase the number of keys we can combine additive and multiplicative ciphers to obtain affine ciphers.

Y = a Ä X Å Z
where X, Y, Z Î {0, 1, … 25}
and a Î {1,3,5,7,9,11,15,17,19,21,23,25}

nNumber of keys:

–12*26=312.

Still too small!

nKey phrase based ciphers

nThe next thing we can try and do is use a phrase as the key (index). We can also specify a starting letter for the translation alphabet.

nThis increases the size of the key space but makes the key (index) easy to remember.

nPhrase: bubble bath

nStarting letter: e

nThis cipher is significantly more resistant to exhaustive key search, but …

nStatistical cryptanalysis

n… it is insecure against statistical cryptanalysis.

nStatistical properties of the plaintext language can be used to cancel many keys in one step and enable the cryptanalyst to find the key without trying all of them.

nStatistical analysis relies on there being a relationship between the statistical properties of the plaintext and the statistical properties of the ciphertext, since we assume the attacker has only the ciphertext.

nStatistics of the English language

nThe letters can be grouped according to the frequency with which they occur.

nThe frequency of pairs of consecutive letters (bigrams) and triples of consecutive letters (trigrams) are important clues to cryptanalysts, as are spaces between words.

nFrequent bigrams:

th, he, in, er, an, re, ed,
on, es, st, en, at, to

nFrequent trigrams:

the, ing, and, her, ere, ent
tha, nth, was, eth, for, dth

nIt is important to realise that frequency counts only provide clues to the actual key used. The distribution will differ from sample to sample.

nWhat is the plaintext associated with the following ciphertext?

nAccording to Kirchoff’s Law the encryption algorithm is known to the attacker; it is key phrase substitution.

nBreaking the cipher

nThere are 337 letters, with frequencies:

nThis suggests we should first try Z being the encryption of e.

nThere are 8 JCZ in the ciphertext, this is almost certainly the in the plaintext.

nThe single letters will generally be i or a. In this case there is a single letter word V in the ciphertext.

nThe word JZB in the ciphertext can be identified by looking at the word teB and noting that B occurs in the second frequency group for this ciphertext.

–Some of those letters (t a o i n s h r) have already been identified.

nAfter a few of these kind of steps we can build up a preliminary mapping such as:

nMost of the time we would probably be safe to guess f as the starting position. With that assumption we can fill b,c,d à W,X,Y!

YKHLBA JCZ SVIJ JZB TZVHI JCZ VHJ DR IZXKHLBA VSS
RDHEI DR YVJV LBXSKYLBA YLALJVS IFZZXC CVI
LEFHDNZY EVBLRDSY JCZ FHLEVHT HZVIDB RDH JCLI
CVI WZZB JCZ VYNZBJ DR ELXHDZSZXJHDBLXI JCZ
XDEFSZQLJT DR JCZ RKBXJLDBI JCVJ XVB BDP WZ
FZHRDHEZY WT JCZ EVXCLBZ CVI HLIZB
YHVEVJLXVSST VI V HZIKSJ DR JCLI HZXZBJ
YZNZSDFEZBJ LB JZXCBDSDAT EVBT DR JCZ XLFCZH
ITIJZEI JCVJ PZHZ DBXZ XDBILYZHZY IZXKHZ VHZ BDP
WHZVMVWSZ.

during the last ten years the art of securing all
forms of data including digital speech has
Improved manifold the primary reason for this
has been the advent of microelectronics the
complexity of the functions that can now be
performed by the machine has risen
dramatically as a result of this recent
development in technology many of the cipher
systems that were once considered secure are
now breakable.

nWhat does this tell us?

nA cipher system should not allow statistical properties of the plaintext language to pass to the ciphertext.

nThe ciphertext generated by a “good” cipher system should be statistically indistinguishable from random text.

nSolutions

nPolyalphabetic ciphers.

–Vigenere ciphers.

nStatistical analysis of polyalphabetic ciphers.

–Kasiski method

–index of coincidence

nPolyalphabetic ciphers

nA ciphertext character represents more than one plaintext character. This must be done in a way that allows the plaintext to be recovered.

–For example, if B represents n and t we need to know when to decipher it as n, and when as t.

nA polyalphabetic cipher uses a sequence of substitution alphabets. If this sequence repeats after p characters, we say it has period p.

nThe Vigenère cipher

nThis uses 26 substitution alphabets, and a key word or key phrase.

nThe substitution alphabets are cyclically related.

nAnalysing Vigenère ciphers

nAs we stated earlier, the frequency distribution of the ciphertext can be flattened by using multiple substitution alphabets.

nWe analyse these ciphers by

1.Finding the period.

2.Breaking the ciphertext into components each obtained from a single substitution alphabet.

3.Solving each component using techniques discussed for monoalphabetic ciphers (statistical analysis)

nFinding the period:
The Kasiski method

nWe observe that two identical plaintexts will be encrypted to the same ciphertext if their occurrence is m positions apart, where m=0 mod p, i.e. when m is a multiple of the period p.

nFinding the period:
The Kasiski method

nWe search the ciphertext for repeated segments, and measure the distances between such repeated segments. It is likely, but not guaranteed, that these distances will be a multiple of the period.

nFinding the period:
The index of coincidence.

nConsider a string of length n, where each element is a letter from the English alphabet X=x1x2…xn

l Î {A,B,C,…,Z}, and fl frequency of l

nRandom IC and English IC

nIf X were a random string over the English alphabet we would expect the probability of each letter occurring to be the same, so that

IC » 1/26 » 0.038

nIf X is an English language text then we would expect, for p(l) the probability of a particular letter being l,

代写 CSCI361Computer Security

nThe two values 0.065 and 0.038 are sufficiently far apart that we will often be able to determine the correct keyword length.

nEnglish language letter probabilities

nIC for monoalphabetic ciphers

nFor monoalphabetic ciphers the index of coincidence is the same for the plaintext as for the ciphertext.

nThe IC for the ciphertext of a English text plaintext encrypted under a monoalphabetic cipher, will therefore be approximately 0.065, the same as English text.

nWe can use this test to find the period.

nExample

nSuppose we know the following ciphertext was generated using the Vigenère cipher. We need to find the period.

ooon yho cshexjlg nz xfksledcl ky luw h dltqupduw jjhrolww
jshehj dwns df llwpslpchlodf plzdv yohrh gm audwwyg uyg
vvqnzuss zyghd wfirustg qp djl hbp psqcl augmsmdlguof
pgmjontrf jshehj dwnslf zihj zaav u qxds fuyjw vt jcrxlgmtrfhz
xtvupdftqwz whnomkwhr vgts ftnw soq aksyaunb zlofek
jlzuehv wfiqhkzwiyv loon luw bbcbxw ac mfqq ds uch ssgi
ekw solrhka ihohjnfuoxsas wpqllf qtwz avy hlvlgn cdfns iq
sjvullpk hbx hllowh zxj usqwb xvfgpg ...

nTo find the period we guess and check the IC of the components. Lets try p=2.

oo yo sejg z fsec k lw dtudw jrlw sej ws f lplcld pzv or g adwg y vqzs zgd
frsg p j hp sc agsdgo pmotf sej wsf ij av qd fyw t cxgtfz tudtw wnmwr gs
tw o asan zoe jzev fqkwy lo lw bbw c fq s c sg ew ork iojfoss plf tz v hvg
cfs q julk b hlw zj sw xfp uzpw t ck b dabp oh ew flwh zwhl l cqj rqfb
fvfcvop vqeg glfb ew ilawd zcr ls zaz nwqd g v aqwl sr tdund qpug sl g
yaopq wvv c s shg ybclc z fk yosr sr y ...

on h chxl n xkldl y u h lqpu jhow jhh dn d lwsphof ld yhh m uwy ug vnus
yh wiut q dl b pql ummluf gjnr jhh dnl zh za u xs uj v jrlmrh xvpfqz hokh
vt fn sq kyub lfk luh wihziv on u bcx a mq d uh si k slha hhnuxa wql qw
ay lln dn i svlp hx loh x uqb vgg vfj v uw hx flwv pb k nywz jwuco v zh h
ylpa qladbn hbulu jqpa k ogqay wyok o mfh mluy w ay kzwo u vrvcd
zcql nd p cwtno shh a nh jch lydph i l ersxh u u ...

Component 1: IC = .047082
Component 2: IC = .050946

nTherefore p=6 seems most likely.

nThe keyword is should.

nTransposition Ciphers

nThe previous ciphers are all substitution ciphers

nnow consider classical transposition or permutation ciphers

nthese hide the message by rearranging the letter order

nwithout altering the actual letters used

nRail Fence cipher

nwrite message letters out diagonally over a number of rows

nthen read off cipher row by row

neg. write message out as:

m e m a t r h t g p r y
e t e f e t e o a a t

ngiving ciphertext

MEMATRHTGPRYETEFETEOAAT

–

nTransposition Cipher

nis a more complex transposition

nwrite letters of message out in rows over a specified number of columns

nthen reorder the columns according to some key before reading off the rows

Key: 4312567
Plaintext:
attackpostponeduntiltwoam
代写 CSCI361Computer Security

代写 CSCI361 Computer Security

代写 CSCI361Computer Security