Tuesday, January 12, 2010

Implementing DES

It's a quite outdated now, but back in the day the venerable Data Encryption Standard was a really popular form of symmetric-key cryptography. I have learned about DES twice in my life, once my freshman year of High School and once this year in my Cryptography class. The second time around, having taken Computer Architecture, I was struck by how neatly DES's operations mapped to the most common machine instructions.

I decided that this would be a good opportunity to practice some assembly programming. It seemed tailor-made for the purpose.

I haven't actually written the assembly program. I wanted to get a working copy in Python running first, as a point of reference. I have made two implementations in python. The first converts all the integers to lists of ones and zeros, and uses Python's list manipulation abilities. The second stays at a low level and just uses bit shifting and that sort of thing.

I'll post a more extensive write-up later. For now, let's just say that I'm quite disappointed that the low-level version really isn't noticeably faster than the high level version. Both encrypt about 150,000 blocks per second. It may just be that Python has too much overhead in general, and if you want to get all the benefits of operating closer to the metal you have to code it in C. Global variables and function calls are both rather slow in Python, according to Guido.[1] I'll have to do some profiling to see what needs speeding up.

No comments:

Post a Comment