2
$\begingroup$

I am currently learning about RSA since I didn't understand the public-key-system but now I am… kind of. So I am writing the numbers as follows:

$p = prime\ number\\ q = prime\ number\\ N = Public\ Key\ (p \times q)\\ Z = \phi(N)\\ E = Public\ exponent\\ D = Private\ key$

Now, to calculate $D$, the private key, you need the following formula:

$$D=\frac{ k \times (\phi(N))) +1 }{ E }$$

Can someone please explain me what $k$ means?

$\endgroup$
2
$\begingroup$

It's a translation of $ed \equiv 1 \pmod{\phi(N)}$, namely that $e$ and $d$ are each other's inverse modulo $\phi(N)$, which says that $ed-1$ must be an integer multiple of $\phi(N)$ (recall that $a \equiv b \pmod{c}$ iff $c$ divides $b-a$ in the integers iff $b-a=lc$ for some integer $l$) and some some $k \in \Bbb Z$ exists with $k\phi(N) = ed-1$ (as an equation in $\Bbb Z$) and this translates to your formula via some elementary rewriting.

So the actual value of $k$ is quite irrelevant (and need not be stored or remembered when using or implementing RSA), but this analysis is done before the Wiener/Coppersmith small $d$-attack (via continued fractions or lattices), IIRC. It's a necesary auxiliary unknown in the RSA-system of equations, as it were.

$\endgroup$
1
$\begingroup$

$\big(\hspace{-0.03 in}$You don't need that. $\:$ $\operatorname{L}\hspace{-0.02 in}\operatorname{cm}\hspace{.02 in}(\hspace{.04 in}p\hspace{-0.04 in}-\hspace{-0.05 in}1,\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.05 in}1)$ can be used instead of $\phi(N)$.$\hspace{-0.03 in}\big)$

$k$ is an integer which will make the quotient an integer.
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

$\endgroup$
  • $\begingroup$ How do you choose, calculate it? $\endgroup$ – fihdi Jul 23 '15 at 22:54
  • $\begingroup$ You go to the "Computation" section of the page I linked to. $\;$ $\endgroup$ – user991 Jul 23 '15 at 23:02
  • $\begingroup$ Is it what I think it means: When the division above(without k) happens to be not an integer but some number with decimal places. k will multiply it so it becomes a round, integer? $\endgroup$ – fihdi Jul 23 '15 at 23:52
  • 1
    $\begingroup$ No, since the image should have an open-parenthesis just before the $k$. $\;$ $\endgroup$ – user991 Jul 23 '15 at 23:59
  • 1
    $\begingroup$ No, since the image should have an open-parenthesis just before the k. I just edited the question, replacing that image with MathJax. Doing so, I reproduced the open-parenthesis error to make sure the question remained unchanged and nothing breaks. Please feel invited to correct the formula if you think it makes sense. $\endgroup$ – e-sushi Jul 24 '15 at 6:34
0
$\begingroup$

DE= 1 mod (ϕ(N)) so D=(k×(ϕ(N)))+1)/E with k is 1, 2, 3... The private k D can be computed efficiently by using the Extended Euclidean algorithm.

$\endgroup$
  • $\begingroup$ Have a look at MathJax for better formatting. $\endgroup$ – AleksanderRas Sep 18 at 13:18
-2
$\begingroup$

k is not actually needed as you only need to find d.just leave k and calculate and multiply it by a number which will be k to make it an integer

$\endgroup$
  • $\begingroup$ This answer is rather unintelligible to me, especially the last sentence. You're welcome to answer questions here, but please put in the effort and format your questions well. Then reread them as if you are the person that asked the question; would this be easy to understand? That kind of effort is required to create good answers. $\endgroup$ – Maarten Bodewes Sep 17 at 23:25
  • $\begingroup$ @datboi Please edit your response. $\endgroup$ – Patriot Sep 18 at 22:35

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.