### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Network Security CSC 474

NCS

GPA 3.94

### View Full Document

## 31

## 0

## Popular in Course

## Popular in ComputerScienence

This 92 page Class Notes was uploaded by Jaden Jakubowski on Thursday October 15, 2015. The Class Notes belongs to CSC 474 at North Carolina State University taught by Peng Ning in Fall. Since its upload, it has received 31 views. For similar materials see /class/223809/csc-474-north-carolina-state-university in ComputerScienence at North Carolina State University.

## Reviews for Network Security

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/15/15

NC STATE UNIVERSITY ComputerScience CSC 474 Information Systems Security Topic 22 Secret Key Cryptography CSC311 Dr Pengng Agenda Generic block cipher Feistel cipher DES Modes of block ciphers Multiple encryptions Message authentication through secret key cryptography NC STATE UNIVERSITY Computer Science csc 474 Dr PengNing Y Computer Science Generic Block Cipher CSC 4m Dr Pang Ning Generic Block Cipher Plaintext Cipher block Secret key block 0 Of length oflength N NC STATE UNIVERSITY Computer Science csc 474 Dr PengNing Generic Block Encryption Cont d 0 Convert one block to another onetoone Long enough to avoid knownplaintext attack but not too long performance 64 bit typical 0 Na39139ve 264 input values 64 bits each 0 Output should look random No correlation between plaintext and ciphertext Bit spreading NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning Generic Block Encryption Cont d Achieve by substitution 7 Need to know how to substitute each plaintext message 7 How many bits in the key for kbit blocks bits Achieve by permutation 7 Need to know which position each bit is placed 7 How many bits for kbit blocks bits Achieve by combinations of substitutions and permutations 7 How about 9P98989P9 7 How about 89P9P989 7 Lesson NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 6 Feistel Cipher NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning Feistel Cipher Confusion 7 Make the relationship between the plainteXtkey and the cipherteXt as complex as possible 7 Achieved by complex substitution algorithm Diffusion 7 Dissipate the statistical structure of the plaintext 7 Achieved by having each plainteXt digit affect many cipherteXt digits 7 Equivalently having each cipherteXt digit affected by many plainteXt digits NC STATE UNIVERSITY Computer Science CSC 474 Dr Peng Ning Feistel Cipher cont d Alternate diffusion and confusion Equivalently alternate substitution and permutation NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 9 Feistel Cipher Structure Plaintext 2W bits La Ra Encuption Round 1 Round 139 Round 71 Ciphertext 2W bits NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 10 Feistel Cipher Structure cont d Ciphertext 2W bits Dec ption La Round 1 Round 139 Round 71 r n1 Plaintext 2W bits NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 11 One Round Feistel Cipher Plaintext 2W bits Encryption NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 11 Realization of Feistel Cipher Parameters Block Size typically 64 bits Key Size commonly 128 bits Number of Rounds l6 Subkey Generation algorithm Round Function NC STATE UNIVERSITY Computer Science csc 474 Dr PengNing 13 NC STATE UNIVERSITY CompllterSCience DES Data Encryption Standard CSC J74 Dr Peng Ning DES Data Encryption Standard Published in l977 standardized in l979 expired in l 998 Similar structure to Feistel cipher Key 64 bit quantity8 bit parity56bit key 7 Every 8th bit is a parity bit 64 bit input 64 bit output 64 bit M 64 bit C 39 3 DES 739 3 Encryption 56 bits Computer Science csc 474 Dr Peng Ning 15 DES Top V1 ew Initial Permutation 48bit Kl 48bit K2 48bitK16 Swap 32bit halves Final Permutation NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 16 Bit Permutation lto l Input Output 1 0 1 1 1 2261332 3 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 17 Initial and Final Permutations Initial permutation IP View the input as M 8 X 8 bit matrix Transform M into M1 in two steps Transpose row X into column 9X 0ltXlt9 Apply permutation on the rows For even row y it becomes row y2 For odd row y it becomes row 5y2 0 Final permutation FP IP391 Why NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 18 PerRound Key Generation w I Ci128bits Di128bits Circular Left Shift Circular Left Shift Rounci 12916 single shift Others two bits Permutation with Discard 48 its i 28 bits Di 28 bits NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 19 A DES Round I 32 its H 32 bits One Round K E Mangler ncryption F unct10n gt 32 bits 32 bits I 32 bits I NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 20 Bits Expansion 1 4 5 32 Input MO H1 H0H1 i quot 1 Output IHOiOHIiOHIHOHIi 1M 1 2 3 4 5 6 7 8 48 ComputerScience csc474 Dr PengNing 21 EBoxofDES How is the E Box de ned 32 1 2 3 4 5 4 5 6 7 8 9 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 21 Mangler Function subkey The permutation produces spread among the chunksSboxes Computer Science csc 474 Dr Peng Ning S Box Substitute and Shrink 48 bits gt 32 bits 86 gt 8 4 2 bits used to select amongst 4 permutations for the rest of the 4bit quantity 2 bits row 01 02 O3 O4 4 bits an 1nteger between 0 and 15 column 118 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 24 81 p 71 Each row and column contain different numbers 0 l 2 3 4 5 6 15 0 l4 4 l3 1 2 15 ll 1 0 15 7 4 l4 2 l3 2 4 l 14 8 l3 6 2 3 15 12 8 2 4 9 1 Example input 100110 output Computer Science csc 474 Dr Peng Ning 25 DES Standard Cipher Iterative Action 64 bits 7 Key 48 bits 7 Output 64 bits 7 Input h Key Generation BOX 7 Input 56 bits 7 Output 48 bits NC STATE UNIVERSITY Computer Science CSC One round Total 16 rounds 474 Dr Peng Ning Avalanche Effect A small change in either the plaintext or the key should produce a significant change in the ciphertext DES has a strong avalanche effect Example 7 Plaintexts 0X0000000000000000 and 0X8000000000000000 7 Same key 0X016B24621C181C32 7 34 bits difference in ciphertexts 7 Similar result with same plainteXt and slightly different keys NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 27 Concerns About DES Key space problem 56 bit key 256 7 DESCHALL recovered RSA challenge I key on June 17 1997 6 month into the contest 7 25m total cost July 15 1998 RSA DES challenge 11 key recovered in 56 hours Cryptanalysis 7 Sixteen Weak and semiweak keys 7 Differential cryptanalysis require less tries using chosen plainteXtciphertext Biham 1993 Effective up to 15 rounds DES is well designed to defeat differential analysis 7 Linear cryptanalysis requires only known plainteXtciphertext Matsui 1993 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning zx DES Summary 0 Simple easy to implement Hardwaregigabitssecond softwaremegabitssecond 56bit key DES maybe acceptable for non critical applications but triple DES DES3 should be secure for most applications today 0 Supports several operation modes ECB CBC OFBj CFB Nc STATE UNIVERSITY Computer Science csc 474 Dr PengNing 29 Computer Science Modes of Block Cipher Operations csc 474 Dr Peng ng 3n Encrypting a Large Message 0 Modes of block cipher operations ECB Electronic Code Book CBC Cipher Block Chaining Mode OFB Output Feedback Mode CFB Cipher Feedback Mode NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 31 Electronic Code Book ECB M1 M7 M2 M4 MM MM 64 MM i CI i i 02 i i C3 i i C4 i Divide and conquer NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 32 ECB Properties i Cl i i 02 i i C3 i i C4 i N11 2 M3 gt Computer Science csc 474 Dr Peng Ning 33 ECB Properties Cont d Cipher block substitution and rearrangement attacks fabrication of specific information o No error propagation NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 34 Cipher Block Chaining CBC M1 7 M l6ffl NM NM l46l3acl IV Initialization Vector ENC 3quot4 l Cl l l 02 l l C3 l l C4 l M1 M3 very unlikely leads to C1 C3 35 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning CBC Decryption lMlllellMgllMH IV lclllCzll03llC4l ComputerScience csc474 DrPengNing 36 CBC Properties Chaining dependency Each ciphertext block depends on all preceding plaintext blocks Error propagation Each error in cJ affects decipherment of cJ and cJ 1 Predictable bit change in nil1 by alert corresponding bits of cj Error recovery An error in cJ doesn t propagate beyond cJ 1 Can recover from loss of cipher text blocks NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 37 Output Feedback Mode OFB Like a Random Number Generator CJ CJ NC STATE UNIVERSITY Computer Science WC 0 4 csc 474 Dr Peng Ning 38 OF B Properties Chaining dependencies 7 Key stream is plainteXtindependent 7 Allow precomputing of pseudorandom stream One Time Pad XOR can be implemented very efficiently No error propagation problem as in CBC Error recovery 7 Can recover from bit error 7 But not from block loss If the attacker knows the plaintext he can change the ciphertext by XORing it with the plaintext and then XORing with whatever he wants to transmit NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 39 General k bit CFB NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 40 CFB Properties NC STATE UNIVERSITY Computer Science Chaining dependencies 7 Ciphertext block cj depends on all preceding plaintext blocks Error propagation 7 Bit error in one ciphertext block affects the next several blocks Error recovery 7 Can recover from bit errors after several blocks 7 Can resynchronize after loss of blocks Secure against known plaintext attack plaintext substitution Less vulnerable to tampering with ciphertext cipher Ci s impact on n1i1 is subtle through encryption function and thus less predictable csc 474 Dr PengNing 41 Computer Science Multiple Encryption CSC J 74 Dr Peng Ning 41 Triple DES Maj or limitation of DES Key length is too short 56 bits 0 Question Can we apply DES multiple times to increase the strength of encryption Advantage preserve the existing investment in software and equipment NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 43 Triple DES Cont d Double DES Encrypt the plaintext twice with two different DES keys Key length increases to 112 bits Two concerns Is DES a group Ek2Ek1P Ek3P Implication Meetin themiddle attack NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 44 Meetinthemiddle attack Encryption P X C 4 Observation K2 K1 l X l P H E C For a known pair RC 7 Encrypt P for all 256 values for K1 7 Store the results in a table sorted by the value of X 7 Decrypt C for all 256 values for K2 and for each result check the table 7 A match reveals a possible combination of key Decryption XEK1PDK2C NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 45 Meetinthemiddle attack Cont d Analysis 7 With one pair PC keys that can survive the test is 2112264248 7 For each pair of keys K1K2 the probability that we can nd a match in the table is 23954 7 With another pair P C the probability that any incorrect key can survive both tests is 248 25423915 7 The probability that the correct keys are determined is 12 Goal of double DES 7 Increase the difficulty of exhaustive key search 2112 keys 7 In effect the effort is on the order of 255 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 46 Triple DES Cont d Encryption P E C K1 K2 K1 Decryption y i i P I3 C Apply DES encryptiondecryption three times 7 With two keys or three keys 39 Why EDE 7 It s not clear if DES is a group when this was proposed 7 If one key is used it s equivalent to doing DES once NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 47 Triple DES Is Not Ideal Ef ciency demands schemes with longer keys to begin with Triple DES runs one third as fast as DES on the same platform 0 New candidates are numerous RC5 IDEA two sh CAST etc New AES NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 48 Computer Science Message Authentication through Secret Key Algorithms CSC w Dr Pengng Message Authentication Message authentication is the process to verify that received messages come from the alleged source and have not been altered The goals of message authentication is to prevent 7 Masquerade insertion of messages from a fraudulent source 7 Content modi cation change of messages 7 Sequence modi cation insertion deletion and reordering of messages 7 Timing modi cation delay or replay of messages NC STATE UNIVERSITY Computer Science csc 474 Dr PengNing 50 Message Authentication Functions 0 Message encryption 0 Message Authentication Code MAC 0 Hash function NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 51 Encryption for Message Authentication 0 Conventional cryptography Use the structure or pattern in the plaintext Accept the decrypted plainteXt if it is in an intelligible form No guarantee Append an errordetecting code Frame Check Sequence or F CS to the plaintext before encryption Encryption CEKPHFP Decryption P HFPDKC and then check if FP FP The order of FCS and encryption is critical NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 51 Message Authentication Code MAC MAC Also known as cryptographic checksum Message Integrity Code MIC Assumption the sender and the receiver share a common secret key A small fixedsize block generated from the message with secret key cryptography Usually appended to the original message NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 53 MAC Cont d Source Destination Compare CKM 0 Mode 1 Message authentication No confidentiality NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 54 MAC Cont d Source Destination Mode 11 7 Message authentication and confidentiality 7 Authentication tied to plainteXt NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 55 MAC Cont d Source Destination CK1EK2M Mode III Message authentication and confidentiality Authentication tied to ciphertext NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 56 Requirements for MAC For M and CKM it s computationally infeasible to construct a message M such that CKM CKM CKM should be uniformly distributed in terms of M 7 For any two messages M and M PrCKM CKM 239quot where n is the number of bits in the MAC 7 Intuition prevent chosen plainteXt attack If M is equal to some known transformation on M then PrCKll CKM 239quot 7 This requirement is subsumed by the above one 7 Intuition no weak spot with respect to certain bits of the message NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 57 MAC Based on DES CBC Mode Known as Data Authentication Algorithm DES CBC mode with IV being zero A message is padded with zeroes to form 64bit blocks The data authentication code DAC ie the MAC consists of either the entire last ciphertext block or the left M bits with 16 SM 564 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 58 MAC Based on DES CBC Mode Cont d M1 M7 M2 M4 64 64 64 46W Cl C2 C3 C4 a I DAC 16 to 64 bits NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 59 NC STATE UNIVERSITY ComPUIEFSCience CSC 474574 Information Systems Security Topic 72 Multilevel Databases csc musu Dr Peng ng Approaches to Multilevel Databases Partitioning Encryption Integrity lock 0 Trusted FrontEnd Distributed Databases NC STATE UNIVERSITY ComputerScience csc 474574 Dr PengNing Partitioning 0 Separate data in different levels into different partitions Redundancy Example the primary key of a logical relation must be duplicated in all partitions in which the relation are stored Usability Example a highlevel user needs to combine both high level and lowlevel data Nc STATE UNIVERSlTY Computer Science csc 474574 Dr Peng Ning 3 NC STATE UNIVERSlTY Computer Science Encryption Encrypt the sensitive data at each level with a key unique to that level 7 Known plaintext attack Example 7 Party attribute is encrypted 7 Alice knows party Democrat for Bob she can compare the ciphertext of Bob s party attribute With other tuples Reason Limited set of plaintexts 7 Authentication Example 7 Replace one ciphertext With another 7 Above problems can be partially avoided with multiple keys 7 Unable to use DBMS functionalities for encrypted data Query optimization indexes etc CSC 474574 Dr Peng Ning 4 Integrity Lock Provide integrity and limited access for a database Data Securitxlass Crypto checksum Access to data items is based on the security labels Any unauthorized changes to data items can be detected Nc STATE UNIVERSlTY Computer Science csc 474574 Dr Peng Ning 5 Integrity Lock DBMS lt gt Trusted Untrusted Access DBMS Controller Sensitive Database w Users Problems 7 Ef ciency Data expansion Processing time required for generating modifying and verifying integrity locks 7 Security Untrusted DBMS sees all data passing through it NC STATE UNIVERSlTY Computer Science csc 474574 Dr Peng Ning 6 Trusted Front End Trusted Front End 7 User authentication 7 Access control 7 Veri cation 7 Essentially a reference monitor I Trusted Front Untrusted H Access Sensltlve DBMS controller Database Jsers Nc STATE UNIVERSlTY Computer Science csc 474574 Dr Peng Ning Trusted Front End Cont d Commutative Filters 7 Processes that interfaces to both the user and the DBMS 7 Reformat the query by putting in more conditions to filter out unnecessary records 7 Example Retrieve NAME Where Occup Physicist A City WashDC From all records R After reformatting Retrieve NAME Where Occup Physicist A City WashDC From all records R Where N amelevel R lt Userlevel A Occuplevel R lt Userlevel A Citylevel R lt Userlevel NC STATE UNIVERSlTY Computer Science csc 474574 Dr Peng Ning 8 Distributed Databases databases queries and send to different databases Users NC STATE UNIVERSlTY Computer Science CSC 474574 Store data items at different level in different physical Trusted frontend translates each query into singlelevel Trusted frontend combines results and returns to the user Dr Peng Ning NC STATE UNIVERSITY ComputerScience CSC 474 Information Systems Security Topic 25 Public Key Algorithms CSC w Dr Pengng Public Key Algorithms Public key algorithms covered in this class RSA encryption and digital signature DiffieHellman key exchange DSA digital signature 0 Number theory underlies most of public key algorithms NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning Use of PublicKey Cryptosystems Encryption decryption 7 The sender encrypts a message with the receiver s public key 7 Only the receiver can decrypt the message Digital signature 7 The sender signs a message with its private key 7 Authentication and nonrepudiation Key exchange 7 Two sides cooperate to exchange a session key 7 Secret key cryptosystems are often used with the session key NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 3 Requirements for PublicKey Algorithms It is computationally easy to generate a pair of public key and private key It is computationally easy to generate a ciphertext using the public key It is computationally easy to decrypt the ciphertext using the private key It is computationally infeasible to determine the private key from the public key It is computationally infeasible to recover the message from the ciphertext and the public key NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning Trapdoor OneWay Function Essential requirement Trapdoor one way function Oneway function f 7 Onetoone mapping 7 YfX easy 7 Xf1Y infeasible Trapdoor oneway function 7 Onetoone mapping 7 Y X easy if k and X are known 7 Xf391kY easy ifk and Y are known 7 Xf391kY infeasible ifY is known but k is unknown Designing publickey algorithm is to find appropriate trapdoor oneway function Computer Science 350474 Dr Peng Ning PublicKey Cryptanalysis Bruteforce attack 7 Try all possible keys Derivation of private key from public key 7 Try to find the relationship between the public key and the private key and compute the private key from the public one Probablemessage attack 7 The public key is known 7 Encrypt all possible messages 7 Try to nd a match between the cipherteXt and one of the above encrypted messages NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 6 RSA Rivest Shamir Adleman The most popular one Support both public key encryption and digital s1gnature Assumptiontheoretical basis Factorization of large primes is hard Variable key length usually 1024 bits Variable plaintext block size Plaintext must be smaller than the key Ciphertext block size is the same as the key length NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 7 RSA Algorithm To generate key pair Pick large primes p and q Let n pq keepp and q to yourself For public key choose e that is relatively prime to Mn plql let pub ltengt For private key find d that is the multiplicative inverse ofe mod am ie ed 1 mod Mn let pri ltdngt NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning I3 How Does RSA Work 0 Given pub lte ngt and priv lta ngt encryption c m9 mod n m lt n decryption m 001 mod n signature s md mod n m lt n verification m s9 mod n NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 9 An Example Choosep 7 andq 17 Compute n pq Compute np1q1 Select e 5 which is relatively prime to n Compute d Lsuch that e d1 mod n Public key lt gt Private key lt gt Encryption 195 mod 119 66 Decryption 6677 mod 119 19 NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 10 Why Does RSA Work 0 Given pub lte ngt and priv lta ngt n P W PIq1 Ed 1 mod Mn x9 x mod n encryption c m9 mod n decryption m cd mod n mew mod n m mod n m since in lt n digital signature similar NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning The Security of RSA Attacks against RSA Brute force Try all possible private keys Can be defeated by using a large key space Mathematical attacks Factor 71 into npq Determine on directly equivalent to factoring n Determine d directly at least as difficult as factoring n Timing attacks Recover the private key according to the running time of the decryption algorithm NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning The Security of RSA Cont d Factoring large integer is very hard But if you can factor big number n then given public key ltengt you can find d and hence the private key by 7 Knowing factors p q such that n pq 7 Then Mn p1q1 7 Then d such that ed 1 mod Mn Ways to make n difficult to factor 7 p and q should differ in length by only a few digits 7 Both pl and q 1 should contain a large prime factor 7 gcdpl ql should be small 7 d gt quot14 NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 13 The Security of RSA Cont d 39 Timing attacks Algorithm for computing 7 Determine the private ab mOd 7 key by observing how 61 lt l long a computer takes to For 139 lt k downto 0 decipher messages d lt dd mod n The attack proceeds b1t If bi 1 by b1t 9 Then 61 lt da mod n 7 The attacker 1s able to Return 61 determine bit j because for some d and a the marked step is extremely slow NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 14 The Security of RSA Cont d Countermeasures against the timing attack Constant eXponentiation time Don t return the result if the computation is too fast Hurt the performance Random delay Confuse the timing attack by adding a random delay The attacker may be able to defeat random delay if the delay is not added carefully Blinding Multiply the cipherteXt by a random number before performing eXponentiation NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning The Security of RSA Cont d RSA Data Security s blinding algorithm Generate a random number r between 0 and n 1 such that gcdr n 1 Compute C C re mod n Compute M C d mod n Compute MM r 1 mod n Performance penalty 2 10 NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning Dif eHellman Key Exchange 0 Shared key public communication 0 No authentication of partners 0 What s involved p is a large prime number about 512 bits g lt p and g is a primitive root of p p and g are publicly known Computer Science csc 474 Dr Peng Ning 17 Dif eHellman Key Exchange Procedure m B0b pick secret Sq randomly pick secret S b randomly compute TAgS mod p compute TB ng mod p send TA to Bob send TB to Alice compute TBS mod p compute TASb mod p Alice and Bob reached the same secret gSGSb mod p which is then used as the shared key NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 18 DH Security Discrete Logarithm Is Hard Tgsmodp 0 Given T g p it is computationally infeasible to compute the value of s discrete logarithm NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning DiffieHellman Scheme 0 Security factors Discrete logarithm is very difficult Shared key the secret itself never transmitted Disadvantages Expensive exponential operation DoS possible Cannot be used to encrypt anything No authentication so you can not sign anything NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning ManInTheMiddle Attack Alice Mr X Bob g5 123 gsx 654 ng 255 123 a 654 a e 654 e 255 654sa1235x 255Sx6545b Mr X plays Bob to Alice and Alice to Bob NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 21 Dif eHellman in Phone Book Mode DH is subject to active manin themiddle attack because their public keycomponent may be intercepted and substituted Phone book mode allows everyone to generate the public keycomponent in advance and publish them through other reliable means eg ltTBgt for Bob All communicating parties agree on their common ltg 17gt Essential reguirement authenticity of the public key NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 21 Encryption With Dif eHellman Everyone computes and publishes ltp g Tgt 7 Tgs mod p Alice communicates with Bob 7 Alice Picks arandom secret Sa Computes ng modpb Use Kab Tbs modpb to encrypt message Send encrypted message along with ng mod pb 7 Bob 853931 10de 853193 10de Tbs 10de Kab Use Kab to decrypt Essentially key distribution encryption NC STATE UNIVERSITY Computer Science CSC 474 Dr Peng Ning 13 Digital Signature Standard DSS By NIST 0 Related to El Gamal 0 Use SHA SHAl to generate the hash value and Digital Signature Algorithm DSA to generate the digital signature 0 Speeded up for signer rather than veri er smart cards NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 24 Digital Signature Algorithm DSA Generate public parameters 7 p 512 to 1024 bit prime 7 q 160 bit prime qlp l 7 g MP quotW modp where 1lt h lt p 7 1 such thatg gt1 7 g is of order q mod p User s private key x 7 Random integer with 0 lt x lt q User s public key y 7 y gquot mod p User s per message secret number 7 k random integer with 0 lt k lt q NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 15 DSA Cont d Signing 7 r gk modp mod q 7 s k 1HMxr mod q 7 Signature r s Verifying 7 M r s received versions of M r s 7 w s 391 mod q 7 M1 HM w mod q 7 M2 r w mod q 7 V gW mod p mod 617 7 if v r then the signature is veri ed NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 26 Why Is DSA Secure 0 No revealing of private key x 0 Can t forge a signature without x 0 No duplicate messages with matched signature 0 Need a permessage secret number k If k is known the private key x can be computed Two messages sharing the same k can reveal the private key x NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 17 NC STATE UNIVERSITY ComputerScience CSC 474574 Information Systems Security Topic 53 Internet Key Management CSC 411574 Dr Pengng Outline Key Management Security Principles Internet Key Management Manual Exchange SKIP Oakley ISAKIVIP IKE NC STATE UNIVERSITY Computer Science CSC 474574 Dr PengNing Key Management 0 Why do we need Internet key management AH and ESP require encryption and authentication keys 0 Process to negotiate and establish lPsec SAs between two entities NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 3 Security Principles 0 Basic security principle for session keys Compromise of a session key Doesn t permit reuse of the compromised session key Doesn t compromise future session keys and longterm keys NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 4 Security Principles Cont d Perfect forward secrecy PFS Compromise of current keys session key or long term key doesn t compromise past session keys Concern for encryption keys but not for authentication keys Not really perfect in the same sense as perfect secrecy for onetime pad NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning Internet Key Management Manual key management Mandatory Useful when lPsec developers are debugging Keys exchanged of ine phone email etc Set up SP1 and negotiate parameters NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning Internet Key Management Cont d 0 Automatic key management Two major competing proposals Simple Key Management for Internet Protocols SKIP ISAKMPOAKLEY Photuris 7 Ephemeral DH authentication Cookie 7 The rst to use cookie to thwart DOS attacks SKEME extension to Photuris Oakley RFC 2412 ISAKMP RFC 2408 ISAKMPOAKLEY gt IKE RFC 2409 Computer Science csc 474574 DI Peng Ning Automatic Key Management 0 Key distribution and management combined SKIP 0 Key establishment protocol Oakley focus on key exchange Key management Internet Security Association amp Key Management Protocol I SAKIVIP Focus on SA and key management Clearly separated from key exchange NC STATE UNIVERSITY Computer Science csc 474574 D Peng Ning SKIP Idea IP is connectionless in nature Using security association forces a pseudo session layer underneath IP Proposal use sessionless key establishment and management Predistributed and authenticated DH public key Packetspecific encryption keys are included in the IP packets NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 9 SKIP Cont d Two types of keys 1 KEK 2 Packet key Certificate repository Bob s certi catequot Alice s certi cate A Alice 7 Bob Kp encrypted with IGEK Payload encrypted with NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 10 SKIP Cont d KEK should be changed periodically Minimize the exposure of KEK Prevent the reuse of compromised packet keys SKIP s approach KEK h K AB n where h is a oneway hash function K AB is the the long term key between A and B and n is a counter NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning SKIP Cont d Limitations No Perfect Forward Secrecy Can be modi ed to provide PFS but it will lose the sessionless property No concept of SA difficult to work with the current lPsec architecture 0 Not the standard but remains as an alternative NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning Oakley Oakley is a re nement of the basic Dif e Hellman key exchange protocol 0 Why need re nement Resource clogging attack Replay attack Manin themiddle attack Choice of D H groups NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning Resource Clogging Attack NC STATE UNIVERSITY Computer Science Many bogus requests With false source IPs Stopping requests is dif cult We need to provide services Ignoring requests is dangerous Denial of service attacks CSC 474574 Dr Peng Ning Resource Clogging Attack Cont d 0 Counter measure If we cannot stop bogus requests at least we should know from where the requests are sent Cookies are used to thwart resource clogging attack Thwart not prevent NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 15 Resource Clogging Attack Cont d Cookie Each side sends a pseudorandom number the cookie in the initial message which the other side acknowledges The acknowledgement must be repeated in the following messages Do not begin D H calculation until getting acknowledgement for the other side NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 16 Requirements for cookie generation The cookie must depend on the speci c parties Prevent an attacker from reusing cookies Impossible to forge Use secret values Ef cient Cookies are also used for key naming Each key is uniquely identified by the initiator s cookie and the responder s cookie NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 17 Replay Attack 0 Counter measure Use nonce 1 Cookie exchange 4 D E 2 Later exchange Observ a l 3 3 59 NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 18 ManInTheMiddle Attack Counter measure 7 Authentication 7 Depend on other mechanisms Preshared key Public key certificates ease NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 19 Oakley Groups 0 How to choose the DH groups 0 no group placeholder or nonDH l MODP 768bit modulus 2 MODP 1024bit modulus 3 MODP 1536bit modulus 4 EC2N over GF2155 5 EC2N over GF2185 NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 20 Ephemeral Dif eHellman Shortterm public key amp Shortterm public key r Session key is computed on the basis of shortterm DH publicprivate keys Exchange of these shortterm public keys requires authentication and integrity 7 Digital signatures 7 Keyed message digests The only protocol known to support Perfect Forward Secrecy NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 21 Ephemeral Dif eHellman 0 Question What happens if the long term key is compromised NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 22 ISAKMP Oakley Key exchange protocol Developed to use with lSAKlVlP 0 ISAKMP Security association and key management protocol Defines procedures and packet formats to establish negotiate modify and delete security associations Defines payloads for security association key exchange etc NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 23 ISAKMP Message Fixed format header 7 64 bit initiator and responder cookies 7 Exchange type 8 bits 7 Next payload type 8 bits 7 Flags encryption commit authentication etc 7 32 bit message ID Resolve multiple phase 2 SAs being negotiated simultaneously 7 Variable number of payloads Each has a generic header with 7 Payload boundaries 7 Next payload type possible none NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 24 ISAKMP Formats Initiator Cookie Responder Cookie Next Payload ExchangeType Flags Message ID a lSAKMP Header 16 Next Payload RESERVED Payload Length b Generic Payload Header NC STATE UNIVERSITY ComputerScience CSC 474574 Dr Peng Ning 25 ISAKMP Phases Phase 1 Establish ISAKMP SA to protect further ISAKMP exchanges Or use preestablished ISAKMP SA ISAKMP SA identified by initiator cookie and responder cookie Phase 2 Negotiate security services in SA for target security protocol or application NC STATE UNIVERSITY ComputerScience CSC 474574 Dr Peng Ning 26 ISAKMP Disadvantage Additional overhead due to 2 phases 0 Advantages Same ISAKMP SA can be used to negotiate phase 2 for multiple protocols ISAKMP SA can be used to facilitate maintenance of SAs ISAKMP SA can simplify phase 2 NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning ISAKMP Domain Of Interpretation D01 D01 de nes Payload format Exchange types Naming conventions for security policies cryptographic algorithms DOI for IPsec has been defined NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning ISAKMP Exchange Types 0 none 1 base 2 identity protection 0 3 authentication only 4 aggressive 5 informational 631 reserved 32239 DOI speci c use 240255 private use NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 29 ISAKMP Exchange Types Base exchange 7 reveals identities Identity protection exchange 7 Protects identities at cost of extra messages Authentication only exchange 7 No key exchange Aggressive exchange 7 Reduce number of message but reveals identity Informational exchange 7 Oneway transmission of information NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 30 ISAKKMP Payload Types O OM4gtUJNgt O none SA P T KB ID CERT CR NC STATE UNIVERSITY Computer Science csc 474574 security association proposal transform key exchange identi cation certi cate certi cate request Dr Peng Ning 31 ISAKKMP Payload Types 8 H hash 9 SIG signature 10 NONCE nonce 11 N noti cation 12 D delete 0 l3 VID vender ID 14127 reserved 128255 private use NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 32 ISAKMP Payload Types NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 33 ISAKMP Exchanges Basic Exchange 1 I gtR SA NONCE Begin ISAKMPSA negotiation 2 R91 SA NONCE Basic SA agreed upon 3 1 gtR KE IDI AUTH Key generated Initiator id veri ed by responder 4 RgtI KE IDR AUTH Responder id veri ed by 1n1t1ator key generated SA established NC STATE UNIVERSITY Computer Science csc 474574 D Peng Ning 34 ISAKMP Exchanges Cont d Identify Protection Exchange 1 I gtR SA Begin ISAKMPSA negotiation 2 R91 SA Basic SA agreed upon 3 I gtR KE NONCE Key generated 4 Rel KE NONCE key generated 5 I gtR IDI AUTH Initiator id verified by responder 6 RgtI IDR AUTH Responder id veri ed by initiator SA established Red messages Payload encrypted after ISAKMP leader NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 35 ISAKMP Exchanges Cont d Authentication Only Exchange 1 I gtR SA NONCE Begin ISAKMPSA negotiation 2 R gtI SA NONCE IDR Basic SA agreed upon AUTH Responder id veri ed by initiator Initiator id veri ed by 3 I gtR IDI AUTH responder SA establlshed NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 36 ISAKMP Exchanges Cont d Aggressive Exchange 1 I gtR SA KE NONCE Begin ISAKMPSA IDI negotiation and key exchange 2 R gtI S A KE NONCE Responder identity veri ed IDR AUTH by responder Key generated Basic SA agreed 3 I gtR AUTH upon Initiator id veri ed by responder SA establlshed Red messages Payload encrypted after ISAKMP header NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 37 ISAKMP Exchanges Cont d Informational Exchange 1 I gtR ND Error or status noti cation or deletion Red message Payload encrypted after ISAKMP header NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 38 IKE Overview IKE ISAKMP part of OAKLEY part of SKEME 7 ISAKMP determines How two peers communicate How these messages are constructed How to secure the communication between the two peers No actual key exchange 7 Oakley Key exchange protocol 7 Combining these two requires a Domain of Interpretation CDOI 39 RFC 2407 NC STATE UNIVERSITY Computer Science CSC 474574 DI Peng Ning 39 IKE Overview Cont d A separate RFC has been published for IKE 7 RFC 2409 Requestresponse protocol 7 Initiator 7 Responder Two phases 7 Phase 1 Establish an IKE ISAKMP SA Essentially the ISAKMP phase 1 Bidirectional 7 Phase 2 Use the IKE SA to establish IPsec SAs Key exchange phase Directional NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 40 IKE Overview Cont d Several Modes 7 Phase 1 Main mode identity protection Aggressive mode 7 Phase 2 Quick mode 7 Other modes New group mode 7 Establish a new group to use in future negotiations 7 Notinphase 1 or 2 7 Must only be used after phase 1 Informational exchanges 7 ISAKMP notify payload 7 ISAKMP delete payload NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 41 IPSEC Architecture Revisited IPSec module 1 What to establish IPSec module 2 7 7 SA IKE policies How to establish the IPsec SAs l Encryption algorithm 2 Hash algorithm 3 DH group 4 Authentication method NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 42 A Clari cation About PFS In RFC 2409 7 When used in the memo PerfectForward Secrecy PFS refers to the notion that compromise of a single key will permit access to only data protected by a single key 7 The key used to protect transmission of data WST NOT be used to derive any additional keys 7 If the key used to protect transmission of data was derived from some other keying material that material WST NOT be used to derive any more keys Is this consistent with What we discussed NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 43 IKE Phase 1 Four authentication methods Digital signature Authentication with public key encryption The above method revised Authentication with a preshared key NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 44 IKE Phase 1 Cont d IKE Phase 1 goal 7 Establish a shared secret SKEYID 7 With signature authentication SKEYID prfNi7b l Nrib gxy 7 With public key encryption SKEYlD prfhashNi7b l Nrib CKYl l CKYR 7 With preshared key SKEYID prfpresharedkey Niib l Nrib 7 Notations prf keyed pseudo random function prfkey message CKYlCKYR l s or R s cookie NiibNrib the body of 1 s or R s nonce NC STATE UNIVERSITY Computer Science csc 474574 D Peng Ning 45 NC STATE UNIVERSITY Computer Science IKE Phase 1 Cont d Three groups of keys Derived key for nonI SAKMP negotiations SKEYIDid prfSKEYID gxyl CKY I l CKYR l 0 Authentication key SKEYIDia 7 prfSKEYID SKEYIDid gxy CKYI CKYR 1 Encryption key SKEYIDie 7 prfSKEYID SKEYIDial gxy CKYI CKYR 2 CSC 474574 DI Peng Ning 46 lKE Phase 1 Cont d To authenticate the established key 7 Initiator generates HASH 7 prfSKEY1D gxi gxr CKYI CKY R SAiib lDiiib 7 Responder generates HASHiR 7 prfSKEYlD gxr gxi CKYR CKYJ SAiib lDirib 7 Authentication with digital signatures HASH and HASHiR are signed and verified 7 Public key encryption or preshared key HASH and HASHiR directly authenticate qe exchange NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 47 IKE Phase 1 Authenticated with Signatures Main Mode NC STATE UNIVERSITY Computer Science CSC 474574 Dr Peng Ning 48 KE Phase 1 Authenticated with Signatures Aggressive Mode NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 49 KE Phase 1 Authenticated with Public Key Encryption Main Mode NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 50 KE Phase 1 Authenticated with Public Key Encryption Aggressive Mode NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 51 Observations Authenticated using public key encryption No nonrepudiation No evidence that shows the negotiation has taken place More difficult to break An attacker has to break both DH and public key encryption Identity protection is provided in aggressive rnode Four public key operations Two public key encryptions Two public key decryptions NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 52 IKE Phase 1 Authenticated with A Revised Mode of Public Key Encryption Main Mode NC STATE UNIVERSITY Computer Science CSC 474574 DI Peng Ning KE Phase 1 Authenticated with A Revised Mode of Public Key Encryption Aggressive Mode NC STATE UNIVERSITY Computer Science csc 474574 D1 Peng Ning 54 Further Details 39 Keii and Keir are taken from Neii and Neir respectively NC STATE UNIVERSITY Computer Science csc 474574 D Peng Ning 55 KE Phase 1 Authenticated with Pre Shared Key Main Mode NC STATE UNIVERSITY Computer Science csc 474574 D1 Peng Ning 56 IKE Phase 1 Authenticated with Pre Shared Key C ont d What provide the authentication Why does it work NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 57 KE Phase 1 Authenticated with Pre Shared Key Aggressive Mode NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 58 IKE Phase 2 Quick Mode 0 Not a complete exchange itself Must be bound to a phase 1 exchange 0 Used to derive keying materials for lPsec SAs Information exchanged with quick mode must be protected by the ISAKMP SA 0 Essentially a SA negotiation and an exchange of nonces Generate fresh key material Prevent replay attack NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning IKE Phase 2 Quick Mode Cont d Basic Quick Mode Refresh the keying material derived from phase 1 0 Quick Mode with optional KE payload Transport additional exponentiation Provide PFS NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 60 lKE Phase 2 Quick Mode Cont d HASH1prfSKEYID7a MID I SA I Ni I KE I IDci I IDcr HASH239prfSKEYID7a MID I Niib I SA I Nr I KE I IDci I chr HASH3 prfSKEYID7a 0 I MID INiib I Nrib NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 61 IKE Phase 2 Quick Mode Cont d If PFS is not needed and KB payloads are not exchanged the new keying material is defined as I KEYMAT prfSKEYDid protoColI SP1 INLb INrib I If PFS is desired and KB payloads were exchanged the new keying material is defined as I KEYMAT prfSKEYlDid ngm xv I protocol I SP1 I Niib lNrib I where gqmxy is the shared secret from the ephemeral DiffieHellman exchange of this Quick Mode In either case quotprotocolquot and quot SP1quot are from the lSAKlVJP Proposal Payload that contained the negotiated Transform NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 62 NC STATE UNIVERSITY ComputerScience CSC 474 Information Systems Security Topic 23 Basic Number Theory CSC311 Dr Pengng Basic Number Theory We are talking about integers Divisor We say that 720 divides a ifa mb for some m denoted bla b is a divisor of a Ifall then a 1 or l If alb and bla then a b or b Any bO divides O If blg and blh then bmgnh for arbitrary integers m and n NC STATE UNIVERSITY Computer Science CSC 474 Dr Peng Ning Basic Number Theory Cont d Prime numbers An integer p gt 1 is a prime number if its only diVisors are 1 1 p and p Examples 2 3 5 711131719 31 Any integer a gt 1 can be factored in a unique way as a pf pgzpf where each p1gtp2gt gtpt are prime numbers and where each algt0 Examples 9113gtlt71101113 gtlt112 x7 NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning Basic Number Theory Cont d 0 Another View of alb Let P be the set of all prime numbers Represent a as a HFEPpa Where ap 2 O Represent b as b HP Eppb where bp 2 0 alb means that a 51 NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning Basic Number Theory Cont d Greatest common divisor gcdab 7 gcda b maxk l kla and klb 7 Examples gcd6153 gcd6024gcd6024l2 gcda0 a 7 gcda b can be easily derived if we can factor a and b Relatively Prime Numbers 7 Integers a and b are relatively prime if gcdab l 7 Example 8 and 15 are relatively prime NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning Modulo Operator Given any positive integer n and any integer a we have a qnr where Osrltn and qanj 7 We write r a mod n 7 The remainder r is often referred to as a residue 7 Example 2 12 mod 5 Two integer a and b are said to be congruent modulo nifamodn bmodn 7 We write a E b modn 7 Example 7 E 12 mod 5 NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning Modulo Operator Cont d Properties of modulo operator a E bmodn ifnaib a mod n 1 mod n implies a E b mod n a E b modn implies b E a mod n aEbmodnandbEcmodnimplyaacmodn NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 7 Modular Arithmetic 0 Observation The mod n operator maps all integers into the set of integers0 l 2 111 0 Modular addition a mod n 1 mod 11 mod n ab mod n 0 Modular subtraction a mod n 1 mod 11 mod n a i b mod n 0 Modular multiplication a mod n x 1 mod 71 mod n a x 1 mod n NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning I3 An Exercise n5 Addition Multiplication 0 l 2 3 Exponentiation 9210 mod 5 NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 4 Properties of Modular Arithmetic Zn0 l rt1 Commutative laws 7 w xmodn xw modn 7 w xx modnxx w modn Associative laws 7 w xymodn wx ymodn 7 wxxxymodnwx xxymodn Distributive law 7 w x x y modn w x xw x y modn Identities 7 0w modnwmodn 7 l x w modnwmodn Additive inverse 7w 7 For each w EZW there exists a 2 such that w F0 mod n NC STATE UNIVERSITY Computer Science es 474 Dr Peng Ning About Multiplicative Inverse Not always exist Example There doesn t exist a 2 such that 6 x z 1 mod 8 Z8 0 l 2 3 4 5 6 7 x6 0 6 12 18 24 30 36 42 Residues 0 6 4 2 0 6 4 2 An integer a EZn has a multiplicative inverse if gcda n l 0 In particular if n is a prime number then all elements in Zn have multiplicative inverse NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 11 Fermat s Theorem If p is prime and a is a positive integer not divisible by p then ap39lal mod p Observation a modp 2a modp pla mod p 1 2 pl a X2a X Xpla aa modp gtlt2a modp x x pla modp modp pl xaP39l 5pl modp Thus aP39IEl modp NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 11 Totient Function Totient function 0n number of integers less than n and relatively prime to n lfn is prime onnl If npq andp q are primes onplql Examples 97 9321 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning Euler s Theorem 0 For every a and n that are relatively prime ad 51 mod n Proof leaves as an exercise Examples a3 nlO olO 3900 mod 10 a2nll oll 2901 mod 11 NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning Modular Exponentiation 0 xy mod n xy mod Z01 mod n 0 ify 1 mod 0n thenxy modn xmodn Example 2100 mod 33 NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 15 Euclid 3 Algorithm 0 Observation gcda b gcdb a mod b Eulid d f dgtfgt 0 Xed Yef If Y 0 return Xgcdd t R X mod Y X eY Y eR Goto 2 owewNH NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 16 Extended Euclid Algorithm Extended Euclid d f X1 X2 X3 lt l0f39 Y1 Y2 Y3 lt 0ld If Y3O return X3gcd d 0 no inverse If Y3l return Y3gcd d f Y2d 1 mod f QX3Y3J T1 T2 T3 lt X1 QY1 X2 QY2 X3 QY3 X1 X2 X3 lt Yl Y2 Y3 Y1 Y2 Y3 lt Tl T2 T3 Goto 2 Observation 7 DH dX2X339ledY2Y3 7 lfY3ltheanldY2l 7 Y2 d 1 mod f WSQW eP NE NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 17 The Power of An Integer Modulo n Consider the following expression amal mod n If a and n are relatively prime then there is at least one integer m that satisfies the above equation 7 That is the Euler s totient function n The least positive exponent m for which the above equation holds is referred to as 7 The order of a mod n 7 The exponent to which a belongs mod n 7 The length of the period generated by a NC STATE UNIVERSITY Computer Science CS 474 Dr Peng Ning 1x Understanding The Order of a mod n 0 Powers of Integers Modulo 19 a a2 a3 a4 a5 a6 a7 a8 19 L110 L111 all 113 114 115 116 117 118 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 1 4 16 7 9 17 11 6 5 1 4 16 7 9 17 11 6 5 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 7 11 1 8 7 18 11 12 1 8 7 18 11 12 1 8 7 18 11 12 1 9 5 7 6 16 11 4 17 1 9 5 7 6 16 11 4 17 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 18 1 Computer Science csc 474 Dr Peng Ning 19 Observations in The Previous Table All sequences end in 1 The length of a sequence divides 19 18 Lengths 1 2 3 6 918 0 Some of the sequences are of length 18 The base integer a generates via powers all nonzero integers modulo 19 NC STATE UNIVERSITY Computer Science es 474 Dr Peng Ning Primitive Root The highest possible order of a mod n is n Primitive root If the order of a mod n is n then a is referred to as a primitive root of n The powers ofa a a2 a 1 are distinct mod n and are all relatively prime to n 0 For a prime number p if a is a primitive root of p then a a2 aquot1 are all the distinct numbers mod p NC STATE UNIVERSITY Computer Science 350474 Dr Peng Ning 21 Discrete Logarithm Given a primitive root a for a prime number p 7 The expression bsai mod p 03139 pl produces the integers from 1 to pl 7 The exponent 139 is referred to as the index of b for the base a mod 21 denoted as indaypb 7 indapl0 because a0 modp l 7 indaypal because a1 modp a Example 7 Integer 2 is a primitive root of prime number 19 Number 1 2 3 4 5 6 7 8 9 Index 0 1 l3 2 16 14 6 3 8 Number 10 11 12 l3 14 15 16 l7 18 Index 17 12 15 5 7 11 4 10 9 Computer Science CS 474 Dr Peng Ning 22 Discrete Logarithm Cont d Consider xaindapx mod p yaindapy mod p and xyzainda bcy modp 7 amdayPW mod p air dapw mod pai dayPY mod p 7 amdayPW mod p aindaphwr daypw mod p 7 By Euler s theorem azsc mod p z39ffz sq mod p 7 indaypxy indapxindmpy mod 13p 7 indayPW rindavPQO mod p Discrete logarithm mod p index mod p Computing a discrete logarithm mod a large prime number p is in general difficult 7 Used as the basis of some public key cryptosystems NC STATE UNIVERSITY Computer Science csc 474 Dr Peng Ning 13

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.