CSE870: Advanced Software Engnineering (Sp 2003)1CSE870: 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 Engnineering (Sp 2003)2CSE870: Advanced Software Engineering: Cheng (Sp 2003) 3RRRBrief Review • Basic Concepts– Encryption– Crypto-system– Symmetric / asymmetric encryption– Cryptographer / crypto-analyst– Crypto-analysis– Breakability CSE870: 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 Engnineering (Sp 2003)3CSE870: 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 Engnineering (Sp 2003)4CSE870: 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 Engnineering (Sp 2003)5CSE870: 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(64bits)initialphaseleftrightfunctionFinverseinitialphaseCipher-text16xtranspositionsubstitution[Shawn Hillis]CSE870: Advanced Software Engnineering (Sp 2003)6CSE870: 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 Engnineering (Sp 2003)7CSE870: 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 Engnineering (Sp 2003)8CSE870: 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 nso 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 Engnineering (Sp 2003)9CSE870: 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: Advanced Software Engnineering (Sp 2003)10CSE870: Advanced
View Full Document