For example say you had 2 prime numbers 509 997, it is very easy to multiply these two number to get 507473. But consider how much harder it is to find the only 2 prime numbers that are the factorization of 119641?
This example uses number which consist of 2 numbers which are 10bits long. International versions of Netscape use numbers 40bits in length. Canada/US versions of Netscape so so far as using 128bit number lengths.
The applet presented on our site uses numbers 512bits long. To get an appriciation of how secure our applet is, we'll go into a bit of math. If you don't want to see all this, just read the occasional comment and you'll get the idea!
| 2b | = | 10d | |
| b log(2) | = | d log(10) | |
| log(2) log(10) |
= | b |
|
| 0.30103 | = | binary length |
40bit = 12 digits long. 128bit = 39 digits long. 512bit = 154 digits long. Note: The estimated number of protons, neutrons and electrons in the observable universe is roughly 86 digits long! Estmate according to the late Carl Sagen from his pinacle "Cosmos" book and 13 part video series |
As massive as these numbers are, I should tell you that someone has actually factored such monsters. A 522bit number was factored in October of 1992 by Arjen Lenstra and Dan Bernstein. They used the most powerful factoring algorithm and theory publicly know so far: The Number Field Sieve. Here is a transcript:
In october 1992 Arjen Lenstra and Dan Bernstein, factored a 522-bit number into primes using the Number Field Sieve. It took three weeks on a massively parallel SIMD computer system (16384 processors, each capable of 200,000 additions per second). The particular number chosen was 2^523 - 1, a special form which could be factored considerably easier than most (as easily, in fact, as any future improvements in factoring are considered likely to make ordinary numbers). Addition is considerably faster than most CPU instructions. For these reasons, this is considered to be a conservative estimate; but for N=522, factoring required execution of approximately 8.5 x 10^8 instructions.
This attack was done on an "easy" number, so the our applet is what some people call "secure". The numbers used my us in our Java Applet are infact more secure than the one mentioned above. To explain why I will beifly discuss 3 "low end" factoring algorithims.
The Sieve of Eratosthenes is called a brute force attack. It goes threw every prime number starting at 2 and tests to see if it will divide the number in question. For a 512bit number, the isn't enough energy in the universe to power a computer long enough to crack our code.
Pollard P-1 is an attck that must be considerd very carefully for if you do not protect yourself, no matter how big your number is there is a chance that it will crack it very quickly. The number of loops needed to find the answer is roughly equal to p'.
| n | = | pq | Where p, q are prime numbers |
| p' | = | The largest prime number that will divide p-1 evenly |
Williams P+1 is simmilar to Pollard's P-1, except the run time is p'.
| n | = | pq | Where p, q are prime numbers |
| p' | = | The largest prime number that will divide p+1 evenly |
To protect you from these attacks, we did the following:
Find a prime number p''.
Find another prime p' such that p' = (p'')a + 1.
Find yet another prime p such that p = (p')b + 1.
Find a prime number q''.
Find another prime q' such that q' = (q'')c + 1.
Find yet another prime q such that q = (q')d + 1.
So now, our number n = pq will be protected from any "cheep and dirty" attacks. If someone wants to steal your credit card number, they'd better have a 16000 processor supercomputer running a higly optimized set of programs to crack our code using the most advanced techniques publicly known to the world and a couple months of dedicated crunch time.
Other sites of interest: