4
$\begingroup$

When I calculate two RSA keys, what if anything, would make any difference which I call the public vs which I call the private key?

$\endgroup$
3
$\begingroup$

In theory RSA keys are symmetric. Meaning that it doesnt matter which one you use as a private key or as a public key. However in practice there are subtle restrictions which break this symmetry.

First of all you generally want your public key to be relatively small. This way, encryption operations dont take too much time to be executed (dont pick a public key to small though because then an attacker may be able to decrypt messages).

On the other hand the private key needs to be large. If the private key is smaller than $\frac{1}{3}n^{\frac{1}{4}}$ (with $n$ being the modulus of the rsa key) then an attacker could execute a very fast attack and recover the private key quickly.

As a result you must handle the private and the public key differently. However if the efficiency of encryption doesn't matter andyou choose to use integers larger than $\frac{1}{3}n^{\frac{1}{4}}$ for both private and public key then you could publish either one and keep the other secret and you would still have a secure and working rsa cryptosystem.

$\endgroup$
2
$\begingroup$

In any RSA-type cryptosystem, a public key necessarily has a modulus $n$, and sometimes has an exponent $e$ if it's not prescribed by the cryptosystem. Sensible cryptosystems like RSA-KEM can prescribe $e = 3$, but some defective standards, based on mistakes like RSAES-PKCS1-v1_5, may require $e$ to be $e = 65537$ or larger and may allow $e$ to vary.

A private key can come in any of several forms:

  • the factors $p$ and $q$ of $n = pq$
  • a private exponent $d$, which solves $e \cdot d \equiv 1 \pmod{\lambda(n)}$
  • Chinese remainder theorem exponents $d_p \equiv d \pmod{p - 1}$ and $d_q \equiv d \pmod{q - 1})$

Any of these forms of the private key is equivalent, given knowledge of $n$: from $p$ and $q$ you can compute $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ and solve $e d \equiv 1 \pmod{\lambda(n)}$ with the extended Euclidean algorithm; from $d$ you can recover a multiple $e \cdot d - 1$ of $\lambda(n)$ and without much additional difficulty proceed to factor $n$; etc. Often, as in, e.g., OpenSSL, many redundant parts of the private key are stored together to speed up the computation.

The main question, then, is: Are the public exponent $e$ and the private exponent $d$ interchangeable? And the answer is: No.

In Rivest, Shamir, and Adleman's seminal paper, the proposed method was to choose $d$ at random to be coprime with $\phi(n) = (p - 1)(q - 1)$ and then to derive $e$ from $d$ by solving $ed \equiv 1 \pmod{\phi(n)}$. One could do it the other way around: choose $e$ at random to be coprime with $\phi(n)$, and then to derive $d$ from $e$ by solving $ed \equiv 1 \pmod{\phi(n)}$. So, if you were stuck in 1978, it might look like the roles of the two exponents are interchangeable—but if you were stuck in 1978, your encryption scheme would also be trivially breakable,* so maybe you don't want to stay in 1978.

The main cost for a user of RSA is computing modular exponentiation, which for exponent $x$ costs $\lfloor\log_2 x\rfloor$ squarings and $H(x) - 1$ multiplications, where $H$ is Hamming weight. The most efficient exponent is 3—but you can only do this for the public exponent! If you always picked the private exponent $d = 3$, you would still have to publish $e$ in order for anyone to encrypt messages—but if you did that, then armed with knowledge of $e$ and $d$ I could find $\lambda(n)$ and factor $n$ and break the whole cryptosystem!

‘OK, fine,’ you say, ‘so $d = 3$ is no good, but what if I just picked $d$ to be small to speed up decryption?’ As it happens, if $d$ is merely smaller than about $\sqrt[4] n$, I can use Wiener's attack or a variant thereof to recover it! It is therefore crucial that the private exponent $d$ be near uniformly distributed in the whole possible space, which is effectively the case even if you choose the public exponent $e$ to always be something small like 3 or 65537.

Thus while it is perfectly safe in sensible RSA-type cryptosystems to always use $e = 3$, it is dangerous to choose even moderately small $d$; the exponents are very much not interchangeable.

P.S. You may be tempted, by the seductive symmetry of the equations $c = m^e \bmod n$ and $m = c^d \bmod n$, to treat encryption and signature as interchangeable too. Don't do it! It's a trap! If you try to shoehorn a message into this shape, you'll likely end up shooting yourself in the foot; there's much more to encryption and much more to signature, and beyond the use of exponentiation they bear very little resemblance—and if you naively try to combine the two with the same keys you will probably shoot yourself in the other foot too. At that point, you'd better hope you're an octopus.


* They recommend what is effectively RSA-ECB for encryption, and a trivially forgeable hashless signature scheme. The first secure signature scheme by modern standards—assuming suitably scaled parameters—wasn't published until a year later by Rabin in 1979, using the qualitatively different exponent $e = 2$, and the first secure encryption scheme by modern standards wasn't published until some time after that.

$\endgroup$
  • $\begingroup$ It's not only OpenSSL; everything (or nearly) that uses PKCS8, or PKCS12 because that in turn uses PKCS8, uses the full-CRT privatekey from PKCS1 Appendix A. $\endgroup$ – dave_thompson_085 May 18 at 3:31
-1
$\begingroup$

With the secret key you can decrypt and actually you can reconstruct the public key. Knowing the secret key you can decrypt messages, so you want to keep that key confidential. On the other hand knowing the public key you can encrypt messages.

$\endgroup$
  • 2
    $\begingroup$ Mathematically speaking, encryption and decryption are identical. They're both $M^e \mod n$. The difference is whether $e$ is the public value or private value. You could encrypt with your private key and decrypt with your public key, and this is actually used for digital signatures. $\endgroup$ – Daffy Feb 19 '16 at 2:44
-1
$\begingroup$

Mathematically, there is really no difference. Both encrypt and decrypt the same. An RSA key is in the form (e,n) and (d,n) where e,d are public/private exponents and n is the product of 2 large primes. e and n can be known to anyone, while d is the real private part.

So the keys are: public: (e,n) private: (d,n)

However when designing the scheme, we generally use really small public keys. RSA often uses $2^{17}$+1 as the public key exponent e. This allows encrypting (but not decrypting) to be much faster. Choosing this e value is a tad tricky as well. So all in all, we mainly use the same public exponents while having different n and private exponents.

If you gave someone the private key instead of the public key, they would just go through a list of commonly used public key exponents until you found it. The attacker knows d and just tries various e's until ${(m^{d})}^e=m$, and since there are far fewer values of public key exponents than private, they've broken your key.

So from a mathematical perspective, they are the same, but you need to be very careful how you choose those public/private exponents.

$\endgroup$

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.