Archive for September, 2009

Lecture 9

September 30, 2009

Today we covered public-key encryption schemes secure against chosen-ciphertext attacks as well as digital signature schemes. This concludes our discussion of the low-level details of cryptography, though we will continue to see applications of cryptography throughout the rest of the course.

At the end of today’s lecture I mentioned some ‘pitfalls’ that can arise when using cryptography. In the next 1-2 lectures we will see some case studies of things that can go wrong. Please try to read the essays/papers assigned to today’s lecture and next Monday’s lecture in time for Monday’s class. I will also post papers for next Wednesday’s lecture. (One is already there.) These papers are required reading for the midterm exam.


On symmetric-key sizes

September 30, 2009

Bruce Schneier has a post to which I couldn’t resist linking. He discusses why a 49,000-bit key is ridiculous, the dangers of using “home-brewed” cryptography, and the thermodynamic limits of brute-force search (much better than I did in class).

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…

Lecture 8

September 29, 2009

Because of Yom Kippur, we had a guest lecturer (Prof. Arbaugh) talk about malware and rootkits. I hope you found the subject interesting!

After speaking with Prof. Arbaugh, and because some students had to miss class also, I have decided that this lecture will not be considered ‘required material’. (I.e., it will not be covered on the midterm or final exams.)

Announcements, week of Sept. 28

September 26, 2009

On Monday, I will miss class due to Yom Kippur. There will be a guest lecture by Prof. Bill Arbaugh on rootkits (not wireless security as I announced in class).

In Wednesday we will pick up where we left off in the last lecture. I have also listed some reading that should be done before class. We will begin discussing those articles in Wednesday’s class and continue next Monday. (Although it looks like a lot, the first three links are short essays and at least two of the final three links should be fun to read.)

I have also posted some articles to read for next Monday’s lecture, and I may add 1-2 more.

In addition to the above, I have listed several optional articles. In some cases we will discuss these briefly in class but I thought the articles themselves were too technically difficult to make required reading. In other cases we will not have time to discuss them in class but they reinforce the material or are just plain interesting. Feel free to discuss or ask questions about any of them on the blog.

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.)

Lecture 7

September 23, 2009

In this lecture we reviewed El Gamal and RSA public-key encryption (and variants thereof), and then discussed the issue of malleability and how this can lead to attacks. I hope people enjoyed that part of lecture, since I always find describing those attacks fun.

I was asked to prepare some worked out (and partially worked out) examples of El Gamal and RSA encryption, so I will do that in the next two blog posts.

My request for (anonymous) feedback about the course still holds.

Lecture 6

September 21, 2009

We continued our discussion of some basic number theory, and then described the Diffie-Hellman protocol. We also introduced the public-key setting, and introduced the El Gamal and RSA encryption schemes.

The blog is pretty quiet; there are barely any questions in class; and the only questions I get by email are about the homework. Is class moving too slow, so that everything is too easy? Or too fast so that people don’t know what to ask? Are people finding the crypto material uninteresting? Comments welcome! (Anonymous comments are fine for responding to this if you prefer, though I reserve the right to delete any that are inappropriate.)


September 16, 2009

Even though there is a forum for this class, no one seems to be using it. Since I got the same question from two students today, I figured I’d maintain a FAQ here. Questions about the HW can be posted here as well.

PS: For fastest response, email both me and the TA. That way whichever one of us reads your mail first will answer it.

Q1: How are we supposed to generate a DES key?
A1: I wanted you to generate the key yourself, rather than having the JCE do it all for you. Recall that a legal DES key is 64 bits long, but only 56 of this bits are random and the remaining bits are check-bits. I wanted you to generate a random DES key by (1) generating 56 random bits, and then (2) manually setting the check bits appropriately to get a legal 64-bit key. You can look at the DES specification to determine the proper format for a DES key. (For those of you who have the textbook, the information is also in there.)

Q2: How do we access the block ciphers? Are we supposed to implement them ourselves?
A2 (copied from the forum): The point of the HW was to implement the *modes*, assuming you have access to the cipher. Unfortunately, the JCE does not give direct access to the cipher; however, you can access, e.g., the DES cipher as described in the HW:

Cipher DEScipher = Cipher.getInstance(“DES/ECB/NoPadding”);

(and analogously for AES). Why does this give you access to the cipher? That’s what you are supposed to answer as part of the HW.