### Create a StudySoup account

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

Already have a StudySoup account? Login here

# NETWORK SECURITY CSCI 6268

GPA 3.51

### View Full Document

## 19

## 0

## Popular in Course

## Popular in ComputerScienence

This 8 page Class Notes was uploaded by Allie West II on Thursday October 29, 2015. The Class Notes belongs to CSCI 6268 at University of Colorado at Boulder taught by John Black in Fall. Since its upload, it has received 19 views. For similar materials see /class/231978/csci-6268-university-of-colorado-at-boulder in ComputerScienence at University of Colorado at Boulder.

## 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/29/15

Professor John R Black University of Colorado at Boulder Fall 2005 CSCI 6268 Notes on Groups and RSA These are some rough notes for the lectures we did recently concerning groups and related notions in number theory and RSA cryptographyl De nition 1 A group is a nonempty set C along with a binary operation 0 We must have that G is closed under the operation 0 and we must have the following three properties 0 Associative Property for all a b c E G a0 b o c a o b o 0 Existence of an identity element there exists some e E G such that for all a E G a o e 5 O l l o Inuerses for all elements for all a E G there exists some I E G such that ab ba e If a group G is also commutative we call C an Abelian groupl Examples of groups are Z under addition Q under addition R under additionl But Z under multiplication is NOT a group inverses exist only for 1 and 71 If you take Q E 0 you get a group under multiplication check this FINITE GROUPS The groups we just mentioned are nite But there can be nite groups tool The simplest example is the group G 0 under addition check this But that s not very interesting It turns out that Z is a group under addition mod n for any n gt 1 We write this group as Zn and its elements are 0 1 n E 1 The inverse of any element a E Zn is simply n E a and the identity element is 0 of course or multiplication in Z we have to be carefull If we allow 0 to be in our group we won t have an inverse for it so we must disallow it If we take the set 1 2 p E 1 where p is prime and the operation is multiplication mod p we get a group We didn t prove this but it s a fact We write this group as Z where the asterisk reminds us that the operation in the group is multiplicationl What happens if we try doing multiplication modulo some composite Say we try doing multi plication mod n for some n gt 1 As we saw in class we have to be careful once more any number between 1 and n E 1 that is not relatively prime to n will not have an inverse Take for example the element 2 and try to nd its inverse mod 4 It doesn t have one So when we speak of the group Z we mean the set 1 S i S n E 1 i n 1 Then everything will have an inverse For example Z15 1 24 7 8 11 13 14 and the operation is of course multiplication mod 15 You can nd all the inverses in this set as a good exercise In general how do you go about nding inverses in Z31 Well for any element a E Z31 you need to nd some element I such that ab 1 You know that a n 1 by de nition of Z So using Euclid s extended algorithm we nd two integers u and 1 such that au nv 1 and u E Lin 7 1 with u n 1 We know we will ALWAYS succeed in doing this though we didn t prove it Now just set I u and you re done That is the inverse of at And remember sometimes a number is its own inverse for example 14 is the inverse of 14 in the group Z15 How many elements are there in Z2 The answer is of course the number of elements in the set 1 S 239 S n 7 1 239 n 1 So what we re really asking is how many numbers are there between 1 and n 7 1 which are relatively prime to n This is precisely the de nition of This is called the Euler phi function A few handy facts about this function 0 lfp is prime then p 7 1 o lfp and q are distinct primes then gtpq P 1X11 1 5 1 Notice that this rule implies the rst rule above just re not going to need it for RSA o lfp is prime then gtps p5 7 p set s 1 We didn t present this rule in class because we LAGRANGE7S THEOREM We had a really famous result in lecture called Lagrange s Theorem It says something like this let G be a nite group of n elements and with operation 0 Then for any a E a a o a o o a 71 appearances of a is equal to 5 Where 5 is the identity element of the group If we were in Z under addition then 5 would be 0 for example We did some examples of Lagrange s Theorem with various groups including Z25 You can do them yourself for additional practice if you like PUBLICKEY CRYPTOGRAPHY Suppose Alice and Bob want to send information privately between each other but there is some evil adversary trying to learn the content of the communications lf Alice and Bob share a piece of secret information called the key then this is not too hard But without this it s quite unclear how they can hope to succeed The solution is called PublicKey Cryptography And the most wellknown and widelyused method is called RSA after its inventors Rivest Shamir and Adleman Here s how RSA works Alice chooses two primes p an 11 an sets 71 pq Alice also selects some number 5 which is relatively prime to p i 1q7 1 She then computes d as the inverse of e in the group Z200 That should be confusing to you why in this weird group It will become clear later She then publishes to the world the value 5 She wants EVERYONE to know this value But she guards the value 51 with her life No one gets to know this number but Alice Now when Bob wishes to send some message encoded as a number M E Z2 he computes C M 3 mod n and sends this to Alice When Alice receives C she computes Cd mod n and gets M which is Bob s original message There are a couple of things to clear up here First how do we know that M5 mod n is going to always be M again And how do we know that some adversary cannot compute M from just having the public info 5 n along with C And how do we do all this efficiently in software Those modular exponentiations look computationally difficult We now address each of these issues First why is M5 equal to M in the group Z2 This uses some of the rules we have been working on this week Let s go through it We know that e and d are inverses in a di e39rent group Z200 That means that in Z we know ed 1 for some k So what happens when we take M5d M1k n in the group Z2 Med M1kdgtn MMk MMdgtngtk Ml M Can you see why we said that MM 1 above It s Lagrange s theorem Remember is exactly the size of Z so we must get 1 when we raise ANY group element to that power So the method works Now why is it secure Well that would take us a long time to answer but the short answer is that it is BELIEVED to be as hard to crack RSA as it is to factor 7177 And factoring is believed to be hard when p and q are large primes Finally the last question how do we do these computations quickly on a computer Everything is easy except for one part raising a big number to a big power seems like it would take a long time The advantage we have here is that we are doing all arithmetic modulo n so we can always keep our intermediate results between 1 and n 7 1 if we just keep applying the modulus we may go as high as n2 just before we apply the modulus but no higher than this Computing M5 mod n is called the modular exponentiation problem77 and we need a way to solve it quickly on a computer We didn t do this in lecture but in case you re interested here it is The trick to compute this stuff fast is called repeated squaring77 1 went over it in lecture but I ll give you an example quickly to remind you how it works suppose we have to compute 513134 mod 2911 First we convert the exponent into binary 134 is 100001102 27 22 21 Then we begin squaring 513 as needed Each time we square we reduce modulo 2911 because we want to keep the numbers as small as possible for the sake of efficiency 5131 mod 2911 513 5132 mod 2911 1179 5134 mod 2911 11792 mod 29111494 5133 mod 2911 14942 mod 2911 2210 51316 mod 2911 22102 mod 2911 2353 51332 mod 2911 23532 mod 2911 2798 51364 mod 2911 27982 mod 29111125 513123 mod 2911 11252 mod 2911 2251 Now we re set up to compute 513134 mod 2911 using the numbers above 513134 mod 2911 5137 21 mod 2911 51312342 mod 2911 513123 5134 5132 mod 2911 225114941179 mod 2911 1622 This method is vastly more efficient than trying to compute 513134 mod 2911 by direct means But we could do it X be u 513A134 1 1 31 u 1 10666106141857888266632413677053814466 78466106413785650388051707107085144135834447237365101215481207496429 59097246164667876539907161872489529764802711563611566730260838080909 09277437481 vIUAAdI16679964291490884194 82156853196197323518424150205818670259116078782137840072919174086583 981864660548090303679489 n K 2911 1622 But if you tried something like 1712415712921275331999911 rnod 99128447125111 even he would fail You would HAVE to use modular exponentiationl In case you re interested the answer is 57233387830710 Professor John Ri Black University of Colorado at Boulder Fall 2004 CSCI 6268 Notes on Groups and RSA These are some rough notes for the lectures we did recently concerning groups and related notions in number theory and RSA cryptography De nition 1 A group is a nonempty set C along with a binary operation a We must have that G is closed under the operation a and we must have the following three properties 0 Associative Property for all a b c E G a o 12 c a 01 0 0 Existence of an identity element there exists some e E G such that for all a E G a o e e O a a o Inverses for all elements for all a E G there exists some I E G such that ab ba e If a group G is also commutative we call C an Abelian groupi Examples of groups are Z under addition Q under addition R under additioni But Z under multiplication is NOT a group inverses exist only for l and 71 If you take Q 7 0 you get a group under multiplication check this FINITE GROUPSi The groups we just mentioned are nite But there can be nite groups tool The simplest example is the group G 0 under addition check this But that7s not very interesting It turns out that Z is a group under addition mod n for any n gt 1 We write this group as Zn and its elements are 01 n 7 l The inverse of any element a 6 Zn is simply n 7 a and the identity element is 0 of course For multiplication in Z we have to be careful If we allow 0 to be in our group we won7t have an inverse for it so we must disallow it If we take the set l2 p 7 l where p is prime and the operation is multiplication mod p we get a group We didn t prove this but it s a fact We write this group as Z where the asterisk reminds us that the operation in the group is multiplicationi What happens if we try doing multiplication modulo some composite Say we try doing multi plication mod n for some n gt 1 As we saw in class we have to be careful once more any number between 1 and n 7 1 that is not relatively prime to n will not have an inverse Take for example the element 2 and try to nd its inverse mod 4 It doesn7t have one So when we speak of the group Z we mean the set 1 S i S n 7 l 1 Then everything will have an inverse For example Z15 1 2 4 78111314 and the operation is of course multiplication mod 15 You can nd all the inverses in this set as a good exercise In general how do you go about nding inverses in Z Well for any element a E Z you need to nd some element 12 such that ab 1 You know that an l by de nition of Z So using Euclidls extended algorithm we nd two integers u and 1 such that au nv l and u 6 Ln 7 l with un 1 We know we will ALWAYS succeed in doing this though we didn t prove it Now just set I u and you re done That is the inverse of ai And remember sometimes a number is its own inverse for example 14 is the inverse of 14 in the group Zi5i How many elements are there in Z The answer is of course the number of elements in the set 1 S i S n 7 1 i n 1 So what we re really asking is how many numbers are there between 1 and n 7 1 which are relatively prime to n This is precisely the de nition of This is called the Euler phi function A few handy facts about this function 0 If p is prime then p 71 0 If p and q are distinct primes then P DU 1 0 If p is prime then p5 7 ps l Notice that this rule implies the rst rule above just set 8 1 We didn t present this rule in class because we7re not going to need it for RSA LAGRANGE S THEOREM We had a really famous result in lecture called Lagrange7s Theorem It says something like this let G be a nite group of n elements and with operation 0 Then for any a E a a o a o o a n appearances of a is equal to 6 Where 6 is the identity element of the group If we were in Z under addition then 6 would be 0 for example We did some examples of Lagrange7s Theorem with various groups including Z15 You can do them yourself for additional practice if you like PUBLIC KEY CRYPTOGRAPHY Suppose Alice and Bob want to send information privately between each other but there is some evil adversary trying to learn the content of the communications 1f Alice and Bob share a piece of secret information called the key then this is not too hard But without this its quite unclear how they can hope to succeed The solution is called PublicKey Cryptography And the most wellknown and widelyused method is called RSA after its inventors Rivest Shamir and Adleman Here s how RSA works Alice chooses two primes p and q and sets n pq Alice also selects some number 6 which is relatively prime to 10 DC 71 She then computes d as the inverse of e in the group Z2500 That should be confusing to you why in this weird group It will become clear later She then publishes to the world the value en She wants EVERYONE to know this value But she guards the value d with her life No one gets to know this number but Alice Now when Bob wishes to send some message encoded as a number M E Z he computes C Me mod n and sends this to Alice When Alice receives C she computes Cd mod n and gets M which is Bob s original message There are a couple of things to clear up here First how do we know that M8 mod n is going to always be M again And how do we know that some adversary cannot compute M from just having the public info 6 n along with C And how do we do all this efficiently in software Those modular exponentiations look computationally difficult We now address each of these issues First why is M8 equal to M in the group Z This uses some of the rules we have been working on this week Lets go through it We know that e and d are inverses in a di erent group Z2500 That means that in Z we know ed 1 for some Is So what happens when we take Me M1k n in the group Z2 Med M1k n M MWW M nk 1k M M M Can you see why we said that Ma 1 above 1t7s Lagrangels theoreml Remember is exactly the size of Z so we must get 1 when we raise ANY group element to that power So the method works Now why is it secure Well that would take us a long time to answer but the short answer is that it is BELIEVED to be as hard to crack RSA as it is to factor n And factoring is believed to be hard when p and q are large primes Finally the last question how do we do these computations quickly on a computer Everything is easy except for one part raising a big number to a big power seems like it would take a long time The advantage we have here is that we are doing all arithmetic modulo n so we can always keep our intermediate results between 1 and n 7 1 if we just keep applying the modulus we may go as high as n2 just before we apply the modulus but no higher than this Computing Me mod n is called the modular exponentiation problem77 and we need a way to solve it quickly on a computer We didn t do this in lecture but in case you7re interested here it is The trick to compute this stuff fast is called repeated squaring77 1 went over it in lecture but llll give you an example quickly to remind you how it works suppose we have to compute 513134 mod 2911 First we convert the exponent into binary 134 is 100001102 27 22 21 Then we begin squaring 513 as needed Each time we square we reduce modulo 2911 because we want to keep the numbers as small as possible for the sake of ef ciency 5131 mod 2911 513 5132 mod 2911 1179 5134 mod 2911 11792 mod 2911 1494 5138 mod 2911 14942 mod 2911 2210 51316 mod 2911 22102 mod 2911 2353 51332 mod 2911 23532 mod 2911 2798 51364 mod 2911 27982 mod 29111125 513123 mod 2911 11252 mod 2911 2251 Now we re set up to compute 513134 mod 2911 using the numbers above 513134 mod 2911 5132quot 221 mod 2911 51312342 mod 2911 513123 5134 5132 mod 2911 2251 14941179 mod 2911 1622 This method is vastly more ef cient than trying to compute 513134 mod 2911 by direct means But we could do it obc n 5132134 11 14312876534254347708236005439153387158141857888266632413677053814466 82156853196197323518424150205818670259116078782137840072919174086583 981864660548090303679489 n X 2911 1622 But if you tried something like 171241i 712921275881999911 rnod 99128447125111 even he would fail You would HA E to use modular exponentiationl In case you re interested7 the answer is 57233387830710

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

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

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