1
$\begingroup$

I was attempting Wiener's Attack on RSA with a simple example and I came to a one variable modulo equation which I managed to solve with brute-force but I think it must be easier than that with some algorithm/formula.

here it is.

$e * d \equiv 1 \mod phi(N)$

e and phi(N) are known: e = 5 550 641 and phi(N) = 15 726 816

so it gives us: $5 550 641 * d \equiv 1 \mod phi(N)$

I got the answer, d = 17 but as I mentioned only with brute force, is there any formula or algorithm for solving this equation?

$\endgroup$
1
$\begingroup$

Solving $5550641 d \equiv 1 \pmod{15726816}$ can be done very quickly. This is called finding the modular inverse of $5550641$ modulo $15726816$. The best way to do this is through the Euclidean Algorithm (along with back substitution. This is sometimes called the Extended Euclidean Algorithm).

This is a topic that has been asked extensively on this site, so I will link you to some examples.

  1. In Modular Inverses it is asked to find the modular inverse of $19$ mod $141$. This is the same question as yours, but with different numbers.
  2. In Using Extended Euclidean Algorithm for $85$ and $45$ we have another example with still different numbers.
  3. In How to use the Extended Euclidean Algorithm manually? some details are given in a more general context, with an eye towards computing by hand. I'll note that in your case, you should really use a computer. But I'm assuming that you want to understand, as otherwise you could just prompt wolframalpha.

Good luck!

$\endgroup$
10
  • $\begingroup$ Back substitution is not the Extended Euclidean algorithm. The E.E.A. is a special layout which directly outputs the g.c.d. and the coefficients of a Bézout's relation between two numbers (One step further yields the l.c.m.). See for instance my answer to this question. $\endgroup$ – Bernard Jan 18 '17 at 16:14
  • $\begingroup$ @ mixedmath, Done, Thanks ! $\endgroup$ – Leonardo Jan 18 '17 at 16:25
  • $\begingroup$ @Bernard The "extended Euclidean algorithm" is an overloaded term that may refer to many different variants of this algorithm (including the common back-substitution method). I do agree however that the augmented form using equations or matrices is better (I present that here in an elementary form) since it is much less error-prone, easier to remember, and motivates generalizations such as (Hermite-)Smith normal form, etc. $\endgroup$ – Bill Dubuque Jan 18 '17 at 18:36
  • $\begingroup$ @Bernard I prefer the fractional form of the extended Eucldean algorithm, but that's a little tricky for novices. $\endgroup$ – Bill Dubuque Jan 18 '17 at 18:41
  • $\begingroup$ @Bill Dubuque: It seems like you work within the class group of fractionary ideals. Am I right? $\endgroup$ – Bernard Jan 18 '17 at 18:57

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.