HW #3: Public Key Cryptography

CS 392/6813: Computer Security

Fall 2008

[100pts] DUE 10/03/2008 at Midnight

Problem 1 [7.5*4=30pts]

1)  We discussed how to use the Euclidian algorithm to compute the GCD of two numbers. Use this algorithm to compute the following values. Show all of the steps involved.

a.  The GCD of 42 and 225.

b.  The GCD of 52 and 876.

2)  We also discussed the use of the Extended Euclidian algorithm to calculate modular inverses. Use this algorithm to compute the following values. Show all of the steps involved.

a.  3270-1(mod 122939945)

b.  13-1 (mod 31)

3)  Let n be a product of two large primes p and q (i.e., n = pq). Assume that x, y, and g are relatively prime to n.

a.  If x y (mod n), is gx gy (mod n)?

b.  If x y (mod Φ(n)) instead, is gx gy (mod n)?

4)  Assuming an RSA key that is sufficiently long enough to be secure, is it possible to produce a ciphertext that is equal to the plaintext that it encrypts? In other words, is it ever the case that rsa_encrypt(m)=m? Show why or why not.

Problem 2 [15pts]

Familiarize yourself with the Chinese Remainder Theorem (CRT). Use the CRT to solve the following system of simultaneous modular equations. Show your work.

x 4 (mod 9)

x 7 (mod 13)

x 8 (mod 10)

Explain (don’t just copy) how the CRT can be used to accelerate RSA decryption. How fast is RSA decryption with the CRT speedup in comparison to RSA decryption without the CRT speedup?

Problem 3 [30pts]

Download the RSA code found at http://www.funet.fi/pub/crypt/cryptography/asymmetric/rsa/rsaref2.tar.gz

Review the RSA key generation, encryption, and decryption functions and the sample code, then perform the following:

1)  Execute the key generation function to generate a public key (e,n) and corresponding private key d. Compute the execution time.

2)  Choose any message m < n and execute the encryption function to encrypt m using (e,n) and obtain its ciphertext c. Compute the execution time.

3)  Execute the decryption function on c using d to recover m. Compute the execution time.

Repeat each of these operations 100 times and give the average execution time for each of the three. List the type and speed of the processor as well as the amount of memory (RAM) on the machine on which you execute the code.

Also answer the following questions: What is the most costly computation in the key generation process? What algorithm is being used for this computation in the provided source code? Repeat this computation 100 times and submit the average processing time it takes.

Problem 4 [25pts]

A ciphertext encrypted with the RSA cryptosystem is shown below. Your objective is to decrypt it. The public key used to encrypt this message is e=48925 and n=88579. For your solution, submit the private key values d, p, q, and the decrypted message. Additionally, you should encrypt another message of your choosing using the same public key and submit this as well. Be sure to include any scripts you used in the decryption process.

In order to change the plaintext back to English text, you need to know how the alphabetic characters are encoded as elements of Zn. Each element of Zn represents a triplet of alphabetic characters as shown in the following examples. You will have to invert this process after decrypting the provided ciphertext.

DOG -> 3*(262) + 14*26 + 6 = 2398

CAT -> 2*(262) + 0*26 + 19 = 1371

ZZZ -> 25*(262) + 25*26 + 25 = 17575

RSA Ciphertext:

60889 37946 13359 61629 35960 13747 78834 49227 84215 86122 87439 43734 38158 8458 18622 55024 22017 65470 69718 57218 37356 60021 80231 64221 84215 64183 38158 11695 32873 51556 43693 42384 28684 56643 16482 36470 36958 34099 18622 2725 4838 55693 21784 56912 45631 33784 1259 42843 75880 9277 14094 40049 2725 4838 53270 24090 20502 70258 18918 49618 37188 27157 77163 7319 26213 57174 71298 41542 56321 29813 52454 63836 6663 47785 37931 36810 27558 25371 74810 63103 63836 21363 50114 57040 29490 82146 59464 19146 37188 55783 13636 73706 45851 35668 10687 40940 36698 72746 4964 23375 15068 3001 29315 60558 19526 16924 8077 57988 22115 40564 72746 72149 72469 76727 37908 83551 56912 10356 59866 43734 7108 13978 29067 81241 76097 9828 34241 77551 24455 23096 22017 67636 76443 83474 57945 19146 68149 84980 13519 37716 70451 45265 9595 37188 46258 75887 72763 43643 10997 63244 19814 60985 7108 13978 63848 88326 84832 25398 22147 42549 76564 76426 88318 48449 22017 11715 6598 37188 22017 8101 67878 87637 46258 18669 14131 83853 65306 76443 26419 18737 24738