0
$\begingroup$

I'm studying the RSA algorithm and the theory says to select $d$ to be the multiplicative inverse of.

$$ e \mod \phi(n) $$

If we take this approach I know that it is important that $e$ and $\phi(n)$ are coprime.

Why is this "better" as opposed to say the following equation where $e$ is still selected as a coprime to $\phi(n)$:

$$ d = \frac{\phi(n) + 1}{e} $$

I would like to have a deep explanation. I do not have formal math training, so any links to help understand the answer is very much appreciated.

$\endgroup$
  • 2
    $\begingroup$ It is very unlikely that (phi(n)+1)/e is an integer. $\endgroup$ – fkraiem May 28 '16 at 14:55
  • 1
    $\begingroup$ What problems will d not being an integer cause from a practical or a theoretical perspective? $\endgroup$ – Ishan Antony May 28 '16 at 16:59
  • 3
    $\begingroup$ @IshanAntony Now you need to define what modular exponentiation with a fractional exponent is supposed to be. $\endgroup$ – CodesInChaos May 28 '16 at 21:49
1
$\begingroup$

In the standarized RSA algorithm the private key $d$ is calculated computing the modular multiplicative inverse with the Extended Euclidean GCD that satisfies:

$1\equiv e \cdot d\pmod {\varphi(p \cdot q})$

Notice that modular multiplicative inverse can be expressed as:

$$d=\frac{\varphi(p\cdot q)\cdot k + 1}{e}$$

for some $k$ multiple of $\varphi$($p\cdot q$). We know that $e$ is 17 bits (65537) so $k$ will be small, thus computing $d$ with this method would be realizable. You have to know the factorization of the semiprime for computing $\varphi(p \cdot q)$.

Mathematically other ways for computing the private key exist, such as the Euler Criterion.

For calculating the modular multiplicative inverse we would have:

$d\equiv e^{\varphi(\varphi(p \cdot q))-1}\pmod {\varphi(p \cdot q})$

As you can see we would need to have the factorization of $\varphi(p\cdot q)$, so we cannot deal with big semiprime modulus. Concretely we need the factors of $(p-1)$ and $(q-1)$ in order to compute $\varphi(p-1) \cdot \varphi(q-1)$

$\endgroup$
  • $\begingroup$ Comments on my question more directly answered my question.. which is we need the private key to be an integer and that modular multiplicative inverse is a guaranteed way to achieve it.. notice that I asked why is the standard way better $\endgroup$ – Ishan Antony May 29 '16 at 15:53
  • 1
    $\begingroup$ @kub0x: Modular inverses are easily obtained from extended Euclidean algorithm. There is no need to know $\varphi(p-1)$ or $\varphi(q-1)$. $\endgroup$ – user94293 May 30 '16 at 4:41
  • $\begingroup$ @user94293: If you take a closer look to the beginning of my post you will see that I mention the Extended euclidean as the standard algorithm. I just have given more methods, like Euler's.. you know, more information more knowledge ;) $\endgroup$ – kub0x May 30 '16 at 12:35
  • $\begingroup$ @kub0x The method you present is not practical for concrete implementations of RSA as for a $2048$-bit RSA modulus, it requires factoring two $1024$-bit integers. Efficient methods not relying of the extended Euclidean algorithm for computing modular inverses can be found in [ Joye and Paillier, CHES 2003, dx.doi.org/10.1007/978-3-540-45238-6_20 ]. $\endgroup$ – user94293 May 30 '16 at 14:14
  • $\begingroup$ @user94293: Yes, you are right on that. At the bottom of the post I explained that you have to factor the modulus totient. I just wanted to give a different mathematical approach, but pointing the Extended Euclidean as the recommended. Regards. $\endgroup$ – kub0x May 30 '16 at 14:46
0
$\begingroup$

The number $1$ is known as the multiplicative identity.

In RSA, $d$ is the multiplicative inverse of $e$, therefore, $ed=1$. Mathematically $d$ would normally be a fraction, such as, $e=4$, then $d={1\over 4}$, thereby $4\cdot {1\over 4}=1$. RSA uses modular rings, so we compute $d$ as a modular multiplicative inverse of $e$, then $d\equiv e^{-1}\bmod \varphi(p\cdot q)$ (for textbook RSA), resulting in $1\equiv ed\bmod \varphi(p\cdot q)$.

Now if we round-robin a message, $C=M^e\bmod(p\cdot q)$, then $M'=C^d\bmod(p\cdot q)$, we get $M'=M$, the original message. If we do a little substitution, we have $M'=(M^e)^d=M^{ed}=M^1$, which we know is equivalent to $M'=M$ because any positive number to the power of $1$ equals itself, as in, $438^1=438$.

Given the equations $d\equiv e^{-1}\bmod \varphi(p\cdot q)$ and $d={{\varphi(p\cdot q) \cdot k+1}\over e}$, both require knowledge of $p$ and $q$, however, the second requires also finding a value for $k$ which produces an integer result. This is more challenging for larger $(p\cdot q)$ than performing the modular multiplicative inverse function.

$\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.