Tengo una idea de que hay que eliminar las letras que más se repiten, pero no pasa de eso.
Alguna pista, un tipo de cifrado específico para investigarlo?

Si lo que quieres es aprender supongo que podremos decirte qué y donde buscar información.
Busca algo de historia de la criptografía e informate de los tipos de cifrado clasicos, que son los mas básicos

Por ejemplo, aqui tienes un PDF de la revista Sigma que te puede servir

TE DARE UNA AYUDA OK:

en la gloria del imperio romano este poseia multiples enemigos entonces CESAR para prevenir que sus enemigos leyeran sus cartas de tacticas con los generales este creo una especie de CIFRADO