1
$\begingroup$

So doing a little research on RSA, and knowing the public key contains N. So breaking down the steps to cracking it, I'd have to search for P and Q (which takes a very long time as I understand it), (where P*Q = N). aka, prime 1 and prime 2.

So it takes a long time to find a suitable prime pair. For me I see 2 actions and I want to know which action takes the longer time.

  1. Finding a 1024 prime number.
  2. Having 1 prime number and dividing N by testable prime number to see if it produces another prime, aka prime 2.

So is the time mostly spent finding prime 1 and THEN trying to factor out N, or is the time spent finding a large prime, but its easy to divide N by prime 1 and see it not work?

Sorry if this is confusing, I am having a hard time constructing the question.

Improve this question
$\endgroup$
1
  • $\begingroup$ Your strategy for finding the number in step 1 is made impractical by the fact that there are very many 1024-bit primes. See answer to another question math.stackexchange.com/a/263630 for estimate of amount of such primes existing. In practice you would end up trying step 2 very many times with "wrong" candidates, and this formula would take much longer than state of art factoring algorithms, which are also too slow for large modulus. $\endgroup$
    – user4982
    Dec 29, 2016 at 17:27

2 Answers 2

Reset to default
3
$\begingroup$

You seem to be under the impression that factorizing (finding P and Q) means to try many primes and hope to find the right one, aka the "brute force" solution. This is not the case, it would take forever. Eg. 1024bit means

179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

possible numbers. Even with the best computers, it would take far longer than the universe exists. And to start with, 1024 is in the past, nowadays 4096 is common.
...point is, there are better (and more complicated) factoring methods, and with quantum computers it gets much better again (sad for cryptographers :/).

Anyways, to answer your direct question: "Neither".
"Finding" a prime number actually means

Take any number and run some checks if it could be prime. If the check says "could be" often enough, then let's say it is a prime.

Why? Because getting hard evidence that a 4096bit number is prime is very slow too.

So, finding a prime means running checks. Checking if the second number (after division) is prime means running the same checks. There is no difference other than the division.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Your 'possible numbers' appears to count all nonnegative integers less than 2^1024, but in crypto we use 1024-bit to mean less than 2^1024 but NOT less than 2^1023; this is only 2^1023. We usually limit RSA primes to the top half of the N-bit range to make their product exactly 2N-bit, so half again. And the number of primes among those 2^1022 numbers is quite a bit less -- almost 3 orders of magnitude -- though still large. And most people now are using 1024-bit factors=2048-bit modulus; some use 4096-bit modulus but I think hardly anyone uses 4096-bit factors. $\endgroup$
    – dave_thompson_085
    Jan 6, 2017 at 16:33
0
$\begingroup$

Cracking RSA requires you to find the two prime factors of $n$. This is difficult; because the factors $p$ and $q$ are prime, the only numbers that divide $n$ (other than itself and $1$) are $p$ and $q$. It would take way too long to find a suitable $p$ or $q$ using the naive approach of "just try everything". Even if you find some other prime number, it still probably won't divide $n$.

Some very smart people have come up with better algorithms; the two fastest-known ones are the quadratic sieve and the general number field sieve. They're faster than trying everything, but still very slow.

In fact, it's good that prime factorization (and thus cracking RSA) is slow; if it was fast, everyone would do it, and RSA wouldn't be useful at all—what's the point of an encryption scheme that anyone can break?

Just generating a key is much easier, though. You pick $p$ and $q$ first, then multiply them to get $n$. After computing the other magical values like $e$, $d$, and $\phi$, you then release $n$ and $e$ to the public and keep the rest private. That way, you can read the messages using the secret values, but everyone else would have to factor $n$ to do the same. That's the point of public-key cryptography.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.