How do I calculate e, d and N based on raw and encrypted message in RSA?

Question

I've got raw and encrypted message, which contains only numbers. For example:

Message: 32016550980634121428089400169, encrypted: 35682226122303060179704449482

I've written such an algorithm:

d = 1
n = enc+1

for k in tqdm(range(1, 10**7)):
  e = k * n
  if pow(msg, e, n) == enc:
      print("WE")

But looks like I've mistaken somewhere. How do I make it work?

Answer 1

As Ilmari said, coming up with the unique $N, e, d$ is impossible (as that are literally an infinite number of possibilities). However, if you're just interested in one possible set (which might not be the one that was actually used to generate the numbers initially), then below is one approach. Note: while it is feasible, it may be a bit more complex than throwing together a quick Python program and running it; if the below is too technical for you, well, this problem just might not be for you:

• We know that $M^e - C = k N$ for the message $M$, the ciphertext $C$ (which you known), the values $e, N$ (which you don't) and some integer $k$.

• Guess $e = 3$ (you don't know if that's correct, and you don't have any way to verify it, but it makes the below steps easier);

• Compute $M^3 - C$ and factor it (and this step is the most expensive; $M^3 - C$ is a 284 bit number, and while there are factorization programs out there that can handle it, you're not going to write one - you'll have to find one someone else has written).

• From the factors of $M^3 - C$, see if you can pick out two factors $P, Q$ which both have $P, Q \ne 1 \pmod 3$ (necessary for RSA with $e = 3$), and for which $P \times Q > C, M$.

• If you can do that, then you have $N = P \times Q$, and you can deduce $d$ in the standard way.

• If you can't find two factors that meet the criteria, but you can find three factors, then you could claim that it's multi-prime RSA, and do it that way. Otherwise, you'd need to try $e=5$; however, that's more expensive - $M^5 - C$ is a 474 bit number; to factor that, you'd probably need to rely on the public Factoring-As-A-Service cloud; that'll cost real money, and you're probably not that interested...

Answer 2

In general, you can't do that. You have one equation and two unknowns (not three, since $d$ is uniquely determined by $n$ and $e$, even if actually computing it without knowing the factors of $n$ is difficult), so the solution will in general not be unique.

Of course, you could guess that $e$ might be one of the common values (e.g. 3 or 65537) and try to solve for $n$. But that only works if you guess the right $e$. And even if you do manage to determine $n$ this way, you'll still have to factor $n$ to be able to calculate $d$.

---

As for your code, it has many mistakes. I have no idea why you're setting n = enc+1 or e = k * n, for example — neither of those make any sense whatsoever. It looks as if you may be missing some fairly basic knowledge of either Python programming or the mathematics behind RSA.

As I can't really tell from just your code what it is that you might be missing, all I can suggest is finding some good tutorials and revising the basics. And maybe ask for help from your instructor / TA / tutor / etc., if you have one available.