Due: Wednesday, September 24, 2003 M. Shamos

For general homework policies, see Homework 1.

All homework must be submitted as a Microsoft Word .doc file, by email to jieh@cs.cmu.edu, with a copy to shamos@cs.cmu.edu. Homework is due by 11:59 p.m. on the announced date.

Problem 1. [50 points ] Catalog websites such as www.staples.com (office products) are very good at maintaining databases with huge number of products that can be ordered remotely but are usually poor at capturing customer requirements, such as a stapler that can staple 75 sheets at once or the right pen for marking on glass. Yet capturing the customer’s needs and preferences is a fundamental step in any kind of commerce.

(a) [10 points] Visit www.staples.com and try to determine the highest capacity stapler sold on the website (measured by number of sheets of paper it will staple, sometimes called “sheet capacity”). Count the number of web pages you had to examine in order to find out this information. Give the product number of the highest capacity stapler you can find, tell its capacity and the number of pages you examined. Then tell how you are sure that there is no stapler on the website that has a higher capacity.

(b) [10 points] Now do the same thing at www.officedepot.com but use the “Search By Feature” link when you get to “Staplers and Accessories.” Tell how many pages you had to view (counting the home page as the first one) and give the product number of the highest capacity stapler sold by Office Depot.

(c) [30 points] It seems clear that most online catalogs are not much more than searchable versions of printed catalogs. They may be very convenient for lookup if you know what you want, but there is no easy way for the customer to communicate his needs other than through keyword queries. The purpose of this question is to develop an automated way of capturing product features to create a facility like Office Depot’s “Search by Feature”, but for any type of product, not just office products. The idea is to start with a data sheet for each product and create a menu of features by scanning the text of the data sheet. Some sample data sheets (for a variety of products) are:

http://seiko.fcms.de/en/site/contentvvp1200/produkt_video_features.xml

http://www.masterg.com/printroom/data-xerox-3001.html

http://www.rocol.com/sitesafety/english/datasheets/technical/Spill%20Control.html

http://www.imaging-resource.com/PRODS/MX17/M17DAT.HTM

You are in charge of web design for a company that sells 10,000 different products. Assume that you have machine-readable manufacturer’s data sheets for every product and that software is available to parse the sheets and deliver pairs of strings of the form (attribute, value) for each product your company sells. For example, from the first data sheet above for the Seiko VP-1200 we might get pairs like (“Printing method”, “monochrome direct thermal”) and (“Gray shades”, “256”).

Explain how you would create a search function that automatically presents users with the ability to select a product based on any set of attribute(s) for any of your company’s products.

Problem 2. [50 points] RSA

(a) [25 points] Decrypt the following message:

21245 04208 20587 15352 27585 08190 35950 23280 09397 25407 10311 35950 19501 30235

It was encrypted using RSA with e = 25307 and n = 38383. Each of the five-digit code numbers in the message represents two ASCII characters of the plaintext. You may find the following applet helpful: http://cisnet.baruch.cuny.edu/holowczak/classes/9444/rsademo/. You may also have to write a short computer program to help you, since performing the necessary calculations manually may be tedious. Before you start, think first about a strategy for doing the decryption. In addition to giving the plaintext, you must explain how you obtained it.

(b) [25 points] Even good cryptographic algorithms must be used carefully. In particular, you should never encrypt a message given to you by someone else, since it might be used to decrypt a different message you sent earlier to a different person. Suppose eavesdropper Eve is listening to an exchange of RSA-encrypted messages between Alice and Bob. Bob’s public key is (e, n). Both of these numbers are public. Alice sends message M to Bob encrypted with his public key. The ciphertext she sends is c = M^e (mod n). Eve now knows c, e and n, but if n = pq is a very large number, she can’t factor it to determine p and q, which she needs to calculate the decryption key d, which is the multiplicative inverse of e (mod (p-1)(q-1)). So Eve selects a random number r < n and calculates the following quantities:

1. x = r^e (mod n)

2. y = xc (mod n)

3. t = r^(-1) (mod n), that is, t is the multiplicative inverse of r (mod n), the unique number t such that rt = 1 (mod n)

Eve now asks Bob to encrypt y with his private key d. He thinks this is safe, since there’s no way for anyone to figure out his private key from an encrypted message (that’s true). So Bob happily sends Eve the number u = y^d (mod n). From all of this information, Eve still can’t obtain d. But she can now decrypt c to obtain the original message M! Show how Eve can do this.