CSE870: Advanced Software Engnineering (Sp 2003)1CSE870: Advanced Software Engineering: Cheng (Sp 2003) 1RRREncryptionA Brief OverviewCSE870: Advanced Software Engineering: Cheng (Sp 2003) 2RRRAcknowledgements• Charles Pfleedger• E. Spafford• William A. Stein• FOLDOC• Sunit Chauhan• Jim Xu, et al.• Shawn HillisCSE870: Advanced Software Engnineering (Sp 2003)2CSE870: Advanced Software Engineering: Cheng (Sp 2003) 3RRROutline• Basic concepts• Stream ciphers• Block ciphers• Summary of Stream and Block ciphers• Public key encryptionCSE870: Advanced Software Engineering: Cheng (Sp 2003) 4RRRWhy do we need encryption• Scenario: – Swants 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 Engnineering (Sp 2003)3CSE870: Advanced Software Engineering: Cheng (Sp 2003) 5RRRBasic Concepts• 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 2003) 6RRRBasic Concepts – cont’d• Cryptosystem– 5-tuple <E, D, M, K, C>• M: set of plain text• C: set of cipher text• K: set of keys• E: M x K -> C• D: C x K -> MCSE870: Advanced Software Engnineering (Sp 2003)4CSE870: Advanced Software Engineering: Cheng (Sp 2003) 7RRRBasic Concepts – cont’d• 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 2003) 8RRRBasic Concepts – cont’d• 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 Engnineering (Sp 2003)5CSE870: Advanced Software Engineering: Cheng (Sp 2003) 9RRRPictorial RepresentationKeyPlaintext CiphertextOriginalPlaintextEncryption DecryptionEncryption KeyPlaintext CiphertextOriginalPlaintextEncryption DecryptionDecryption KeyKDKESymmetric Encryption:Asymmetric Encryption:CSE870: Advanced Software Engineering: Cheng (Sp 2003) 10RRRBasic Concepts – cont’d• 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 Engnineering (Sp 2003)6CSE870: Advanced Software Engineering: Cheng (Sp 2003) 11RRRBasic Concepts – cont’d• Cryptanalysis– 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 2003) 12RRRBasic Concepts – cont’d• Breakability– 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 1010ops/sec– Require 1020secs – 1012years– Reality Check:• Cryptanalyst won’t just try the “hard” ways– Ex: more clever approach, might only take 1015ops• 1010 ops/sec, 1015ops will take about one day• Breakability estimates are based on CURRENT technologyCSE870: Advanced Software Engnineering (Sp 2003)7CSE870: Advanced Software Engineering: Cheng (Sp 2003) 13RRRStream Ciphers and Block Ciphers• Stream Ciphers– Letter by letter– E.g. substitution-based cipher• Block cipher– Block by block– E.g. transposition based cipherCSE870: Advanced Software Engineering: Cheng (Sp 2003) 14RRRCharacter Representations• Study ways to encrypt any computer material:– ASCII/EBCDIC chars– Binary data or Object code– Control stream25242322212019181716151413ZYXWVUTSRQPON1211109876543210MLKJIHGFEDCBACSE870: Advanced Software Engnineering (Sp 2003)8CSE870: Advanced Software Engineering: Cheng (Sp 2003) 15RRRSubstitution-based Encryption• Monoalphabetic Ciphers– Caesar Cipher: ci= E(pi) = pi+ k– Cryptosystem • K: {k| 0<=k<=25}• E: (m+k) mod 26• D: (26+c-k) mod 26• C = M = {all sequence of roman letters}– Examples ( k=3)• wuhdwb lpsrvvleoh,• wklv phvvdjh lv qrw wrr kdug wr euhdn– Evaluation• Easy to perform in field (no written instructions)• Too simple, very easy to breakCSE870: Advanced Software Engineering: Cheng (Sp 2003) 16RRRSubstitution-based Encryption –cont’d– Weakness: study frequency distribution[Jim Xu, et al.]CSE870: Advanced Software Engnineering (Sp 2003)9CSE870: Advanced Software Engineering: Cheng (Sp 2003) 17RRRSubstitution-based Encryption-cont’d• Polyalphabetic Substitution Ciphers– Desire flat distribution– Combine distributions that are high with low ones• Encipher Tas a and sometimes
View Full Document
Unlocking...