CS 70 Discrete Mathematics for CSSpring 2005 Clancy/Wagner HW 7Due Saturday, March 19Coverage: This assignment involves topics from the lectures of March 1, 8, and 10, and from Rosensection 2.6.Administrative reminders: We will accept only unformatted text files or PDF files for homework sub-mission. Include your name, login name, section number, and partner list in your submission. Give thecommand submit hw7 to submit your solution to this assignment.We advise you to work with a partner. If you haven’t yet switched partners, you should do so for thisassignment.Question 1 is a programming assignment. You should work on your own for the programming assignment(but you may work with a partner for the rest of the questions, as usual).Homework exercises:1. (24 pts.) Implementing RSAYou are to complete a program (either in Scheme or in Java) to generate a public/private key pair andencrypt and decrypt messages. In Scheme, this involves completing the functions key-component-list,inverse, and mod-power in the framework file rsa.scm. The analogous task in Java is to com-plete the methods createKeys, inverse, and modPower in the framework file RSA.java.Don’t change any of the code provided in the file other than what’s specified.The Scheme functions will be tested in stk. The Java code will be tested both with a RSAtester.javaclass that has access to the methods you are to provide, and with a shell script that calls the mainmethod. Command-line arguments to the RSA program are as follows.• The first argument is either -e, specifying that an ASCII string is to be encrypted, or -d, speci-fying that a big integer is to be decrypted.• The second argument is the string (enclosed in double quotes) or the big integer. If the secondargument is -, i.e. a single hyphen, the string or big integer is read from standard input; thisallows easy chaining of an encryption with a decryption or vice versa.• The third argument is only relevant for an encryption. If provided, it specifies the name of a filethat contains a public key. If the third argument is not provided, the file public-key in yourworking directory is used.Initialization code provided in both programs reads or create files in your working directory namedprivate-key and public-key if they don’t yet exist; each should contain a single line contain-ing two numbers.CS 70, Spring 2005, HW 7 1Scheme and Java both have built-in support for large integers. You are not allowed to use Scheme’sexpt-mod function. Java provides in the class java.math.BigInteger enough support tocomplete this assignment with hardly any code. Thus, you may not use the following methods injava.math.BigInteger:• gcd (BigInteger)• isProbablePrime (int)• modInverse (BigInteger)• modPow (BigInteger, BigInteger)• pow (int)• probablePrime (int, Random)You are also forbidden to use any other RSA or bignum library, whether part of Java or external.The class java.util.Random provides a random number generator that you may find useful whengenerating keys. The Scheme counterpart is the random function; given an integer argument n, itreturns a random integer between 0 and n− 1, inclusive.Framework files are in the directory ˜cs70/code.The directory ˜cs70/public-keys will contain files named aa, ab, etc.; file xy will contain thepublic key for user cs70-xy in the format described above. Each file initially will contain the pair3 6682189(the corresponding private key is 4451347 6682189). These files are writable; we encourage youto update your file with more reasonable values for the public key, to allow other students to test theircode by sending you messages.2. (6 pts.) Thinking about nSuppose someone chose a value for n that was not a product of two primes, i.e., n = pq with p > 1,q > 1, and q is composite. It would obviously be easier to factor, thus posing a security risk. Butwould the encrypting and decrypting operations still work with this n? Defend your answer.3. (6 pts.) Euclid’s argumentConsider the following result, first proved many centuries ago.Theorem 1 (Euclid) There exist infinitely many primes.Proof: Assume to the contrary that there exist finitely many primes. Let these primes (in increasingorder) be p1= 2, p2= 3, p3= 5, ..., pk. Let qk= p1p2p3··· pk+ 1. Note that qkis a new numbernot in the list of primes p1,..., pk. At the same time, it is not divisible by pifor any i, since qk≡p1p2p3··· pk+ 1 ≡ 1 (mod pi), which would mean that qkis a new prime different from p1,..., pk,which is a contradiction. This completes the proof. 2Let p1,..., pkrepresent the first k primes. Are we guaranteed that p1p2p3··· pk+ 1 is always primefor all k ≥ 1? Is the above proof valid? Explain.4. (24 pts.) String matchingCS 70, Spring 2005, HW 7 2(a) Consider again the fingerprint Fp(w) = w mod p, where we identify the integer w = 2n−1wn−1+··· + 2w1+ w0∈ N with the n-bit bitstring w = hw0,w1,..., wn−1i.Fix n,m ∈ N with n < m. Let X be a m-bit string hx0,x1,..., xm−1i. Let X(i)denote the n-bitsubstring hxi,xi+1,..., xi+n−1i of X that starts at position i, or equivalently, the integer X(i)=2n−1xi+n−1+ ··· + 2xi+1+ xi∈ N. For example, if m = 5, n = 4, and X = h0,1, 1,0, 1i, thenX(0)= h0,1,1, 0i = 6 and X(1)= h1,1,0, 1i = 11.Show how to efficiently compute Fp(X(i)) from Fp(X(i+1)).(b) Suppose we are given a m-bit string X and a n-bit stringY, and we want to test whetherY appearsas a substring of X. Consider the following naive algorithm:NAIVESTRINGMATCH(X,Y):1. For i = m− n down to 0, do:2. If X(i)= Y, return i.3. Return “No match.”Argue that this naive algorithm has a O(mn) worst-case running time, if we count each bitoperation as one unit of time.(c) Give a faster algorithm. (Hint: make step #2 more efficient.)(d) Suppose your algorithm is allowed to have a small chance (say, < 1/m) of returning an erroneousanswer. Describe an algorithm with a O(mlgm) worst-case running time. Your analysis of therunning time can be somewhat informal, but be sure to show all parameter choices.(If you cannot find an algorithm with such a provable bound on the running time, reduce theasymptotic running time as much as you are able. Ignore constant factors.)CS 70, Spring 2005, HW 7
View Full Document
Unlocking...