I have a series of backup files which are being generated daily and which I need to store encrypted. The files are to be used by bob as and when they need it.

I am planning to use public key cryptography with private key being held by the bob. The backup program will have the public key and will encrypt the files with it, and bob will use the private key to decrypt it.

I need to rotate the encryption keys periodically. For new files this is not a problem as the backup program can start encryption with the new key and bob will have to use the new key to decrypt it.

But for old files, bob will have to keep track of the date and also all the old private keys to successfully decrypt a random file from the past.

Is there any secure protocol where when a new key pair is generated all old files are "converted" so that it can be decrypted using the new key alone and the old key can be safely destroyed.

  • $\begingroup$ There are two reasons for rotating the keys (1) Since this backups have life time of years and we need to protect against key compromise. (2) Policy, al keys and passwords have life times and needs to be rotated periodically. $\endgroup$
    – Xuo Guoto
    Aug 3 at 4:21

1 Answer 1


I'll assume this involves the standard construction of the file being some header + symmetric encrypted blob and we're talking about changing the asymmetric data in the header to change the private key required for decryption.

You're asking for a way to transform a file encrypted under some public key A to one encrypted under public key B. this means there is some function f_A2B(A_encrypted_file) --> B_encrypted file that does the conversion.

forward secrecy

Deleting the secret key a corresponding to PK A would normally prevent decryption of all files encrypted with A. f() breaks this property since a file encrypted to A can be run through f() then decrypted with b. Deleting the old key only provides forward secrecy if we also delete f() after converting any files we wish to carry forward. f() has properties similar to a private key although it cannot directly decrypt files

That's the forward secrecy property of what you're asking for. Old unconverted backups become innaccessible if the old keys are destroyed and they're not converted to use the new keys.

backwards secrecy

generating a new keypair B,b and using the public key B would normally prevent a compromised previous keypair A,a from mattering. This works just fine if and only if f() is one way only. If there's some way to invert f() to convert a file encrypted under a key B to key A or to reveal the relationship between secret keys a and b then someone who compromises a key a could decrypt files encrypted to later keys.

system requirements

Figure out which of these properties you need (forward secrecy, old unconverted files become innaccessible), (backwards secrecy, key compromises don't allow decryption after rekey+conversion)

My guess is you're looking for backwards secrecy. If you assume f() is public knowledge and make no attempts to protect it, then there's no forward secrecy since attackers can just convert in the forwards direction.

Useful Primitives


ECDH does allow doing such a conversion although f() is easily reversible. Suppose we have two key pairs A=aG, B=bG and wish to migrate a hypothetical file encrypted under A to B. During encryption, an ephemeral keypair E=eG was created and the key K=eA=(ea)G was used to encrypt the file and E was packaged along with it in the header. During decryption the holder of the a private key calculates K=aE=eaG to get back K.

A key linking multiplier c=a/b can be used to convert a file to use the new key B. The ephemeral public key is multiplied by this factor to get E'=cE. Now the receiver can calculate K=bE'=b(cE)=b(a/b)(e)G=eaG

This allows for converting between encryption keys but both in the forwards and backwards directions, $f^{-1}(·)$ is trivial to compute given $f(·)$. It also allows finding a from b or the other way around. They used to be two separate unknowns and we're supplying an equation, remove a degree of freedom from the system.

RSA with close moduli

RSA provides a trapdoor permutation between values in the range [1...N-1] where N is the product of two large prime numbers p and q. Keypairs can be generated so their modulus is very close to some value. As an example, it is possible to generate a modulus of the form 2^n+k where k is approximately n/2 bits by picking some random p then finding a prime q close to 2^n/p.

So while the domain of two keys will not be the same, it can be close and this is enough to allow values to be passed between various encrypt/decrypt functions more or less at will with only a negligible probability of an overflow. Overflow conditions will only ever be caused by attacker chosen values and so can be considered equivalent to a DOS attack in much the same way as an invalid ciphertext.

To turn this into a useful primitive, pick some security level ... say 4096 bits ... then choose some modulus target value (EG:2^4096) then choose kepairs with N close to that target. The resulting keypairs have encrypt and decrypt functions (eg:A(x), a(x), keeping with the capital/lowercase public/private key convention) These functions are inverses (IE:a(A(x))=x) though they are not commutative between keypairs (EG:A(B(x))≠B(A(x)))

Building a real system

It's difficult to make this work ideally with the above primitives. You'll likely need to do something more complicated than just deleting a key and generating a new one.

The ECDH primitive is ideal but because it reveals the relationship between keys, it allows for backwards as well as forwards movement along the key timeline when f() is public. It provides neither forward or reverse secrecy unless you protect f()

One reasonable choice is to assume there is no forward secrecy and all backups can be decrypted forever. Essentially f() is public.

The RSA primitive can be applied in this case. Just chain encryption operations as files get converted. a hypothetical file is encrypted with symmetric key K and we store x=A(K) in the header. this can be decrypted with a(). At some point in the future, that value is updated to x'=B(x) and now we'd need to do a(b(x'))=K to find k. This is nice because file size stays constant, there's a 512 byte 4096 bit RSA ciphertext along with a little metadata and that's it.

  • $\begingroup$ Thanks for the detailed answer explaining all the concepts. I need some time to understand and digest this! $\endgroup$
    – Xuo Guoto
    Aug 3 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.