Friday, July 18, 2014

Cracking AES or RSA encryption using light

AES and RSA encryption rely on determining whether a large number is prime.  This is hard in the sense of computational difficulty since it takes a long time to determine whether, say, 23409283889381 is prime.

You can try dividing 23409283889381 by every integer below it greater than 1, and seeing if there's a remainder.  This is called "trial division" and would rely on fast methods of computing 'mod' function.

Like this:

5 mod 3 = 2
10 mod 5 = 0

i.e.

If we have X mod Y = 0 then Y divides X and X is not prime.

Fast computational methods use the 'crossoff method' where we list all numbers in sequence and then cross of multiples of 2:

2,4,6,8, ...

then multiples of 3:

3,6,9,12,15

The 'holes' left over, i.e. 5, 7... are prime.  This is the basis behind various sieving methods.  Fast algorithms use the crossoff method since processors are better at multiplying than dividing.

Regardless, though, the crossoff method running with a 3.0 GHz processor and a lot of ram still takes a lot of time and couldn't possibly reach the large numbers that are required to crack 1024- or 2048- bit encryption.

Imagine, however, there were a setup of Young's double-slit experiment where we shine light (or a laser) at a small hole.  The effect is a set of parallel lines of light.  Now if these parallel lines of light are evenly spaced, and we measure the distance to each of the lines of light from, say, the left- hand side, and say the distance between the lines was 2 mm then we would have light lines at 2,4,6,8, ...mm corresponding to the multiples of 2,4,6,8 as above.  If we changed the distance of the light to the hole and the frequency of the light, we could get parallel lines spaced evenly apart at 3,6,9,12,15, mm.

If we then set up a reel of blank film (like in a camera) and exposed the light onto this film we would be able to very precisely tell where the holes (primes) are.  The accuracy of doing this would be limited only by how accurately our light rays and film could be - possibly to the molecular level or even atomic level.  If it's on the atomic level, then there's 127,000,000 units in one inch of film.  That's not nearly enough, though, to scale to what we need.  (We'd need a whole bunch of film).

Photons of light, however, don't have size.  And there are more advanced methods using lenses and optics and interferometry to do this (without film!), although I'm not a specialist in constructing such a thing.

The point, though, is that light travels infinitely fast so effectively the multiply operation takes zero time, and so does modulating the interval between integers (if many lights or many frequencies of light are shined simultaneously).
==

Update:

Oh whoops - these guys found this out first in 2009 I guess!

J.F. Clauser, J.P. Dowling, "Factoring integers with Young's $N$-slit interferometer"(preprint 10/2009)
[abstract:] "We show that a Young's $N$ slit interferometer can be used to factor the integer $N$. The device could factor four- or five-digit numbers in a practical fashion. This work shows how number theory may arise in physical problems, and may provide some insight as to how quantum computers can carry out factoring problems by interferometric means."