### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Computer and Network Security CSC 574

NCS

GPA 3.94

### View Full Document

## 19

## 0

## Popular in Course

## Popular in ComputerScienence

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

## Popular in ComputerScienence

## Reviews for Computer and 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 ComPUtBFSCience CSC 474574 Information Systems Security Topic 25 Public Key Algorithms rsc zwsm Dr Deng ng 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 474574 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 csc 474574 Dr Peng Ning 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 csc 474574 Dr Peng Ning Trapdoor OneWay Function Essential requirement Trapdoor oneway 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 csc 474574 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 find a match between the ciphertext and one of the above encrypted messages NC STATE UNIVERSITY Computer Science csc 474574 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 csc 474574 Dr Peng Ning 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 gm ie ed 1 mod Mn let pri ltdngt NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning I3 How Does RSA Work 0 Given pub lte ngt and priv lta ngt encryption c me mod n m lt n decryption m cd mod n signature s md mod n m lt n verification m s9 mod n NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 9 An Example Choosep 7 and q 17 Compute n pq Compute np1q1 Select e 5 which is relatively prime to n Compute d such 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 csc 474574 Dr Peng Ning 10 Why Does RSA Work 0 Given pub lte ngt and priv lta ngt n P W 17141 Ed 1 mod Mn x9 x mod n encryption c me mod n decryption m 001 mod n mew mod n m mod n m since in lt n digital signature similar NC STATE UNIVERSITY Computer Science csc 474574 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 csc 474574 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 lgey ltengt you can find d and hence the private key y 7 Knowing factors p q such that n pq 7 Then Mn p1q1 7 Then 61 such that ed 1 mod g0 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 csc 474574 Dr Peng Ning The Security of RSA Cont d I Timing attacks Algorithm for computing 7 Determine the private 61b mOd 7 key by observing how 51 lt 1 long a computer takes to decipher messages Forz39 lt k downto 0 d lt dd mod n The attack proceeds b1t If bi 1 by b1t nib Then d 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 csc 474574 Dr Peng Ning 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 csc 474574 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 csc 474574 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 474574 Dr Peng Ning 17 Dif eHellman Key Exchange Procedure w Bob pick secret Sa randomly pick secret Sb randomly compute TAgsa mod p compute T 5ng mod p send T A to Bob send TB to Alice compute TBS mod p compute T A55 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 csc 474574 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 csc 474574 Dr Peng Ning DiffieHellman Scheme 0 Security factors Discrete logarithm 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 csc 474574 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 csc 474574 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 requirement authenticity of the public key NC STATE UNIVERSITY Computer Science csc 474574 Dr Peng Ning 22 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 gbsa3b 10de ngbSa 10de Tbs 10de Kab Use Kab to decrypt Essentially key distribution encryption NC STATE UNIVERSITY Computer Science CSC 4745 74 Dr Peng Ning 23 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 csc 474574 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 csc 474574 Dr Peng Ning 25 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 ul HM w mod q 7 M2 r w mod q 7 V g 1 2m0dp mod q 7 if v r then the signature is veri ed NC STATE UNIVERSITY Computer Science csc 474574 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 csc 474574 Dr Peng Ning 27

### 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

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.