-3

I took the p&q value as 61 & 53 and n=3233 e=17 d=? How to find it? Plz help me...

Amigo
  • 1
  • 1
  • 2
  • 1
    [This](http://crypto.stackexchange.com/a/20932/555) and the description of the [Extended Euclidian algorithm](http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) might also help. Surprisingly, I fail to find a complete step by step answer performing $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$ on our site! – fgrieu Jan 08 '16 at 10:39

1 Answers1

0

It isn't hard to find d!

We know $ed=1\bmod \phi(n)$.

$\phi(n)=\phi(61)\phi(53)=(60)(52)=3120$

So $17d=1\bmod 3120$. From the euclidean algorithm you can easily find "d".

R. Jalaei Salahi
  • 131
  • 8
  • 3
    A more rigorous notations is writing $ed\equiv1\pmod{\phi(n)}$ or $ed\bmod\phi(n)=1$. Problem with $ed=1\bmod\phi(n)$ is that it can (and arguably should) be read $ed=(1\bmod\phi(n))$, that is $ed=1$. Also, $ed\equiv1\pmod{\phi(n)}$ is a sufficient condition, but is not necessary; the necessary and sufficient condition, used in [PKCS#1](https://www.emc.com/collateral/white-papers/h11300-pkcs-1v2-2-rsa-cryptography-standard-wp.pdf#page=7), is $ed\equiv1\pmod{\lambda(n)}$. $d=413$ is a valid private exponent, but $17\times413\bmod3120\ne1$. – fgrieu Jan 08 '16 at 07:15
  • Can u explain briefly?? – Amigo Jan 08 '16 at 07:16