OutlineAcknowledgementsBrief ReviewBrief Review – cont’dSlide 5Secure Encryption SystemsSym vs Asym Encryption AlgorithmsData Encryption Standard (DES)DES – cont’dDES – cont’dSlide 11One Cycle in DESSlide 13Public Key Systems (PKS)Some “Hard” theoriesSome “Hard” theories – cont’dExample PKSRSARSA – cont’dSlide 20Slide 21Slide 22RSA – cont’dMerkle-HellmanMerkle-Hellman – cont’dMerkle-Hellman - cont’dSlide 27Merkle-Hellman - cont’dSlide 29Evaluation of PKSCrypto-related TechniquesDigital SignaturesDigital Signatures – cont’dDigital CertificatesDigital Certificates – cont’dSlide 36SummaryCSE870: Advanced Software Engineering: Cheng (Sp 2003)1RRROutline•Brief review•Mainstream crypto-algorithms–Symmetric encryption algorithms•DES–Asymmetric encryption algorithms•RSA•Merkle-Hellman•Other crypto-related techniques–Digital signature–Digital certificateCSE870: 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 Engineering: Cheng (Sp 2003)3RRRBrief Review •Basic Concepts–Encryption–Crypto-system–Symmetric / asymmetric encryption–Cryptographer / crypto-analyst–Crypto-analysis–BreakabilityCSE870: Advanced Software Engineering: Cheng (Sp 2003)4RRRBrief Review – cont’d•Stream ciphers–Substitution-based ciphers•Mono-alphabetic ciphers: Caesar cipher•Poly-alphabetic ciphers: multiple alphabets–Strengths•Simple•Fast•Low error propagation rate–Weaknesses•Sustainable to frequency-based attacks•Sustainable to pattern-based attacksCSE870: Advanced Software Engineering: Cheng (Sp 2003)5RRRBrief Review – cont’d•Block ciphers–Transposition•Columnar transposition•Double transposition•Fractionated transposition–Strengths•Good diffusion, immune to pattern-based attacks–Weaknesses•Slow•Error propagation rateCSE870: Advanced Software Engineering: Cheng (Sp 2003)6RRRSecure Encryption Systems•Weaknesses of stream and block ciphers–Can be manually broken, although tedious•We will introduce–some “hard” encryption algorithms–Review 3 key, important encryption algs•DES, RSA, M-H–Look at cryptography related techniquesCSE870: Advanced Software Engineering: Cheng (Sp 2003)7RRRSym vs Asym Encryption Algorithms•Symmetric encryption algorithm–Encryption key == decryption key–DES•Asymmetric algorithms–Encryption key != decryption key–Basis of public-key encryption algorithms–RSA, M-H, …CSE870: Advanced Software Engineering: Cheng (Sp 2003)8RRRData Encryption Standard (DES)•Based on Shannon’s theory of information secrecy–Confusion: info is changed so that output bits have no obvious relation to input bits–Diffusion: spread the effect of one plaintext bits to other cipher-text bits.•History of DES–Developed by US govt for general public use (by National Institute of Standards and Technologies)–Milestones: 1972(CFP) - 1975(IBM) – 1976(NIST) – 2001(AES)–Cracked in 1999•56-bit key, Cracked in 22 hours 15 min (1999)–Extensions of DES•Triple-DES, length of key extends to 56*3•AES, 128, 192, or 256-bit key (2001)CSE870: Advanced Software Engineering: Cheng (Sp 2003)9RRRDES – cont’d •Overview of DES–Repeats 16 cycles of •substitution, for confusion•transposition, for diffusion–Splits data block into 2 pieces:•Scrambles each half independently•Combines key with one half –(key is transformed during each cycle)•Swap 2 halves•Repeat 16 times.CSE870: Advanced Software Engineering: Cheng (Sp 2003)10RRRDES – cont’d•Overview of DES – cont’dPlaintext(64b its)initialphaseleftrightfunctionfunctionFFinverseinitialphaseCipher-text16xtranspositionsubstitution[Shawn Hillis]CSE870: Advanced Software Engineering: Cheng (Sp 2003)11RRRDES – cont’d[NPS.Navy]CSE870: Advanced Software Engineering: Cheng (Sp 2003)12RRROne Cycle in DESLeft HalfRight HalfNew Left Half(Old Right Half)New Right Half++Key shiftedPermuted KeyPermuted Data[Pfleeger97]CSE870: Advanced Software Engineering: Cheng (Sp 2003)13RRRDES – cont’d•Evaluation–Strengths include•fast•simple•standard–Weaknesses include•weak keys, length of key is only 56bit•number of iterations, only 16•NSA involvement, trapdoor?CSE870: Advanced Software Engineering: Cheng (Sp 2003)14RRRPublic Key Systems (PKS)•Traditional key system (symmetric enc system):–Need a key for every pair of users–N*(N-1)/2 keys, grows exponentially with users–Each user has to keep track of many keys•Public key systems (asymmetric enc system)–Each user only has 2 keys: public and private key•M=D(kPRIV,E(kPUB,M))–Solid mathematical basis: one way functions: •E: M x Ke -> C and D=E-1: C x Kd -> M•Easy for Kd-holders to compute D, while difficult for others–May publish the public key freely•others can ally encrypt mesgs for A with A’s public keyCSE870: Advanced Software Engineering: Cheng (Sp 2003)15RRRSome “Hard” theories•Computational complexity–Is number of steps or arithmetic operations required to solve a computational problem–Polynomial time–NP, Non-deterministic polynomial time–NP-hard–NP-complete•Satisfaction problem•Hamilton’s problem–Cryptographers try to •find encryption algorithms that would require NP-complete algorithms to decryptCSE870: Advanced Software Engineering: Cheng (Sp 2003)16RRRSome “Hard” theories – cont’d•Basic number theory:–Prime factorization•Primes–1|p, p|p, no other factors•Euclid’s algorithm•The unsolved prime factorization problem problem–Is there an algorithm which can factor any k-digit number n so quickly that it’s running time is bound by a polynomial function of k–Modular Arithmetic•a = b mod N iff N|(a-b)–Inverses[William A. Stein]CSE870: Advanced Software Engineering: Cheng (Sp 2003)17RRRExample PKS•Rivest-Shamir-Adelman (RSA):–Based on number theory–Suspected to be NP-complete, not proven•Merkle-Hellman:–Based on knapsack problem–Proven to be NP-completeCSE870: Advanced Software Engineering: Cheng (Sp 2003)18RRRRSA•The most widely used enc and auth algorithm–In IE, Netscape, Notes, SSH Secure Shell, Quicken, etc.•Proposed in 1977 by –Ronald L. Rivest, MIT, now in MIT–Adi Shamir, MIT, now in Weizmann Institute–Leonard Adleman, MIT, now in USC•Now owned by RSA SecurityCSE870:
View Full Document
Unlocking...