1
$\begingroup$

Who calculates the private exponent $d$ in RSA? Only $(n, e)$ are public and to calculate $d$ (with $d$ being the multiplicative inverse of $e$ with respect to $\phi(n)$), the receiver need $\phi(n)$.

So how is the receiver getting $\phi(n)$ and if the receiver is not getting $\phi(n)$ then who is calculating $d$?

$\endgroup$
5
$\begingroup$

In RSA, the owner of the private key calculates $d$, unless otherwise stated.

In public key cryptography, including RSA:

  1. The public key allows to encipher or/and verify signature.
  2. The private key allows to decipher or/and sign.
  3. Unless otherwise stated it is assumed that the owner/holder of the private key has generated both that private key and the public key, and does not reveal the private key.
    In practice, some device (computer, HSM, Smart Card..) and code does that task, perhaps under supervision of some person not the holder/owner of the private key (which might be a computer, sometime not the one used for the generation); this is typically ignored in cryptography, and considered part of computer security.
  4. Unless otherwise stated it is assumed that, somewhat, all public keys get known to all, without alteration or impersonation of who their owner is.
    In practice, this is often done using digital certificates.
$\endgroup$
1
$\begingroup$

The private exponent $d$ is generated during key pair generation. The private exponent and the modulus form the private key. The value $d$ depends on the public exponent and the modulus: $d ≡ e−1 \mod λ(n)$ where $λ(n) = \text{lcm}(λ(p), λ(q)) = \text{lcm}(p − 1, q − 1)$. In other words, the private key and public key depend on each other and are therefore part of the same key pair generation.

As the name implies the private exponent needs to be kept private. To do this it is generally best to create the key pair where the private key is required to be used. The RSA private key is generally used for signature generation and decryption. That means that the signer needs to generate the key pair and / or that the entity that performs the decryption (the receiver in your question).

The public key needs to be trusted by the other party to make encryption or authentication schemes work. Otherwise it is impossible to verify that the sender encrypts or verifies with the correct key. For the sender to send a message they must have received the public key. A public key infrastructure (PKI) is often used to distribute the public keys. An example of this is the PKIX which uses X.509 certificates in browsers.


So usually the following steps are performed in order:

  1. generate key pair
  2. distribute / trust public key
  3. use public key / private key of key pair

And (3) can consist of encrypt with public key, decrypt with private key where the private key of the receiver contains $d$.

What you are probably missing is step 2, where the public key is distributed in advance to the sender. This distribution step is often not mentioned when a text focuses on the mathematical operations.

So to wrap up: a protocol cannot just start off with a public key; the key pair needs to be generated in advance by one party. The private key - which includes the private exponent $d$ - is generated at key pair generation at the receiver. The function $\phi(n)$ is used within the key pair generation; it is not communicated by itself.


Notes:

  • The value of $d$ is not strictly required for RSA calculations if the Chinese Remainder Theorem (CRT) is used. That means that the value of $d$ may never be calculated for some cryptosystems.
  • Sometimes hardware such as smart cards, TPM's or HSM's are used to keep the private key secure. In that case the key pair generation is performed on the hardware device. The private key - incuding $d$ if used - will then never leave the device: the operations are performed within the hardware.
  • It is also possible to send messages without encrypting with the public key; the public key can also be used for authenticating one party to another. For instance TLS 1.3 requires you to use RSA only for authenticating the server (but only if RSA is indicated in the cipher suite, of course - other authentication methods exist).
  • Some Certificate Authorities create key pairs for their customers, and then securely transport the private key and certificate containing the public key. This is however frowned upon by most cryptographers as the private key is now known to the CA as well, and needs additional security measures to keep secure. It was famously deployed by Diginotar before it went bankrupt after signing TLS certificates for the wrong domains.
$\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.