0
$\begingroup$

I have found two ways to compute the RSA private key, but i have trouble understanding why they are equivalent.

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

$2) E* D=1 \mod \phi(N)$


$1)$ AFAIK comes from taking the relationship between eulers theorem and a modular identity such that. $$ M^{1+ \phi(N)} \equiv M \mod N \qquad \land \qquad M^{E*D} \equiv M \mod N \\ \qquad \text{ Euler} \qquad \qquad \qquad \qquad \qquad \qquad \text{ Identity}$$

So we can see that the exponents must be the same, and that exponentiating by an integer $K$ should make no difference in modular arithmethic

$k \phi(N)+1 = E*D$

so

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


The origin of $2)$ eludes me, why is it equivalent to $1)$?

$\endgroup$
1
$\begingroup$

$D={k \phi(N)+1 \over E}$ is equivalent to $ED = k \phi(N) + 1$

$ED \equiv 1 \pmod {\phi(N)}$ means "there's some integer $k$ s.t. $ED = 1 + k \phi(N)$"

Hence, they're equivalent.

BTW: the actual necessary and sufficient condition on E, D actually is $ED \equiv 1 \pmod {\text{lcm}(P-1, Q-1)}$ (for RSA modulii that consists of two primes); the relation you're using is sufficient, but not necessary.

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