Graphics Programs Reference
In-Depth Information
Since this is all done modulo N , the following is also true, due to the way
multiplication works in modulus arithmetic:
M φ( N )
· M φ( N )
=1·1(mod N )
M 2 · φ( N )
=1(mod N )
This process could be repeated again and again S times to produce this:
M S · φ( N )
=1(mod N )
If both sides are multiplied by M , the result is:
M S · φ( N ) · M =1· M (mod N )
M S · φ( N ) + 1
= M (mod N )
This equation is basically the core of RSA. A number, M, raised to a power
modulo N, produces the original number M again. This is basically a function
that returns its own input, which isn't all that interesting by itself. But if this
equation could be broken up into two separate parts, then one part could be
used to encrypt and the other to decrypt, producing the original message
again. This can be done by finding two numbers, E and D, that multiplied
together equal S times φ( N ) plus 1. Then this value can be substituted into
the previous equation:
E · D = S · φ( N )+1
M E · D
= M (mod N )
This is equivalent to:
M E D
= M (mod N )
which can be broken up into two steps:
ME = C (mod N )
CD = M (mod N )
And that's basically RSA. The security of the algorithm is tied to keeping
D secret. But since N and E are both public values, if N can be factored into
the original P and Q , then φ( N ) can easily be calculated with ( P − 1) · ( Q − 1),
and then D can be determined with the extended Euclidean algorithm. There-
fore, the key sizes for RSA must be chosen with the best-known factoring
algorithm in mind to maintain computational security. Currently, the best-
known factoring algorithm for large numbers is the number field sieve (NFS).
This algorithm has a subexponential run time, which is pretty good, but still
not fast enough to crack a 2,048-bit RSA key in a reasonable amount of time.
0x742
Peter Shor's Quantum Factoring Algorithm
Once again, quantum computation promises amazing increases in computa-
tion potential. Peter Shor was able to take advantage of the massive parallelism
of quantum computers to efficiently factor numbers using an old number-
theory trick.
Search WWH ::




Custom Search