I have written a brief summary of material that will be covered on the midterm. Please read the caveat at the top, though.

## Archive for the ‘other’ Category

### Midterm review

October 22, 2009### Encryption and authentication protocols

September 29, 2009In case you missed it, a question I asked on this blog way back in lecture 4 has generated a bit of discussion (which I am glad to see!). I’ll try to come up with similar questions on other lectures…

### Textbook RSA examples

September 23, 2009I will give one worked out example, followed by a partial one. (Recall that textbook RSA encryption is insecure and should not be used. This is just for illustration.)

Say the receiver chooses and . Then and . Take public exponent (one can verify that ). Then because . The receiver publishes the public key .

Say the sender wants to send the message . She would compute or and send the ciphertext 8321 to the receiver.

The receiver can decrypt the ciphertext 8321 by computing or . (Note: these numbers were already too large to be handled by ‘bc’ directly. One can compute the result in several steps, using the fact that . (Why?))

Now I’ll try a smaller example. Choose and , and take . What will the receiver’s public key be? What will it’s private key be?

Say the sender wants to send the message . What will the ciphertext be?

Verify that the receiver can correctly recover the message from the ciphertext.

### El Gamal examples

September 23, 2009I will give one worked out example, followed by a partial one. As in class, this example is not entirely accurate and you should not rely on it to implement El Gamal encryption for real.

Note that you can easily perform modular arithmetic (on “small” values) using the ‘bc’ command on unix. E.g., you can compute by typing ‘bc’ at the unix command line and then typing .

Say the receiver chooses prime , and (one can check that 33 is a generator of ), and secret exponent . Then . (I won’t explicitly write the “” anymore.) The receiver would publish the public key .

Say a sender wants to send the message . It chooses random exponent , say, computes the ciphertext , and sends this to the receiver.

To decrypt the ciphertext , the receiver needs to compute . Recall that dividing by 62 modulo 71 really means to multiply by . We did not discuss how to compute multiplicative inverses in class, but one can verify that because . Thus, the receiver will compute . Of course, this was exactly the message sent by the sender!

Now a partial example. Let’s take and . (One can check that 2 is a generator of .) Say the receiver chooses secret exponent . What would the receiver’s public key be?

Now say a sender wants to send the message using random exponent . What would be the ciphertext computed by the sender?

Finally, verify that decryption successfully recovers the message. (You may have difficulty finding the correct multiplicative inverse. **Hint:** .)