Description
Purpose
The purpose of this project is for you to gain experience with writing and testing relatively simple procedures. Youshouldreadtheprojectsubmissioninstructionscarefullytofindouthowtoretrievetheprojectfile and submit your solutions. For each problem below, include your code (with identification of the problem number being solved), as well as comments and explanations of your code, and demonstrate your code’s functionality against a set of test cases. On occasion, we may provide some example test cases, but you shouldalwayscreateandincludeyourownadditional,meaningfultestcasestoensurethatyourcodeworks notonlyontypicalinputs,butalsoonmoredifficultcases. Getinthehabitofwritingandrunningthesetest cases aftereveryprocedure you write — no matter how trivial the procedure may seem to you.
Scenario
Alyssa P. Hacker and Ben Bitdiddle have founded a startup company, SCrypto, that will provide cryptography services for Scheme programmers, allowing them to encode and decode secret messages using a code thatisveryhardtobreak. Thefirstproducttheydecidetocreateisanimplementationofanencryptionalgorithm called RSA. Named after its inventors,Rivest,Shamir, andAdelman, RSA is a public-key encryption algorithm. Thismeansthatinsteadofusingthesamekeyforbothencryptinganddecryptingmessages,RSA has two keys: a public key e used for encrypting, and a private key d for decrypting. The public key can be known by anybody; in fact, it’s often put in a public directory, so that Alyssa can send secret messages to Ben simply by looking up his public key e in the directory. His private key d must be known only to Ben, so that nobody else can decrypt messages sent to him. RSA is widely used for web site security today; your modern browser certificates contain a public-key/private-key pair.
1
ThebasicideaofRSAiswonderfullysimple. First,werepresentthemessagewewanttosendasaninteger 1. Then, to encrypt a message m (represented as a number), we use the public key e as an exponent:
c = me (mod n)
The resulting number c is the encrypted message (The notation (mod n) means take the remainder after dividing by a certain number n, which will be explained later). To decrypt c, we raise it to the power of the private key d:
cd (mod n)
which recovers the original message m. RSA is simple, but the devil is in the details. The public key e and private key d must be chosen so that for all integers m, it is the case that
(me)d = m (mod n)
In other words, encrypting and then decrypting must always give back the original message. Furthermore, sincewewanttheencryptiontobehardtobreak,weneedtomakesurethattheprivatekey d isveryhardto discover, even if you know the public key e. The beauty of RSA lies in these details.
Your job in this project is to implement RSA. By the end of the project, you will have written procedures that generate a public-key/private-key pair, and procedures that encrypt and decrypt messages. Along the way, you will have to create procedural and data abstractions for solving the subproblems involved in implementing RSA, including:
• modular arithmetic (addition, subtraction, and multiplication mod n) • fast exponentiation (computing an when n is very large) • generating large random numbers • testing whether a large number is prime • picking a large prime number at random • finding multiplicative inverses mod n
Problem1: ModularArithmetic
The first thing we need for implementing RSA are operators for modular arithmetic. Modular arithmetic is arithmeticonareducedsetofintegers,intherange 0 to n−1 forsomefixedinteger n 0. Theinteger n is calledthemodulus. Toindicatethatwearedoingmodulararithmetic,wewrite(mod n)afteranexpression: for example, 5 + 8 (mod 12). 1There are several ways to do this. One way is to encrypt one byte of the message at a time, using its numeric value as the integer representation. Another way is to treat the bytes of the message as digits in a base-256 number, so that the entire message becomes the integer. We’ll use the latter approach in this project. Practical RSA does something in between, treating chunks of the message as integers and encrypting one chunk at a time
Addition, subtraction, and multiplication work mostly the same way as in integer arithmetic, except that the result must always be in the range [0,n−1]. We guarantee this by taking the remainder of the result after dividingbyn. Forexample,5+8=13inintegerarithmetic,butinmod-12arithmetic,wetaketheremainder after dividing 13 by 12, which is 1. Here are some other examples:
5 + 8 = 1 (mod 12) 2 + 3 = 5 (mod 12) 6∗5 = 6 (mod 12) 9 – 18 = 3 (mod 12)
Thelastexamplemaybesomewhatmysterious,since9-18=-9inordinaryintegerarithmetic. Todetermine the correct value of -9 (mod 12), we need to add or subtract a multiple of 12 that produces a result in the desired range [0,11]. More formally, we need to find integers a and b such that -9 = 12a + b, where 0 ≤ b ≤ 11. By choosing a = -1, we have -9 = -12 + b which solves for b = 3. Scheme actually has two operators for computing remainders after division: remainder and modulo. Tryapplyingeachoperatortosomeintegers. For example:
(modulo 13 8) ; – ? (remainder 13 8) ; – ? (modulo -13 8) ; – ? (remainder -13 8) ; – ? (modulo -13 -8) ; – ? (remainder -13 -8) ; – ?
Whatisthedifferencebetween remainder and modulo? Which one is the best choice for implementing modular arithmetic as described above? Include your test results and your answers to these questions in a comment in your solution. Write procedures for addition, subtraction, and multiplication modulo n. Each procedure should take three parameters: the values to combine, a and b, and the modulus n. For example, the expression (+mod 7 5 8) should compute 7 + 5 (mod 8).
(define +mod (lambda (a b n) YOUR-CODE-HERE))
(define -mod (lambda (a b n) YOUR-CODE-HERE))
(define *mod (lambda (a b n) YOUR-CODE-HERE))
Test your code for at least the following cases:
(+mod 7 5 8) ; – 4 (+mod 10 10 3) ; – 2 (-mod 5 12 2) ; – 1 (*mod 6 6 9) ; – 0 (+mod 99 99 100) ; – ? (*mod 50 -3 100) ; – ?
Noteaboutpreparingyoursubmission Youshouldalsoinsertyourowncommentsonlinesprecededbysemicolons. Youranswerstothequestions inboldface that appear throughout this project should be included in your file in this way. Your procedures should not be commented out, of course, so that your TA can run your file to try out your code.
Problem2: RaisingaNumbertoaPower
This problem is easy if you’ve read Chapter 1 in the textbook.
Recall that the basic operation in RSA encryption and decryption is raising a number to a power (modulo n). For example, to encrypt a message m using public key e, we need to compute me (mod n).
Here’s a simple procedure that computes ab (mod n) by multiplying a by itself b times. Note that it uses modular arithmetic operations, namely∗mod, rather than∗:
(define slow-exptmod (lambda (a b n) (if (= b 0) 1 (*mod a (slow-exptmod a (- b 1) n) n))))
Answerthesequestionsincommentsinyourfile: Whatistheorderofgrowthintimeofslow-exptmod? Whatisitsorderofgrowthinspace? Does slow-exptmod useaniterativealgorithmorarecursive algorithm? Measure time and space the same way we did in lecture: time by counting the number of primitive operations that the computation uses, and space by counting the maximum number of pending operations.
As its name suggests, slow-exptmod isn’t going to be fast enough for our purposes. We can make it faster using the trick of repeated squaring 2. Compare these two ways of computing 38 . The left column shows how slow-exptmod would do it, and the right column uses repeated squaring:
3ˆ0 = 1 3ˆ0 = 1 3ˆ1 = 3ˆ0*3 = 3 3ˆ1 = 1 * 3 = 3 3ˆ2 = 3ˆ1*3 = 9 3ˆ2 = (3ˆ1)*(3ˆ1) = 9 3ˆ3 = 3ˆ2*3 = 27 3ˆ4 = (3ˆ2)*(3ˆ2) = 81 3ˆ4 = 3ˆ3*3 = 81 3ˆ8 = (3ˆ4)*(3ˆ4) = 6561 2This technique was also shown in lecture for computing “expt”, and is also discussed in section 1.2.4 of the textbook.
3ˆ5 = 3ˆ4*3 = 243 3ˆ6 = 3ˆ5*3 = 729 3ˆ7 = 3ˆ6*3 = 2187 3ˆ8 = 3ˆ7*3 = 6561
Write a procedure exptmod that computes ab (mod n) using repeated squaring. You should use your modular arithmetic operations, particularly∗mod, in your solution. Do not use expt or slow-exptmod in your solution.
(define exptmod (lambda (a b n) YOUR-CODE-HERE))
Testyourcodeforatleastthefollowingcases:
(exptmod 2 0 10) ; – 1 (exptmod 2 3 10) ; – 8 (exptmod 3 4 10) ; – 1 (exptmod 2 15 100) ; – 68 (exptmod -5 3 100) ; – 75
Answer these questions in comments in your file: What is the order of growth in time of your implementation of exptmod? What is its order of growth in space? Does your exptmod use an iterative algorithmorarecursivealgorithm?
Problem3: LargeRandomNumber
In order to generate RSA keys at random, we will need a source of random numbers. Scheme has a built-in procedure random that takes a single integer n 0 and returns a random integer in the range [0,n−1]. For example, here are the results of a few calls to random:
(random 10) ; – 1 (random 10) ; – 6 (random 10) ; – 6 (random 10) ; – 0 (random 10) ; – 7
Unfortunately, the implementation of random in Racket (DrScheme) is not sufficient for our purposes, because its parameter n can be no larger than 231 −1, which is only a couple billion. We’re going to want random numbers at least as large as 2128, if not larger.
So our goal for this problem is a procedure big-random that behaves like random, taking a parameter n 0 and returning a random number in [0,n−1], but that doesn’t have any limit on the size of n.
Startbywritingaprocedurerandom-k-digit-numberthattakesanintegerk 0andreturnsarandom k-digitnumber. Youshouldchooseeachdigitusingthebuilt-inprocedurerandom,thenconstructthek-digit number by putting those digits together. For example, if you generate two digits a and b, then you can form a two-digit number by computing 10a + b. Testyourprocedureonatleastthefollowingtestcases:
(random-k-digit-number 1) ; – ? (1 digit) (random-k-digit-number 3) ; – ??? (1-3 digits) (random-k-digit-number 3) ; – ??? (is it different?) (random-k-digit-number 50) ; – ???… (1-50 digits)
Notethat random-k-digit-number mayreturnanumbershorterthan k digits,sincetheleadingdigits of the number may turn out to be 0. The result will be a random number in the range [0,10k−1]. With random-k-digit-number, we can now generate arbitrarily large random numbers. But we want big-randomtotakeamaximumn,notadigitcount. Soweneedawaytouserandom-k-digit-number to generate random numbers in the range [0,n−1]. We’ll do this by first generating a random number with the same number of digits as n, then ensuring that this number is less than n. Write a procedure count-digits that takes an integer n 0 and returns the number of digits in its decimal representation. The basic idea is to count digits by repeatedly dividing by 10. Test your procedureonatleastthefollowingtestcases:
(count-digits 3) ; – 1 (count-digits 2007) ; – 4 (count-digits 123456789) ; – 9
We’re almost ready to write the new big-random function, but there’s one more problem. Suppose somebody calls (big-random 500), expecting to get back a number between 0 and 499. We use count-digits to determine that 500 has 3 digits, and then use random-k-digit-number to generate a random 3-digit number. If that number is less than 500, then great, we can return it as the result of big-random. But what if the number is greater than or equal to 500? Then we just pick another random 3-digit number. We repeat this process until we get a number that’s in the range we want.
This is a simple example of a probabilistic algorithm – an algorithm that depends on random chance. A probabilisticalgorithmisn’tguaranteedtosucceed,butitsprobabilityofsuccesscanbemadeashighaswe need it to be. In this case, it’s possible for the algorithm to have a really bad string of luck, and repeatedly pick 3-digit numbers higher than 500. But the chance of this happening, say, 1000 times in a row is the same as the chance of flipping heads on a coin 1000 times in a row, which is less than the probability that cosmic rays will cause your computer to make an error in running your Scheme code. So, in practice, as long as we keep picking random numbers (and assuming random-k-digit-number really is random), this probabilistic algorithm is just as likely to succeed as a deterministic algorithm. Usethisapproachtowriteaprocedurebig-randomthattakesaninteger n 0 andreturnsarandom numberfrom0to n−1. Your procedure should handle arbitrarily large n. Sinceyourprocedureneedstogeneratearandomnumber,testitforaproperty,andthenreturnitifitsatisfies thatproperty,youmayfindtheletspecialformuseful. Letevaluatesoneormoresubexpressionsandassigns
names to each one, then evaluates its final expression (using those names) and returns that as its result. For example, the code below computes the square of a random number, using let to name the number:
(let ((n (random 100))) (* n n))
Note that (* (random 100) (random 100)) does not do the same thing! Testbig-randomonatleastthesetestcases:
(big-random 100) ; – ?? (1-2 digit number) (big-random 100) ; – ?? (is it different?) (big-random 1) ; – 0 (big-random 1) ; – 0 (should be always 0) (big-random (expt 10 40)) ; – ????… (roughly 40-digit number)
Problem4: PrimeNumbers
This problem is easy if you’ve read Chapter 1 in the textbook.
In order for RSA encryption and decryption to work correctly, the modulus n must be the product of two prime numbers, p and q. In order for it to be secure against easy cracking, these prime numbers must be large. So we need a way to find large prime numbers.
We’llstartbydevelopingatestforwhetheranumberisprime. Bydefinition,aprimenumberisnotdivisible byanyintegerotherthanitselfand1. Thisleadsdirectlytoasimplewaytotestwhethernisprime,bytesting every number less than n to see if it’s a factor of n:
(define test-factors (lambda (n k) (cond ((= k n) #t) ((= (remainder n k) 0) #f) (else (test-factors n (+ k 1))))))
(define slow-prime? (lambda (n) (if (< n 2) #f (test-factors n 2))))
Answerthesequestionsincommentsinyourfile: Whatistheorderofgrowthintimeofslow-prime?? What is its order of growth in space? Does slow-prime? use an iterative algorithm or a recursive algorithm? Unfortunately slow-prime? is too slow. Ben Bitdiddle proposes two optimizations:
• “Weonlyhavetocheckfactorslessthanorequalto√n”. Howwouldthisaffecttheorderofgrowth in time? Note that we’re not asking you to write Scheme code implementing Ben’s suggestion; just think about it and answer this question as a comment in your file. • “We only have to check odd factors (and 2, as a special case)”. How would this affect the order of growthintime?
Ben’s improvements won’t be enough for us to test very large numbers for primality; we need a completely different algorithm. For faster prime number testing, we turn to a beautiful result about modular arithmetic. Fermat’sLittleTheoremstatesthatif p isprime,then ap = a (mod p)forall a. Inotherwords,if p isprime, then we can take any integer a, raise it to the power p, take the remainder after dividing by p, and we’ll get a back again (modulo p). Test Fermat’s Little Theorem using your exptmod procedure and a few suitable choices of a and p. Include your tests in your answer file.
The converse of the theorem doesn’t hold, unfortunately; if p is composite (not prime), then it isn’t always true that ap 6= a (mod p). But it’s true often enough that we can use this theorem as the basis for a probabilistic algorithm that tests whether a number p is prime:
1. Pick a random integer a in the range [0,p−1], using your big-random procedure. 2. Test whether ap = a (mod p).
3. If not, then p is definitely not prime, by Fermat’s Little Theorem.
4. If so, then p may or may not be prime. Repeat the test with a new random integer a.
If you pick enough random numbers a, and all of them pass the test of Fermat’s Little Theorem, then you have strong confidence that p is prime 3. Write a procedure prime? that uses this technique to test whether its parameter p is prime. Your procedure should test at least 20 random values of a before assuming that p is prime. In fact, it’s good practicetodefineanameforthisconstant, prime-test-iterations,sinceitmayneedtobeadjusted later.
(define prime-test-iterations 20)
(define prime? (lambda (p) YOUR-CODE-HERE))
Testprime? onatleastthefollowingtestcases:
(prime? 2) ; - #t (prime? 4) ; - #f 3But not certainty. Some composite numbers p, called Carmichael numbers, pass the test for almost all a. Fortunately Carmichael numbers are rare. See http://mathworld.wolfram.com/CarmichaelNumber.html for more information
(prime? 1) ; - #f (prime? 0) ; - #f (prime? 200) ; - ? (prime? 199) ; - ?
Answer these questions in comments in your file: What is the order of growth in time of your implementation of prime? What is its order of growth in space? Be sure to take the calls to exptmod into account when answering these questions. Does prime? use an iterative algorithm or a recursive algorithm?
Problem5: RandomPrimes
Nowwe’rereadytofindthelargeprimenumberspandqthatweneedforRSA.Fortunately,primenumbers arefairlycommon4,sowecanfindthembyaprobabilisticgenerateandteststrategy. We’llguessanumber at random, and then test whether it’s prime. If not, we’ll pick another random number, and repeat.
Write a procedure random-prime that returns a random prime number p. It should take a parameter n that limits the size of the prime returned, so that p < n.
(define random-prime (lambda (n) YOUR-CODE-HERE))
Note that your procedure is probabilistic – i.e., most of the time it successfully returns a prime number, but sometimes it may fail. In what ways can your random-prime procedure fail? Answer this question in a comment. Some kinds of failure are better than others. Testrandom-primeonatleastthetestcasesbelow.
(random-prime 3) ; - 2 (random-prime 3) ; - 2 (must be always 2) (random-prime 100) ; - ? (random-prime 100) ; - ? (is it different?) (random-prime 100000) ; - ?
Problem6: MultiplicativeInverses
Recall that RSA needs two keys e and d such that (me)d = m (mod n) for every possible message m. It turns out that this works if e and d are chosen so that ed = 1(mod (p−1)(q−1)). So we need a way to find multiplicative inverses in modular arithmetic. Given an integer e and a modulus n,wewanttofind d suchthat ed = 1(modn). Inrationalorrealarithmetic, d wouldbe 1/e,butwewantan 4Another famous result, the Prime Number Theorem, holds that the number of primes less than n is roughly n/lnn. For example, if we pick a random 40-digit number, then the probability that it’s prime is roughly 1/ln1040 , or 1/92. See http: //mathworld.wolfram.com/PrimeNumberTheorem.html.
integer. Themultiplicativeinverseof e existsifandonlyif e and n havenocommonfactors;inotherwords, only if the greatest common divisor (GCD) of e and n is 1. (The GCD algorithm is described in section 1.2.5 of the text, but you can use the Scheme built-in procedure gcd for this project.)
Here’s how we find the multiplicative inverse d. We want ed = 1(modn), which means that ed + nk = 1 for some integer k. So we’ll write a procedure that solves the general equation ax + by = 1, where a and b are given, x and y are variables, and all of these values are integers. We’ll use this procedure to solve ed + nk = 1 for d and k. Then we can throw away k and simply return d.
So we’ve reduced the problem to solving ax + by = 1 for x and y, given a and b. We assume that all of these terms are integers, and that a and b are greater than 0. Let q be the quotient of dividing a by b, and let r be the remainder (Scheme has builtin procedures quotient and remainder for this purpose.). Then a = qb + r. Now consider the special case when r = 1 : then a = qb + 1, which means a∗1 + b(−q) = 1, so we have our solution. Otherwise, if r 6= 1, recursively solve the equation bx0 + ry0 = 1, and use the solution (x0,y0) to find the solution to the original equation ax + by = 1:
1 = bx0 + ry0 = bx0 + (a−qb)y0 = ay0 + b(x0−qy0)
Writeaprocedureax+by=1thatsolvesforxandyusingtheapproachoutlinedabove. Your procedure should return (x,y) as a list.
(define ax+by=1 (lambda (a b) YOUR-CODE-HERE))
Test ax + by = 1 onatleastthetestcasesbelow. Note that it will only succeed if gcd(a,b) = 1, so don’t expect it to work otherwise.
(ax+by=1 17 13) ; - (-3 4) 17*-3 + 13*4 = 1 (ax+by=1 7 3) ; - (1 -2) 7*1 + 3*-2 = 1 (ax+by=1 10 27) ; - (-8 3) 10*-8 + 3*27 = 1
Nowwriteaprocedure inverse-mod thatfindsthemultiplicativeinverseof e modulo n,using ax+ by = 1. Note that before trying to invert e, your procedure should ensure that gcd(e,n) = 1. You can use thebuiltinSchemeprocedure gcd totestthis, andtheSchemebuiltinprocedure display toprintanerror message if the test fails.
(define inverse-mod (lambda (e n) YOUR-CODE-HERE))
Test inverse-mod onatleastthetestcasesbelow.
(inverse-mod 5 11) ; - 9 5*9 = 45 = 1 (mod 11) (inverse-mod 9 11) ; - 5
(inverse-mod 7 11) ; - 8 7*8 = 56 = 1 (mod 11) (inverse-mod 5 12) ; - 5 5*5 = 25 = 1 (mod 12) (inverse-mod 8 12) ; - error no inverse exists (inverse-mod (random-prime 101) 101) - ? (test your answer with *mod)
Problem7: RSA
We’renowreadytoimplementRSA.First,weneedtorepresentpublicandprivatekeys. We’llusethesame abstraction for both kinds of keys. A key will consist of an exponent (e or d) and a modulus (n).
Write a data abstraction for keys, including a constructor make-key and two selectors get-modulus and get-exponent.
Next, we need to be able to generate public keys and private keys. First choose two random primes p and q, andletthemodulus n = pq. Thevalueecanbeanynumbersuchthat gcd(e,(p−1)(q−1)) = 1. Arandom number less than n that meets this criterion is fine (although it may take a few tries to find it). Finally, the value d should be the multiplicative inverse of e (mod(p−1)(q−1)). Writeaprocedurerandom-keypairthatgeneratesarandompublickeyanditscorrespondingprivate key (represented using your key abstraction) and returns them as a list. Your procedure should take a single parameter m, and produce a key pair capable of encoding any message in the range [0,m−1]. That means, in particular, that the modulus n of the generated key pair must be at least as large as m.
(define random-keypair (lambda (m) YOUR-CODE-HERE))
Writeaprocedurersathattakesakeyandamessageintegerandreturnstheencryptedordecrypted form of the message. Recall that in RSA, both encryption and decryption do the same thing, raising the message integer to a power. Use your key abstraction to implement this procedure; don’t violate the abstraction boundary.
(define rsa (lambda (key message) YOUR-CODE-HERE))
Test your rsa procedure on several generated key pairs and several message integers, to ensure that it encrypts and decrypts properly. What happens when you try to encrypt and decrypt a message integer which is too large for the key – i.e., larger than the modulus n?
Finally,let’stieitalltogetherbywritingproceduresthatcanencryptanddecryptmessagestrings,notjustintegers. Theprovidedcodeforthisprojectincludestwoprocedures,string-integerandinteger-string, that convert a string into an integer and vice versa. For example:
(string-integer "hello") ; - 1578072040808
(integer-string 1578072040808) ; - "hello" (string-integer "") ; - 1 (integer-string 1) ; - ""
In order to use the provided code in your own file without having to copy and paste it, put the provided file rsa.scm in the same folder as your own file and add the expression (load “rsa.scm”) at the top of your file. The load procedure evaluates all the definitions and expressions in rsa.scm, so that you can use string-integer and integer-string in your own code. Writeaprocedureencryptthattakesamessagestringandapublickeyandreturnsthemessageasan integer, encrypted using the public key. Also write its counterpart procedure, decrypt, that takes an encrypted message integer and a private key and decodes it to produce the original string. Note that although the original message is a string, the encrypted message should be represented as an integer.
(define encrypt (lambda (public-key string) YOUR-CODE-HERE))
(define decrypt (lambda (private-key encrypted-message) YOUR-CODE-HERE))
Demonstrate that your program can encrypt and decrypt the following messages. Use a randomly generated key pair that is big enough to encrypt all the messages below.
"hello Comp200!" "" "This is fun!"