Can Discovering a Formula for the Nth Prime Compromise Online Security?

[hddd123456789]

Let's say you discovered a discreet, simple formula that gave you the nth prime. Ok, but now being a web developer, I'm somewhat familiar with the use of large primes for online security. Now if you published this formula, wouldn't you be essentially responsible for compromising the better part of online security? (I could be wrong about primes forming the "better"-part of online security, but they're certainly an important one none-the-less I think).

 

[PeteyCoco]

It's the duty of the other guy to pick safe passwords; it was their decision to place faith in prime numbers. If such a formula does exist and is found, I'm sure it will make for a great footnote in future math texts to show how "backwards" those guys from the 21st century were that they thought primes were safe.

 

[hddd123456789]

I this case, the password you choose is unlikely to make much of a difference. From what I understand, knowing the nth prime could potentially allow a hacker sniffing online traffic to decrypt an otherwise secure and encrypted connection, one which, for example, was being used to send a user's password to the server when logging in.

I don't know, I doubt an algorithm responsible for securing much of if not all of internet communication could be deemed as "backwards" anytime soon. I guess we'll hope that such a nice simple formula doesn't exist :P

 

[Borek]

Coding/decoding - at least for RSA - is based not on knowing nth prime, but on factoring primes product. My understanding is that the cost of finding primes during factorization is negligible (but I can be wrong).

 

[hddd123456789]

I'm somewhat familiar with how RSA works, and I'm not at all suggesting that knowing the nth prime will reveal a straight forward path to breaking RSA, but straight-forward or not, it may well be its Achilles' heal. I'm no number theorist, but I'm sure that combining a knowledge of the nth prime with some number-theoretic methods will allow you to quickly determine which primes might be factors of some arbitrarily large number.

The simplicity of the assumed function is meant to imply that if I can know the nth prime, then I should be able to solve for n and in turn solve for the index of an arbitrarily large prime number. The prime counting function, π(x), that tells you the (approximate?) number of primes less than a number x might play a role here as well.

So, anyone find that there really isn't anything to worry about?

 

[hddd123456789]

My understanding is that the cost of finding primes during factorization is negligible (but I can be wrong).

From what I gather, the very strength of RSA is based on the difficulty in determining the two prime factors that multiply together to produce an arbitrarily large number. And by arbitrarily large, I mean a number that might have several hundred digits, or more. To find which two primes are factors would require one to determine whether the numbers we are looking at is prime or not. And if the prime factors are in themselves large enough, then no computer can determine this in a useful amount of time.

 

[DavidSnider]

Let's assume we have already calculated all 1024 bit primes so that Prime(n) runs in O(1) time.

Then what?

 

[hddd123456789]

Let's assume we have already calculated all 1024 bit primes so that Prime(n) runs in O(1) time.

Then what?

1024 bit numbers means roughly 2^1024 or 1.79*10^308 possible permutations. To be useful, it would need to be stored in a database. I'm thinking on the fly here, but this would require 2^1024 rows of 1024 bit numbers. That's roughly (2^1024)*1024 bits, I think. Point being, you can't store all those numbers in the world's worth of hard drives. If you could then this would be the classic dictionary attack which is commonly used against hashing algorithms.

 

[DavidSnider]

2^1024 would only store all the prime numbers.

To perform a dictionary attack on a public key you would have to index the product of every pair of those prime numbers.

 

[-Job-]

Coding/decoding - at least for RSA - is based not on knowing nth prime, but on factoring primes product. My understanding is that the cost of finding primes during factorization is negligible (but I can be wrong).

Integer factorization is a difficult problem to solve using current technology.

In Computer Science, problems are grouped according to time complexity. Generally speaking, problems in the complexity class P are efficiently solved by today's computers, even for large instances (e.g. sorting a million numbers can be done in a few million operations).

The problem of factorization is contained in the complexity class BQP and is only known to be efficiently solvable by Quantum Computers.

Factoring large integers, of hundreds or thousands of digits, is not viable even in today's super computers, using the best known algorithms - this is not to say that it's impossible. Integer Factorization has not been proven to not be in P - it's actually an open problem in Computer Science.

A related problem, Primality Testing, which asks whether a given number is a prime, is efficiently solvable - it was proven to be in P in 2002.

The popularity of RSA based encryption is one reason why governments have a particular interest in Quantum Computers.

 

[-Job-]

From what I gather, the very strength of RSA is based on the difficulty in determining the two prime factors that multiply together to produce an arbitrarily large number. And by arbitrarily large, I mean a number that might have several hundred digits, or more. To find which two primes are factors would require one to determine whether the numbers we are looking at is prime or not. And if the prime factors are in themselves large enough, then no computer can determine this in a useful amount of time.

Determining whether a number is prime can be efficiently computed using AKS but, as you allude to, identifying the prime factors for an n-bit number, requires potentially checking all 2^n-1 possible divisors - which is not feasible for large numbers.

However, there may well be a strategy by which a number may be factored in n^c operations for some constant c - it's an open question. An efficient factoring algorithm would be quite a significant achievement in the field of Computer Science (and quite possibly a national threat).

It might interest you that there is another computational problem that is also not known to be efficiently solvable, Graph Isomorphism, which asks whether two graphs of n nodes are essentially the same graph.

Graph Isomorphism and Integer Factorization sit in the same "unknown spot", between the complexity classes P and NP-Complete, not known to belong to either one.

These open questions in Computer Science are a lot of fun to think about if you enjoy a good puzzle - why can't we determine whether two graphs are the same in n² operations?

 

[K^2]

From what I gather, the very strength of RSA is based on the difficulty in determining the two prime factors that multiply together to produce an arbitrarily large number. And by arbitrarily large, I mean a number that might have several hundred digits, or more. To find which two primes are factors would require one to determine whether the numbers we are looking at is prime or not. And if the prime factors are in themselves large enough, then no computer can determine this in a useful amount of time.

No. RSA does not need the two numbers to be prime. Only relatively prime. The methods used to generate these two primes can actually give you non-prime numbers occasionally, and the method still works. The reason you want two prime numbers is because having extra factors makes it that much easier to find one.

At any rate, the process boils down to factorization problem, and knowing primes only speeds up the process by a factor of number of non-prime numbers you can skip. Since number of primes goes roughly as n/ln(n), a very simple formula for Nth prime only gives you an advantage of ln(n), which would still keep long keys completely safe.

On another hand, having ability to get Nth prime would make it easier to generate RSA keys of significant length. Since computational intensity is the main limit on how long you want keys for particular application, odds are, discovering formula for Nth prime would actually make RSA more secure.

That's roughly (2^1024)*1024 bits, I think. Point being, you can't store all those numbers in the world's worth of hard drives.

And by "world", you can safely mean the observable universe. In fact, there isn't enough matter in the universe to store this much information classically.