1
$\begingroup$

Given $e,d,N$ such that $e \times d \equiv 1 \pmod{ \varphi(n)}$. Can we efficiently calculate $\varphi(N)$.

$\varphi(N)$ will have multiples values. We need to eliminate those values that are

  1. higher than $N$
  2. Odd and some other criteria

Is there any efficient algorithm to find $\varphi(N)$.

$\endgroup$
1
$\begingroup$

Bellow algorithm is able to factor $n$ with probability at least $\frac{1}{2}$:

RSA-FACTOR(n, a, b)

comment: we are assuming that $ab=1\pmod {\phi(n)}$

write $ab - 1 = 2^sr$

choose $w$ at random such that $1\leq w \leq n-1$

$x= gcd(w, n)$

if $l<x<n$ then return $(x)$

comment: $x$ is a factor of $n$

$v=w^r \pmod n$

if $v=1 \pmod n$ then

then return ("failure")

while $v \ne 1 \pmod n$ do

$v_0=v$

$v =v^2 \pmod n$

if $v_0=-1 \pmod n$ then return ("failure")

else $x=gcd (v_0+ 1 , n )$

return $(x)$

This is an algorithm 5.10 in the page $204$ of "CRYPTOGRAPHY THEORY AND PRACTICE" by DOUGLAS R. STINSON.

$\endgroup$
  • $\begingroup$ Does that algorithm also work when $ab\equiv 1 \pmod {\lambda(n)}$, since $ab\equiv 1 \pmod {\varphi(n)}$ is not a necessary condition for RSA to work? $\endgroup$ – CodesInChaos May 2 '17 at 11:39
  • $\begingroup$ Dear @CodesInChaos, In the proof of algorithm, $w^{2^sr}=1 \pmod n$ is important for us. So algorithm also work when $ab\equiv 1 \pmod {\lambda(n)}$. $\endgroup$ – Meysam Ghahramani May 2 '17 at 12:05
1
$\begingroup$

When you know $e,d,N$, you can calculate $ed-1$, which is a multiple of $\Phi(n)$. I guess that's what you meant by

$\Phi(n)$ will have multiple values.

The sentence itself is wrong, though. As a function it does not have "multiple values" for a fixed $n$. You know a multiple of the value.

There are various algorithms to do this:

This looks like a homework question, so I won't give an explicit algorithm.

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