Low exponent attack on RSA public key

Question

question is here. determine true or false

I think that in the RSA cryptosystem, one should use large private key because of the low exponent attack.

Also, In RSA cryptosystem, one should use large public key because of the low exponent attack.

1. Is my thinking right?
2. How much long or big do these key need to be?

Answer 1

First note that the key size of RSA is determined by the size of the modulus $N$ denoted $n$. As the modulus is always the same size for both the public key and private key. So this question is probably about the size of the exponent rather than the actual key size.

The private key exponent must be large otherwise RSA becomes vulnerable. This is the attack by Dan Boneh and Glenn Durfee , as fgrieu already explained in his answer. Of course if the private exponent is sufficiently small it could also be brute forced by an attacker.

When setting the public key exponent to a small value, such as the fourth prime of Fermat ($2^{16} + 1$ or $65537$) and using the standard key pair generation procedures the private key will with a very high probability be large enough, given a high enough key size.

Now the modulus and public exponent are considered public knowledge. So there is no good reason to choose a high public exponent to avoid brute force. The public exponent simply needs to be safe within the RSA cryptosystem. Furthermore, a small RSA key, especially one with as few bits as possible, is most efficient when calculating $p^e \bmod N$ (where $p$ is the padded message).

So, in conclusion, no, you should not use a large public exponent. The public key size is always the same size as the private key size, so that part of the original question doesn't make sense.

Answer 2

The reason to use a large private key (or rather, not to attempt to use a small private exponent) are given in 5. The reasons to use a large public key are in 1, and have nothing to do with exponent size (private or public). There is no known reason to use a larger public exponent than suggested in 2, and that's uncommon.

In RSA:

1. One should use a large enough size $n$ for the public modulus $N$; that's important because anything that factors $N$ will break the RSA instance using that $N$, and the resistance of $N$ to factorization tends to grow with $n$ (for constant number of factors of size proportional to $n$). The bit size $n$ of $N$, with $2^{n-1}\le N<2^n$, is known as the key size, public key size, or public modulus size. Official security recommendations start at $n=2048$.
2. The public exponent $e$ can be fixed to $e=2^{16}+1$, which is most common, compatible, and unobjectionable; or $e=3$ which gives a significantly faster public-key operation (see cautionary note). In modern practice, $e$ is typically a small odd prime fixed and chosen before $N$ and its factors. In any case, $e$ must be odd and at least $3$.
3. The factors of $N$ must be large distinct primes, and not one more than an integer sharing a prime factor with $e$. They must be randomly and secretly generated and combined into their product $N$. Standard practice is to select two primes $p$ and $q$ as about uniformly random primes in range $[2^{(n-1)/2},2^{n/2}]$ with $\gcd(p-1,e)=1=\gcd(q-1,e)$, simplifying to $p\bmod e\ne1$ and $q\bmod e\ne1$ when $e$ is prime; then compute $N=p\,q$.
4. A private exponent $d$ is most commonly secretly computed from $e$ and factors of $N$. The smallest working positive $d$ is $d=e^{-1}\bmod\lambda(N)$ with $\lambda(N)=\operatorname{LCM}(p-1,q-1)$ when $N=p\,q$. It is also common to use $d=e^{-1}\bmod\varphi(N)$ with $\varphi(N)=(p-1)(q-1)$.
5. No attempt should be made to significantly shorten $d$ ("small decryption key") by choosing $e$ or the factors $p$ and $q$ of $N$ for that purpose; that's not possible anyway when following advice in 2 and 3 above. It is known that $d$ shorter than $0.292\,n$ is unsafe; see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999. It is unclear what a safe minimum would be; and better speedup is achieved by a common implementation of the private-key function uisng the Chinese Remainder Theorem.
6. The textbook public-key function $x\to x^e\bmod N$ should be used for encryption, and/or the textbook private-key function $x\to x^d\bmod N$ used for signature generation, only when $x$ is
   • essentially random in some large interval (with bit size of its width close to $n$) and not under the control of an adversary; for example, $x$ can safely be a random bitstring of $n-1$ bits, converted to integer from binary, encrypted as $y=x^e\bmod N$, decrypted as $x=y^d\bmod N$, and then considered a shared secret, used in part as an encryption key for a message encrypted using symmetric cryptography;
   • or produced by some appropriate padding technique adapted to the usage (encryption or signature); a recommendable encryption padding is RSA-OAEP; a recommendable signature padding is RSASSA-PSS.
7. Care should be taken that implementations using a private key (decryption, signature generation) or secret data (encryption) can be vulnerable to side-channel or fault attacks.

Cautionary note: many uses of textbook RSA in introductory literature, and even in the industry, violate 6 to some degree. There is anecdotal evidence that when making goofs there, choosing very small $e$ (like $3$, or much smaller than $n$) makes things worse; but there is no evidence that $e=3$ is less safe than $e=2^{16}+1$, or that any low public-exponent attack applies, when abiding to 6.