CRYPTOLOGY - Hacking: The Art of Exploitation - page 400

Without some way to manipulate the odds of the superposition states,
the same effect could be achieved by just guessing keys. Fortuitously, a man
named Lov Grover came up with an algorithm that can manipulate the odds
of the superposition states. This algorithm allows the odds of a certain desired
state to increase while the others decrease. This process is repeated several
times until the decohering of the superp o sition into the desired state is
nearly guaranteed. This takes about steps.
Using some basic exponential math skills, you will notice that this just
effectively halves the key size for an exhaustive brute-force attack. So, for the
ultra paranoid, doubling the key size of a block cipher will make it resistant
to even the theoretical possibilities of an exhaustive brute-force attack with a
quantum computer.

On

0x740 Asymmetric Encryption

Asymmetric ciphers use two keys: a public key and a private key. The public
key is made public, while the private key is kept private; hence the clever names.
Any message that is encrypted with the public key can only be decrypted with
the private key. This removes the issue of key distribution—public keys are
public, and by using the public key, a message can be encrypted for the
corresponding private key. Unlike symmetric ciphers, there's no need for an
out-of-band communication channel to transmit the secret key. However,
asymmetric ciphers tend to be quite a bit slower than symmetric ciphers.

0x741 RSA

RSA is one of the more popular asymmetric algorithms. The security of RSA
is based on the difficulty of factoring large numbers. First, two prime numbers
are chosen, P and Q, and their product, N, is computed:

N = P · Q

Then, the number of numbers between 1 and N − 1 that are relatively
prime to N must be calculated (two numbers are relatively prime if their greatest
common divisor is 1). This is known as Euler's totient function, and it is usually
denoted by the lowercase Greek letter phi (φ).
For example, φ(9) = 6, since 1, 2, 4, 5, 7, and 8 are relatively prime to 9.
It should be easy to notice that if N is prime, φ( N ) will be N − 1. A somewhat
less obvious fact is that if N is the product of exactly two prime numbers, P
and Q , then φ( P · Q ) = ( P − 1) · ( Q − 1). This comes in handy, since φ( N )
must be calculated for RSA.
An encryption key, E , that is relatively prime to φ( N ), must be chosen
at random. Then a decryption key must be found that satisfies the following
equation, where S is any integer:

E · D = S · φ( N )+1

This can be solved with the extended Euclidean algorithm. The Euclidean
algorithm is a very old algorithm that happens to be a very fast way to calculate