2
$\begingroup$

I'm trying to understand what the smallest possible RSA public and private keys are. When using $p = 2, q = 3$, the encryption function doesn't encrypt. So I have to shift one prime to get $p = 3, q = 3$ and then the private key is $(9, 3)$ and the public key is also $(9, 3)$. I know that it is trivial to factor the product of two equal primes and it is bad to have the identical private and public key. However is it the lowest (feasible) RSA key pair or am I missing something here?

$\endgroup$
1
  • $\begingroup$ Note that 3 is not a valid public key in this case because $\varphi(9)=3\cdot 2=6$ which is not co-prime with 3. $\endgroup$
    – SEJPM
    Aug 18 '20 at 9:04
9
$\begingroup$

Per the definition of RSA in PKCS#1v2.2

In a valid RSA private key, the RSA modulus $n$ is the product of $u$ distinct odd primes $r_i$, $i=1$, $2$, …, $u$, where $u\ge2$.

That makes $n=3\cdot5=15$ the smallest public modulus.

and the RSA public exponent $e$ is an integer between $3$ and $n–1$ satisfying $\operatorname{GCD}(e,\lambda(n))=1$, where $\lambda(n)=\operatorname{LCM}(r_1–1,\ldots,r_u–1)$

That makes $e=3$ the smallest public exponent. $(n,e)=(15,3)$ happens to be a valid public key, since $\lambda(15)=4$ and $\operatorname{GCD}(3,4)=1$.

The RSA private exponent $d$ is a positive integer less than $n$ satisfying $e\cdot d\equiv1\pmod{\lambda(n)}\,$.

That makes $d=1$ the smallest private exponent. It corresponds e.g. to $(n,e)=(15,5)$. Encryption (and decryption) with that key is identity, but there is no worded prescription against that.


If we prohibit $d=1$, then $d=3$ becomes the smallest private exponent, matching $(n,e)=(15,3)$. More generally, different definitions of RSA yield different lower limits. Allowing $u=1$, $e=1$, and removing the prescription that $r_i$ is odd, makes $(n,e,d)=(2,1,1)$ acceptable. For FIPS 186-4, the smallest $n$ is 1024-bit, likelyA $(\lfloor2^{1023/2}\rfloor+257)\cdot(\lfloor2^{1023/2}\rfloor+2^{412}+431)\,$; the smallest $e$ is $65537\,$; and the smallest $d$ isB $2^{512}+1$.


A: Under the plausible assumption that each of $\lfloor2^{1023/2}\rfloor+256$, $\lfloor2^{1023/2}\rfloor+258$, $\lfloor2^{1023/2}\rfloor+2^{412}+430$ and $\lfloor2^{1023/2}\rfloor+2^{412}+432$ has a prime factor at least $2^{100}$, which I did not check.

B: Some valid matching public key $(n,e)$ exists with high likelihood. It's a mildly interesting problem to exhibit one.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.