CSci 1901: Lab 3, February 1

Lab 3: RSA Encryption

Related files:

For this lab we will work with an encryption system called RSA. RSA requires that a user selects 2 large prime numbers, that we call p and q. From them the user computes n=p*q and m=(p-1)*(q-1). The next step is to select a number e such that 1  <  e  <  n, and that e and m are relatively prime, i.e. gcd(e,m)=1. Next compute d such that d*e mod m = 1. d is called the multiplicative inverse of e.

When using RSA, the numbers n and e form the public key of a person, while the numbers n and d are the private key. You can publish your public key, people will use it for encoding but you will be the only one who can decode the messages by using your private key.

To encrypt a message first transform it into a positive integer t. The message being encrypted t must be less than n.

The encryption function is c = (t^e) mod n, where c is the encryption of t.

The decryption function is t = (c^d) mod n, t is the decrypted message (a positive integer) and c is the encrypted message (a positive integer).

To learn more about RSA look at The Mathematical Guts of RSA Encryption and the example

Step 1 (Drill)

Write a procedure, (count-primes a b), that takes in two positive integers and returns the number of prime numbers in the range a to b (inclusive). The lab template contains a definition for the predicate (prime? n) which you may use to test if a given number is prime.

STk> (count-primes 3 7)
3
STk> (count-primes 3 8)
3
STk> (count-primes 21 22)
0

2 points

Step 2 (Application - RSA Encryption)

Write a procedure, (find-e p q), that takes in two arguments p and q, as described above. You should loop from 2 until (p*q) testing each number as a possible integer for e and return the first number that would be a valid e for RSA encryption. If no such e exists return #f.

Recall e must satisfy gcd(e,m) = 1 and there must exist a d such that (d * e) mod m = 1, where m is (p-1)*(q-1). You may use the builtin in gcd to test the first condition. To check the second condition you may use the procedure (modular-inverse e m) defined in the lab template. This procedure returns the number d if such a number exists and #f otherwise. (ifs and conds will treat numbers like #t.)

Hint: This function is somewhat different then the functions we have written up until now. To write this procedure you will have to guess some value for e, say 2, and check if it is valid. If not guess the next possible e and so on. This will require you to write a recursive procedure with an argument for the current guess of e. You can then use recursive calls to "loop" through the potential values for e. The definition of find-e doesn't have an argument for the guess, so you have will to create a helper procedure. This can look something like this:

(define (find-e p q)
  ;; Use a helper to loop through possible guesses:
  (define (check i)
    code goes here
    )

  ;; Start checking at 2
  (check 2)
)

Inside of the check helper procedure, you must check if i (your guess for e) is greater than (* p q). If it is then you have tried all possible guesses for e and none of them worked, so no possible e exists for this p and q so you can just return #t. Otherwise, check the two conditions above, if i passes both tests than return i because it is a valid e. Otherwise, try a new value by calling check again with the next guess.

3 points

Step 3 (Application - RSA Encryption)

To make a public and private key you first must choose a valid p, q, e, and d combination.

1 point

Steps 4 & 5 (Application - RSA Encryption)

Recall that before encrypting a message we have to convert each word into an integer. For this conversion you will use the procedure word->number that we are providing in the lab template file.

For this part you will use the procedure number->word that we are providing to convert a number into a word. You will decrypt a message chosen from the ones sent to you by someone else in the class. You will use your private key to decode the messages, since they have been encoded using your public key.

Hint: encrypt and decrypt will require you to compute values of the form a^b mod c, use the procedure (expmod a b c) defined in the book and included in the lab template to compute these values.

4 points

Bonus Question

Complete the following exercises from the text:
  1. Exercise 1.12. This requires writing a procedure that computes the binomial coefficient (nk) using a recursive process on the Pascal triangle. The binomial coefficent is usually computed as (nk) = n!/k!*(n-k)! This exercise requires to use the recursive process described in the exercise instead of using the factorial function.
  2. Exercise 1.16. This requires rewriting the procedure fast-expt so that it generates a linear iterative process.
  3. Exercise 1.17. This requires writing a fast multiplication procedure using additions. You can write the procedure to generate a linear recursive process or a linear iterative process, whatever you prefer.
The bonus will add 1 point to your lab score. It might not seem much for the work you have to do, but points will add up and you will learn much more!

Congratulations on completing Lab 3!
Lab 3 point total: 10 pts

First Challenge Question Challenge questions are more open ended and more difficult. I can turn in answers to the challenge questions at any time in the semester.

Are you ready for a challenge? Try to answer Exercise 1.28. This requires that you understand the math described in the exercise, you write the corresponding Scheme code, and include test case to show that your procedure work as expected.

This is what you will learn in this lab

Copyright: © 2000-2006 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.