RSA description and algorithm

RSA stands for Rivest, Shamir, and Adleman, they are the inventors of the RSA cryptosystem. RSA is one of the algorithms used in PKI (Public Key Infrastructure), asymmetric key encryption scheme. RSA is a block chiper, it encrypt message in blocks (block by block).

RSA can be used for security (encryption), confidentiality (signature), and key exchange purposes.
Nowadays, it is often used for signature and key exchange only, this is because the encryption and decryption are slow, it consumes times.

RSA security is so much depends on the difficulty of factoring large prime number. At this time (writing time, 2001) the calculation required to find the factor the value to break the key is slow, many cryptanalysts consider that linear attack and differential attack are difficult to applied in RSA, only mathematical attack (eg: number field sieve factoring algorithm by John M. Pollard) and brute force are feasible, but the time needed to use these attacks are quite long, therefore they are considered as impractical. May be later in the future as computer speed increased, this encryption algorithm may consider insecure and unused, but dont forget we can just simply increase the size of the key to prevent it from attacker. The common size for the key length now is 1024 bits for P and Q, therefore N is 2048 bits, if the implementation (the library) of RSA is fast enough, we can double the key size.

Below is the algorithms for creating key, encryption, decryption, the signing is the same like decryption and verification is the same like encryption. These three main functions are very simple.

1. Creating keys:
   1. Generate (find) two large prime numbers (P and Q)
   2. Calculate N = PQ
   3. Calculate M = phi(N) = (P - 1)(Q - 1) = (Euler totient function)
   4. Select any integer E, the rules to select E are:
   

   a. E is positive integer b. 0 < E < M c. GCD (M, E) = 1 ... (GCD = Greater Common Divisor) NOTE: It is recommended to use E = 65537 (17 bits).

   5. Calculate D a use Extended Euclid Theorem (mod inverse)
   

   (E * D) = 1 (mod M) (E * D) mod M = 1

   
   Public key: E, N
   Private key:
   

   Normal (slow):	D and N
   Chinese Remainder Theorem (faster):	P, Q, dP, dQ, invQ dP = E * dP mod (P-1) = 1 dQ = E * dQ mod (Q-1) = 1 invQ = Q * invQ mod P = 1

   
   

2. Encryption / Verification:
   Original plain text (a block value) = X ... X < N
   Chipertext = C ... C = (X^E) mod N

3. Decryption / Signing:
   Chipertext = C
   Dechiper text = Y
   

   Normal (slow way):	Y = (C^D) mod N
   CRT (faster way):	M1 = (C^dP) mod P M2 = (C^dQ) mod Q H = (M1 - M2) invQ mod P Y = M2 + (Q * H)

If everything goes fine, the value of Y and X should be equal (Y = X), otherwise there is must be something wrong with the program (implementation).

Note that both encryption and decryption in RSA involve raising a large integer power followed by mod operation. If the exponential is first done over the two values and then reduced by the modulo, this operation requires very big space and many computing power, but we can reduce (divide) the exponent value by 2 then continue with mod operation, repeating this simple operation is faster and use less space and less computing power. A SIMPLE pseudo code for this algorithm is below:

E = exponential value,
M = message to encrypt,
N = modulo value
C = chipertext value

C = 1 ... set it as default value
While E

If E is odd

C = C * M

C = C % N

E = E / 2

M = M * M

M = M % N

While Loop

But of course this simple mod exponential calculation is slow, montgomery's mod exp is fast and it is implemented in BN module (from OpenSSL, www.openssl.org).

High-Speed RSA Implementation document by Cetin Kaya Koc (koc@ece.orst.edu) is a good reference for anyone who want to create RSA library, the document explain the number theory used in RSA, it only describes the faster way of math calculation behind RSA.

Also any RSA implementation should compatible to PKCS#1, the last version is v2.1(pdf), also read the RSA OAEP specification (pdf), this document is available in RSA web site (www.rsa.com), this is unnecessary to be done if you only want to used it in a private group only.

Any suggestion or question about this RSA article is welcome, just email me.