IS 2150 / TEL 2810 Introduction to SecurityObjectivesSecure Information Transmission (network security model)Security of Information Systems (Network access model)Issues in Network securityCryptologyElementary Number TheoryDivisorsPrime NumbersGreatest common divisor (GCD)Relatively Prime NumbersThe modulo operationModular ArithmeticModulo OperationSlide 15Brief HistoryCryptosystemExampleCæsar cipherAttacksClassical CryptographySlide 22Slide 23Transposition CipherAttacking the CipherSlide 26Slide 27Substitution CiphersSlide 29Statistical AttackCharacter Frequencies (Denning)Statistical AnalysisCorrelation: (i) for 0 ≤ i ≤ 25The ResultCæsar’s ProblemVigenère CipherRelevant Parts of TableauUseful TermsAttacking the CipherOne-Time PadOverview of the DESDESEnciphermentThe f FunctionControversyDES ModesCBC Mode DecryptionSelf-Healing PropertyPublic Key CryptographyRequirementsDiffie-HellmanAlgorithmSlide 53RSASlide 55Confidentiality using RSAAuthentication using RSAConfidentiality + AuthenticationWarningsCryptographic ChecksumsMathematical characteristicsDefinitionCollisionsKeysMessage DigestHash Message Authentication Code (HMAC)Protection StrengthAverage time required for exhaustive key searchKey Points1IS 2150 / TEL 2810Introduction to SecurityJames JoshiAssistant Professor, SISLecture 8October 25, 2007Basic CryptographyNetwork Security2ObjectivesUnderstand/explain/employ the basic cryptographic techniquesReview the basic number theory used in cryptosystemsClassical systemPublic-key systemSome crypto analysisMessage digest3Secure Information Transmission(network security model)Trusted Third Partyarbiter, distributer of secret informationOpponentSecure MessageSecure Message MessageInformation channelSender ReceiverSecret InformationSecurity related transformationSecret Information Message4Security 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 securityDistribution of secret information to enable secure exchange of informationEffect of communication protocols needs to be consideredEncryption if used cleverly and correctly, can provide several of the security services Physical and logical placement of security mechanismsCountermeasures need to be considered6CryptologyCRYPTOLOGYCRYPTOGRAPHY CRYPTANALYSISPrivate Key(Secret Key)Public KeyBlock Cipher Stream Cipher Integer FactorizationDiscrete LogarithmEncipher, encryptDecipher, decrypt7Elementary Number TheoryNatural numbers N = {1,2,3,…}Whole numbers W = {0,1,2,3, …}Integers Z = {…,-2,-1,0,1,2,3, …}DivisorsA number b is said to divide a if a = mb for some m where a, b, m ZWe write this as b | aRead as “b divides a”8DivisorsSome common propertiesIf a | 1, a = +1 or –1If a|b and b|a then a = +b or –bAny b Z divides 0 if b 0If b|g and b|h then b|(mg + nh) where b,m,n,g,h ZExamples: The positive divisors of 42 are 1,2,3,6,7,14,21,423|6 and 3|21 => 3|21m+6n for m,n Z9Prime NumbersAn integer p is said to be a prime number if its only positive divisors are 1 and itself2, 3, 7, 11, ..Any integer can be expressed as a unique product of prime numbers raised to positive integral powersExamples7569 = 3 x 3 x 29 x 29 = 32 x 2925886 = 2 x 27 x 109 = 2 x 33 x 1094900 = 72 x 52 x 22100 = ?250 = ?This process is called Prime Factorization10Greatest common divisor (GCD)Definition: Greatest Common DivisorThis is the largest divisor of both a and bGiven two integers a and b, the positive integer c is called their GCD or greatest common divisor if and only ifc | a and c | b Any divisor of both a and b also divides cNotation: gcd(a, b) = cExample: gcd(49,63) = ?11Relatively Prime NumbersTwo numbers are said to be relatively prime if their gcd is 1Example: 63 and 22 are relatively primeHow do you determine if two numbers are relatively prime?Find their GCD orFind their prime factorsIf they do not have a common prime factor other than 1, they are relatively primeExample: 63 = 9 x 7 = 32 x 7 and 22 = 11 x 212The modulo operationWhat is 27 mod 5?DefinitionLet a, r, m be integers and let m > 0We write a r mod m if m divides r – a (or a – r) and 0 r < mm is called the modulusr is called the remainderNote that a = m.q + r where q is another integer (quotient)13Modular ArithmeticWe say that a b mod m if m | a – bRead as: a is congruent to b modulo mm is called the modulusExample: 27 2 mod 5Note that b is the remainder after dividing a by m BUT Example: 27 7 mod 5 and 7 2 mod 5a b mod m => b a mod m Example: 2 27 mod 5We usually consider the smallest positive remainder which is sometimes called the residue14Modulo OperationThe modulo operation “reduces” the infinite set of integers to a finite setExample: modulo 5 operationWe 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 OperationProperties[(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 HistoryAll encryption algorithms from BC till 1976 were secret key algorithmsAlso called private key algorithms or symmetric key algorithmsJulius Caesar used a substitution cipherWidespread 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 CD set of decryption functions d: C K MM set of plaintextsK set of keysC set of ciphertexts18ExampleCæsar cipherM = { sequences of letters }K = { i | i is 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 cipherLet k = 9, m =
View Full Document