openssl / openssl/openssl

Review RSA operation with large modulus and/or large public exponents

Open
#6,130 16 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

triaged: refactor
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.

  1. If anybody knows, please explain why 16385 is too large for OpenSSL.

  2. 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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.