Assuming I have multiple symmetric keys on specific machine(more than 10000 probably), can I use the same rsa key to encrypt all of those keys? I'm a bit concerned from a situation where multiple encrypted keys will have similar pattern and will leak data about the original ones


You shouldn't be concerned if you use PKCS#1 v2 encryption padding - the OAEP.

OAEP, the Optimal Asymmetric Encryption Padding guarantees that even the slightest difference in raw plaintext (in your case, your symmetric keys) will result in huge difference in padded plaintext.

  • $\begingroup$ I thought PKCS and OAEP are different padding algorithms.Also, is OAEP secure enough(math wise) $\endgroup$
    – user83734
    Sep 23 '20 at 4:59
  • 2
    $\begingroup$ @user83734: PKCS (Public Key Cryptography Standards) is a collection of specifications that used to be at the website of RSA Security/Labs. It ended at EMC, and got lost in a website revamping. Some of it is now in RFCs. PKCS#1 specifies RSA keys, encryption and signature. As I just wrote, PKCS#1v2[.2] contains two RSA encryption paddings, named RSAES-OAEP (aka [RSA-]OAEP or PKCS[#]1[ ]v2[[.]1|2][ OAEP][ encryption][ padding]), and an old one named RSAES-PKCS1-v1_5 (aka PKCS[[#]1[[ ]v1[.[5]]]][ original|old][ encryption][ padding]). $\endgroup$
    – fgrieu
    Sep 23 '20 at 5:25
  • 2
    $\begingroup$ Although a padding parameter or option in software named 'pcks1' or just 'pkcs' usually was chosen before that name became ambiguous, i.e. before pkcs1v2, and not changed after, and thus refers to the old scheme (RSAES-PKCS1-v1_5). E.g. OpenSSL comandline rsautl -pkcs and Java 'transform' RSA/ECB/PKCS1Padding both dating to the early 1990s. $\endgroup$ Sep 24 '20 at 1:10

Yes. By any modern definition of a secure cipher, it can safely be used many times with the same key (the OTP can't safely reuse its pad/key, thus is not a proper cipher).

Leaving a lot of formalism aside, RSAES-OAEP of PKCS#1v2.2 is a secure asymmetric cipher, which security is proven (to some degree, under some hypothesis including perfect implementation) from the combination of:

  • The assumed security of the hash that it uses internally.
  • The assumed hardness of the RSA problem: for proper choice of key $(N,e,d)$, finding $m$ that was chosen at random in $[0,N)$ given $m^e\bmod N$.

There's a convoluted history to this result. Unless I missed a later development, the tightest proof is Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval and Jacques Stern's RSA-OAEP is Secure under the RSA Assumption, in Journal of Cryptology, 2004. Abstract:

Recently Victor Shoup noted that there is a gap in the widely believed security result of OAEP against adaptive chosen-ciphertext attacks. Moreover, he showed that, presumably, OAEP cannot be proven secure from the one-wayness of the underlying trapdoor permutation. This paper establishes another result on the security of OAEP. It proves that OAEP offers semantic security against adaptive chosen-ciphertext attacks, in the random oracle model, under the partial-domain one-wayness of the underlying permutation. Therefore, this uses a formally stronger assumption. Nevertheless, since partial-domain one-wayness of the RSA function is equivalent to its (full-domain) onewayness, it follows that the security of RSA-OAEP can actually be proven under the sole RSA assumption, although the reduction is not tight.


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.