What is RSA algorithm and how to use RSA for encryption and decryption using java?

About RSA algorithm

The RSA algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. But the algorithm was released to the public domain by RSA Security on September 6, 2000.

Key generation Using RSA algorithm

RSA involves a public key and a private key. The public key can be shared by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The keys for the RSA algorithm are generated the following way:

RSA Algorithm Example 

           1. Choose two distinct prime numbers p and q. For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length.

Choose p = 3 and q = 11

      
 2. Compute n = pq. n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.

Compute n = p * q = 3 * 11 = 33

       
 3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1), where φ is Euler's totient function.

Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20

       
 4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e. e and φ(n) are coprime.

• e is released as the public key exponent.
• e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 216 + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.

Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7

5. Determine d as d⁻¹ ≡ e (mod φ(n)), i.e., d is the multiplicative inverse of e (modulo φ(n)).  This is more clearly stated as solve for d given d⋅e ≡ 1 (mod φ(n)) 
6.    This is often computed using the extended Euclidean algorithm.

         d is kept as the private key exponent.

7. Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]

Public key is (e, n) => (7, 33)

Private key is (d, n) => (3, 33)

The encryption of m = 2 is c = 2⁷ % 33 = 29

The decryption of c = 29 is m = 29³ % 33 = 2

Another working example to clear the RSA algorithm

Here is an example of RSA encryption and decryption.

1. Choose two distinct prime numbers, such as

p=61 and q=53.

2. Compute n = pq giving

n=61*53 = 3233.

3. Compute the totient of the product as φ(n) = (p − 1)(q − 1) giving

4. Choose any number 1 < e < 3120 that is coprime to 3120. Choosing a prime number for e leaves us only to check that e is not a divisor of 3120.

Let

5. Compute d, the modular multiplicative inverse of e (mod φ(n)) yielding 

       

The public key is (n = 3233, e = 17). For a padded plaintext message m, the encryption function is

     

The private key is (n = 3233, d = 2753). For an encrypted ciphertext c, the decryption function is c²⁷⁵³(mod 3233).

 

For instance, in order to encrypt m = 65, we calculate

  

To decrypt c = 2790, we calculate

Java example to use RSA algorithm to encrypt and decrypt secure information.

Jar files needed to execute the below program

1. FlexiCoreProvider-1.7p6.signed.jar

      2. CoDec-build21-jdk13.jar

AsymmetricEncryptionSampleUsingRSA.java

package com.gaurav.java.security;

import java.io.FileInputStream;

import java.io.FileOutputStream;

import java.security.KeyPair;

import java.security.KeyPairGenerator;

import java.security.PrivateKey;

import java.security.PublicKey;

import java.security.Security;

import javax.crypto.Cipher;

import javax.crypto.CipherInputStream;

import javax.crypto.CipherOutputStream;

import de.flexiprovider.core.FlexiCoreProvider;

public class AsymmetricEncryptionSampleUsingRSA {

      public static void main(String[] args) throws Exception {

            Security.addProvider(new FlexiCoreProvider());

            KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA", "FlexiCore");

            Cipher cipher = Cipher.getInstance("RSA", "FlexiCore");

            kpg.initialize(1024);

            KeyPair keyPair = kpg.generateKeyPair();

            PrivateKey privateKey = keyPair.getPrivate();

            PublicKey publicKey = keyPair.getPublic();

            /** This Code can be used to encrypt Data */

            cipher.init(Cipher.ENCRYPT_MODE, publicKey);

            String secureInformationFile = "C://secureInformation.txt";

            String ciphertextFile = "encryptedTextUsingRSA.txt";

            FileInputStream fileInputStream = new FileInputStream(

                        secureInformationFile);

            FileOutputStream fileOutputStream = new FileOutputStream(ciphertextFile);

            CipherOutputStream cipherOutputStream = new CipherOutputStream(

                        fileOutputStream, cipher);

            byte[] dataBlock = new byte[32];

            int dataItems;

            while ((dataItems = fileInputStream.read(dataBlock)) != -1) {

                  cipherOutputStream.write(dataBlock, 0, dataItems);

            }

            System.out.println("File Written successfully in encryption mode");

            cipherOutputStream.close();

            /** This Code can be used to decrypt data */

            String cleartextAgainFile = "decryptedTextUsingRSA.txt";

            cipher.init(Cipher.DECRYPT_MODE, privateKey);

            fileInputStream = new FileInputStream(ciphertextFile);

            CipherInputStream cipherInputStream = new CipherInputStream(fileInputStream, cipher);

            fileOutputStream = new FileOutputStream(cleartextAgainFile);

            while ((dataItems = cipherInputStream.read(dataBlock)) != -1) {

                  fileOutputStream.write(dataBlock, 0, dataItems);

            }

            System.out.println("File Written successfully in decryption mode");

            fileOutputStream.close();

      }

}

Content of secureInformation.txt

SecurePasswordIndia2013

Note: - encryptedTextUsingRSA.txt and decryptedTextUsingRSA.txt, these two file will be generated by code in the classpath location. encryptedTextUsingRSA.txt file will contain converted encrypted message corresponding to SecurePasswordIndia2013 and decryptedTextUsingRSA.txt will contain the same decrypted message value as SecurePasswordIndia2013.

 

Reference taken from http://en.wikipedia.org