what's your favorite algoritm to use? the cr.yp.to's NaCL library?
I think, that using algorithm made not in USA may be safer, or using not so popular rather than most popular like AES. With this idea using of NaCL/LibSodium may look as good choice (even if we know that DJB is US citizen; but he says there are no most side channels in his lib).
You can try candidates from AES round 2 (not only the Rijndael, but also
Serpent or Twofish), or something from japanese CRYPTREC or european NESSIE or ECRYPT/eSTREAM.
You may also use crypto made in Russia (sure, there will be no backdoor from NSA, but there can be backdoor from KGB):
And, as I already mentioned in comments, you can try to combine several crypto together trying to get more security against backdoors.
For symmetrical cipher you may setup this chain: firstly use Salsa20, then reencrypt data with XXTEA and then - by AES. You even can do similar thing to asymmetrical algorithms. For example when you should transmit short secret key to somebody using his public keys, you and he may use several public-key algos: NTRUEncrypt, some ECC-based RSA and prime field based RSA. How can you combine them? Generate some rather long random key (300 bytes or more), split it into 3 parts, send each part with some algo; then you and receiver can combine parts together, compact them using any hash-sum (HMAC, PBKDF2, or just SHA512 of all parts) and use part of this hash sum as master key to encipher you highly-valued alkaida plans.
Even if 1 or 2 algos from chain will be breaked by backdoor... Oh, wait...
You can't use any random number generator because you can't believe in them.. There are real plans for converting Intel Ivy's hardware good-designed hardware PRNG into flawed generator with 2*32 - 2*40 period - NSA can change just two masks to put trojan here:
In this paper we introduced a new type of sub-transistor level hardware Trojan
that only requires modication of the dopant masks. No additional transistors
or gates are added and no other layout mask needs to be modied. Since only
changes to the metal, polysilicion or active area can be reliably detected with
optical inspection, our dopant Trojans are immune to optical inspection, one of
the most important Trojan detection mechanism.
This trojan RNG is undetectable for Chipworks (cut the chip and look on transistors) and everybody from outside world. Intel uses HW PRNG to get raw data and then they encrypt data using some fixed AES key. You don't know the key from the Trojan, and EVERY test for PRNG (NIST and other) will be passed - because output of AES is tested. But Intel and NSA, who knows the key, will restore all random data generated from this PRNG in small number of operations.
.. So, you can't use single PRNG. Use several, both HW and SW (or even measure white noise with fast ADC) and then XOR them together. You may add encryption after XORing to get better random.
When you use several algorithms, and one or two are broken, you will have the third.