Mixing
What is the minimum and maximum value of an RSA private exponent?
Clash Royale CLAN TAG#URR8PPP
up vote
10
down vote
favorite
Is it possible to calculate the minimum and maximum value of the private exponent for an RSA key, for example for a 1024 key size? In other words, what is the range of values in which the private exponent can occur?
rsa key-size
edited Aug 9 at 6:32
Maarten Bodewes
47.5k566174
asked Aug 8 at 22:01
Rohit
513
add a comment |Â
up vote
10
down vote
favorite
Is it possible to calculate the minimum and maximum value of the private exponent for an RSA key, for example for a 1024 key size? In other words, what is the range of values in which the private exponent can occur?
rsa key-size
edited Aug 9 at 6:32
Maarten Bodewes
47.5k566174
asked Aug 8 at 22:01
Rohit
513
I quite heavily edited the question, please check if it is still OK. I changed the question from size to values, as RSA works on numbers. From the minimum and maximum value it is of course easy to determine the possible sizes that an RSA private exponent can take on (just take the $log_2$ of the value).
– Maarten Bodewes
Aug 9 at 6:34
add a comment |Â
up vote
10
down vote
favorite
up vote
10
down vote
favorite
Is it possible to calculate the minimum and maximum value of the private exponent for an RSA key, for example for a 1024 key size? In other words, what is the range of values in which the private exponent can occur?
rsa key-size
edited Aug 9 at 6:32
Maarten Bodewes
47.5k566174
asked Aug 8 at 22:01
Rohit
513
Is it possible to calculate the minimum and maximum value of the private exponent for an RSA key, for example for a 1024 key size? In other words, what is the range of values in which the private exponent can occur?
rsa key-size
edited Aug 9 at 6:32
Maarten Bodewes
47.5k566174
asked Aug 8 at 22:01
Rohit
513
edited Aug 9 at 6:32
Maarten Bodewes
47.5k566174
edited Aug 9 at 6:32
Maarten Bodewes
47.5k566174
edited Aug 9 at 6:32
Maarten Bodewes
47.5k566174
47.5k566174
asked Aug 8 at 22:01
Rohit
513
asked Aug 8 at 22:01
Rohit
513
asked Aug 8 at 22:01
Rohit
513
513
I quite heavily edited the question, please check if it is still OK. I changed the question from size to values, as RSA works on numbers. From the minimum and maximum value it is of course easy to determine the possible sizes that an RSA private exponent can take on (just take the $log_2$ of the value).
– Maarten Bodewes
Aug 9 at 6:34
add a comment |Â
I quite heavily edited the question, please check if it is still OK. I changed the question from size to values, as RSA works on numbers. From the minimum and maximum value it is of course easy to determine the possible sizes that an RSA private exponent can take on (just take the $log_2$ of the value).
– Maarten Bodewes
Aug 9 at 6:34
I quite heavily edited the question, please check if it is still OK. I changed the question from size to values, as RSA works on numbers. From the minimum and maximum value it is of course easy to determine the possible sizes that an RSA private exponent can take on (just take the $log_2$ of the value).
– Maarten Bodewes
Aug 9 at 6:34
I quite heavily edited the question, please check if it is still OK. I changed the question from size to values, as RSA works on numbers. From the minimum and maximum value it is of course easy to determine the possible sizes that an RSA private exponent can take on (just take the $log_2$ of the value).
– Maarten Bodewes
Aug 9 at 6:34
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
21
down vote
In summary:
- Modern practice is to fix a small public exponent $e$ such as $e=2^(2^4)+1=65537$, then choose a public modulus $N$ of $textnlen$ bits (the key size) with large random prime factors compatible with $e$, then compute the RSA private exponent $d$ from that. With near certainty, that $d$ will be at least $textnlen/2$-bit. That can be used as a minimum for other methods. For RSA1024, that's $d$ at least 512-bit.
- If given a choice, compute $d=e^-1bmodlambda(N)$, and it's bit size will be strictly lower than the key size. For RSA1024, that's $d$ at most 1023-bit. See Carmichael function for the definition of $lambda(N)$.
- Otherwise, it is still recommendable to keep $d<N$ for compatibility with common software. For RSA1024, that implies $d$ at most 1024-bit.
Note: by the mathematical definition, a positive integer $m$ is $b$-bit when $2^b-1le m<2^b$. Computer implementations often measure the size of integers differently: adding one for sign, or/and rounding up to the next multiple of some power of two, or/and adding more overhead for headers.
Caveat: RSA1024 might be vulnerable right now to well-funded and competent adversaries. For new applications, it has been deprecated for a decade at least, and RSA2048 is considered OK only till 2020 or 2030, depending on source (see the Keylength website).
Minimum value
Negative $d$ work, but at the price of an extra inversion modulo $N$ at each use, thus have little practical interest. We exclude negative $d$ in the following.
When $e$ is fixed or chosen then $d$ computed (as is modern practice), the lower bound for $d$ is commonly $d>2^textnlen/2$ (e.g. in FIPSÂ 186-4), or $d>0$, or just unspecified. In fact, $d$ will typically be few (if any) bit(s) less than $textnlen$, and $d<2^textnlen-64$ should seldom occur. $d>2^textnlen/2$ is met with overwhelming probability for any sound key generation procedure that computes $d$ without attempt to minimize it, or in other words where:
- $d$ is computed from the public exponent $e$ and the prime factors of the public modulus $N$ (these factors are noted $p$ and $q$ is the common case of $N=p,q$; or more generally $r_i$, with $N=prod r_i$, and $p=r_1$, $q=r_2$ ).
- and $e$ and the $r_i$ are chosen independently of each others, except for meeting the requirements: the $r_i$ are suitably large random primes, $gcd((r_i-1),e)=1$ (implying $e$ odd), and $ege3$.
Exceptions to the above:- Sometime it is additionally checked that the $r_i$ are suitably different from each others. For safely large $r_i$ and good random generator, such check never fails.
- From a mathematical standpoint, $e$ can safely be chosen as $N$, in which case it depends on the $r_i$. That is the case in Christopher Cocks's 1973 cryptosystem, see here for bibliography.
In any case, $d$ must be much larger than $N^0.292$ in order to avoid an attack by Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^0.292$, in proceedings of Eurocrypt 1999. A safer lower bound is $d>sqrt N$, or the aforementioned $d>2^textnlen/2$. That consideration is relevant at least when $d$ is chosen, as in in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem (in CACM, 1978).
Maximum value
The upper bound for $d$ depends on context.
- From a mathematical standpoint, there is no limit: any $d$ with $lambda(N)$ dividing $e,d-1$ is acceptable, where (for distinct $r_i$ ) $lambda(N)$ is computed as the Least Common Multiple of the $(r_i-1)$. We can add any multiple of $lambda(N)$ to any valid $d$, and obtain another valid $d$.
- In a PKCS#1 context, we must additionally have $0<d<N$, which implies $d<2^textnlen$. That leaves at least two possible $d$, sometime more.
- Some definitions of RSA state that $d=e^-1bmodvarphi(N)$, where (for distinct $r_i$ ) $varphi(N)=prod(r_i-1)$, see Euler's totient. This implies $d<varphi(N)$, which implies $d<N$ and $d<2^textnlen$. For usual RSA with two factors, that method of computing $d$ implies $d<N-2sqrt N$, thus the upper bound is slightly lower than $d<N$ in PKCS#1.
- In a FIPSÂ 186-4 context, it is required that $d=e^-1bmodlambda(n)$. That is the smallest positive $d$, and it is often markedly lower than with the previous method. We get $d<lambda(N)$, thus $d<varphi(N)/2$, thus $d<2^textnlen-1$, and for two factors $d<N/2-sqrt N$.
answered Aug 8 at 23:03
fgrieu
72k6149308
add a comment |Â
up vote
8
down vote
Modern cryptography generally chooses a static public exponent. Nowadays this is almost universally the fifth prime of Fermat or F4, 65537 or 010001 in hexadecimals. From this the private key is calculated given the two prime numbers that are half the size of the key size.
The calculation that is performed can be seen in the answer to Calculating RSA private exponent. It is important to notice that the calculation returns a private exponent in the range $[0, N)$. Testing has shown that this value is well distributed within this range.
So the maximum value is simply $N - 1$, and this means that the private exponent can be as large as the key size. The minimum size is harder to establish, but please note that the chance that it is very small isn't all that high; the chance that it is 64 bits smaller than the key size is about $1/2^63.5$ (the precise chance depends on the value of the modulus). So even if the minimum value is 0, such a small size will never be generated.
This does however mean that:
- About once in 192 times that the private exponent is full byte smaller in size than the modulus.
- About once in 192 * 256 times the private exponent is two full bytes smaller in size than the modulus.
- ... and so on ...
Notes:
The private exponent is commonly encoded as a signed big endian number (an ASN.1 INTEGER) which means that the size also differs because of left padding with a zero byte to avoid negative values. This answer doesn't go into ASN.1 overhead or Chinese Remainder Theorem (CRT) parameters.
If you manage to generate a $d$ that is 128 bits smaller than the key size then you might as well restart key generation. You may need to log such an unlikely event. The chance that something is wrong is much larger than the chance that such a small private exponent gets calculated.
A smaller private exponent does not mean that the private key is less secure. That is, unless the size is much smaller and / or the size of the private exponent is caused by miscalculation.
The modulus $N$ is in between $2^l-1$ and $2^l$ where $l$ is the key size. The maximum size of the modulus does of course influence the maximum value of the private exponent $d$. If the modulus is close to $2^l-1$ then the chance that the private exponent is almost always one bit smaller than the modulus. If the modulus is close to $2^l$ then the chance of this is about 0.5 (50%).
answered Aug 9 at 7:27
Maarten Bodewes
47.5k566174
1
The excellent answer of fgrieu deserves a less theoretical counterpart, in my opinion :)
– Maarten Bodewes
Aug 9 at 7:28
1
"Testing has shown that $d$ is well distributed within this range $[0,N)$" applies when computing $d=e^-1bmodvarphi(N)$. However FIPS 186-4 requires, and PKCS#1 allows, to compute $d=e^-1bmodlambda(N)$, and then $d$ never hits the upper half of the interval, and is further very observably biased towards low values in $[0,N/2)$. It happens with e.g. BouncyCastle 6, at that spot in the code, and many things targeting FIPS186-4 certification, I guess.
– fgrieu
Aug 9 at 18:51
Interesting, I'll do some more testing, I didn't t that behavior before but it has been some time that I tested this the last time. Note that this only is a single bit difference with the given answer though.
– Maarten Bodewes
Aug 9 at 19:58
@fgrieu I can see it happening with Bouncy indeed. I tested Java which doesn't seem to do this, but that's for an old version of Java, Java 1.8.0_171 to be precise... I'll test Java 10 later on.
– Maarten Bodewes
Aug 11 at 20:49
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
21
down vote
In summary:
- Modern practice is to fix a small public exponent $e$ such as $e=2^(2^4)+1=65537$, then choose a public modulus $N$ of $textnlen$ bits (the key size) with large random prime factors compatible with $e$, then compute the RSA private exponent $d$ from that. With near certainty, that $d$ will be at least $textnlen/2$-bit. That can be used as a minimum for other methods. For RSA1024, that's $d$ at least 512-bit.
- If given a choice, compute $d=e^-1bmodlambda(N)$, and it's bit size will be strictly lower than the key size. For RSA1024, that's $d$ at most 1023-bit. See Carmichael function for the definition of $lambda(N)$.
- Otherwise, it is still recommendable to keep $d<N$ for compatibility with common software. For RSA1024, that implies $d$ at most 1024-bit.
Note: by the mathematical definition, a positive integer $m$ is $b$-bit when $2^b-1le m<2^b$. Computer implementations often measure the size of integers differently: adding one for sign, or/and rounding up to the next multiple of some power of two, or/and adding more overhead for headers.
Caveat: RSA1024 might be vulnerable right now to well-funded and competent adversaries. For new applications, it has been deprecated for a decade at least, and RSA2048 is considered OK only till 2020 or 2030, depending on source (see the Keylength website).
Minimum value
Negative $d$ work, but at the price of an extra inversion modulo $N$ at each use, thus have little practical interest. We exclude negative $d$ in the following.
When $e$ is fixed or chosen then $d$ computed (as is modern practice), the lower bound for $d$ is commonly $d>2^textnlen/2$ (e.g. in FIPSÂ 186-4), or $d>0$, or just unspecified. In fact, $d$ will typically be few (if any) bit(s) less than $textnlen$, and $d<2^textnlen-64$ should seldom occur. $d>2^textnlen/2$ is met with overwhelming probability for any sound key generation procedure that computes $d$ without attempt to minimize it, or in other words where:
- $d$ is computed from the public exponent $e$ and the prime factors of the public modulus $N$ (these factors are noted $p$ and $q$ is the common case of $N=p,q$; or more generally $r_i$, with $N=prod r_i$, and $p=r_1$, $q=r_2$ ).
- and $e$ and the $r_i$ are chosen independently of each others, except for meeting the requirements: the $r_i$ are suitably large random primes, $gcd((r_i-1),e)=1$ (implying $e$ odd), and $ege3$.
Exceptions to the above:- Sometime it is additionally checked that the $r_i$ are suitably different from each others. For safely large $r_i$ and good random generator, such check never fails.
- From a mathematical standpoint, $e$ can safely be chosen as $N$, in which case it depends on the $r_i$. That is the case in Christopher Cocks's 1973 cryptosystem, see here for bibliography.
In any case, $d$ must be much larger than $N^0.292$ in order to avoid an attack by Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^0.292$, in proceedings of Eurocrypt 1999. A safer lower bound is $d>sqrt N$, or the aforementioned $d>2^textnlen/2$. That consideration is relevant at least when $d$ is chosen, as in in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem (in CACM, 1978).
Maximum value
The upper bound for $d$ depends on context.
- From a mathematical standpoint, there is no limit: any $d$ with $lambda(N)$ dividing $e,d-1$ is acceptable, where (for distinct $r_i$ ) $lambda(N)$ is computed as the Least Common Multiple of the $(r_i-1)$. We can add any multiple of $lambda(N)$ to any valid $d$, and obtain another valid $d$.
- In a PKCS#1 context, we must additionally have $0<d<N$, which implies $d<2^textnlen$. That leaves at least two possible $d$, sometime more.
- Some definitions of RSA state that $d=e^-1bmodvarphi(N)$, where (for distinct $r_i$ ) $varphi(N)=prod(r_i-1)$, see Euler's totient. This implies $d<varphi(N)$, which implies $d<N$ and $d<2^textnlen$. For usual RSA with two factors, that method of computing $d$ implies $d<N-2sqrt N$, thus the upper bound is slightly lower than $d<N$ in PKCS#1.
- In a FIPSÂ 186-4 context, it is required that $d=e^-1bmodlambda(n)$. That is the smallest positive $d$, and it is often markedly lower than with the previous method. We get $d<lambda(N)$, thus $d<varphi(N)/2$, thus $d<2^textnlen-1$, and for two factors $d<N/2-sqrt N$.
answered Aug 8 at 23:03
fgrieu
72k6149308
add a comment |Â
up vote
21
down vote
In summary:
- Modern practice is to fix a small public exponent $e$ such as $e=2^(2^4)+1=65537$, then choose a public modulus $N$ of $textnlen$ bits (the key size) with large random prime factors compatible with $e$, then compute the RSA private exponent $d$ from that. With near certainty, that $d$ will be at least $textnlen/2$-bit. That can be used as a minimum for other methods. For RSA1024, that's $d$ at least 512-bit.
- If given a choice, compute $d=e^-1bmodlambda(N)$, and it's bit size will be strictly lower than the key size. For RSA1024, that's $d$ at most 1023-bit. See Carmichael function for the definition of $lambda(N)$.
- Otherwise, it is still recommendable to keep $d<N$ for compatibility with common software. For RSA1024, that implies $d$ at most 1024-bit.
Note: by the mathematical definition, a positive integer $m$ is $b$-bit when $2^b-1le m<2^b$. Computer implementations often measure the size of integers differently: adding one for sign, or/and rounding up to the next multiple of some power of two, or/and adding more overhead for headers.
Caveat: RSA1024 might be vulnerable right now to well-funded and competent adversaries. For new applications, it has been deprecated for a decade at least, and RSA2048 is considered OK only till 2020 or 2030, depending on source (see the Keylength website).
Minimum value
Negative $d$ work, but at the price of an extra inversion modulo $N$ at each use, thus have little practical interest. We exclude negative $d$ in the following.
When $e$ is fixed or chosen then $d$ computed (as is modern practice), the lower bound for $d$ is commonly $d>2^textnlen/2$ (e.g. in FIPSÂ 186-4), or $d>0$, or just unspecified. In fact, $d$ will typically be few (if any) bit(s) less than $textnlen$, and $d<2^textnlen-64$ should seldom occur. $d>2^textnlen/2$ is met with overwhelming probability for any sound key generation procedure that computes $d$ without attempt to minimize it, or in other words where:
- $d$ is computed from the public exponent $e$ and the prime factors of the public modulus $N$ (these factors are noted $p$ and $q$ is the common case of $N=p,q$; or more generally $r_i$, with $N=prod r_i$, and $p=r_1$, $q=r_2$ ).
- and $e$ and the $r_i$ are chosen independently of each others, except for meeting the requirements: the $r_i$ are suitably large random primes, $gcd((r_i-1),e)=1$ (implying $e$ odd), and $ege3$.
Exceptions to the above:- Sometime it is additionally checked that the $r_i$ are suitably different from each others. For safely large $r_i$ and good random generator, such check never fails.
- From a mathematical standpoint, $e$ can safely be chosen as $N$, in which case it depends on the $r_i$. That is the case in Christopher Cocks's 1973 cryptosystem, see here for bibliography.
In any case, $d$ must be much larger than $N^0.292$ in order to avoid an attack by Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^0.292$, in proceedings of Eurocrypt 1999. A safer lower bound is $d>sqrt N$, or the aforementioned $d>2^textnlen/2$. That consideration is relevant at least when $d$ is chosen, as in in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem (in CACM, 1978).
Maximum value
The upper bound for $d$ depends on context.
- From a mathematical standpoint, there is no limit: any $d$ with $lambda(N)$ dividing $e,d-1$ is acceptable, where (for distinct $r_i$ ) $lambda(N)$ is computed as the Least Common Multiple of the $(r_i-1)$. We can add any multiple of $lambda(N)$ to any valid $d$, and obtain another valid $d$.
- In a PKCS#1 context, we must additionally have $0<d<N$, which implies $d<2^textnlen$. That leaves at least two possible $d$, sometime more.
- Some definitions of RSA state that $d=e^-1bmodvarphi(N)$, where (for distinct $r_i$ ) $varphi(N)=prod(r_i-1)$, see Euler's totient. This implies $d<varphi(N)$, which implies $d<N$ and $d<2^textnlen$. For usual RSA with two factors, that method of computing $d$ implies $d<N-2sqrt N$, thus the upper bound is slightly lower than $d<N$ in PKCS#1.
- In a FIPSÂ 186-4 context, it is required that $d=e^-1bmodlambda(n)$. That is the smallest positive $d$, and it is often markedly lower than with the previous method. We get $d<lambda(N)$, thus $d<varphi(N)/2$, thus $d<2^textnlen-1$, and for two factors $d<N/2-sqrt N$.
answered Aug 8 at 23:03
fgrieu
72k6149308
add a comment |Â
up vote
21
down vote
up vote
21
down vote
In summary:
- Modern practice is to fix a small public exponent $e$ such as $e=2^(2^4)+1=65537$, then choose a public modulus $N$ of $textnlen$ bits (the key size) with large random prime factors compatible with $e$, then compute the RSA private exponent $d$ from that. With near certainty, that $d$ will be at least $textnlen/2$-bit. That can be used as a minimum for other methods. For RSA1024, that's $d$ at least 512-bit.
- If given a choice, compute $d=e^-1bmodlambda(N)$, and it's bit size will be strictly lower than the key size. For RSA1024, that's $d$ at most 1023-bit. See Carmichael function for the definition of $lambda(N)$.
- Otherwise, it is still recommendable to keep $d<N$ for compatibility with common software. For RSA1024, that implies $d$ at most 1024-bit.
Note: by the mathematical definition, a positive integer $m$ is $b$-bit when $2^b-1le m<2^b$. Computer implementations often measure the size of integers differently: adding one for sign, or/and rounding up to the next multiple of some power of two, or/and adding more overhead for headers.
Caveat: RSA1024 might be vulnerable right now to well-funded and competent adversaries. For new applications, it has been deprecated for a decade at least, and RSA2048 is considered OK only till 2020 or 2030, depending on source (see the Keylength website).
Minimum value
Negative $d$ work, but at the price of an extra inversion modulo $N$ at each use, thus have little practical interest. We exclude negative $d$ in the following.
When $e$ is fixed or chosen then $d$ computed (as is modern practice), the lower bound for $d$ is commonly $d>2^textnlen/2$ (e.g. in FIPSÂ 186-4), or $d>0$, or just unspecified. In fact, $d$ will typically be few (if any) bit(s) less than $textnlen$, and $d<2^textnlen-64$ should seldom occur. $d>2^textnlen/2$ is met with overwhelming probability for any sound key generation procedure that computes $d$ without attempt to minimize it, or in other words where:
- $d$ is computed from the public exponent $e$ and the prime factors of the public modulus $N$ (these factors are noted $p$ and $q$ is the common case of $N=p,q$; or more generally $r_i$, with $N=prod r_i$, and $p=r_1$, $q=r_2$ ).
- and $e$ and the $r_i$ are chosen independently of each others, except for meeting the requirements: the $r_i$ are suitably large random primes, $gcd((r_i-1),e)=1$ (implying $e$ odd), and $ege3$.
Exceptions to the above:- Sometime it is additionally checked that the $r_i$ are suitably different from each others. For safely large $r_i$ and good random generator, such check never fails.
- From a mathematical standpoint, $e$ can safely be chosen as $N$, in which case it depends on the $r_i$. That is the case in Christopher Cocks's 1973 cryptosystem, see here for bibliography.
In any case, $d$ must be much larger than $N^0.292$ in order to avoid an attack by Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^0.292$, in proceedings of Eurocrypt 1999. A safer lower bound is $d>sqrt N$, or the aforementioned $d>2^textnlen/2$. That consideration is relevant at least when $d$ is chosen, as in in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem (in CACM, 1978).
Maximum value
The upper bound for $d$ depends on context.
- From a mathematical standpoint, there is no limit: any $d$ with $lambda(N)$ dividing $e,d-1$ is acceptable, where (for distinct $r_i$ ) $lambda(N)$ is computed as the Least Common Multiple of the $(r_i-1)$. We can add any multiple of $lambda(N)$ to any valid $d$, and obtain another valid $d$.
- In a PKCS#1 context, we must additionally have $0<d<N$, which implies $d<2^textnlen$. That leaves at least two possible $d$, sometime more.
- Some definitions of RSA state that $d=e^-1bmodvarphi(N)$, where (for distinct $r_i$ ) $varphi(N)=prod(r_i-1)$, see Euler's totient. This implies $d<varphi(N)$, which implies $d<N$ and $d<2^textnlen$. For usual RSA with two factors, that method of computing $d$ implies $d<N-2sqrt N$, thus the upper bound is slightly lower than $d<N$ in PKCS#1.
- In a FIPSÂ 186-4 context, it is required that $d=e^-1bmodlambda(n)$. That is the smallest positive $d$, and it is often markedly lower than with the previous method. We get $d<lambda(N)$, thus $d<varphi(N)/2$, thus $d<2^textnlen-1$, and for two factors $d<N/2-sqrt N$.
answered Aug 8 at 23:03
fgrieu
72k6149308
In summary:
- Modern practice is to fix a small public exponent $e$ such as $e=2^(2^4)+1=65537$, then choose a public modulus $N$ of $textnlen$ bits (the key size) with large random prime factors compatible with $e$, then compute the RSA private exponent $d$ from that. With near certainty, that $d$ will be at least $textnlen/2$-bit. That can be used as a minimum for other methods. For RSA1024, that's $d$ at least 512-bit.
- If given a choice, compute $d=e^-1bmodlambda(N)$, and it's bit size will be strictly lower than the key size. For RSA1024, that's $d$ at most 1023-bit. See Carmichael function for the definition of $lambda(N)$.
- Otherwise, it is still recommendable to keep $d<N$ for compatibility with common software. For RSA1024, that implies $d$ at most 1024-bit.
Note: by the mathematical definition, a positive integer $m$ is $b$-bit when $2^b-1le m<2^b$. Computer implementations often measure the size of integers differently: adding one for sign, or/and rounding up to the next multiple of some power of two, or/and adding more overhead for headers.
Caveat: RSA1024 might be vulnerable right now to well-funded and competent adversaries. For new applications, it has been deprecated for a decade at least, and RSA2048 is considered OK only till 2020 or 2030, depending on source (see the Keylength website).
Minimum value
Negative $d$ work, but at the price of an extra inversion modulo $N$ at each use, thus have little practical interest. We exclude negative $d$ in the following.
When $e$ is fixed or chosen then $d$ computed (as is modern practice), the lower bound for $d$ is commonly $d>2^textnlen/2$ (e.g. in FIPSÂ 186-4), or $d>0$, or just unspecified. In fact, $d$ will typically be few (if any) bit(s) less than $textnlen$, and $d<2^textnlen-64$ should seldom occur. $d>2^textnlen/2$ is met with overwhelming probability for any sound key generation procedure that computes $d$ without attempt to minimize it, or in other words where:
- $d$ is computed from the public exponent $e$ and the prime factors of the public modulus $N$ (these factors are noted $p$ and $q$ is the common case of $N=p,q$; or more generally $r_i$, with $N=prod r_i$, and $p=r_1$, $q=r_2$ ).
- and $e$ and the $r_i$ are chosen independently of each others, except for meeting the requirements: the $r_i$ are suitably large random primes, $gcd((r_i-1),e)=1$ (implying $e$ odd), and $ege3$.
Exceptions to the above:- Sometime it is additionally checked that the $r_i$ are suitably different from each others. For safely large $r_i$ and good random generator, such check never fails.
- From a mathematical standpoint, $e$ can safely be chosen as $N$, in which case it depends on the $r_i$. That is the case in Christopher Cocks's 1973 cryptosystem, see here for bibliography.
In any case, $d$ must be much larger than $N^0.292$ in order to avoid an attack by Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^0.292$, in proceedings of Eurocrypt 1999. A safer lower bound is $d>sqrt N$, or the aforementioned $d>2^textnlen/2$. That consideration is relevant at least when $d$ is chosen, as in in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem (in CACM, 1978).
Maximum value
The upper bound for $d$ depends on context.
- From a mathematical standpoint, there is no limit: any $d$ with $lambda(N)$ dividing $e,d-1$ is acceptable, where (for distinct $r_i$ ) $lambda(N)$ is computed as the Least Common Multiple of the $(r_i-1)$. We can add any multiple of $lambda(N)$ to any valid $d$, and obtain another valid $d$.
- In a PKCS#1 context, we must additionally have $0<d<N$, which implies $d<2^textnlen$. That leaves at least two possible $d$, sometime more.
- Some definitions of RSA state that $d=e^-1bmodvarphi(N)$, where (for distinct $r_i$ ) $varphi(N)=prod(r_i-1)$, see Euler's totient. This implies $d<varphi(N)$, which implies $d<N$ and $d<2^textnlen$. For usual RSA with two factors, that method of computing $d$ implies $d<N-2sqrt N$, thus the upper bound is slightly lower than $d<N$ in PKCS#1.
- In a FIPSÂ 186-4 context, it is required that $d=e^-1bmodlambda(n)$. That is the smallest positive $d$, and it is often markedly lower than with the previous method. We get $d<lambda(N)$, thus $d<varphi(N)/2$, thus $d<2^textnlen-1$, and for two factors $d<N/2-sqrt N$.
answered Aug 8 at 23:03
fgrieu
72k6149308
edited Aug 9 at 23:14
answered Aug 8 at 23:03
fgrieu
72k6149308
answered Aug 8 at 23:03
fgrieu
72k6149308
answered Aug 8 at 23:03
fgrieu
72k6149308
72k6149308
add a comment |Â
add a comment |Â
up vote
8
down vote
Modern cryptography generally chooses a static public exponent. Nowadays this is almost universally the fifth prime of Fermat or F4, 65537 or 010001 in hexadecimals. From this the private key is calculated given the two prime numbers that are half the size of the key size.
The calculation that is performed can be seen in the answer to Calculating RSA private exponent. It is important to notice that the calculation returns a private exponent in the range $[0, N)$. Testing has shown that this value is well distributed within this range.
So the maximum value is simply $N - 1$, and this means that the private exponent can be as large as the key size. The minimum size is harder to establish, but please note that the chance that it is very small isn't all that high; the chance that it is 64 bits smaller than the key size is about $1/2^63.5$ (the precise chance depends on the value of the modulus). So even if the minimum value is 0, such a small size will never be generated.
This does however mean that:
- About once in 192 times that the private exponent is full byte smaller in size than the modulus.
- About once in 192 * 256 times the private exponent is two full bytes smaller in size than the modulus.
- ... and so on ...
Notes:
The private exponent is commonly encoded as a signed big endian number (an ASN.1 INTEGER) which means that the size also differs because of left padding with a zero byte to avoid negative values. This answer doesn't go into ASN.1 overhead or Chinese Remainder Theorem (CRT) parameters.
If you manage to generate a $d$ that is 128 bits smaller than the key size then you might as well restart key generation. You may need to log such an unlikely event. The chance that something is wrong is much larger than the chance that such a small private exponent gets calculated.
A smaller private exponent does not mean that the private key is less secure. That is, unless the size is much smaller and / or the size of the private exponent is caused by miscalculation.
The modulus $N$ is in between $2^l-1$ and $2^l$ where $l$ is the key size. The maximum size of the modulus does of course influence the maximum value of the private exponent $d$. If the modulus is close to $2^l-1$ then the chance that the private exponent is almost always one bit smaller than the modulus. If the modulus is close to $2^l$ then the chance of this is about 0.5 (50%).
answered Aug 9 at 7:27
Maarten Bodewes
47.5k566174
1
The excellent answer of fgrieu deserves a less theoretical counterpart, in my opinion :)
– Maarten Bodewes
Aug 9 at 7:28
1
"Testing has shown that $d$ is well distributed within this range $[0,N)$" applies when computing $d=e^-1bmodvarphi(N)$. However FIPS 186-4 requires, and PKCS#1 allows, to compute $d=e^-1bmodlambda(N)$, and then $d$ never hits the upper half of the interval, and is further very observably biased towards low values in $[0,N/2)$. It happens with e.g. BouncyCastle 6, at that spot in the code, and many things targeting FIPS186-4 certification, I guess.
– fgrieu
Aug 9 at 18:51
Interesting, I'll do some more testing, I didn't t that behavior before but it has been some time that I tested this the last time. Note that this only is a single bit difference with the given answer though.
– Maarten Bodewes
Aug 9 at 19:58
@fgrieu I can see it happening with Bouncy indeed. I tested Java which doesn't seem to do this, but that's for an old version of Java, Java 1.8.0_171 to be precise... I'll test Java 10 later on.
– Maarten Bodewes
Aug 11 at 20:49
add a comment |Â
up vote
8
down vote
Modern cryptography generally chooses a static public exponent. Nowadays this is almost universally the fifth prime of Fermat or F4, 65537 or 010001 in hexadecimals. From this the private key is calculated given the two prime numbers that are half the size of the key size.
The calculation that is performed can be seen in the answer to Calculating RSA private exponent. It is important to notice that the calculation returns a private exponent in the range $[0, N)$. Testing has shown that this value is well distributed within this range.
So the maximum value is simply $N - 1$, and this means that the private exponent can be as large as the key size. The minimum size is harder to establish, but please note that the chance that it is very small isn't all that high; the chance that it is 64 bits smaller than the key size is about $1/2^63.5$ (the precise chance depends on the value of the modulus). So even if the minimum value is 0, such a small size will never be generated.
This does however mean that:
- About once in 192 times that the private exponent is full byte smaller in size than the modulus.
- About once in 192 * 256 times the private exponent is two full bytes smaller in size than the modulus.
- ... and so on ...
Notes:
The private exponent is commonly encoded as a signed big endian number (an ASN.1 INTEGER) which means that the size also differs because of left padding with a zero byte to avoid negative values. This answer doesn't go into ASN.1 overhead or Chinese Remainder Theorem (CRT) parameters.
If you manage to generate a $d$ that is 128 bits smaller than the key size then you might as well restart key generation. You may need to log such an unlikely event. The chance that something is wrong is much larger than the chance that such a small private exponent gets calculated.
A smaller private exponent does not mean that the private key is less secure. That is, unless the size is much smaller and / or the size of the private exponent is caused by miscalculation.
The modulus $N$ is in between $2^l-1$ and $2^l$ where $l$ is the key size. The maximum size of the modulus does of course influence the maximum value of the private exponent $d$. If the modulus is close to $2^l-1$ then the chance that the private exponent is almost always one bit smaller than the modulus. If the modulus is close to $2^l$ then the chance of this is about 0.5 (50%).
answered Aug 9 at 7:27
Maarten Bodewes
47.5k566174
1
The excellent answer of fgrieu deserves a less theoretical counterpart, in my opinion :)
– Maarten Bodewes
Aug 9 at 7:28
1
"Testing has shown that $d$ is well distributed within this range $[0,N)$" applies when computing $d=e^-1bmodvarphi(N)$. However FIPS 186-4 requires, and PKCS#1 allows, to compute $d=e^-1bmodlambda(N)$, and then $d$ never hits the upper half of the interval, and is further very observably biased towards low values in $[0,N/2)$. It happens with e.g. BouncyCastle 6, at that spot in the code, and many things targeting FIPS186-4 certification, I guess.
– fgrieu
Aug 9 at 18:51
Interesting, I'll do some more testing, I didn't t that behavior before but it has been some time that I tested this the last time. Note that this only is a single bit difference with the given answer though.
– Maarten Bodewes
Aug 9 at 19:58
@fgrieu I can see it happening with Bouncy indeed. I tested Java which doesn't seem to do this, but that's for an old version of Java, Java 1.8.0_171 to be precise... I'll test Java 10 later on.
– Maarten Bodewes
Aug 11 at 20:49
add a comment |Â
up vote
8
down vote
up vote
8
down vote
Modern cryptography generally chooses a static public exponent. Nowadays this is almost universally the fifth prime of Fermat or F4, 65537 or 010001 in hexadecimals. From this the private key is calculated given the two prime numbers that are half the size of the key size.
The calculation that is performed can be seen in the answer to Calculating RSA private exponent. It is important to notice that the calculation returns a private exponent in the range $[0, N)$. Testing has shown that this value is well distributed within this range.
So the maximum value is simply $N - 1$, and this means that the private exponent can be as large as the key size. The minimum size is harder to establish, but please note that the chance that it is very small isn't all that high; the chance that it is 64 bits smaller than the key size is about $1/2^63.5$ (the precise chance depends on the value of the modulus). So even if the minimum value is 0, such a small size will never be generated.
This does however mean that:
- About once in 192 times that the private exponent is full byte smaller in size than the modulus.
- About once in 192 * 256 times the private exponent is two full bytes smaller in size than the modulus.
- ... and so on ...
Notes:
The private exponent is commonly encoded as a signed big endian number (an ASN.1 INTEGER) which means that the size also differs because of left padding with a zero byte to avoid negative values. This answer doesn't go into ASN.1 overhead or Chinese Remainder Theorem (CRT) parameters.
If you manage to generate a $d$ that is 128 bits smaller than the key size then you might as well restart key generation. You may need to log such an unlikely event. The chance that something is wrong is much larger than the chance that such a small private exponent gets calculated.
A smaller private exponent does not mean that the private key is less secure. That is, unless the size is much smaller and / or the size of the private exponent is caused by miscalculation.
The modulus $N$ is in between $2^l-1$ and $2^l$ where $l$ is the key size. The maximum size of the modulus does of course influence the maximum value of the private exponent $d$. If the modulus is close to $2^l-1$ then the chance that the private exponent is almost always one bit smaller than the modulus. If the modulus is close to $2^l$ then the chance of this is about 0.5 (50%).
answered Aug 9 at 7:27
Maarten Bodewes
47.5k566174
Modern cryptography generally chooses a static public exponent. Nowadays this is almost universally the fifth prime of Fermat or F4, 65537 or 010001 in hexadecimals. From this the private key is calculated given the two prime numbers that are half the size of the key size.
The calculation that is performed can be seen in the answer to Calculating RSA private exponent. It is important to notice that the calculation returns a private exponent in the range $[0, N)$. Testing has shown that this value is well distributed within this range.
So the maximum value is simply $N - 1$, and this means that the private exponent can be as large as the key size. The minimum size is harder to establish, but please note that the chance that it is very small isn't all that high; the chance that it is 64 bits smaller than the key size is about $1/2^63.5$ (the precise chance depends on the value of the modulus). So even if the minimum value is 0, such a small size will never be generated.
This does however mean that:
- About once in 192 times that the private exponent is full byte smaller in size than the modulus.
- About once in 192 * 256 times the private exponent is two full bytes smaller in size than the modulus.
- ... and so on ...
Notes:
The private exponent is commonly encoded as a signed big endian number (an ASN.1 INTEGER) which means that the size also differs because of left padding with a zero byte to avoid negative values. This answer doesn't go into ASN.1 overhead or Chinese Remainder Theorem (CRT) parameters.
If you manage to generate a $d$ that is 128 bits smaller than the key size then you might as well restart key generation. You may need to log such an unlikely event. The chance that something is wrong is much larger than the chance that such a small private exponent gets calculated.
A smaller private exponent does not mean that the private key is less secure. That is, unless the size is much smaller and / or the size of the private exponent is caused by miscalculation.
The modulus $N$ is in between $2^l-1$ and $2^l$ where $l$ is the key size. The maximum size of the modulus does of course influence the maximum value of the private exponent $d$. If the modulus is close to $2^l-1$ then the chance that the private exponent is almost always one bit smaller than the modulus. If the modulus is close to $2^l$ then the chance of this is about 0.5 (50%).
answered Aug 9 at 7:27
Maarten Bodewes
47.5k566174
edited Aug 10 at 3:14
answered Aug 9 at 7:27
Maarten Bodewes
47.5k566174
answered Aug 9 at 7:27
Maarten Bodewes
47.5k566174
answered Aug 9 at 7:27
Maarten Bodewes
47.5k566174
47.5k566174
1
The excellent answer of fgrieu deserves a less theoretical counterpart, in my opinion :)
– Maarten Bodewes
Aug 9 at 7:28
1
"Testing has shown that $d$ is well distributed within this range $[0,N)$" applies when computing $d=e^-1bmodvarphi(N)$. However FIPS 186-4 requires, and PKCS#1 allows, to compute $d=e^-1bmodlambda(N)$, and then $d$ never hits the upper half of the interval, and is further very observably biased towards low values in $[0,N/2)$. It happens with e.g. BouncyCastle 6, at that spot in the code, and many things targeting FIPS186-4 certification, I guess.
– fgrieu
Aug 9 at 18:51
Interesting, I'll do some more testing, I didn't t that behavior before but it has been some time that I tested this the last time. Note that this only is a single bit difference with the given answer though.
– Maarten Bodewes
Aug 9 at 19:58
@fgrieu I can see it happening with Bouncy indeed. I tested Java which doesn't seem to do this, but that's for an old version of Java, Java 1.8.0_171 to be precise... I'll test Java 10 later on.
– Maarten Bodewes
Aug 11 at 20:49
add a comment |Â
1
The excellent answer of fgrieu deserves a less theoretical counterpart, in my opinion :)
– Maarten Bodewes
Aug 9 at 7:28
1
"Testing has shown that $d$ is well distributed within this range $[0,N)$" applies when computing $d=e^-1bmodvarphi(N)$. However FIPS 186-4 requires, and PKCS#1 allows, to compute $d=e^-1bmodlambda(N)$, and then $d$ never hits the upper half of the interval, and is further very observably biased towards low values in $[0,N/2)$. It happens with e.g. BouncyCastle 6, at that spot in the code, and many things targeting FIPS186-4 certification, I guess.
– fgrieu
Aug 9 at 18:51
Interesting, I'll do some more testing, I didn't t that behavior before but it has been some time that I tested this the last time. Note that this only is a single bit difference with the given answer though.
– Maarten Bodewes
Aug 9 at 19:58
@fgrieu I can see it happening with Bouncy indeed. I tested Java which doesn't seem to do this, but that's for an old version of Java, Java 1.8.0_171 to be precise... I'll test Java 10 later on.
– Maarten Bodewes
Aug 11 at 20:49
1
1
The excellent answer of fgrieu deserves a less theoretical counterpart, in my opinion :)
– Maarten Bodewes
Aug 9 at 7:28
The excellent answer of fgrieu deserves a less theoretical counterpart, in my opinion :)
– Maarten Bodewes
Aug 9 at 7:28
1
1
"Testing has shown that $d$ is well distributed within this range $[0,N)$" applies when computing $d=e^-1bmodvarphi(N)$. However FIPS 186-4 requires, and PKCS#1 allows, to compute $d=e^-1bmodlambda(N)$, and then $d$ never hits the upper half of the interval, and is further very observably biased towards low values in $[0,N/2)$. It happens with e.g. BouncyCastle 6, at that spot in the code, and many things targeting FIPS186-4 certification, I guess.
– fgrieu
Aug 9 at 18:51
"Testing has shown that $d$ is well distributed within this range $[0,N)$" applies when computing $d=e^-1bmodvarphi(N)$. However FIPS 186-4 requires, and PKCS#1 allows, to compute $d=e^-1bmodlambda(N)$, and then $d$ never hits the upper half of the interval, and is further very observably biased towards low values in $[0,N/2)$. It happens with e.g. BouncyCastle 6, at that spot in the code, and many things targeting FIPS186-4 certification, I guess.
– fgrieu
Aug 9 at 18:51
Interesting, I'll do some more testing, I didn't t that behavior before but it has been some time that I tested this the last time. Note that this only is a single bit difference with the given answer though.
– Maarten Bodewes
Aug 9 at 19:58
Interesting, I'll do some more testing, I didn't t that behavior before but it has been some time that I tested this the last time. Note that this only is a single bit difference with the given answer though.
– Maarten Bodewes
Aug 9 at 19:58
@fgrieu I can see it happening with Bouncy indeed. I tested Java which doesn't seem to do this, but that's for an old version of Java, Java 1.8.0_171 to be precise... I'll test Java 10 later on.
– Maarten Bodewes
Aug 11 at 20:49
@fgrieu I can see it happening with Bouncy indeed. I tested Java which doesn't seem to do this, but that's for an old version of Java, Java 1.8.0_171 to be precise... I'll test Java 10 later on.
– Maarten Bodewes
Aug 11 at 20:49
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f61402%2fwhat-is-the-minimum-and-maximum-value-of-an-rsa-private-exponent%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I quite heavily edited the question, please check if it is still OK. I changed the question from size to values, as RSA works on numbers. From the minimum and maximum value it is of course easy to determine the possible sizes that an RSA private exponent can take on (just take the $log_2$ of the value).
– Maarten Bodewes
Aug 9 at 6:34