Cryptography course–the power of XOR

I took a Cryptography I course on coursera.org taught by Stanford’s Dan Boneh. The lectures are easy listening (I usually put on my wireless headphones while doing a household chore, and set my iPad somewhere convenient if I need to glance at the slide), although clocking in at about 2  hours a week, are certainly a bit of a commitment. The are broken into 5-20 minute chunks, the online system tracks which you have listened to already, and asks you 0-3 questions a lecture to make the whole process more interactive and to jolt you to attention if you’ve filtered out an important section.

It was a great experience, and they just started a new offering August 27 at https://www.coursera.org/course/crypto

The homework exercises took me between 20 and 40 minutes per week, and formed an important part of the understanding. Here’s a fun question modified from a homework question:

One time pad encryption

Solving this shows us how important it is that a one time pad is only used once. Recall one time pad encryption is proved to be impossible to crack if used as correctly. For our purposes, it defined as

(a) k ⊕ m = c

where k is the one time pad, ⊕ is the xor function, m is the message and c is the resulting cipher text

 Now for the question

Suppose you are told that the one time pad encryption of the message “attack Iraq” is 1000100111110100110100100011110001111000101000000000100010011101000010001100101110001010 (the plaintext letters are encoded as 8-bit ASCII, and the key is likewise 88 bits, naturally). What would be the one time pad encryption of the message “attack Iran” under the same OTP key?

Recall that anything xor’d with itself is 0, and xor’ing with 0 is the identity: in mathematical language that (b) k ⊕ k=0, and (c) m ⊕ 0 = m. Essentially we can “cancel out” anything we would like to get rid of in an xor equation, by xoring it back into the equation one more time. Thus we can xor c=k ⊕ m with m, which we know is “attack Iraq” to get c⊕m=k ⊕ m⊕ m=0⊕k=k to retrieve the one time pad k. Now we can use the one time pad again to encrypt our message m2 “attack Iran” to get the new cipher text c2.

c2=k ⊕ m2=(c1⊕m1)⊕ m2. Since we have m1 “attack Iraq” and c1, given above, and m2 “attack Iran”, we can easily compute new cyphertext using the same key. What do you get?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s