2
$\begingroup$

For RSA or elliptic cryptography, can we use the same public/private keys for several exchanges, or is that unsafe? Does it lower the security of the protocol?

To me it doesn't matter, as receiving multiple encrypted messages does not give more information about the factorisation of the public key. Am I correct?

$\endgroup$
1
  • 1
    $\begingroup$ in theory, it is totally safe. in practice, we are using keys in corporate applications that have lifespan of less than 27 months. $\endgroup$
    – sefiks
    Commented Mar 6 at 10:18

1 Answer 1

5
$\begingroup$

Receiving multiple (RSA) encrypted message does not give more information about the factorization of the public key.

Indeed. If the outcome and internals of decryption remain secret, there's a strong argument: anyone can encipher, thus if more encrypted messages significantly helped towards factorization, that would yield a factorization method. And even if the messages are chosen by an adversary and the corresponding plaintext revealed by the holder of the private key, it's widely believed that still stands (a proof remains an open problem).

But that's not a valid justification that we can use the key indefinitely: there are ways the security of RSA (encryption or signature) can be jeopardized other than by a leak of the private key.

An example with RSAES-PKCS1-v1.5: assume a 2048-bit public modulus, and messages of 243 bytes either YYY…YYY orNNN…NNN (say a vote). The random padding is 80 bits, the effort to decipher an intercepted ciphertext is an expected $2^{80}$ trial encryptions and that's arguably reasonably secure. But if that is used to cast a large number $n$ of votes the expected effort to decipher $k\ll n$ votes is $2^{80}k/n$ trial encryptions and searches in the ciphertexts, decreasing with $n$. However that weakness really is with the padding, and in RSA we have others (e.g. RSAES-OAEP) which yield security reducible to the RSA problem (not extraction of private key).

Another reason to limit key usage is side channels: the more measurements (of power consumption over time, electromagnetic emissions…) an adversary can make with a device holding a private key (like a Smart Card), the higher the risk that this key can be extracted.

That said, in RSA, with provably secure padding and side channels left aside, it seems we can use a key practically indefinitely for both encryption and signature.

In well-designed uses of ECC, as far as I know, that also stands for practical purposes (even though in signature, if we let adversaries sign at will, the quantitative security proofs we have fade).

That can't be generalized to all asymmetric cryptosystems. In some schemes, security drops badly past some number of uses. E.g. in Lamport signature, we can sign a single time, a severe limitation. And in variations, the number of signatures is strictly limited.

$\endgroup$
1
  • $\begingroup$ thank you very much for this detailed answer, I'm very sorry to reply this late. So it is true in theory, but in practice the key must be changed on a regular basis due to implementation/hardware reasons which can lower the security $\endgroup$
    – Wheatley
    Commented Mar 10 at 21:14

Your Answer

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

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