Modular arithmetic

Question

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

Answer 1

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.

Answer 2

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:

• A probabilistic algorithm was given in the original RSA paper A method for obtaining digital signatures and public-key cryptosystems by Rivest, Shamir and Adleman, 1978
• A deterministic algorithm was given in Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring by May, 2004.
• This answer on SO references a different paper called Twenty Years of Attacks on the RSA Cryptosystem by Boneh, 1999.

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