代写 CSCI361 Computer Security

  • 100%原创包过,高质量代写&免费提供Turnitin报告--24小时客服QQ&微信:273427
  •  代写 CSCI361 Computer Security

    nCSCI361

    Computer Security
    nClassical cryptology
    n
    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.
    n
    nCryptanalysis: Analysing security algorithms with the aim of breaching security.
    nThe basic secrecy channel
    nThe basic secrecy channel
    nThe channel can be a communication channel or a storage channel.
    n
    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.
    n
    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).
    n
    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.
    n
    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.
    n
    nKirchoff’s Law
    nThis is the main assumption of cryptology.
    n
      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.
    n
    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.
    n
    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.
    n
    nExample: Consider the plaintext and ciphertext alphabets to be the set of binary strings of length 3.
    n
    n
    n
    n
    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…
    n
    n
    n
    n
    n
    n
    n
    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.
    n
    n
    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:
    n
    n
    n
    n
    n
    n
    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.
    n
    nThe key set must be large enough so that exhaustive key search is not easy.
    n
    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.
    n
    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
    n
    n
    代写 CSCI361 Computer Security
     
      which is the substitution alphabet for the Caesar cipher.
    nModular addition for additive ciphers
    nAdditive ciphers can be described by modular addition.
    n
    n
    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.
    n
    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.
    n
    nThis increases the size of the key space but makes the key (index) easy to remember.
    n
    nPhrase:   bubble bath
    nStarting letter:   e
    n
    n
    n
    n
    n
    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.
    n
    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.
    n
    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.
    n
    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.
    n
    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.
    nBreaking the cipher
    nThere are 337 letters, with frequencies:
    n
    n
    n
    n
    n
    nThis suggests we should first try Z being the encryption of e.
    n
    n
    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.
    n
    nAfter a few of these kind of steps we can build up a preliminary mapping such as:
    n
    n
    n
    n
    n
    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!
    n
    n
    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.
    n
    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.
    n
    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.
    n
    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,
    n
    n
    代写 CSCI361 Computer 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 ...
    n
    n
    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 ...
    n
    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
    n
    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
    代写 CSCI361 Computer Security