2
$\begingroup$

I'm looking to design a protocol between two parties A and B to generate sequence of RSA private keys $p_{a_0}, p_{a_1}, ... p_{a_k}$ and a sequence of corresponding RSA public keys $P_{b_0}, P_{b_1} ... P_{b_k}$.

with the property that $P_{b_k}$ is the corresponding public key of private key $p_{a_k}$. But there is a twist:

$A,B$ will share an initial secret. After this point $A$ will generate its private keys ,and $B$ will generate JUST the public keys and $B$ should have NO way of knowing what $A's$ private keys are. So $B$ should be able to offline generate public keys without knowing what they're private keys are but the protocol should ensure that $A$ ends up with correspoing private keys to $B$'s public key sequence.

The use case is in an "eventually-compromised" system that is $A,B$ initially can share information freely but at some point their computers/networks become infected at which point they shut down and operate in a purely offline manner for a while. During this time I want them to be able to create documents/digitally sign/verify digital signatures of each other despite the inability to communicate and possibility of discovering that some of their keys have been compromised.

$\endgroup$
2
$\begingroup$

If RSA is not a requirement, here's a potential solution that uses ECC.

A generates a key-pair, $p_0, P_0$. A and B share a secret $s$ and the public key $P_0$. To move to the next key-pair, A multiplies the private key by $s$ and B multiplies the public key by $s$, so that the key-pair is $p_n = s^np_0, P_n = s^nP_0$ at step $n$.

$\endgroup$
1
$\begingroup$

The modulus (which is part of both the public and private key) directly depends on the two (or more) primes that make up the private key. So there is no way of doing what you say is required - at least not with RSA.

It makes more sense to generate a batch of keys and then share the public keys at the time that you are sharing the secret. After that you can update keys at the moment that there is a connection, possibly authenticated by the shared secret using a MAC.

$\endgroup$
2
  • $\begingroup$ And since the public key must of course depend on the private key I don't think it is even possible using any cryptosystem. If the private key depends on the shared secret then of course both parties can generate the private key; in that case you might as well use a MAC + ratchet. $\endgroup$ – Maarten Bodewes Jul 30 '20 at 10:06
  • $\begingroup$ And I was put in place by Aman in the answer above. So it is possible and even very doable, but not for RSA. $\endgroup$ – Maarten Bodewes Aug 7 '20 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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