EncryptionSlide 2TerminologySlide 4Encryption AlgorithmsPictorial RepresentationMore TermsCryptanalysisBreakable EncryptionCharacter RepresentationsSubstitution-based EncryptionPolyalphabetic Substitution CiphersSubstitution DiscussionTranspositions (Permutations)Transposition TechniquesTranspositionsSecure Encryption SystemsImportant Encryption AlgsSome “Hard” theoriesPublic Key EncryptionMerkle-Hellman KnapsacksSuperincreasing KnapsackMerkle-Hellman (cont’d)Slide 24Slide 25ExampleRSA: Rivest-Shamir-AdelmanDES: Data Encryption StandardOne Cycle in DESCSE870: Advanced Software Engineering: Cheng (Sp 2002)1RRREncryptionA Brief OverviewCSE870: Advanced Software Engineering: Cheng (Sp 2002)2RRREncryption•Encryption: –Definition: mechanisms to disguise the message so that if the intermission is intercepted/diverted, the content of the message will not be understood. –Impact: foundational building block to security-based computingCSE870: Advanced Software Engineering: Cheng (Sp 2002)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 be delivered to R appearing to come from SCSE870: Advanced Software Engineering: Cheng (Sp 2002)4RRRTerminology•Encryption: process of encoding a message so that its meaning is not obvious•Decryption: transforming encrypted message back to its normal form•Encode/decode: translating phrases to other words or phrases•Encipher/decipher: translating letters or symbols individually. •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 (Sp 2002)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 (Sp 2002)6RRRPictorial RepresentationKeyPlaintext CiphertextOriginalPlaintextEncryption DecryptionEncryption KeyPlaintext CiphertextOriginalPlaintextEncryption DecryptionDecryption KeyKDKESymmetric Encryption:Asymmetric Encryption:CSE870: Advanced Software Engineering: Cheng (Sp 2002)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 or receiver. –Cryptanalyst: Works on behalf of unauthorized interceptor•Cryptology: research/study into encryption/decryption–Includes cryptography and cryptanalysis.CSE870: Advanced Software Engineering: Cheng (Sp 2002)8RRRCryptanalysis•Objective: Break an encryption–Deduce the meaning of a ciphertext mesg–Determine decrypting algorithm that matches an encrypting algorithm•Possible techniques:–break single message–Recognize patterns in encrypted mesgs•break subsequent mesgs with straightforward decryption alg–Find general weaknesses in encryption alg•Without necessarily intercepting any mesgs•Tools:–Encrypted mesgs, known encryption algs, intercepted plaintext, data elements known/suspected of being in ciphertext, mathematical/statistical techniques, props of languages, computers, and luckCSE870: Advanced Software Engineering: Cheng (Sp 2002)9RRRBreakable Encryption•Encryption algorithm is BREAKABLE:–Given enough time and data, an analyst could determine the algorithm–Practicality is issue–For given cipher scheme, may have 1030 possible decipherments•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 Engineering: Cheng (Sp 2002)10RRRCharacter Representations•Study ways to encrypt any computer material:–ASCII/EBCDIC chars–Binary data or Object code–Control streamA B C D E F G H I J K L M0 1 2 3 4 5 6 7 8 9 10 11 12N O P Q R S T U V W X Y Z13 14 15 16 17 18 19 20 21 22 23 24 25CSE870: Advanced Software Engineering: Cheng (Sp 2002)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) ; –Use a key:–Weakness: study frequency distributionA B C D E F G H I J K L M N O P Q R S T U V W X Y ZK E YA B C D E F G H I J K L M N O P Q R S T U V W XS P EC T A U L R B D F G H I J K N N O Q V W X Y ZCSE870: Advanced Software Engineering: Cheng (Sp 2002)12RRRPolyalphabetic Substitution Ciphers•Desire flat distribution•Combine distributions that are high with low ones–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 mod 26 mod 26TREAT YIMPO SSIBL EFumnf dyvtf czysh hCSE870: Advanced Software Engineering: Cheng (Sp 2002)13RRRSubstitution Discussion•Major weakness: –frequency distribution •(index of coincidence: measure of variation between frequencies in a distribution)–Some letters are just used more frequently than others–Numerous enciphering techniques still can make it difficult to 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 of pattern begins•Compute difference between start points of success instances•Determine all factors of each
View Full Document