1

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?

Leonardo
  • 557
  • 1
  • 6
  • 16

1 Answers1

1

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!

Community
  • 1
davidlowryduda
  • 88,861
  • 11
  • 160
  • 306
  • 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](http://math.stackexchange.com/questions/2099165/how-to-solve-min-x-in-mathbb-n-0-quad-x-cdot-714-quad-mod-quad-1972-qua/2099198#2099198). – Bernard Jan 18 '17 at 16:14
  • @ mixedmath, Done, Thanks ! – Leonardo Jan 18 '17 at 16:25
  • @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)](http://math.stackexchange.com/questions/85830/how-to-use-the-extended-euclidean-algorithm-manually/85841#85841) since it is much less error-prone, easier to remember, and motivates generalizations such as (Hermite-)Smith normal form, etc. – Bill Dubuque Jan 18 '17 at 18:36
  • @Bernard I prefer the [fractional form](http://math.stackexchange.com/a/2053174/242) of the extended Eucldean algorithm, but that's a little tricky for novices. – Bill Dubuque Jan 18 '17 at 18:41
  • @Bill Dubuque: It seems like you work within the class group of fractionary ideals. Am I right? – Bernard Jan 18 '17 at 18:57
  • @Bernard It's much simpler: I'm just overloading fractional notation to denote solution sets of linear equations in $\,\Bbb Z/m\,$ (which is what you obtain if you optimize the EEA by ignoring one of the Bezout coefficients). It's a natural generalization of the fractional form of [Gauss's algorithm](http://math.stackexchange.com/a/174687/242) to the case of non-prime modulus. – Bill Dubuque Jan 18 '17 at 19:10
  • Ah! I think I'll have to study it in more detail. Is it easy to implement it? – Bernard Jan 18 '17 at 19:13
  • @Bernard Yes. It's equivalent to what you do, except working with only one column (or row) of Bezout coefficients, and expressing the resulting linear modular equations in (multi-valued) fraction notation. – Bill Dubuque Jan 18 '17 at 19:15
  • @Bernard While linking I just noticed that Marc van Leeuwen also mentioned a form of this [well-known EEA optimization here.](http://math.stackexchange.com/a/252923/242) You might find that version an easier introduction since it doesn't require simultaneous understanding of the fractional language (though that is easy). – Bill Dubuque Jan 18 '17 at 19:22
  • Yes, this version is perfectly clear. I'll study in more detail the connection with your way of obtaining modular inverses. – Bernard Jan 18 '17 at 19:28