Sua definição de "chaves rotativas" está correta. Você precisa descriptografar os dados com a chave "antiga" e criptografar novamente com a chave "nova". Há muitas lojas que fazem isso anualmente, e sim - é muito trabalho e melhor feito por um programa automatizado (provavelmente você pode escrever sua própria ferramenta - eu não tenho conhecimento de nenhum outro, mas eu tenho certeza de que eles existem).
< Rant >
A interpretação do requisito do PCI-DSS 2.0 3.6.4 "Alterações na chave criptográfica para chaves que atingiram o final do seu criptoperíodo (por exemplo, após um período de tempo definido ..." como "Você tem que girar as chaves anualmente ou o mundo terminará "é míope, e nas minhas / minhas opiniões de auditor incorreto: Se você estiver usando um algoritmo suficientemente strong (por exemplo, AES-256) e não tiver violações conhecidas de sua chave, girar suas chaves não fornecerá substancialmente melhor segurança - na verdade, cria uma nova exposição (a chave antiga precisa ser disponibilizada para um programa pelo tempo que for necessário para descriptografar / criptografar novamente seus dados - mesmo que a máquina que faz esse trabalho seja segura, ela ainda envolve colocar a chave em mais de um lugar).
Note que se você quiser fazer este argumento com sucesso, você precisa de duas coisas: Um auditor que tenha um entendimento básico de criptografia, e uma política defensável que voe em face de Publicação NIST 800-57 (especificamente a tabela" cryptoperiods recomendados "). Nossa política, por exemplo, exige AES-256 (que é livre de ataques práticos, e levaria uma eternidade à força bruta) e força uma rotação de chaves quando alguém com acesso direto às chaves é encerrado (funcionários do sysadmin chave, certos oficiais do nível C ).
< / Rant >