Penso che la funzione CalcolaPotenza debba essere

codice:
char CalcolaPotenza( int N, int e, unsigned long long r )
{
	unsigned long long ris = 1;
	for ( ; e > 0; e-- )
		ris *=N ;

	ris %= r;

	return ris;
}
in quanto prima esegui l'elevamento a potenza e solo alla fine calcoli il modulo

E infatti per la cifratura funziona.

Ovviamente non va per la decifratura dato che il risultato dell'elevamento a potenza è eccessivo.