RSA

In cryptography, RSA (which stands for Rivest, Shamir, and Adleman who first publicly described it ; see below) is an algorithm for public-key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys and the use of up-to-date implementations.

Public key algorithm invented in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman (RSA)
􀀀Supports Encryption and Digital Signatures
􀀀Most widely used public key algorithm
􀀀Gets its security from integer factorization problem
􀀀Relatively easy to understand and implement
􀀀Patent free (since 2000)

Operation
The RSA algorithm involves three steps: key generation, encryption and decryption.

RSA Usage
RSA is used in security protocols such as;
􀀀IPSEC/IKE - IP data security
􀀀TLS/SSL - transport data security (web)
􀀀PGP - email security
􀀀SSH - terminal connection security
􀀀SILC - conferencing service security

RSA Security

RSA gets its security from factorization problem. Difficulty of factoring large numbers is the basis of security of RSA. Over 1000 bits long numbers are used.
􀀀Integer factorization problem (finding number's prime factors):
􀀀Positive integer n, find its prime factors: n = p1 p2 ... pi where pi is positive distinct prime number
􀀀Example: 257603 = 41 * 61 * 103
􀀀Factorization algorithms can be used (attempted at least) to factor faster than brute forcing: Trial division, Pollard's rho, Pollard's p-1, Quadratic sieve, elliptic curve factorization, Random square factoring, Number field sieve, etc.

RSA Problem 􀀀
RSA Problem (RSAP) is also the basis of security of RSA, in addition of factorization problem. The RSA problem assures the security of the RSA encryption and RSA digital signatures.

Implementation Tools 􀀀
In order to implement RSA you will need:
􀀀Arbitrary precision arithmetic (multipleprecision arithmetic)
􀀀Pseudo Random Number Generator (PRNG)
􀀀Prime number generator
􀀀Difficulty of implementation greatly depends of the target platform, application usage and how much of the tools you need to implement from scratch.