1IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssistant Professor, SISLecture 8October 25, 2007Basic CryptographyNetwork Security2Objectives Understand/explain/employ the basic cryptographic techniques Review the basic number theory used in cryptosystems Classical system Public-key system Some crypto analysis Message digest3Secure Information Transmission(network security model)Trusted Third Partyarbiter, distributer of secret informationOpponentSecure MessageSecure MessageMessageInformation channelSender ReceiverSecret InformationSecurity related transformationSecret InformationMessage4Security of Information Systems(Network access model)GateKeeperOpponent- hackers- softwareAccess ChannelInternalSecurity ControlDataSoftwareGatekeeper – firewall or equivalent, password-based loginInternal Security Control – Access control, Logs, audits, virus scans etc.5Issues in Network security Distribution of secret information to enable secure exchange of information Effect of communication protocols needs to be considered Encryption if used cleverly and correctly, can provide several of the security services Physical and logical placement of security mechanisms Countermeasures need to be considered6CryptologyCRYPTOLOGYCRYPTOGRAPHY CRYPTANALYSISPrivate Key(Secret Key)Public KeyBlock Cipher Stream Cipher Integer FactorizationDiscrete LogarithmEncipher, encryptDecipher, decrypt7Elementary Number Theory Natural numbers N = {1,2,3,…} Whole numbers W = {0,1,2,3, …} Integers Z = {…,-2,-1,0,1,2,3, …} Divisors A number bis said to divide aif a= mbfor some m where a, b, m∈ Z We write this as b|a Read as “bdivides a”8Divisors Some common properties If a| 1, a= +1 or –1 If a|band b|athen a= +b or –b Any b∈ Z divides 0 if b ≠ 0 If b|gand b|hthen b|(mg + nh) where b,m,n,g,h∈ Z Examples: The positive divisors of 42 are 1,2,3,6,7,14,21,42 3|6 and 3|21 => 3|21m+6n for m,n∈ Z9Prime Numbers An integer pis said to be a prime number if its only positive divisors are 1 and itself 2, 3, 7, 11, .. Any integer can be expressed as a uniqueproduct of prime numbers raised to positive integral powers Examples 7569 = 3 x 3 x 29 x 29 = 32x 292 5886 = 2 x 27 x 109 = 2 x 33x 109 4900 = 72x 52 x22 100 = ? 250 = ? This process is called Prime Factorization10Greatest common divisor (GCD) Definition: Greatest Common Divisor This is the largest divisor of both aand b Given two integers aand b, the positive integer cis called their GCD or greatest common divisor if and only ifc| aand c| b Any divisor of both aand balso divides c Notation: gcd(a, b) = c Example: gcd(49,63) = ?11Relatively Prime Numbers Two numbers are said to be relatively prime if their gcd is 1 Example: 63 and 22 are relatively prime How do you determine if two numbers are relatively prime? Find their GCD or Find their prime factors If they do not have a common prime factor other than 1, they are relatively prime Example: 63 = 9 x 7 = 32x 7 and 22 = 11 x 212The modulo operation What is 27 mod 5? Definition Let a, r, mbe integers and let m> 0 We write a≡rmod mif mdivides r–a (or a–r) and 0 ≤r< mmis called the modulusr is called the remainder Note that a= m.q+ r where qis another integer (quotient)13Modular Arithmetic We say that a ≡bmod mif m| a–b Read as: ais congruent to bmodulo mm is called the modulus Example: 27 ≡ 2 mod 5 Note that bis the remainderafter dividing aby m BUT Example: 27 ≡ 7 mod 5 and 7 ≡ 2 mod 5a ≡bmod m => b ≡amod m Example: 2 ≡ 27 mod 5 We usually consider the smallest positive remainder which is sometimes called the residue14Modulo Operation The modulo operation “reduces” the infinite set of integers to a finite set Example: modulo 5 operation We have five sets {…,-10, -5, 0, 5, 10, …} => a≡ 0 mod 5 {…,-9,-4,1,6,11,…} => a≡ 1 mod 5 {…,-8,-3,2,7,12,…} => a≡ 2 mod 5, etc. The set of residues of integers modulo 5 has five elements {0,1,2,3,4} and is denoted Z5.15Modulo Operation Properties [(a mod n) + (b mod n)] mod n = (a + b) mod n [(a mod n) - (b mod n)] mod n = (a -b) mod n [(a mod n) × (b mod n)] mod n = (a ×b) mod n (-1) mod n = n -1 (Using b = q.n+ r, with b = -1, q = -1 and r = n-1)16Brief History All encryption algorithms from BC till 1976 were secret key algorithms Also called private key algorithms or symmetric key algorithms Julius Caesar used a substitution cipher Widespread use in World War II (enigma) Public key algorithms were introduced in 1976 by Whitfield Diffie and Martin Hellman17Cryptosystem (E, D, M, K, C) E set of encryption functions e: M × K → C D set of decryption functions d: C × K → M M set of plaintexts K set of keys C set of ciphertexts18Example Cæsar cipher M = { sequences of letters } K = { i| iis an integer and 0 ≤i≤ 25 } E = { Ek| k∈ K and for all letters m,Ek(m) = (m+ k) mod 26 } D = { Dk| k∈ K and for all letters c,Dk(c) = (26 + c–k) mod 26 } C = M19Cæsar cipher Let k = 9, m = “VELVET” (21 4 11 21 4 19)Ek(m) = (30 13 20 30 13 28) mod 26=“4 13 20 4 13 2” = “ENUENC”Dk(m) = (26 + c – k) mod 26= (21 30 37 21 30 19) mod 26= “21 4 11 21 4 19” = “VELVET”25242322212019181716151413ZYXWVUTSRQPON1211109876543210MLKJIHGFEDCBA20AttacksCiphertext only: adversary has only Y; goal ?Known plaintext: adversary has X, Y; goal ?Chosen plaintext: adversary gets a specific plaintext enciphered; goal ?21Classical CryptographyKey SourceOscarEncrypt(algorithm)Decrypt(algorithm)Alice BobSecret key KSecure ChannelPlaintext XCiphertext YPlaintext XEd (Cryptoanalyst)X’, K’22Classical Cryptography Sender, receiver share common key Keys may be the same, or trivial to derive from one another Sometimes called symmetric cryptography Two basic types Transposition ciphers Substitution ciphers Product ciphers Combinations of the two basic types23Classical Cryptographyy = Ek(x) : Ciphertext Æ Encryptionx = Dk(y) : Plaintext Æ Decryptionk = encryption and decryption key The functions Ek() and Dk() must be inverses of one anotherEk(Dk(y)) = ?Dk(Ek(x)) = ?Ek(Dk(x)) = ?24Transposition Cipher Rearrange letters in plaintext to produce
View Full Document
Unlocking...