18-08-2012, 03:22 PM
RSA Algorithm
RSA.pdf (Size: 124.01 KB / Downloads: 53)
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.
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.
Arbitrary Precision Arithmetic
Used to handle large numbers (arbitrary in length)
Provides optimized implementations of arithmetic
operations such as modular computation and exponential
computation.
If you need to implement these yourself the task of
implementing RSA is usually large.
Several free libraries available (GMP, NSS MPI, Bignum,
etc).
RSA operations will use arbitrary precision arithmetic
(encryption, digital signatures).
RSA Key Generation
Select public exponent e, which is used as public key with n. It is used to encrypt messages
and to verify digital signatures. The e is stored for later with n. The e is usually small number
but it can be 1 < e <
. The e must be relatively prime to
, hence gcd(e,
) = 1 (gcd =
greatest common divisor, use Euclidean algorithm).
NOTES: Usually e is small to make encryption faster. However, using very small e (<16
bit number) is not recommended. A popular starting value for e is 65537. If e is not
relatively prime to
, then it is usually added by 2 untill it becomes relatively prime. This
makes the finding of e as fast as possible.
Compute private exponent d, which is the actual RSA private key. The d must not be
disclosed at any time or the security of the RSA is compromised. The d is found by
computing the multiplicative inverse d = e - 1 mod
. The extended Euclidean algorithm is
commonly used to compute inverses. The d exponent is used to decrypt messages and to
compute digital signatures.
NOTES: Implementations try to find as small d as possible to make decryption faster.
This is fine as long as it is assured that d is about the same size as n. If it is only onequarter
of size it is not considered safe to be used. It is possible to find a smaller d by
using lcm(p-1,q-1) instead of
(lcm = least common multiple, lcm(p-1,q-1) =
/ gcd(p-
1,q-1)). The PKCS#1 standard recommends this.