--I slightly edit plus add comments to Goucher's message repeated below. To Warren, Use a N-bit key to seed a Blum-Blum-Shub pseudorandom number generator, and XOR its output with the message. That's much quicker than RSA (multiplication is faster than modular exponentiation) and far more secure. Time to encrypt/decrypt = O(N log N log log N) * (length of message) Time to brute-force = O(2^N) In pseudocode, we have: -------- p,q,r = N-bit long primes (N=1024 should suffice) distinct primes of the form 4k+3, derived from the key by a deterministic process. M = p*q Repeat{ XOR 32 bits of plaintext with (r mod 2^32) to produce 32 bits ciphertext Let r := r^2 mod M; Once the entire plaintext is processed, exit this loop. } -------- It's cryptographically secure, as even complete knowledge of the state of PRNG would not allow previous states to be computed, thanks to the difficulty of integer factorisation. It's also a very good PRNG, with no obvious patterns in its output. Hence, even if your nemesis has a crib and XORs it with the ciphertext to obtain some of the PRNG output, he/she will still have great difficulty extrapolating. Also, there's the convenience that the algorithm is symmetric for encryption and decryption. --Adam P. Goucher --WDS: elegant. Really, though, this is a PRNG (psu-random number generator) not a cryptosystem. I realize you can misuse it as a cryptosystem, but that sacrifices the usefulness of having an Encrypt(Message,Key) box which is a useful primitive for doing other stuff. Also with Goucher's system if you re-use the same key for a different message, you are dead (kind of like one-time pads only work once). Also, with Goucher's system the preprocessing time (to determine p,q from key) is rather large, maybe of order N^4, motivating people to choke by re-using old key for a new message. Also, by the way, I think to get theoretical nirvana with BlumBlumShub you must only use one bit of r at a time, not 32 bits (right?) costing a factor 32 work. The time consumption here seems to be with fast multiplication about N^2 * logN ops per plaintext bit which for N bit message and key would be N^3 * logN. (And slower if use slow multiplication.) The security level is around N^(1/3) considering NFS integer factoring algorithm. So... asymptotic-wise, this sucks, it is even worse than everything I said before! Elegance-wise, it is very neatly defined.