CSci 1901: Lab 4, February 8

Lab 4: More RSA Encryption

Related files:

For this lab we will extend the RSA encryption method we began in Lab3 to encode and decode messages. Recall that RSA requires that you select 2 large prime numbers, p and q, from which you compute n=p*q and m=(p-1)*(q-1). Next you select a number e such that e is greater than 1 and less than n, and that e and m are relatively prime, i.e. gcd(e,m)=1. Finally you compute d such that d*e mod m = 1.

Your public key is the pair (* p q) and e. e is called the public exponent, n=(p*q) is called the modulus. Your private key is the pair (* p q) and d. d is called the private exponent.

Step 1 (Drill)

Write the procedure, (sum-list lst), which takes in a list of numbers and returns the sum of all of the elements of the list.

STk> (sum-list (list 1 2 4))
STk> (sum-list (list 1))
STk> (sum-list (list 1 1 1 0 0 0 2 2 2 3))
STk> (sum-list (list))
STk> (sum-list (list 1 2 3 4 5))

Write the procedure (sum-primes lst) that takes in a list of numbers and returns the sum of all of the elements of the list that are prime. Like last week, the lab template contains the predicate (prime? n) that you may make use of.

STk> (sum-primes (list 3 4 5 6 7))
STk> (sum-primes (list 3 3 4 4 3))
STk> (sum-primes (list 3))
STk> (sum-primes (list 4))
STk> (sum-primes (list))

2 points

Step 2 (Drill)

Write the procedure (filter-odds lst) that takes in a list of numbers and returns a list with the odd elements removed. You may make use of the builtin (odd? x) predicate that returns #t if its argument is odd, and #f otherwise.
STk> (filter-odds (list 1 2 3 4 5 6 7 8))
(2 4 6 8)
STk> (filter-odds (list 2 2 3 3 6))
(2 2 6)
STk> (filter-odds (list 2 4 6 8 10))
(2 4 6 8 10)
STk> (filter-odds (list 3 5 101 71))

2 point

Step 3 (Application - RSA Encryption)

Last week when you passed your public-key to procedures you passed the parts individually, for instance encrypt took in e and n separately. A better approach would have been to create a data structure to store your public-keys, including a constructor for making public keys from values of e and n and accessor methods to obtain these values from an instance of the data structure. These three procedures could be for instance:
(define (make-public-key e n) (cons e n))
(define (public-exponent public-key) (car public-key))
(define (public-modulus public-key) (cdr public-key))

Write a similar constructor make-private-key for private keys. Also write the appropriate accessor methods - private-exponent and private-modulus.

Now copy your definitions for my-p, my-q, my-n, my-m, my-e, and my-d from last weeks lab into this weeks lab, and add the following definitions for my-public-key and my-private-key.

(define my-public-key (make-public-key my-e my-n))
(define my-private-key (make-private-key my-d my-n))

1 point

Steps 4(Application - RSA Encryption)

Rewrite encrypt from last week's lab so that instead of taking in values for e and n directly it just takes in a public-key. To obtain the value corresponding to what was e, extract it from the public-key data structure using (public-exponent public-key). Likewise use public-modulus to obtain what was n.

The procedure was of the form (encrypt word e n), and the new one should have the form (encrypt word public-key).

Repeat this process to rewrite the decrypt procedure to use your private-key abstraction instead of d and n directly.

encrypt and decrypt should now work as follows:

STk> (encrypt 'hello my-public-key)
STk> (decrypt 21535366738991243783161928400  my-private-key) 

2 points

Part 5 (Application - RSA Encryption)

3 points

Bonus Question

Complete the following exercises from the text:
  1. Exercise 1.29, which is on using the Simpson rule to compute the integral of a n function f between a and b. The Simpons rule is as follows
    where h = (b - a)/n, for some even integer n, and yk = f(a + kh). (Increasing n increases the accuracy of the approximation.)
    Define a procedure that takes as arguments f, a, b, and n and returns the value of the integral, computed using Simpson's Rule. Use your procedure to integrate cube between 0 and 1 (with n = 100 and n = 1000).
  2. Exercise 1.39 which is approximating the tangent function using the continued fraction representation
    where x is in radians. Define a procedure (tan-cf x k) that computes an approximation to the tangent function based on Lambert's formula. K specifies the number of terms to compute.
    How large must you make k in order to get an approximation that is accurate to 4 decimal places?
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 4!
Lab 4 point total: 10 pts

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.