CMU 15-827, Homework 1

Out: 1 October 1997

Due: 15 October 1997

Ground rules:  You are strongly encouraged to work in groups on this
homework.  I recommend groups of three people -- but groups of 2 or 4
are fine too.  If you want to work on this by yourself, let us know.
Each group should only turn in one copy of the homework.


You are encouraged to use any sources whatsoever in completing this
homework.  However, please be careful to document any sources that you
use (excluding class lectures, help from the instructors, and material
from the textbook.)

(la)  Generate RSA moduli of 512 bits and 1024 bits; generate
      public-private key pair for both moduli.

(b)  Program or copy routines for RSA and DES encryption for the most 
     interesting hardware platforms you have access to.

(c)  Carefully obtain benchmark figures -- what is the throughput of the
     routines, what is the set up cost for inserting a new key, how many 
     keys can be searched per minute; how many megabytes can be encrypted
     under a single key.  For RSA, find these benchmark figures for both
     sizes of moduli.

(d)  What can you do to speed up the performance of your routines on your
     chosen hardware platforms?  Describe improvements, and when feasible,
     implement them and remeasure.

(2)  Work out the theory of Rabin and RSA encryption for moduli that are 
     products of 3 odd primes.  Repeat for products of k odd primes.  What
     advantages, if any, does this offer?

(3)  We have discussed the use of triple-DES to increase the key search
     size (under a known-plaintext attack) to 2^112.  What is the minimum
     key  search space that you can discover (using "meet in the middle"
     attacks) if you use quadruple-DES?  k-independent invocations of DES?

(4)  We discussed a method of calculating average salary using Shamir's
     secret sharing in class.  Describe a simpler method that does not
     use secret sharing.  Remember, the ground rules are that for each
     user U, no one except U and the coalition of the universe of
     employees except for U to determine U's salary.

(5)  One solution that has been proposed for protecting aggregate data is
     to add noise to the sample.  For example, each person could modify
     his reported salary by adding a random variable chosen over a fixed
     distribution.  This method has often been proposed for protecting
     survey data.  What do you think of this method?  What are its
     advantages and disadvantages?

     (Protecting privacy in personal databases is very important the
     largest scandal with the US census occured with the 1940 census --
     after Pearl Harbor, almost all Japanese-Americans and many
     Italian-Americans on the West coast were rounded up and sent to
     internment camps.  The census bureau refused to release the names
     associated with their surveys (to protect confidentiality), but to
     make sure that the authorities "got" all of their target set, the
     authorities used ethnic census data for each block.  If a given
     city block had 4 Italian-Americans and 2 Japanese-Americans, the
     authorities could make sure that they accounted for all of these
     citizens.  Some researchers have proposed adding noise as a way to
     achieve this)

(6)  Zero-knowledge authentication does not exchange a secret key.  What
     class of applications is it appropriate for?

(7)  As we discussed in class, strict certificate hierarchies that depend
     on a single root key are vulnerable to attacks where the root key is 
     disclosed.  Describe methods for allowing root heirarchies where 
     disclosure of a single key -- even a root key -- does not compromise
     the system.  

     (a)  Describe the architecture of your system

     (b)  Describe how new keys are generated

     (c)  Describe how certificates are updated when root keys are
          changed (perhaps because the root key has been disclosed)

     (d)  Describe how keys are revoked.