How can I add bits of security? (e.g. RSA + ECC)

If we have an RSA layer of encryption over some text with n bits of security, then we use an elliptic curve, say with m bits of security, how can we calculate the total bits of security with RSA(ECC(...))? Do we multiply, add, or something else to caulcate the total bits of security?

• RSA has n bits of security,
• ECC has m bits of security,
• We are doing RSA(ECC(...)), how many bits of security does it have.

The answer to this really depends on taking a close look at what RSA(ECC(...)) means and thinking about what an attacker would need to do to break it.

Side note here: elliptic curves don't do encryption -- they do signatures and key exchange, so I'm not totally sure what RSA(ECC(...)) means -- so this is the first "it depends" that we'll run into.

If it means that first you encrypt with ECC, then you encrypt with RSA, then what would an attacker need to do to break it? Well, they start with the RSA ciphertext. If they cracked that (by doing 2n work), then they would have revealed the ECC ciphertext. If they cracked that (by doing 2m work), then they would reveal the plain text. They have done 2n + 2m total work.

If we're talking about key exchanges, then how does the combiner function work? Do they have to break only one of them at min(2n, 2m) work? Does the attacker have enough information to crack each independently at 2n + 2m work? Or are they combined in such a way that you really need to attack them both together, in which case it would be 2n * 2m = 2n+m work?

If we're talking about signatures, then RSA(ECC(...)) doesn't make sense, and instead you have something more like RSA(...), ECC(...). Does the security of the protocol require them to break only one of them at min(2n, 2m) work? Or both of them independently at 2n + 2m work?

TL;DR: The answer, unfortunately, is a big fat "it depends" based on the details of how RSA(ECC(...)) works.

• Apart from that it is not clear what "X bits of security" really mean. If the OP is just talking about key length then he needs to understand that RSA with key length N does not provide the same security by far as ECC with key length N. Oct 4 '19 at 7:00
• Yes, good point. I was assuming that the question means "n bits of security" as in "An RSA 2048 key has 52 bits of security against a quantum adversary", or whatever the numbers work out to these days. Oct 4 '19 at 13:23