CS-235. Problem Set 6


  1. Ex.4.3
  2. Ex.4.4
  3. Ex.4.5
  4. Secret Sharing and RSA:
    A great mafia boss Vito uses RSA to receive letters from his associates. Everyone (who is important) knows Vito's public key PK=(n,e); and they encrypt a message m as c=EPK(m) := me mod n.
    Only Vito knows the secret key SK=(n,d), and uses it to decrypt the received ciphertext c as follows: m=DSK(c) := cd mod n.
    [irrelevant to this problem, but in fact, a sender would not encrypt a message itself as above -- instead she would use the above encryption mechanism to encrypt a "session key", which would then be used to encrypt (using a more efficient symmetric cipher) the actual message. this is how SSL/TLS works when you make a payment on-line.]
    As Michael and Fredo are growing up, Vito is thinking about retiring. But he is not too sure about each of his son's loyalty to him and to each other. So he does not want either one of them to be in sole possession of the secret key. Propose how Vito can use some of the secret sharing ideas we discussed in the class to assure that only by working together Michael and Fredo will be able to decrypt messages encrypted for the same public key PK that Vito has been using.
    (a) Namely, describe how Vito could compute secret keys SK0 and SK1 such that he than would give one of these secret keys to each of his sons and then to decrypt a message they would need to do the following: given ciphertext c, one computes c' := DSKb(c), and then the other would compute m :=DSKb(c'), where b is a bit and b is its complement (i.e., they could decrypt in either order). At the same time, just one of the sons would not be able to decipher any of these messages.
    (b) Suppose that in Godfather 1.5, it turns out that Sonny (the oldest son of Vito) manages to survive and makes a dramatic comeback, returning after a long recovery. Could Vito have designed such scheme as above but for three people, so all three of them have to cooperate for each message?
    (c) Extra credit: Now, suppose that Vito decides that he want to split up his operations, so that Michael is in charge of one branch, while Fredo is in charge of the other, but both have to work with Sonny. How can this be achieved?