cryptography

This was much harder than it should have been. While this is the certainly the most trivial post on crypto-math on the webs, I wanted to share my MATLAB xor code in the hope that I save someone else’s time. It is a basic property of cryptography that a one time pad must be used only once. A example like this makes it very concrete:

Suppose you are told that the one time pad encryption of the message “attack at dawn” is 09e1c5f70a65ac519458e7e53f36 (the plaintext letters are encoded as 8-bit ASCII and the givenciphertext is written in hex). What would be the one time pad encryption of the message “attack at dusk” under the same OTP key?

Let $m_0$ be the message “attack at dawn”, then $m_1$ is the message “attack at dusk”, and $c_1$, $c_2$ the corresponding ciphertexts. If $p$ is the one-time pad (OTP) that encrypts the message, we then have:

$$ c_0 = m_0 \oplus p$$

So we can obtain the one-time pad by performing an XOR of the ciphertext with the plaintext:

$$ p = c_0 \oplus m_0 \text{.}$$

This enables us to encrypt the new message without using the OTP explicitly:

$$c_1 = m_1 \oplus p = m_1 \oplus \left(c_0 \oplus m_0 \right) = c_0 \oplus (m_0 \oplus m_1) \text{.}$$

You could truncate down to the only characters that are different, but since I’m writing a script for this, I didn’t bother.

In python this would be super short:

def strxor(s1,s2):
return ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(s1,s2))

strxor(strxor("6c73d5240a948c86981bc294814d".decode('hex'), "attack at dawn"), "attack at dusk").encode('hex')

>>>'6c73d5240a948c86981bc2808548'

But, the government won’t allow me to have python on my laptop and I need to use matlab.

Some Helpful Links

• My course slides: http://spark-university.s3.amazonaws.com/stanford-crypto/slides/02-stream-v2-annotated.pdf
• Another Solution: http://crypto.stackexchange.com/questions/10534/how-to-decode-an-otp-message
• Some good general info: http://www.binaryvision.nl/3075/statistical-test/

We are swimming in a sea of information. Without encryption this whole operation would be a very public event. Encryption enables our communications to be anonymous or secure and makes e-commerce and private communications possible. Because of this, I registered for Dan Boneth’s cryptography course. At this point, I’ve only watched one lecture, but I have some initial thoughts (and some code) that I wanted to jot down.

At it’s most simple, Encryption is used to convert data into a form that a third party can’t read. There are multiple reasons for wanting to do this, but the most common is a desire for security or privacy. In a more comprehensive sense, the aim of cryptography is to construct and analyze protocols that overcome the influence of adversaries and which are related to various aspects in information security such as data confidentiality, data integrity, authentication, and non-repudiation. Modern cryptography is heavily based on mathematical theory and assumptions about the capability of current computer hardware. No code is infinitely secure, and is theoretically possible to break, but a “secure code” is considered infeasible to break by any known practical means. The study of encryption is of high interest to me, because it intersects many of my current interests: the disciplines of mathematics, computer science, and electrical engineering.

Dan Boneth’s initial lecture covered the traditional overview, definition and history of cryptography. His overview was rich with basic applications of cryptography and its role in our lives today.

The concept of encryption and decryption requires some extra information to encode and decode the signal. Though this information takes many forms, it is commonly known as the key. There may be cases when same key can be used for both encryption and decryption (a shared key) while in certain cases, encryption and decryption may require different keys (such as a public/private key arrangement) and this is one way to organize existing techniques.

He provides a strong admonishment to use “standard cryptographic primitives” that have withstood public scrutiny and makes the point that without the necessary peer-review by a very large community of hundreds of people for many, many, many years, one can’t trust a cryptographic implementation. For this reason he admonishes the student to never trust an implementation based on proprietary primitives. (The student is left to wonder what exactly a cryptographic primitive is.)

He highlights that cryptography has its limitations and even a secure cryptographic channel does not guarantee a secure implementation. It was helpful that he followed this statement up with what exactly an insecure implementation is by surveying how to break different ciphers. He mentions an known insecure Blu-Ray protection standard called AACS and mentions an additional forthcoming discussion of the mechanics of its compromise.

From here, he discusses applications such as private elections and auctions and also the mechanism of digital signatures. He ends the lecture by discussing some of the “magic” recent developments in encryption such as homomorphic encryption — where operations can be accomplished on encrypted data without decryption. (See the DARPA proceed program.) This has fascinating applications such as the ability to query a database without providing an observer of database (before, during or after) any insight into the nature of the query.

He closes with a discussion stating that any cryptographic implementation has three requirements: precise specification of a threat model, a proposed construction, and a proof that breaking construction under threat mode will solve an underlying hard problem.

The next lecture was my favorite. Here, Boneth surveyed the history of cryptography which included a lot of the codes you play with in school such as symmetric and substitution cyphers, along with a discussion how to break these by using frequency and pattern recognition techniques. (Mostly based on known distributions of letters in the underlying language.)

He then introduces interesting ciphers such as the caesar cipher. In the Caesar cipher each letter of the alphabet is shifted along some number of places; for example, in a Caesar cipher of shift 3, A would become D, B would become E, Y would become B and so on. He then moves on to more complex ciphers such as the Vigenère cipher (a simple form of polyalphabetic substitution developed in Rome in the 16th century) and an interesting discussion of rotor machines (the most famous of which was the German Enigma). The Vigenère cipher consists of several Caesar ciphers in sequence with different shift values. He ended with the lecture with a quick description of modern encryption techniques.

I always enjoy these introductory lectures of a course — I can generally follow everything and am excited about the material. A lot of my friend in college would not go to the first lecture, but I never missed it. It was always go to at least one lecture where I could follow along. This sounds like it will be an interesting ride.

Enough of the discussion; let’s see how this works. As discussed above, the Vigenère cipher produces encrypted ciphertext from an input plaintext message using a key and a matrix of substitution alphabets. From the MATLAB below, you can generate the Vigenère square, also known as the tabula recta, this table can be used for encryption and decryption. It consists of the alphabet written out 26 times in different rows, each alphabet shifted cyclically to the left compared to the previous alphabet, corresponding to the 26 possible Caesar ciphers. At different points in the encryption process, the cipher uses a different alphabet from one of the rows. The alphabet used at each point depends on a repeating keyword.

Let’s try this with MATLAB (see code below). If I use a key of ‘Ceasar knows something you do not’ and a secret message of Titus Lucretius Carus (a Roman epicurean epic poet), we get:

encrypt('Titus Lucretius Carus', 'Ceasar knows something you do not')
VMTLSQKDPE KHLFLGTYBE
decrypt('VMTLSQKDPE KHLFLGTYBE', 'Ceasar knows something you do not')
TITUS LUCRETIUS CARUS

It works!