Your Perfect Assignment is Just a Click Away
We Write Custom Academic Papers

100% Original, Plagiarism Free, Customized to your instructions!

glass
pen
clip
papers
heaphones

Cryptography Homework 2: Understanding Symmetric Ciphers

Cryptography Homework 2: Understanding Symmetric Ciphers

Homework 2: Understanding Symmetric Ciphers

Purpose

This homework is designed to do several things:

• The proficiency problems may become part of your portfolio that demonstrates meeting the content objectives of the course.

• Doing challenge problems and submitting them (and their revised version(s)) demonstrates some of our overall objectives.

• Submitting your check in memo and homework problems are an opportunity to get feedback from Dr. Bolkema.

Instructions

Do as many of the proficiency problems as you feel necessary to meet the objectives. The challenge problems are optional but encouraged. Recall that you can submit up to three problems per week for direct feedback from Dr. Bolkema.

Submit a check-in memo by Friday at noon (under the check in memos tab on Blackboard) by Friday at noon that describes your progress on these problems (and some other things). There are specific questions to answer there. This goes privately to Dr. B who will then give you feedback.

Content Objectives – Module 2

By doing this homework you will demonstrate that you are able to

1. Apply modular arithmetic algorithms for fast-powering, division, and finding greatest common divi- sors.

2. Implement symmetric ciphers involving modular arithmetic.

3. Discuss plaintext attacks on symmetric ciphers.

Proficiency Problems

1. (Objective 1)

(a) Use the Euclidean algorithm to compute gcd(291, 252).

(b) Use the square-and-mulitply algorithm to compute 17183 mod 256.

(c) Use the division algorithm to compute the quotient and remainder of 34787 divided by 353.

2. (Objective 1) Let a and b be positive integers.

(a) Suppose that there are integers u and v satisfying au + bv = 1. Prove that gcd(a, b) = 1.

(b) Suppose that there are integers u and v satisfying au + bv = 6. Is it necessarily true that gcd(a, b) = 6? If not, give a specific counterexample, and describe in general all of the possible values of gcd(a, b).

(c) Suppose that (u1, v1) and (u2, v2) are two solutions in integers to the equation au + bv = 1. Prove that a divides v2 ?v1 and that b divides u2 ?u1.

3. (Objective 2) Let N be a large integer and let K = M = C = /N. For each of the functions

e : K×M?C

listed below, answer the following questions.

• Is e an encryption function?

• If e is an encryption function, what is its associated decryption function d?

• If e is not an encryption function, could you modify the given function into an encryption function by using some smaller set of keys?

(a) ek(m) ? k ?m mod N (b) ek(m) ? k ·m mod N (c) ek(m) ? (k + m)2 mod N

4. (Objective 2 & 3) Consider the affine cipher with key k = (k1, k2) whose encryption and decryption functions are given by

ek(m) ? k1 ·m + k2 mod p dk(c) ? k?1 · (c?k2) mod p

where k?1 is the inverse of k1 modulo p.

(a) Let p = 541 and let the key be k = (34, 71). Encrypt the message m = 204. Decrypt the ciphertext c = 431.

(b) Assuming that p is public knowledge, explain why the affine cipher is vulnerable to a known plaintext attack. How many plaintext/ciphertext pairs are likely to be needed in order to recover the private key?

(c) Alice and Bob decide to use the prime p = 601 for their affine cipher. The value of p is public knowledge, and Eve intercepts the ciphertexts c1 = 324 and c2 = 381 and also manages to find out that the corresponding plaintexts are m1 = 387 and m2 = 491. Determine the private key and then use it to encrypt the message m3 = 173.

(d) Suppose now that p is not public knowledge. Is the affine cipher still vulnerable to a known plaintext attack? If so, how many plaintext/ciphertext pairs are likely to be needed in order to recover the private key?

5. (Objective 2 & 3) Consider the Hill cipher defined by

ek(m) ? k1 ·m + k2 mod p dk(c) ? k?11 · (c?k2) mod p

where m, c, and k2 are column vectors of length n, and k1 is an n×n matrix.

(a) We use the vector Hill cipher with p = 7 and the key k1 =

( 1 3 2 2

) and k2 =

( 5 4

) .

(i) Encrypt the message m =

( 2 1

) (ii) What is the matrix k?11 used for decryption?

(iii) Decrypt the message c =

( 3 5

) .

(b) Explain why the Hill cipher is vulnerable to a known plaintext attack.

(c) The following plaintext/ciphertext pairs were generated using a Hill cipher with the prime p = 11. Find the keys k1 and k2.

m1 =

( 5 4

) , c1 =

( 1 8

) , m2 =

( 8 10

) , c2 =

( 8 5

) , m3 =

( 7 1

) , c3 =

( 8 7

) (d) Explain how any simple substitution cipher that involves a permutation of the alphabet can be

thought of as a special case of a Hill cipher.

6. (Objective 3) Explain why the cipher

ek(m) = k ?m and dk(c) = k ? c

defined by of bit strings is not secure against a known plaintext attack. Demonstrate your attack by finding the private key used to encrypt the 16-bit ciphertext c = 1001010001010111 if you know that the corresponding plaintext is m = 0010010000101100.

Challenge Problems

Justify your answers with complete sentences explaining your reasoning.

7. Let N, g, and A be positive integers. Prove that the following algorithm returns the value gA mod N.

Input: positive integers N, g, and A.

1. Set a = g and b = 1.

2. While A > 0

i) If A ? 1 mod 2, set b = b ·a mod N. ii) Set a = a2 mod N and set A = A/2.

iii) If A > 0, continue with loop at Step 2.

3. Return the number b, which equals gA mod N.

8. Alice and Bob choose a key space K containing 256 keys. Eve builds a special-purpose computer that can check 10, 000, 000, 000 keys per second.

(a) How many days does it take Eve to check half of the keys in K? (b) Alice and Bob replace their key space with a larger set containing 2B different keys. How large

should Alice and Bob choose B in order to force Eve’s computer to spend 100 years checking half the keys? (Use the approximation that there are 365.25 days in a year.)

9. Bob and Alice use a cryptosystem in which their private key is a (large) prime k and their plaintexts and ciphertexts are integers. Bob encrypts a message m by computing the product c = km. Eve intercepts the following two ciphertexts:

c1 = 12849217045006222, c2 = 6485880443666222.

Use greatest common divisors to find Bob and Alice’s private key.

Order Solution Now

Our Service Charter

1. Professional & Expert Writers: Homework Free only hires the best. Our writers are specially selected and recruited, after which they undergo further training to perfect their skills for specialization purposes. Moreover, our writers are holders of masters and Ph.D. degrees. They have impressive academic records, besides being native English speakers.

2. Top Quality Papers: Our customers are always guaranteed of papers that exceed their expectations. All our writers have +5 years of experience. This implies that all papers are written by individuals who are experts in their fields. In addition, the quality team reviews all the papers before sending them to the customers.

3. Plagiarism-Free Papers: All papers provided by Homework Free are written from scratch. Appropriate referencing and citation of key information are followed. Plagiarism checkers are used by the Quality assurance team and our editors just to double-check that there are no instances of plagiarism.

4. Timely Delivery: Time wasted is equivalent to a failed dedication and commitment. Homework Free is known for timely delivery of any pending customer orders. Customers are well informed of the progress of their papers to ensure they keep track of what the writer is providing before the final draft is sent for grading.

5. Affordable Prices: Our prices are fairly structured to fit in all groups. Any customer willing to place their assignments with us can do so at very affordable prices. In addition, our customers enjoy regular discounts and bonuses.

6. 24/7 Customer Support: At Homework Free, we have put in place a team of experts who answer to all customer inquiries promptly. The best part is the ever-availability of the team. Customers can make inquiries anytime.

Homework Free Org

Your one stop solution for all your online studies solutions. Hire some of the world's highly rated writers to handle your writing assignments. And guess what, you don't have to break the bank.

© 2020 Homework Free Org