Default size: If a library supports a key default size for RSA keys then this key size should be at least 2048 bits. This limit is based on the minimum recommendation of [NIST SP 800-57] part1 revision 4, Table 2, page 53. NIST recommends a minimal security strength of 112 bits for keys used until 2030. 112 bit security strength translates to a minimal key size of 2048 bits. Other organizations recommend somewhat different sizes: [Enisa], Section 3.6 also suggests that 2048-bit RSA keys provide a security strength of about 112 bits, but recommends a security strength of 128 bits for near term systems, hence 3072 bit RSA keys. [ECRYPT II], Section 13.3 suggests at least 2432 bits for new keys.
All the references above clearly state that keys smaller than 2048 bits should only be used in legacy cases. Therefore, it seems wrong to use a default key size smaller than 2048 bits. If a user really wants a small RSA key then such a choice should be made by explicitly providing the desired key length during the initalization of a key pair generator.
According to https://docs.oracle.com/javase/7/docs/api/javax/crypto/Cipher.html every implementation of the Java platform is required to implement RSA with both 1024 and 2048 bit key sizes. Hence a 2048 bit default should not lead to compatibility problems.
Cryptographically strong random numbers: So far the tests check that java.util.Random is not used. This needs to be extended.
Other bugs: The public exponent e should be larger than 1 [CVE-1999-1444]
PKCS #1 v1.5 padding is susceptible to adaptive chosen ciphertext attacks and hence should be avoided [B98]. The difficulty of exploiting protocols using PKCS #1 v1.5 encryption often depends on the amount of information leaked after decrypting corrupt ciphertexts. Implementations frequently leak information about the decrypted plaintext in form of error messages. The content of the error messages are extremely helpful to potential attackers. Bardou et al. [BFKLSST12] analyze the difficult of attacks based on different types of information leakage. Smart even describes an attack that only needs about 40 chosen ciphertexts [S10], though in this case the encryption did not use PKCS #1 padding.
Bugs
Tests To test whether an implementation leaks more information than necessary a test decrypts some random ciphertexts and catches the exceptions. If the exceptions are distinguishable then the test assumes that unnecessary information about the padding is leaked.
Due to the nature of unit tests not every attack can be detected this way. Some attacks require a large number of ciphertexts to be detected if random ciphertexts are used. For example Klima et al. [KPR03] describe an implementation flaw that could not be detected with our test.
Timing leakages because of differences in parsing the padding can leak information (e.g. CVE-2015-7827). Such differences are too small to be reliably detectable in unit tests.
Manger describes an chosen ciphertext attack against RSA in [M01]. There are implementations that were susceptible to Mangers attack, e.g. [CVE-2012-5081].
Potential problems:
Countermeasures: A good way to implement RSA signature verification is described in the standard PKCS#1 v.2.2 Section 8.2.2. This standard proposes to reconstruct the padding during verification and compare the padded hash to the value $$s^e \bmod n$$ obtained from applying a public key exponentiation to the signature s. Since this is a recurring bug it makes also a lot of sense to avoid small public exponents and prefer for example e=65537 .
List of broken implementations This is a large list.
[B98]: D. Bleichenbacher, “Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS# 1” Crypto 98
[M01]: J. Manger, “A chosen ciphertext attack on RSA optimal asymmetric encryption padding (OAEP) as standardized in PKCS# 1 v2.0”, Crypto 2001 This paper shows that OAEP is susceptible to a chosen ciphertext attack if error messages distinguish between different failure condidtions. [S10]: N. Smart, “Errors matter: Breaking RSA-based PIN encryption with thirty ciphertext validity queries” RSA conference, 2010 This paper shows that padding oracle attacks can be successful with even a small number of queries.
[KPR03]: V. Klima, O. Pokorny, and T. Rosa, “Attacking RSA-based Sessions in SSL/TLS” https://eprint.iacr.org/2003/052/
[BFKLSST12]: “Efficient padding oracle attacks on cryptographic hardware” R. Bardou, R. Focardi, Y. Kawamoto, L. Simionato, G. Steel, J.K. Tsay, Crypto 2012
[NIST SP 800-57]: http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf
[Enisa]: “Algorithms, key size and parameters report – 2014” https://www.enisa.europa.eu/publications/algorithms-key-size-and-parameters-report-2014
[ECRYPT II]: Yearly Report on Algorithms and Keysizes (2011-2012), http://www.ecrypt.eu.org/ecrypt2/documents/D.SPA.20.pdf
[CVE-1999-1444]: Alibaba 2.0 generated RSA key pairs with an exponent 1
[CVE-2012-5081]: Java JSSE provider leaked information through exceptions and timing. Both the PKCS #1 padding and the OAEP padding were broken: http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/MeyerChristopher/diss.pdf