Review RSA operation with large modulus and/or large public exponents
Nobody has claimed this yet.
- Dominant language
- C
- Stars
- 30.8k
- Forks
- 11.5k
- Avg merge
- 10m
- Merged PRs (30d)
- 1
Description
Prepare two RSA keys by the following commands (keep calm for the second):
openssl genpkey -algorithm rsa -pkeyopt rsa_keygen_bits:4096 -pkeyopt rsa_keygen_pubexp:0x010000000000000001 -out rsa04096.key
openssl genpkey -algorithm rsa -pkeyopt rsa_keygen_bits:17000 -pkeyopt rsa_keygen_pubexp:0x1000000000000001 -out rsa17000.key
Then try to use these keys for encryption and signing. Remember that for encryption you use the public exponent, and for signing the private.
openssl rsautl -encrypt -in test.txt -out test.enc -inkey rsa04096.key
openssl rsautl -sign -in test.txt -out test.sig -inkey rsa04096.key
openssl rsautl -encrypt -in test.txt -out test.enc -inkey rsa17000.key
openssl rsautl -sign -in test.txt -out test.sig -inkey rsa17000.key
Signing passes, encryption not. With 4096 key due to "bad e value", and the 17000 key modulus is too large. OK, encryption failed. Try to verify the signature file test.sig:
openssl rsautl -verify -in test.sig -out test.ver -inkey rsa04096.key
openssl rsautl -verify -in test.sig -out test.ver -inkey rsa17000.key
Both fail, again because of "bad e value" and "modulus too large".
Strange, isn't it?
Explanation:
The public (not the private) key operations are restricted in include/openssl/rsa.h by
define OPENSSL_RSA_MAX_MODULUS_BITS 16384
define OPENSSL_RSA_SMALL_MODULUS_BITS 3072
/* exponent limit enforced for "large" modulus only */
define OPENSSL_RSA_MAX_PUBEXP_BITS 64
Therefore signing with an indeed large modulus is fine, encryption not. If the modulus length is greater the 3072, then additional the bit length of the exponent is restricted.
-
If anybody knows, please explain why 16385 is too large for OpenSSL.
-
For the public exponent there are some reasons to restrict the bit length. A small length of the public key ensures a large length of the private exponent. Small private exponents are risky. Therefore if you see a small public exponent, you can be sure that the corresponding private exponent is large enough.
Usually (NIST did it since FIPS 186-3) the bit length of the public exponent should be less than 256 (for modulus length not smaller 2048). For a smaller modulus length I guess, it should be less than 64.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Reproduce the reported behavior with the four openssl rsautl commands and the two generated keys, then inspect the public-operation limits in include/openssl/rsa.h. Determine whether the differing signing, encryption, and verification results are intentional; done means the restriction is resolved or clearly documented and the large-modulus cases are covered by tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- cryptography, security
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100