next up previous
Next: ``Proofs" Up: Quantum Computing Notes Previous: Factoring


One of the reasons that the Shor factoring algorithm caused such a stir, is that one of the cryptographic techniques which had come into widespread use in the 90s was the RSA public key cryptographic algorithm. RSA was invented first by GCHQ, the British Codebreaking establishment in the early 70's, but was kept secret by them. It was then reinvented by Rivest Shamir and Adelman (thus RSA) in the late 70s.

One of the key difficulties with all cryptography is the exchange of keys. Many systems have been invented which offer very great security, but all depend on both the sender and the receiver having receipt of a key. This is true of the unconditionally secure "One Time Pad" as it is of various other algorithms like DES, Blowfish, Enigma,.... Although one can imagine generating a secure channel, via quantum cryptography, highly trusted couriers, or face to face meetings, the key exchange is most problematic and difficult feature of cryptography.

In the late 70's Diffie and Hellman (in the public literature anyway) pointed out the possibility ( and a specific example) of what has come to be called public key cryptography. In this type of cryptography, there exist two keys. One is used to encrypt the message, and the other to decrypt. Furthermore the encryption key is such that even if an enemy knows the encryption key and knows the algorithm used to encrypt the message, he cannot use that information to discover what the private key is, and thus cannot decrypt any messages. That such a system was even possible came as a complete surprise to the cryptographic community.

Instead of discussing the Diffie Hellman procedure and variants thereof, I will limit myself to to the RSA technique. The RSA technique begins by finding two prime numbers $p$ and $q$. These two primes must be kept secret. These primes are multiplied together to give a composite number $R$. This number $R$ will be made public as a part of the public key. In addition the person chooses a number $e$, which will also be made public. This number must be chosen so that $e$ and the the numbers $p-1$ and $q-1$ have no factors in common. A common choice for $e$ is 17, or $37$. It is usually chosen small so as to make the work of anyone encrypting a message to you easy to carry out.

The encryption process is carried out by breaking the message up into numbers less than $R$ (but greater than $R^{2/e}$- in fact the number is padded so as to always make is greater than $R/2$). Call this number $M$ for message. The encrypted messages is now obtained by calculating the number

C= (M^e)_{mod_R}
\end{displaymath} (19)

Note that this is not done by exponentiating $M$ and then dividing by $R$ and finding the remainder taking the remainder. Rather using the fact that $(ab)_{mod~R}=(a_{mod~R} b_{mod_R})$, $C$ is calculated by successively squaring M, taking the modulus at each squaring and then multiplying together the appropriate powers of M, taking the remainder at each multiplication. In this way one never deals with products longer than twice the length of $R$.

Because of the random "wrapping" that taking the modulus does (ie the remainder seems to have no particular relation to the original) it seems that even knowing what $R$ and $e$ are the attacker cannot take the logarithm to discover what the original message $M$ was.

However, knowing $p$ and $q$, the recipient can determine the original message. He defines another number $d$ such that

(de)_{mod~(p-1)(q-1)} =1
\end{displaymath} (20)

I.e., knowing $p$ and $q$, one can find $(p-1)(q-1)$ and then find the value of $d$ wish solves this equation.

The theorem then is that for any number $a<R$, which does not have $p$ or $q$ as factors,

\end{displaymath} (21)

Thus taking the encrypted message $C=(M^e)_{mod~R}$ and raising it to the power of $d$ mod $R$, will give
(C^d)_{mod~R}= ((M^e_{mod~R})^d)_{mod~R}=((M^e)^d)_{mod~R}=M
\end{displaymath} (22)

The secret key $d$ must be kept secret,or anyone can decrypt the messages. However, unless the attacker knows $p$ and $q$, he can not figure out what $d$ is from $e$ and $R$. Thus if he can factor $R$, he will know $p$ and $q$ and thus $d$.

The best classical algorithm (the Number field sieve) has an estimated number of operations required to find the factors of order

e^{1.92 (ln(R))^{1\over 3} (ln(ln(R)))^{2\over 3} }
\end{displaymath} (23)

For R a 2000 bit number, this comes out to approximately $10^{35}$ operations. Considering $10^{18}$ seconds in the age of the universe, the factoring of such a number would require $10^{17}$ operations per second. Even at a Gigaop ($10^9$ operations per second) rate, this requires of order $10^8$ computers (or $10^5$ Terraop computers).

Note that this rate is still far far faster than "exhaustive search" in which one tries all numbers less than $\sqrt{N}$ to see if they divide $N$. Assuming that each such trial division takes about $ln_2(R)^2$ operations ($10^6$), there are still $2^{1000}\approx 10^{300}$ such operations required, for a total of about $10^{306}$ operations to factor by exhaustive search.

For an introduction to Cryptography, see for example

(This latter one is somewhat outdated by now)

Also see the excellent review of current cryptography in Bruce Schneier's Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd Edition John Wiley & Sons; ISBN: 0471117099

next up previous
Next: ``Proofs" Up: Quantum Computing Notes Previous: Factoring
Bill Unruh