1
$\begingroup$

Say, we have RSA public key $(n,e)=(221,7)$,

and the encryption of the message $m=12$ is $$c=m^e \bmod n= 12^7 \bmod (221) = 194 \bmod (221)$$

Can we find the $d$ by solving the equation;

$$194^d \bmod(221)=12$$

I get that the numbers I used are way smaller than they are in real life, but this should be easier then just guessing $p$ and $q$ from $n$ right?

$\endgroup$
  • $\begingroup$ I know that is one way to do it, but that would take a lot more time with bigger numbers than the way I described, right? $\endgroup$ – Willy Dec 19 '18 at 13:58
  • $\begingroup$ I don't think that is the same as what I'm saying. I'm trying to find $d$ while the RSA problem just wants to know the original message. $\endgroup$ – Willy Dec 19 '18 at 14:06
  • $\begingroup$ You say "the way I described", but you didn't describe anything. You said "solving the equation", not how you'd do it. $\endgroup$ – fkraiem Dec 19 '18 at 14:15
  • $\begingroup$ That is true. I have no idea how I would solve that equation. I just thought it would be far easier than factoring $n$. Isn't that true? $\endgroup$ – Willy Dec 19 '18 at 14:21
  • 1
    $\begingroup$ If you can solve that equation, you can factor. Hence, discrete log modulo a composite $n$ cannot be easier than factoring $n$ $\endgroup$ – poncho Dec 19 '18 at 17:53
0
$\begingroup$

The security of RSA is based on two mathematical problems;

  1. Factoring large numbers. In RSA case, finding the factors of $n$. The Current record is 768-bit. There is no known Polynomial-time algorithm for factoring. The best-known algorithms are sub-exponential.

  2. RSA problem: finding the $e$-th root of an arbitrary number. There is no efficient method exit for large key sizes > 1024.

The most efficient method of RSA problems is factoring $n$. if you can solve RSA problem you can access the messages and this is a successful attack breaking a cryptosystem.

The break of a scheme requires revealing the plaintext(s). Tough many attacks based on finding the encryption keys, finding the key is not necessary it is sufficient.


Equivalence of your problem into factoring

Let define problem $B$ as given $c$ and the public key $(e,n)$ finding the $d$ in an RSA setup.

$$c^d \bmod(n)=m$$

  • Let $\mathcal{A}$ the algorithm that solves the problem $B$. Then, by using Fact 1 we can factor $n$ in $\mathcal{O}(N^3)$-time where $N=\log_2 n$ given $(e,d,n)$
  • Similarly, it is clear once we factor $n = p \cdot q$ we can find the $d$ as in the RSA key-gen.

So the problem $B$ is equivalent to factoring.

$\endgroup$
  • $\begingroup$ Does this mean that factoring $n$ is easier than solving the equation I posted? If so, why is that? Because it doesn't like that to me. $\endgroup$ – Willy Dec 19 '18 at 14:19
  • $\begingroup$ > Just as there are no proofs that integer factorization is computationally difficult, there are also no proofs that the RSA problem is similarly difficult. $\endgroup$ – kelalaka Dec 19 '18 at 14:20
  • $\begingroup$ Is the RSA problem what I described? Because I don't see how you could compare it to the type of equation I posted. $\endgroup$ – Willy Dec 19 '18 at 14:23
  • $\begingroup$ @Willy I've updated the answer. $\endgroup$ – kelalaka Dec 21 '18 at 19:36
  • $\begingroup$ "So the problem $B$ is equivalent to factoring." This does answer my question, although I don't really understand how you came to this conclusion. Thanks for the answer though. $\endgroup$ – Willy Dec 22 '18 at 20:14
2
$\begingroup$

There are "hidden unknowns" in the notation. Suppose that $n$ is the modulus, $e$ the public exponent, $d$ the private exponent. Given a message $m$, its encrypted value is $c = m^e \bmod n$ (I am ignoring padding here), and you can certainly choose a message $m$ and compute $c$ given the public elements $e$ and $n$ (that's how RSA encryption works). Now, you might want to find $d$ by solving the following equation: $$ c^d = m \bmod n $$ with only $d$ being unknown.

When working with real numbers, an equation of the form: $$ a^x = b $$ for given values $a$ and $b$, is solved as: $$ x = \frac{\ln b}{\ln b} $$ and you could imagine that "solving RSA" is just a matter of computing logarithm with the required precision.

However, this would neglect an important part, which is somewhat hidden in the notation. When we work "modulo $n$", we are actually having the following: $$ c^d = m + kn $$ for the known ciphertext $c$, message $m$ and modulus $n$, unknown private exponent $d$, and unknown integer $k$. At that point, you have a single equation with two unknowns, and the usual tools of analysis with real numbers (e.g. logarithms) won't help at all.

In all generality, RSA is expressed in algebraic things such as rings of integers modulo $n$, and all equation solving activities in such things have their own rules, quite distinct from what you may have learned with real numbers. Obtaining $d$ from $e$ can be done relatively easily when $n$ is prime, but, of course, the crux of RSA is that $n$ is not prime.

We do not have any proof that factoring $n$ into its factors is really required to recover an unknown plaintext from the ciphertext. We do know that recovering the private exponent $d$ is equivalent to factoring $n$ (i.e. if you factor $n$ you can easily obtain $d$ from $e$, and if you somehow obtained $d$ and $e$ you can easily factor $n$); but there could be a method by which a ciphertext can be decrypted without revealing the private exponent itself. Right now, factoring $n$ is the best attack we know of; and factoring big integers is a problem that has been studied for quite some time (more than 2500 years, in fact), and the only sure thing we know is that there is no obviously easy solution. There might be an efficient factoring method, but it is definitely not obvious.

$\endgroup$
  • $\begingroup$ >However, this would neglect an important part, which is somewhat hidden in the notation. When we work "modulo n", we are actually having the following: $c^d=m+kn$. I don't understand this part. Could you explain this? $\endgroup$ – Willy Dec 19 '18 at 14:32
  • $\begingroup$ @Willy The "modulo" operation is an integer division, and we keep only the remainder. This means that we subtract or add some multiple of the modulus $n$. The $kn$ value is that multiple of $n$ that we add and subtract. Solving for $d$ would also entail finding the right $k$, and we cannot do both at the same time with the tools meant for real numbers. $\endgroup$ – Thomas Pornin Dec 19 '18 at 15:03
  • $\begingroup$ I almost understand what you're saying but I'm stuck with "This means that we substract or add some multiple of the modulus $n$." I don't really see what you mean with this. $\endgroup$ – Willy Dec 19 '18 at 15:18

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.