### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction to Cryptography MATH 373

WVU

GPA 3.8

### View Full Document

## 161

## 0

## Popular in Course

## Popular in Mathematics (M)

This 4 page Class Notes was uploaded by Rae Kutch on Saturday September 12, 2015. The Class Notes belongs to MATH 373 at West Virginia University taught by Hong-Jian Lai in Fall. Since its upload, it has received 161 views. For similar materials see /class/202657/math-373-west-virginia-university in Mathematics (M) at West Virginia University.

## Reviews for Introduction to Cryptography

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

Homework 2 Solutions 123a Find a single value x that simultaneously solves the two congruences z E3 mod 7 and z E4 mod 9 Solution Since z E 3 mod 7 as an integer z 3 1 7y for some integer y Substitute z 37y into zE4 mod 9 to get 37yE4 mod 9 Now we solve 37y E 4 mod 9 by adding E3 mod 9 both sides This yields 7y E 1 mod 9 To nd 7 1 mod 9 we use Euclidean Algorithm you can also use matlab to get 1 gcd7 9 47 E39 and so 7 1 E 4 mod 9 Hence y E 47y E 4 mod 9 or y 4 9m for an integer m To nd m we substitute y 4 1 9m into z 3 1 7y 3 1 74 9m 31 63m for integer m Therefore the smallest positive solution of z is z 31 128a Here in this exercise ord22816 asks the exponent of 2 in the unique factorization of 2816 Solution We can factor 2816 4704 44176 441611 2811 and so ord22816 8 132a For each of the following primes is 2 a primitive root modulo p Solutions p 7 We compute that 22 E 4 23 E 1 mod 7 Therefore the order of 2 mod 7 is 3 not 6 and so 2 is not a primitive root mod 7 ii p 13 We compute that 22 E 4 23 E 8 24 E 3 25 E 6 212 E 1 mod 13 Therefore the order of 2 mod 13 is 12 and so 2 is a primitive root mod 13 iii p 19 We compute that 22 E 4 23 E 8 24 E 16 E E3 25 E E6 E13 26 E E12 E 7 27 E 14 E E2 28 E E4 E 15 29 E E8 E 11 218 E1 mod 19 Therefore the order of 2 mod 19 is 18 and so 2 is a primitive root mod 19 iv p 23 We compute that 22 E 4 23 E 8 24 E 16 E E6 25 E E12 E 11 26 E 22 E E1 212 E 26 26 E 1 mod 23 Therefore the order of 2 mod 23 is 12 not 22 and so 2 is not a primitive root mod 23 134a Let p be an odd prime and let I be an integer with p Prove that either I has two square roots modulo p or else I has no square roots modulo p Proof lt su ices to show that if b has at least one square root modulo p then I must have exactly two square roots modulo p We explain this by nding each of the following observations Square root of I cannot be 0 mod p Suppose that a is a square root of 1 mod p Since p a E 0 mod 19 Therefore p X0 and so gcdap 1 If a2 E 1 mod p then a E Ea mod p Since a2 E mod p it follows that Ea2 E a2 E 1 mod p and so Ea must also be a square root of 1 mod p We need to explain that a E Ea mod p If we had a E Ea mod p then 2a E 0 mod p and so pl2a Since gcdap 1 that pl2a and gcdap 1 imply that pl2 contrary to the assumption that p is an odd prime Hence a E Ea mod p and so I has at least two square roots I cannot have more than 2 square roots Suppose that for some 0 E Zp such that c E a mod p and c E Ea mod p but 02 E mod p Then we have a2 E E 02 mod p or equivalently a E ca E c E a2 E 02 E b E b E 0 mod p This means in integers pla E ca 0 Since p is a prime either pla E c whence c E a mod p or pla E c whence c E Ea mod p Either way will lead to a contradiction to the assumption that c E a mod p and c E Ea mod 19 Thus I must have exactly two square roots if it has at least one 134bi Find solutions of z2 E mod p with p b 7 2 This is to nd solutions of z2 E 2 mod 7 Solutions We compute that 22 E 4 32 E 2 42 E E32 E 2 52 E E22 E 4 mod 7 2 E Therefore z mod 7 has solutions z E 3 4 in Z7 141 Consider the af ne cipher with alphabet set Zp de ne by ekm Ep k1m k2 dkc E1 kf1c E k2 a Let p 541 and let the key be k1 k2 34 71 Encrypt the message m 204 Decrypt the cipher text 0 431 c Alice and Bob decide to use the prime p 601 for their af ne cipher The value p is in public knowledge and Eve intercepts the cipher texts 01 324 and 62 381 and also manage to nd out that the corresponding plain texts are m1 387 and m2 491 Determine the key and then use it to encrypt the message 7713 173 Solution a To encrypt the message m 204 compute 61 E541 34204 71 E541 515 The cipher text corresponding to m 204 is 515 To decrypt the cipher text 0 4317 we need to compute kfl E541 34 1 E541E 366 Then the corresponding plain text is m1 E541 17103 7 k2 E541 3664317 71 E541 297 The related matlab computations are we will learn to use matlab to compute matrix inverse and multiplication later in labs gtgt p541 P 541 gtgt clmod3420471 p cl 515 gtgt k1invpowermod34 1 p klinv 366 gtgt m1modk1inv43171 p m1 297 c Now Eve knows p 601 Let k 11 be the affine cipher key7 and the encryption function is ekm a m I Then Eve knows also that 324 EP 387a 4 67 3812p 491a I Now Eve wants to nd the values of a and 1 Method 1 Use of substitution Substitute 1 Ep 324 7 387a into 381 E1 491a b to obtain 381 E1 491a 324 7 387a This reduces to 104a Ep 381 7 324 EP 57 Compute the inverse 104 1 EP 549 Then a 27 104 1 57 Ep 549 57 EP 417 and 1 Ep 324 7 387a 2p 83 gtgt 381324 549 gtgt a mod54957 p a 41 gtgt b mod324387a p 83 Method 2 Use of matrices and linear algebra We are to solve in Zp 387 1 a i 324 491 1 b 7 381 39 Let A denote the 2 X 2 matrix in the system Compute d detA 387 7 491 EP 7104 and al 1 Ep 52 Thus the inverse of A is A71 52 1 71 52 752 39Hence a 52 752 324 41 V 7491 387 311 291 b 311 291 381 83 The related matlab computations are gtgt p601 P 601 gtgt d 387491 d 104 gtgt dinvpowermodd 1 p dinv 52 gtgt mod49152 p ans 311 gtgt mod38752 p ans 291 gtgt a mod5232452381 p a 41 gtgt b mod311324291381 p b 83

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

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on 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.