In a classic cryptosystem in order to make sure that nobody, except the intended recipient, deciphers the message, the people involved had to strive to keep the key secret. In a public-key cryptosystem. The public key cryptography solves one of the most vexing problems of all prior cryptography: the necessity of establishing a secure channel for the exchange of the key.

RSA algorithm is a public-key cryptosystem defined by Rivest, Shamir, and Adleman. The scheme is as follows:

Let p and q be distinct large primes and let n be their product. Assume that we also computed two integers, d (for decryption) and e (for encryption) such that

d * e 1 (mod ø(n))

The integers n and e are made public, while p, q, and d are kept secret.

Let m be the message to be sent, where m is a positive integer less than and relativley prime to n. A plaintext message is easily converted to a number by using either the alphabet position of each letter (a=01, b=02, ..., z=26) or using the standard ASCII table. If necessary (so that m<n), the message can be broken into several blocks.

The encoder computes and sends the number

m' = m^e mod n

To decode, we simply compute

e^d mod n

Now, since both n and e are public, the question arises: can we compute from them d? The answer: it is possible, if n is factored into prime numbers.

The security of RSA depends on the fact that it takes an impractical amount of time to factor large numbers. I will quote here a section on factoring from Cryptography FAQ (ftp://ripem.msu.edu/pub/crypt/sci.crypt/sci.crypt-faq.txt)

6.9. How fast can people factor numbers?

It depends on the size of the numbers, and their form. Numbers in special forms, such as a^n - b for `small' b, are more readily factored through specialized techniques and not necessarily related to the difficulty of factoring in general. Hence a specific factoring `breakthrough' for a special number form may have no practical value or relevance to particular instances (and those generated for use in cryptographic systems are specifically `filtered' to resist such approaches.) The most important observation about factoring is that all known algorithms require an exponential amount of time in the _size_ of the number (measured in bits, log2(n) where `n' is the number). Cryptgraphic algorithms built on the difficulty of factoring generally depend on this exponential-time property. (The distinction of `exponential' vs. `polynomial time' algorithms, or NP vs. P, is a major area of active computational research, with insights very closely intertwined with cryptographic security.)

In October 1992 Arjen Lenstra and Dan Bernstein factored 2^523 - 1 into primes, using about three weeks of MasPar time. (The MasPar is a 16384-processor SIMD machine; each processor can add about 200000 integers per second.) The algorithm there is called the ``number field sieve''; it is quite a bit faster for special numbers like 2^523 - 1 than for general numbers n, but it takes time only exp(O(log^{1/3} n log^{2/3} log n)) in any case.

An older and more popular method for smaller numbers is the ``multiple polynomial quadratic sieve'', which takes time exp(O(log^{1/2} n log^{1/2} log n)) - faster than the number field sieve for small n, but slower for large n. The breakeven point is somewhere between 100 and 150 digits, depending on the implementations.

Factorization is a fast-moving field - the state of the art just a few years ago was nowhere near as good as it is now. If no new methods are developed, then 2048-bit RSA keys will always be safe from factorization, but one can't predict the future. (Before the number field sieve was found, many people conjectured that the quadratic sieve was asymptotically as fast as any factoring method could be.)

You can also try Java emulation of RSA algorithm or find out more about RSA algorithm in RSA FAQ.