Archive for the ‘other’ Category

Midterm review

October 22, 2009

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

Encryption and authentication protocols

September 29, 2009

In 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, 2009

I 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 p = 137 and q = 127. Then N=pq=17399 and \phi(N)=136 \cdot 126 = 17136. Take public exponent e=5 (one can verify that gcd(5, 17136)=1). Then d=13709 because 5 \cdot 13709= 1 \bmod 17136. The receiver publishes the public key (N=17399, e=5).

Say the sender wants to send the message m=16410. She would compute c=m^e \bmod N or 16410^5 = 8321 \bmod 17399 and send the ciphertext 8321 to the receiver.

The receiver can decrypt the ciphertext 8321 by computing 8321^d \bmod N or 8321^{13709} = 16410 \bmod 17399. (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 8321^{13709} \bmod 17399 = 8321 \cdot (((8321^2 \bmod 17399)^2 \bmod 17399)^{23} \bmod 17399)^{149} \bmod 17399. (Why?))

Now I’ll try a smaller example. Choose p=17 and q=23, and take e=3. What will the receiver’s public key be? What will it’s private key be?

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

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

El Gamal examples

September 23, 2009

I 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 5^2 \bmod 24 by typing ‘bc’ at the unix command line and then typing \verb+5^2 % 24+.

Say the receiver chooses prime p = 71, and g=33 (one can check that 33 is a generator of {\mathbb Z}_{71}^*), and secret exponent x=62. Then h = g^x \bmod 71 = 10. (I won’t explicitly write the “\bmod 71” anymore.) The receiver would publish the public key (p=71, g=33, h=10).

Say a sender wants to send the message m=15. It chooses random exponent r=31, say, computes the ciphertext (g^r, h^rm) = (62, 18), and sends this to the receiver.

To decrypt the ciphertext (62, 18), the receiver needs to compute 18/62^x = 18/62^{62}. Recall that dividing by 62 modulo 71 really means to multiply by 62^{-1} \bmod 71. We did not discuss how to compute multiplicative inverses in class, but one can verify that 62^{-1} = 63 \bmod 71 because 62 \cdot 63 = 1 \bmod 71. Thus, the receiver will compute 18 \cdot (62^{-1})^{62} = 18 \cdot 63^{62} \bmod 71 = 15. Of course, this was exactly the message sent by the sender!

Now a partial example. Let’s take p=107 and g = 2. (One can check that 2 is a generator of {\mathbb Z}_{107}^*.) Say the receiver chooses secret exponent x=29. What would the receiver’s public key be?

Now say a sender wants to send the message m=100 using random exponent r=19. 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: 2^{-1} = 54 \bmod 107.)