Now released the first version of the AVRCryptoLib for the GNU C compiler.
It contains DES Triple DES and RSA Encrypt and Decrypt for both Keys in Ram or Flash
Also AES, Skipjack, MD5 and SHA-1 Documentation and Source code is included and some test programs.
The interfacing to function is in C but all the main functions are in assembly language for speed and size

The DES will do a decryption in 8.3ms @16Mc Mega Core.
And 512^3 RSA in 69ms @16mc on a Mega core 512^512 in 26 sec.
For 512^3 RSA you will need 4 * Keysize of ram and for 512^512 you will need 5 the Keysize.

This is the table of all the cycles 

DES CyclesCode sizeRam needed
Encrypt1339661782 bytes122+24 bytes
Decrypt1341341780 bytes122+24 bytes
Combined2082 bytes122+24 bytes
Triple Des CyclesCode sizeRam needed
Encrypt4025681974 bytes122+32 bytes
Decrypt4026881974 bytes122+32 bytes
Combined2390 bytes122+32 bytes
RSA 64 bits Key in RamCyclesCode sizeRam needed
Encrypt1051026760 bytes5 * Keysize bytes
Decrypt22946690 bytes4 * Keysize bytes
Conbined1040 bytes5 * Keysize bytes
RSA 64 Key in FlashCyclesCode sizeRam needed
Encrypt1118827746 bytes4 * Keysize bytes
Decrypt24660692 bytes3 * Keysize bytes
Combined-1028 bytes4 * Keysize bytes
AES 128 SFCyclesCode sizeRam needed
Encrypt7622900 bytes768+16 bytes
Decrypt8279904 bytes768+16 bytes
Combined1302 bytes768+16 bytes
AES 128 SRCyclesCode sizeRam needed
Encrypt7762966 bytes256+16 bytes
Decrypt84111222 bytes256+16 bytes
Combined1620 bytes256+16 bytes
SkipJackCyclesCode sizeRam needed
Encrypt5777526 bytes18 bytes
Decrypt5727520 bytes18 bytes
Combined-790 bytes18 bytes
MD5CyclesCode sizeRam needed
Block 1KBytes3395011842 bytes113 bytes
SHA-1CyclesCode sizeRam needed
Block 1KBytes4898901640 bytes120 bytes