### Create a StudySoup account

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

Already have a StudySoup account? Login here

# CryptographyComp Netwk Sec ECE 646

Mason

GPA 3.94

### View Full Document

## 44

## 0

## Popular in Course

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

This 21 page Class Notes was uploaded by Antonina Wuckert on Monday September 28, 2015. The Class Notes belongs to ECE 646 at George Mason University taught by Krzysztof Gaj in Fall. Since its upload, it has received 44 views. For similar materials see /class/215023/ece-646-george-mason-university in ELECTRICAL AND COMPUTER ENGINEERING at George Mason University.

## Popular in ELECTRICAL AND COMPUTER ENGINEERING

## Reviews for CryptographyComp Netwk Sec

### 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: 09/28/15

ECE 646 Lecture 5 Mathematical Background Modular Arithmetic Motivation Publickey ciphers RSA as a trapdoor oneway function PUBLIC KEY message ciphertext M CfMMemodN C M f 1C Cd mod N PRIVATE KEY N P Q P Q large prime numbers e d 21 mod P1Q1 RSA keys PUBLIC KEY PRIVATE KEY e N d P Q 9 P Q P Q large prime numbers N N P Q gcde P1 1 and gcde Ql 1 e d 21 mod P1Q1 MiniRSA keys PUBLIC KEY PRIVATE KEY 6N dPQ PQ P5 Q11 N NPQ55 e gcde 51 1 and gcde 111 1 e3 d 3 1 E 1 mod 40 d27 MiniRSA as a trapdoor oneway function PUBLIC KEY ciphertext M2 C f2 23 mod 55 8 C8 M f 1C 827 message modS 2 PRIVATE KEY N511 511primenumbers 3 27 El mod 51111 Basic de nitions General Notation Z integers El there exists El there exists unique V for all 6 belongs to e does not belong to Divisibility a b a divides b a is a divisor of b ab iff ElceZ suchthat bca af b a does not divide b a is not a divisor of b True or False 318 147 763 13651421 1414 063 70 50 00 Prime vs composite numbers An integer p 2 2 is said to be prime if its only positive divisors are 1 and p OtheIWise p is called composite Prime or composite 915720113103 1117 12391427 See The Prime Pages prime number research records and resources by Chris Caldwell httpwwwutmeduresearchprimes Greatest common divisor Greatest common divisor of a and b denoted by gcdgaa b is the largest positive integer that divides both a and b dgcdab iff 1da anddb 2 if ca and cbthenc d gcd 8 44 gcd 15 65 gcd 45 30 gcd31 15 gcd 0 40 gcd 121 169 Relatively prime integers Two integers a and b are relatively prime or coprime if gcda b l Properties of the greatest common divisor gcd a b gcd akb b for any k e Z Quotient and remainder Given integers a and n ngt0 El q r e Z such that aq n r and OSrltn q quotient q a diV n r remainder raq n aiLj n ofa d1V1ded by n 2 a mod n 32 modS 32 modS Integers coungruent modulo 11 Two integers a and b are congruent modulo n eguivalent modulo n written a E b iff a mod n b mod n or a b kn k e Z or nab Laws of modular arithmetic 10 Rules of addition subtraction and multiplication modulo n a b mod n a mod n 1 mod 11 mod n a b mod n a mod n 1 mod 11 mod n a b modn a mod n 1 mod 11 mod n 9l3mod5 2525 mod 26 ll Laws of modular arithmetic Regular addition ab ac iff bc Regular multiplication If abac anda 0 then bc Modular addition ab E ac mod n iff b E 0 mod n Modular multiplication If ab Eacm0dn and god a n 1 then b E 0 mod n Modular Multiplication Example 18 42 mod 8 3 67 mod8 3 E 7 m0d8 6 X 0 6Xmod8 0 X 0 5Xmod8 0 12 Algorithms 9i 9 1 90 91 Euclid s Algorithm for computing gcdab ri r r2 maxa b H1 ri1 mod r r1 mina b 0 1 r t1 ng3a b r r7 13 Euclid s Algorithm Example gcd36 126 I i ri l q ri1 rt1 mod rt 2 r2 maxa b 126 1 q1 3 r1 mina b 36 0 go 2 r0 18 gcd36 126 i 1 ql r1 0 ri1 711 39 Ii ri Multiplicative inverse modulo n The multiplicative inverse of a modulo n is an integer x such that ax51modn The multiplicative inverse of a modulo n is denoted by a391 mod n in some books a or a According to this notation a 13912 1 mod n l4 Extended Euclid s Algorithm 1 rixiayin r2 7 n 9920 q1Lral r1 a x1 q 0 r 0 x0 91 1 x1 1 711 xtil r0 x yi y 21 y 10 Yo Y1 ytil Yr rt1xt139ayt139n qi 14 ri ri1rir1quot1i39 ri xi1xi71 39 Ii xi yi1yi7139 Ii yi Extended Euclid s Algorithm 2 rt1xt139alytlquotll rtl xt139alyt1quotll E xtl 39 1 mOd 11 If rt1 gcd a n 1 xt1 a E 1 mod n and as a result 1 xt1 a modn then Extended Euclid s Algorithm for computing z 1391 mod n z39 qi ri x qi 14 2 r2 n 9920 ri 1 q1Lrai r1a x11 0 90 r0 x0 ri1ri1quot1i39ri 1 ql r1 x1 xi1 xirl 39 Ii xi H 911 M 1 t r0 x in Note If rt1 1 the inverse does not exist Extended Euclid s Algorithm Example z 20391 mod 117 z39 qi r x qi i71 ri 2 r 2 117 x2 1 915 r120 x1 ri1ri1quot1i39ri 17 5 1 0 5 0 06 xi1xi7139qi xi 1 1 1 2 qz 7 1 r2 2 x 35 3 93 2 r3 1 x3 4120 1 mod 117 4 r4 x4 1 17 Chm 20 41 mod 117 1 16 Motivation Breaking ciphers Historical ciphers Af ne Cipher Key Key k1 k2 k1 k2 e 0 25 gcd k1 261 Encryption transformation ci fmi k1 mi k2 mod 26 Decryption transformation mi f391ci kl391 ci k2 mod 26 17 Coding characters into numbers gt4 3333333333333 Z l3 l4 ZL WCII IEGD39TJD JUOCU NFltJTgtlt2ltC1HUJPUIOFUO 3333333333333 Key Historical ciphers Af ne Cipher Example 1 Keyk1k2311 3116 025 gcd3261 Encryption transformation cifmi3 mi11m0d26 Decryption transformation kl391 3391 mod 26 9 because 39m0d261 mi f 1ci 9 ci 11m0d 26 18 Historical ciphers Af ne Cipher Example 2 coding encryption decoding N 13 31311mod2624 Y S gt18 gt31811m0d2613 N A O 3011mod2611 L Historical ciphers Af ne Cipher Example 3 coding deciyption decoding Y 24 924 11mod2613 39 N N gt13 gt 913 11mod2618 S L 11 gt 911 11mod260 39 A 19 Breaking the affine cipher 1 Step 1 Establish a relative frequency of letters in the ciphertext Ciphertext FMXVE DKAPH FERBN DKRXR SREFM ORUDS DKDVS HVUFE DKAPR KDLYE VLRHH RH ABCDEFGHIJKLMNOPQRSTUVWXYZ R 8 D 7 EHK 5 Most frequent single letters Average frequency in a random string of letters i6 0038 38 Average frequency in along English text E 13 T N R I O A S 69 D H L 3545 C F P U M Y G W V l53 BXKQJZ ltl 20 Breaking the affine cipher 2 Step 2 Assuming the relative frequency of letters in the corresponding message derive the corresponding equations Assumption Most frequent letters in the message E and T Corresponding equations E gtR fE R T gtD fT D 4 17 f417 19 3 f193 Breaking the affine cipher 3 Step 3 Solving a set of equations for unknowns k1 and k2 f4 17 f19 3 Q 4 k1 k22 17 mod 26 19 k1 k22 3 mod 26 Q 15 k1 E 14 mod 26 Q 15 k1 E 12 mod 26 21

### 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 made $350 in just two days after posting my first study guide."

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

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