The Math behind RSA algorithms
 
 

RSA is a public-key cryptosystem for both encryption and authentication; it was invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, who where working at the MIT
math labs.
 

It works as follows:

It is difficult (presumably) to obtain the private key d from the public key [n,e]. If one could factor n into p and q, however, then one could obtain the private key d. Thus the security of RSA is related to the assumption that factoring is difficult. An easy factoring method or some other feasible attack would “break” RSA.

Here is how RSA works in real life :

RSA privacy encryption: Suppose Jad wants to send a message m to Ziad. Jad
creates the ciphertext c by exponentiating: c=m^e mod n, where e and n are Ziad’s
public key. He sends c to Ziad. To decrypt, Ziad also exponentiates: m=c^d mod n; the
relationship between e and d ensures that Ziad correctly recovers m. Since only Ziad
knows d, only Ziad can decrypt the message m.

RSA authentication: Suppose Jad wants to send a message m to Ziad in such away
that Ziad is assured that the message is authentic and is from Jad. Jad creates a digital signature s by exponentiating: s=m^d mod n, where d and n are Jad’s private key. he then sends m and s to Ziad. To verify the signature, Ziad exponentiates and checks that the message m is recovered: m = s^e mod n, where e and n are Jad’s public key.

Thus encryption and authentication take place without any sharing of private keys: each person uses only other people’s public keys and his or her own private key. Anyone can send an encrypted message or verify a signed message, using only public keys, but only someone in possession of the correct private key can decrypt or sign a message.
 
 
 

Breaking RSA
 
 
This whole section has been taking from an excellent web document, the PGP attack FAQ, though I have a little modified it (it's a little old).
 
[ START OF CUT-OUT OF  "The PGP attack FAQ" ]
 RSA gets it's security from the apparent difficulty in factoring very large composites. However, nothing has been proven with RSA. It is not proved that factoring the public modulus is the only (best) way to break RSA. There may be an as yet undiscovered way to break it. It is also not proven that factoring *has* to be as hard as it is. There exists the possibility that an advance in number theory may lead to the discovery of a polynomial time factoring algorithm. But, none of these things has happened, and no current research points in that direction. However, 3 things that are happening and will continue to happen that take away from the security of RSA are: the advances in factoring technique, computing power and the decrease in the cost of computing hardware. These things, especially the first one, work against the security of RSA. However, as computing power
increases, so does the ability to generate larger keys. It is *much* easier to multiply very large primes than it is to factor the resulting composite (given today's understanding of number theory). 

      -- Brute Force RSA Factoring --

An attacker has access to the public-key. In other words, the attacker has e and n. The
attacker wants the private key. In other words the attacker wants d. To get d, n needs to be factored (which will yield p and q, which can then be used to calculate d).

Factoring n is the best known attack against RSA to date. (Attacking RSA by trying to deduce (p-1)(q-1) is no easier than factoring n, and executing an exhaustive search for values of d is harder than factoring n.) Some of the algorithms used for factoring are as follows:

      - Trial division: The oldest and least efficient. Exponential running time. Try all the
      prime numbers less than sqrt(n).

      - Quadratic Sieve (QS): The fastest algorithm for numbers smaller than 110 digits.

      - Multiple Polynomial Quadratic Sieve (MPQS): Faster version of QS.

      - Double Large Prime Variation of the MPQS: Faster still.

      - Number Field Sieve (NFS): Currently the fastest algorithm known for numbers larger
        than 110 digits. Was used to factor the ninth Fermat number.

These algorithms represent the state of the art in warfare against large composite numbers
(therefore against RSA). The best algorithms have a super-polynomial (sub-exponential)
running time, with the NFS having an asymptotic time estimate closest to polynomial behavior.

Still, factoring large numbers is hard. However, with the advances in number theory and
computing power, it is getting easier. In 1977 Ron Rivest said that factoring a 125-digit
number would take 40 quadrillion years. In 1994 RSA129 was factored using about 5000
MIPS-years of effort from idle CPU cycles on computers across the Internet for eight
months. In 1995 the Blacknet key (116 digits) was factored using about 400 MIPS-years of  effort (1 MIPS-year is a 1,000,000 instruction per second computer running for one year) from several dozen workstations and a MasPar for about three months. Given current trends the keysize that can be factored will only increase as time goes on. The table below estimates the effort required to factor some common PGP-based RSA public-key modulus lengths using the General Number Field Sieve:
 

                      KeySize         MIPS-years required to factor
              -----------------------------------------------------------------
                      512                     30,000
                      768                     200,000,000
                      1024                    300,000,000,000
                      2048                    300,000,000,000,000,000,000
 
 

            -- Chosen cipher-text attack --

An attacker listens in on the insecure channel in which RSA messages are passed. The
attacker collects an encrypted message c, from the target (destined for some other party). The attacker wants to be able to read this message without having to mount a serious factoring effort. In other words, she wants m=c^d.

To recover m, the attacker first chooses a random number, r < n. (The attacker has the
public-key [e,n].) The attacker computes:

x=r^e mod n (She encrypts r with the target's public-key)

 y=xc mod n (Multiplies the target ciphertext with the temp)

t=r^-1 mod n (Multiplicative inverse of r mod n)

The attacker counts on the fact that:

If x=r^e mod n, Then r=x^d mod n

The attacker then gets the target to sign y with her private-key,(which actually decrypts y)
and sends u=y^d mod n to the attacker.
The attacker simply computes:

tu mod n = (r^-1)(y^d) mod n = (r^-1)(x^d)(c^d) mod n = (c^d) mod n = m

To foil this attack do not sign some random document presented to you. Sign a one-way hash of the message instead.

      -- Timing attack against RSA --

A very new area of attack publicly discovered by Paul Kocher deals with the fact that different cryptographic operations (in this case the modular exponentiation operations in RSA) take discretely different amounts of time to process. If the RSA computations are done without the Chinese Remainder theorem, the following applies:

An attacker can exploit slight timing differences in RSA computations to, in many cases, recover d. The attack is a passive one where the attacker sits on a network and observes the RSA operations. The attacker passively observes operations measuring the time it takes to compute each modular exponentiation operation: m=c^d mod n. The attacker also knows c and n. 

      -- Keysizes --

It is pointless to make predictions for recommended keysizes. The breakneck speed at which technology is advancing makes it difficult and dangerous. Respected cryptographers will not make predictions past 10 years and I won't embarrass myself trying to make any. For today's secrets, a 1024-bit is probably safe and a 2048-bit key definitely is. I wouldn't trust these numbers past the end of the century. However, it is worth mentioning that RSA would not have lastest this long if it was as fallible as some crackpots with middle initials would like you to believe.
 
 

[ END OF CUT-OUT OF  "The PGP attack FAQ" ]