Después de analizar mi prueba creo que esto funciona correctamente:
Encriptar:
Código PHP:
int largo,posInicial,posFinal;
char Mensaje []="HOLA";
char Letras []="ABCDEFGHIJKLMNÑOPQRSTUVWXYZ";
int numero=5;
largo = strlen (Letras);
posInicial = strchr (Letras,Mensaje [i]);
posFinal = (largo + posInicial + numero) % largo;
Mensaje [i]=Letras [posFinal];
Desecriptar:
Código PHP:
int largo,posInicial,posFinal;
char Mensaje []="MTPF";
char Letras []="ABCDEFGHIJKLMNÑOPQRSTUVWXYZ";
int numero=5;
largo = strlen (Letras);
posInicial = strchr (Letras,Mensaje [i]);
posFinal = (largo + posInicial - numero) % largo;
Mensaje [i]=Letras [posFinal];
Largo da 27 mientras que el máximo de pos es 26. El fallo lo tenia porque a largo le quitaba 1.