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
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
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
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
1 point
STk> (encrypt 'hello e (* p q)) 21535366738991243783161928400
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.
STk> (decrypt 21535366738991243783161928400 d (* p q)) hello
4 points
(nk) =
n!/k!*(n-k)!
This exercise requires to use the recursive process described in the
exercise instead of using the factorial function.
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.