If one of
the primes p or q was small then searching through
all the numbers would quickly crack the code.
Fermat's trick relies on a simple piece of algebra,
namely that
pxq=((p+q)/2)2-((p-q)/2)2.
What does this little bit of algebra mean? That
every number N=pxq is actually the difference
between two squares A2 and B2
where A=(p+q)/2 and B=(p-q)/2.
Now finding these two squares is generally as
difficult as finding the primes, but if you can
find them you can quickly find the two primes
p and q since p=A+B and q=A-B. But what if one
of the squares is very small. Then by a bit of
trial and error, we will find it quickly, just
in the same way as if one of the primes had been
small. So if Amazon choose their big primes too
close together, then the second square B2
=((p-q)/2)2 is small so can be uncovered
quickly and the code is cracked.
Example: Try to crack 8051
Start by noticing 90x90 is 8100. This is very
close to what we want. We just have to subtract
49 which is 7x7.
8051=8100-49=902-72
Now we use the algebra:
p-q = 2x7 and p+q=2x90 so 2p = p-q +p+q = 2x7
+2x90. Hence p=97 and q=83.
|
