pycrypto

Here's a Quick Python post about encryption using the pycrypto module. Much of it is derived from the excellent overview here.

I tried easy_install first, but it hung for some reason, so I just did:

git clone https://github.com/dlitz/pycrypto.git cd pycrypto python setup.py build sudo python setup.py install

Let's try a little DES:

>>> from Crypto.Cipher import DES >>> des = DES.new('01234567',DES.MODE_ECB) >>> text = 'hello, world' >>> c = des.encrypt(text) Traceback (most recent call last): File "", line 1, in ValueError: Input strings must be a multiple of 8 in length >>> len(text) 12 >>> text += '.' * (8 - len(text) % 8) >>> c = des.encrypt(text) >>> c '\xc4\xf56\xad\xbb\xae\xb8\x84\xbf\xb3\xfaH^\xe3\x10\x16' >>> des.decrypt(c) 'hello, world....' >>>

Here is a different mode of DES called CFB (Cipher Feedback). It requires some random bytes, and two instantiations of the object:

>>> from Crypto.Cipher import DES >>> from Crypto import Random >>> iv = Random.get_random_bytes(8) >>> des1 = DES.new('01234567', DES.MODE_CFB, iv) >>> des2 = DES.new('01234567', DES.MODE_CFB, iv) >>> text = 'hello, world!' >>> c = des1.encrypt(text) >>> c '\x92\xc6\xc7K=\xb0\xf4\x83A\xfd\xa4\x13e' >>> des2.decrypt(c) 'hello, world!'

The venerable xor method is also present:

>>> from Crypto.Cipher import XOR >>> key = '\x00'*4 + '\x01'*4 + '\x10'*4 + '\x11'*4 >>> xor = XOR.new(key) >>> text = '\x00\x01\x10\x11' * 4 >>> c = xor.encrypt(text) >>> p = xor.decrypt(c) >>> text '\x00\x01\x10\x11\x00\x01\x10\x11\x00\x01\x10\x11\x00\x01\x10\x11' >>> key '\x00\x00\x00\x00\x01\x01\x01\x01\x10\x10\x10\x10\x11\x11\x11\x11' >>> c '\x00\x01\x10\x11\x01\x00\x11\x10\x10\x11\x00\x01\x11\x10\x01\x00' >>> p '\x00\x01\x10\x11\x00\x01\x10\x11\x00\x01\x10\x11\x00\x01\x10\x11'

I adapted one of the scripts from Laurent Luce's post to do encryption on a file. Here is the output (the hex values of the key we generated), and some display of the data using hexdump:

> python script.py 21 31 e4 25 b1 ab be fb 3d 35 95 f7 8b 67 ba 24 > hexdump -C m.txt 00000000 48 65 6c 6c 6f 2c 20 77 6f 72 6c 64 21 0a |Hello, world!.| 0000000e > hexdump -C c.txt 00000000 25 bc 08 25 ae 7c fb c3 3a a3 91 83 6a 34 7c 06 |%..%.|..:...j4|.| 00000010 > hexdump -C p.txt 00000000 48 65 6c 6c 6f 2c 20 77 6f 72 6c 64 21 0a 20 20 |Hello, world!. | 00000010

script.py

from Crypto import Random from Crypto.Cipher import DES3 import struct def encrypt_file(ifn, ofn, chunk_size, key, iv): des3 = DES3.new(key, DES3.MODE_CFB, iv) with open(ifn, 'r') as in_file: with open(ofn, 'w') as out_file: while True: chunk = in_file.read(chunk_size) if len(chunk) == 0: break elif len(chunk) % 16 != 0: chunk += ' ' * (16 - len(chunk) % 16) out_file.write(des3.encrypt(chunk)) def decrypt_file(ifn, ofn, chunk_size, key, iv): des3 = DES3.new(key, DES3.MODE_CFB, iv) with open(ifn, 'r') as in_file: with open(ofn, 'w') as out_file: while True: chunk = in_file.read(chunk_size) if len(chunk) == 0: break out_file.write(des3.decrypt(chunk)) SZ = 100 ifn = 'm.txt' ofn = 'c.txt' key = Random.get_random_bytes(16) iv = Random.get_random_bytes(8) L = [struct.unpack('B',k) for k in key] L = [hex(t[0])[2:] for t in L] print ' '.join(L) encrypt_file(ifn, ofn, SZ, key, iv) decrypt_file(ofn, 'p.txt', SZ, key, iv)

bytearray

I came across a post by Python guru David Beazley introducing the bytearray data type. Here is one of his examples, modified slightly:

>>> s = "Hello World" >>> b = bytearray(s) >>> b bytearray(b'Hello World') >>> b[:5] = "Cruel" >>> b bytearray(b'Cruel World') >>> for i in b: ... print i ... 67 114 117 101 108 32 87 111 114 108 100 >>> b.append(33) >>> b bytearray(b'Cruel World!') >>> print b Cruel World!

The usage b"mystring" was new to me as well. According to this SO answer:

the b prefix for string literals is ineffective in 2.6, but it is a useful marker in the program, which flags explicitly the intent of the programmer to have the string as a data string rather than a text string. This info can then be used by the 2to3 converter or similar utilities when the program is ported to Py3k.

More info here (thanks, Ned).

A bytearray has the methods of lists including __getitem__ and __setitem__. Unusually for Python, one can use arguments of both int and str types. The actual type of a bytearray item is < type 'int'>.

>>> b = bytearray('Hello World!') >>> b[-1] = '*' >>> b bytearray(b'Hello World*') >>> ord('!') 33 >>> b[-1] = 33 >>> b bytearray(b'Hello World!')

We can use a bytearray to do a small job of encryption in a very convenient way:

>>> import numpy as np >>> msg = bytearray("Hello World") >>> n = len(msg) >>> L = np.random.randint(0,256,n) >>> key = bytearray(list(L)) >>> len(key) 11 >>> key bytearray(b'N\x963\x8a\x06\xf2\xe9\x92\xb9\xf4L') >>> >>> >>> ctext = bytearray() >>> for c,k in zip(msg,key): ... ctext.append(c ^ k) ... >>> ctext bytearray(b'\x06\xf3_\xe6i\xd2\xbe\xfd\xcb\x98(') >>> ptext = bytearray() >>> for c,k in zip(ctext,key): ... ptext.append(c ^ k) ... >>> ptext bytearray(b'Hello World')

Python mergesort

I need to make a serious commitment to algorithms at some point. I have the 3rd edition of Sedgewick, and worked through volume 1 some years ago. I see the 4th edition has moved to Java; I think that's a big mistake. I would hope for a basic algorithms book in Python, but I'll take C++ over Java any day. (I also have Cormen but put it aside).

I should really buy Knuth's books, but worry they'd be beyond my abilities.

I also have Magnus Hetland's book and Zelle's also, and I think they're great, but haven't found the time to be systematic about either of them either. They are for this summer.

Just for fun, here is a modified version of mergesort (from my book).

There are a couple of ideas here. First, suppose we have two lists that are already sorted. It's easy to merge them into one sorted list, by comparing the next elements in each and choosing the correct one. That's what merge does. The second idea is recursion. That's what mergesort does. The code below is set up to read a power of ten from the input.

This is a good challenge for a beginning Python coder.

Here is some timing on mine:

> time python merge.py 3 real 0m0.054s user 0m0.039s sys 0m0.013s > time python merge.py 4 real 0m0.232s user 0m0.216s sys 0m0.014s > time python merge.py 5 real 0m8.201s user 0m8.178s sys 0m0.020s >

It hangs with N = 1e6, I am not sure why yet.

merge.py

import random, sys def merge(left,right): rL = list() while True: if left and right: if left[0] < right[0]: rL.append(left.pop(0)) else: rL.append(right.pop(0)) continue if left: rL.extend(left) elif right: rL.extend(right) return rL def merge_sort(iL): if len(iL) == 1: return iL n = len(iL)/2 left = merge_sort(iL[:n]) right = merge_sort(iL[n:]) result = merge(left,right) return result if __name__ == '__main__': try: n = int(sys.argv[1]) except: n = 4 N = 10**n L = range(N) random.shuffle(L) result = merge_sort(L) assert result == sorted(L)

defaultdict

A common use case for dictionaries is to hold a count of the occurrences of a key in some other object, for example, words in a file. In this case, one needs to deal with missing keys:

>>> L = list('abcaba') >>> D = dict() >>> for k in L: ... try: ... D[k] += 1 ... except KeyError: ... D[k] = 1 ... >>> D {'a': 3, 'c': 1, 'b': 2}

Another solution is to use the setdefault method of dicts:

>>> D = dict() >>> for k in L: ... D.setdefault(k,0) ... D[k] += 1 ... 0 0 0 1 1 2 >>> D {'a': 3, 'c': 1, 'b': 2}

A better way (certainly better than this second approach) is to use a defaultdict:

>>> from collections import defaultdict >>> D = defaultdict(int) >>> for k in L: ... D[k] += 1 ... >>> D defaultdict(, {'a': 3, 'c': 1, 'b': 2})

Some of the magic involves __missing__:

>>> 'd' in D False >>> D.__missing__('d') 0 >>> 'd' in D True >>> D defaultdict(, {'a': 3, 'c': 1, 'b': 2, 'd': 0})

For more you can go to the docs or here or here, or just do this:

>>> print defaultdict.__missing__.__doc__ __missing__(key) # Called by __getitem__ for missing key; pseudo-code: if self.default_factory is None: raise KeyError((key,)) self[key] = value = self.default_factory() return value

[ UPDATE: The collections.Counter class was mentioned in a comment. Don't know why I didn't mention it in this post, I've used it in many other posts here. If it's convenient to convert the data to a list of keys, that's the way to go. ]