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

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.