RSA-based Double Ratchet Algorithm

Question

I'm reading the Signal specification and they suggest to use EC keys, in particular with X25519 or X448 curves, both for the initial X3DH agreement and the DH ratchet.

I've noticed that languages and libraries seems to have a better support for RSA (for example the two curves recommended by Signal are not available using plain OpenJDK), so I was wondering if it could be possible to achieve the same level of security using RSA keys instead of EC keys (of course, supposing to use keys with proper sizes).

In the specification document they don't explain why EC should be used. I assume it improves performances, but I would like to know if it is a requirement in the context of the Double Ratchet Algorithm or if any good asymmetric cryptography system could be used.

Answer 1

The key ingredient in X3DH is essentially the DH key exchange. Which is a non interactive key exchange protocol where Alice and Bob independently send $g^a$ and $g^b$ and they can establish a shared key $g^{ab}$. But you can't build a non-interactive key exchange protocol using RSA (not that I'm aware of). To exchange a key using RSA, Alice needs to send Bob her public key then Bob encrypts a random key under Alice's public key. Note that we're still sending two messages but the second message can only be sent after the first is received (in the DH case the two messages can be sent simultaneously).

While it is possible to tweak the Signal protocol to use RSA KEMs instead of EC DH, this is not as simple as replacing the asymmetric encryption algorithm, you'd need to make changes on the protocol level and possibly do a new security analysis. See https://eprint.iacr.org/2019/1356 for an example, the original X3DH is Figure 2 and the KEM based one is in Figure 3.

One more reason to use ECDH is because it's much more efficient than RSA and uses much smaller keys.