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.
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)) 7 STk> (sum-list (list 1)) 1 STk> (sum-list (list 1 1 1 0 0 0 2 2 2 3)) 12 STk> (sum-list (list)) 0 STk> (sum-list (list 1 2 3 4 5)) 15
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)) 15 STk> (sum-primes (list 3 3 4 4 3)) 9 STk> (sum-primes (list 3)) 3 STk> (sum-primes (list 4)) 0 STk> (sum-primes (list)) 0
2 points
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
(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
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) 21535366738991243783161928400 STk> (decrypt 21535366738991243783161928400 my-private-key) hello
2 points
STk> (list-encrypt '(hello there) my-public-key) (21535366738991243783161928400 20995383430717601169654110978) STk> (list-encrypt '(C programmers do not die they get cast into void) my-public-key) (14620941571469012153935306931 20646050938108459644373803779 5448837548714002262470184355 22167283850878867480524467992 18099790359573697190186591731 27155808237763629481455263584 1822899848115866044786583558 19397463663947691797552440098 8022303303235824719972853107 10318394737664924709403341322) STk> (list-encrypt '(scheme programmers get garbage collected) my-public-key) (10667884398433131202378347401 20646050938108459644373803779 1822899848115866044786583558 12475564237783808140885630531 9890658091149305891075744194)
Write a procedure to decrypt one by one the words in a list and produce a list of words. This time you want to be able to decrypt a list of encoded numbers that someone else has encrypted, so your procedure should use the decrypt procedure you defined above. It should scan down the list and decrypt the words one by one. You should end up calling the procedure like this:
STk> (list-decrypt '(14620941571469012153935306931 20646050938108459644373803779 5448837548714002262470184355 22167283850878867480524467992 18099790359573697190186591731 27155808237763629481455263584 1822899848115866044786583558 19397463663947691797552440098 8022303303235824719972853107 10318394737664924709403341322) my-private-key) (c programmers do not die they get cast into void) STk> (list-decrypt '(10667884398433131202378347401 20646050938108459644373803779 1822899848115866044786583558 12475564237783808140885630531 9890658091149305891075744194) my-private-key) (scheme programmers get garbage collected)
3 points
Congratulations on completing Lab 4!
Lab 4 point total: 10 pts