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