CSE870: Advanced Software Engnineering1CSE870: Advanced Software Engineering: Cheng 1RRREncryptionA Brief OverviewCSE870: Advanced Software Engineering: Cheng 2RRREncryption• Encryption:– Definition: mechanisms to disguise themessage so that if the information isintercepted/diverted, the content of themessage will not be understood.– Impact: foundational building block tosecurity-based computingCSE870: Advanced Software Engineering: Cheng 3RRRTerminology• Scenario:–S wants to send the message T to R, where an outsider,O, wants the message and tries to access it.–S: Sender–R: Receiver–T: Transmission Medium–O: Interceptor or Intruder.• 4 ways O might try to access message.– Block it: prevent T from reaching R (availability)– Intercept it: read or listen to message (secrecy)– Modify it: obtaining message and changing it– Fabricate: generate an authentic-looking message to bedelivered to R appearing to come from SCSE870: Advanced Software Engnineering2CSE870: Advanced Software Engineering: Cheng 4RRRTerminology• Encryption: process of encoding a message so that itsmeaning is not obvious• Decryption: transforming encrypted message back toits normal form• Encode/decode: translating phrases to other words orphrases• Encipher/decipher: translating letters or symbolsindividually.• Plaintext: original form of message: P = (p1,p2,…, pn)• Ciphertext: encrypted form of message: C = (c1,c2,…, cn)• Encryption/decryption relationships:– C = E(P); P = D(C); P = D(E(P))CSE870: Advanced Software Engineering: Cheng 5RRREncryption Algorithms• Some encryption algs use a key K– C = E(K,P)– E is a SET of encryption algs– Key K selects specific one• Symmetric Encryption: P = D(K,E(K,P))– encryption/decryption keys are the same• Asymmetric Encryption: P = D(KD,E(KE,P))CSE870: Advanced Software Engineering: Cheng 6RRRPictorial RepresentationKeyPlaintext CiphertextOriginalPlaintextEncryption DecryptionEncryption KeyPlaintext CiphertextOriginalPlaintextEncryption DecryptionDecryption KeyKDKESymmetric Encryption:Asymmetric Encryption:CSE870: Advanced Software Engnineering3CSE870: Advanced Software Engineering: Cheng 7RRRMore Terms• Cryptography: (hidden writing)– Practice of using encryption to conceal text• Cryptanalyst:– Person who studies encryption and encrypted messages– Intent: find hidden meaning• Cryptographer and Cryptanalyst:– Both attempt to translate coded material to original form– Cryptographer: works on behalf of legitimate sender orreceiver.– Cryptanalyst: Works on behalf of unauthorized interceptor• Cryptology: research/study into encryption/decryption– Includes cryptography and cryptanalysis.CSE870: Advanced Software Engineering: Cheng 8RRRCryptanalysis• Objective: Break an encryption– Deduce the meaning of a ciphertext mesg– Determine decrypting algorithm that matches an encryptingalgorithm• Possible techniques:– break single message– Recognize patterns in encrypted msgs• break subsequent msgs with straightforward decryption alg– Find general weaknesses in encryption alg• Without necessarily intercepting any msgs• Tools:– Encrypted msgs, known encryption algs, intercepted plaintext, dataelements known/suspected of being in ciphertext,mathematical/statistical techniques, props of languages, computers, andluckCSE870: Advanced Software Engineering: Cheng 9RRRBreakable Encryption• Encryption algorithm is BREAKABLE:– Given enough time/data, an analyst could determine alg.– Practicality is issue– For given cipher scheme, may have 1030 possibledecipherments• Select one from 1030– Current technology: perform 1010 ops/sec• Require 1020 secs == 1012 years• Reality Check:– Cryptanalyst won’t just try the “hard” ways• Ex: more clever approach, might only take 1015 ops– 1010 ops/sec, 1015 ops will take about one day– Breakability estimates are based on CURRENT technologyCSE870: Advanced Software Engnineering4CSE870: Advanced Software Engineering: Cheng 10RRRCharacter Representations• Study ways to encrypt any computermaterial:– ASCII/EBCDIC chars– Binary data or Object code– Control stream25242322212019181716151413ZYXWVUTSRQPON1211109876543210MLKJIHGFEDCBACSE870: Advanced Software Engineering: Cheng 11RRRSubstitution-based Encryption• Monoalphabetic Ciphers– Caesar Cipher: ci = E(pi) = pi + 3• wuhdwb lpsrvvleoh,• wklv phvvdjh lv qrw wrr kdug wr euhdn• Easy to perform in field (no written instructions)– Permutation: reordering of the elements• ci= aπ(pi) ; π (λ) = 25− λ– Use a key:– Weakness: study frequency distributionXWVUTSRQPONMLKJIHGFEDCBAYEKZYXWVQONNKJIHGFDBRLUATCEPSZYXWVUTSRQPONMLKJIHGFEDCBACSE870: Advanced Software Engineering: Cheng 12RRRPolyalphabetic Substitution Ciphers• Desire flat distribution• Combine distributions that are high with lowones– Encipher T as a and sometimes as b– Also encipher X as a and sometimes as b• Use two separate encryption alphabets– Tables for odd and even positionsπ1 (λ) = (3 ∗ λ) mod 26π2 (λ) =( (5 ∗ λ) + 13) mod 26TREAT YIMPO SSIBL EFumnf dyvtf czysh hCSE870: Advanced Software Engnineering5CSE870: Advanced Software Engineering: Cheng 13RRRSubstitution Discussion• Major weakness:– frequency distribution• (index of coincidence: measure of variation between frequencies ina distribution)– Some letters are just used more frequently than others– Numerous enciphering techniques still can make it difficultto hide these patterns– Kasiski Method: find number of alphabets used• Identify repeated patterns of 3 or more chars• For each pattern, write down position at which each instance ofpattern begins• Compute difference between start points of success instances• Determine all factors of each difference• If polyalphabetic subst used, key length will be one of the factorsthat appears often in previous step.CSE870: Advanced Software Engineering: Cheng 14RRRTranspositions (Permutations)• Definition: encryption where letters arerearranged.• Goal: diffusion, spread info frommessage or key out widely across theciphertext.• Try to break established patterns.CSE870: Advanced Software Engineering: Cheng 15RRRTransposition Techniques• ColumnarTranspositions:– Rearrangement ofchars of plaintextinto colsEtc.C12C11C10C9C8C7C6C5C4C3C2C1SKROWNOITISOPSNARTRANMULOCAWOHWOHSOTEGASSEMASISIHTtssoh oaniw haaso lrsto imghw utpir seeoa mrook istwc nasnsCSE870: Advanced
View Full Document
Unlocking...