I'm thrilled to let you know that I've just added encryption and decryption with random padding to my Python RSA module. The code has become much more secure than it was before, and also makes it capable of encrypting and decrypting binary data! This is a big step towards the practicality of the implementation.
I've implemented the padding according to the PKCS#1 standard. The RSA Algorithm page by DI Management explains how to do this very clearly; cudos to them!
Right now these changes are unreleased. I want to add signing and verifying signatures too before I do that. Maybe I'll deprecate the existing functions, as they are much less secure than all the new stuff I'm adding. If you want to try out what I've changed so far, feel free to grab a copy off my Mercurial repository.
photo hosted on Flickr
UPDATE 14:20: I've also implemented PKCS#1 style signatures and signature verification
UPDATE 2011-07-12: the implementation is compatible with OpenSSL, making it very likely compatible with other implementations of PKCS#1 version 1.5!