The term RSA is an acronym for Rivest-Shamir-Adleman who brought out the algorithm in 1977. RSA is an asymmetric cryptographic algorithm which is used for encryption purposes so that only the required sources should know the text and no third party should be allowed to decrypt the text as it is encrypted. RSA works on the fact that it is very hard to factorize large numbers (order of 100+ digits).
The term “Asymmetric” signifies that there are two keys public (known to all) and private (only at the receiver).
So, we need to calculate a private key and a public key for the implementation of RSA.
Public Key comprises of (n, e).
Private Key comprises of (n, d).
Cipher text (encrypted), C = Pe mod n
Plain text (decrypted), P = Cd mod n
Generating the Public Key:
We’ll first select two prime numbers P and Q, where P should not be equal to Q.
P = 7, Q= 11.
Once we have selected the numbers, we need to calculate the value of n and Ø.
n = P * Q
Here, n = 7 * 11 = 77
Ø = (P – 1) * (Q – 1)
Here, Ø = (7 – 1) * (11 – 1) = 6 * 10 = 60
Now, we’ll find the value of e.
Remember, e should be an integer such that, 1 < e < Ø
Also, e should be relatively prime with n.
Therefore, e = 13.
Our Public Key is made of n and e.
Generating the Private Key:
Now, we can calculate the value of d.
The value of d should be such that (d * e) mod Ø should be equal to 1.
i.e., (d * e) mod ø = 1
hence, here we have:
(d * 13) mod 60 = 1
d = (k * Ø + 1)/e, for some integer k.
For k = 8, value of d,
d = (8 * 60 + 1)/13
d = 37
Private Key made of n and d.
Our Public Key: (n = 77 and e = 3)
Our Private Key: (d = 37)
Let us encrypt our Plain Text “HELLO”.
1. First convert the message into a number m. Let us use the ASCII encoding. A: 65, B: 66 ……. Z: 90
“HELLO”: 7269767679
2. We’ll calculate the cipher text,
C = me (mod n)
C = 72697676793 (mod 60)
C = 39
3. To get back the plain text, we have
Cd = m (mod n)
3937 = m (mod 60)
m = 7269767679
Java Program for RSA Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
import java.io.DataInputStream; import java.io.IOException; import java.math.BigInteger; import java.util.Random; public class RSA { private BigInteger P; private BigInteger Q; private BigInteger N; private BigInteger PHI; private BigInteger e; private BigInteger d; private int maxLength = 1024; private Random R; public RSA() { R = new Random(); P = BigInteger.probablePrime(maxLength, R); Q = BigInteger.probablePrime(maxLength, R); N = P.multiply(Q); PHI = P.subtract(BigInteger.ONE).multiply( Q.subtract(BigInteger.ONE)); e = BigInteger.probablePrime(maxLength / 2, R); while (PHI.gcd(e).compareTo(BigInteger.ONE) > 0 && e.compareTo(PHI) < 0) { e.add(BigInteger.ONE); } d = e.modInverse(PHI); } public RSA(BigInteger e, BigInteger d, BigInteger N) { this.e = e; this.d = d; this.N = N; } public static void main (String [] arguments) throws IOException { RSA rsa = new RSA(); DataInputStream input = new DataInputStream(System.in); String inputString; System.out.println("Enter message you wish to send."); inputString = input.readLine(); System.out.println("Encrypting the message: " + inputString); System.out.println("The message in bytes is:: " + bToS(inputString.getBytes())); // encryption byte[] cipher = rsa.encryptMessage(inputString.getBytes()); // decryption byte[] plain = rsa.decryptMessage(cipher); System.out.println("Decrypting Bytes: " + bToS(plain)); System.out.println("Plain message is: " + new String(plain)); } private static String bToS(byte[] cipher) { String temp = ""; for (byte b : cipher) { temp += Byte.toString(b); } return temp; } // Encrypting the message public byte[] encryptMessage(byte[] message) { return (new BigInteger(message)).modPow(e, N).toByteArray(); } // Decrypting the message public byte[] decryptMessage(byte[] message) { return (new BigInteger(message)).modPow(d, N).toByteArray(); } } |
Output:
Enter message you wish to send.
hello world
Encrypting the message: hello world
The message in bytes is:: 10410110810811132119111114108100
Decrypting Bytes: 10410110810811132119111114108100
Plain message is: hello world
