The Red Herring Threat to Asymmetrical Public Key Cyphers
Sven Gelbhaar
30 September 2008
Ever since I started using public key encryption schemes it has been
pointed out that looming on the horizon was the threat of Shor’s Algorithm
used in conjunction with Quantum Computers that may one day undo said
public key encryption. This, however, is most likely nothing but a
misleading, or at least futile approach to breaking such schemes.
For a complete breakdown of what Shor’s Algorithm sets out to do please
refer to the appropriate wikipedia entry. To summarize however, allow me
to quote the current entry:
The problem we are trying to solve is: given a composite number N, find an
integer p, strictly between 1 and N, that divides N.Shor’s algorithm
consists of two parts:
- A reduction of the factoring problem to the problem of order-finding,
which can be done on a classical computer. - A quantum algorithm to solve the order-finding problem.
Let’s backtrack a bit. Before we can even consider the algorithm itself we
have to look at its foundation Quantum Mechanics. Please refer to a
previous paper of mine entitled From Wave Theory to Quantum Mechanics for a
complete enumeration of how Quantum Mechanics are superfluous, and amounts
in practice to little more than probability theory.
Another argument against Quantum Mechanics not touched upon in that text is
that we have no concrete way of entangling photons, so how does one
construct such a computer? The current theory holds that by exposing a
crystal of beta barium borate to UV radiation that there’s a small
probability that this will result in a photon pair which is entangled, when
it is much more likely that these photons simple decay in a similar
progression. Yet we continue to multiply complexities needlessly.
Now back to Shor’s Algorithm; its basic premise as I understand it is to
use Quantum Computers to (stochastically) find factors for the primes which
make up the public/private key pair. However what it fails to take into
consideration is that this pseudo-random feature made possible by our lack
of sufficient technology to sample the sub-microscopic world will most
definitely return the same random factors to test, and if Probability
Theory is to be believed will probably be slower the larger the prime gets,
much like in our attempts to use classical computers to factor them.
So I have shown that Quantum Mechanics is improbable, that we have no real
way of building Quantum Computers, and that even if all of those problems
were overcome that Shor’s Algorithm would provide no real advantage in
breaking public key encryption schemes that any other pseudo-random number
generator couldn’t. After all of this we can only conclude that we really
have to go back to the drawing board as a society when pressed to find new
ways to break existing encryption schemes.