# Java Program to Implement the RSA Algorithm

**RSA** or **Rivest–Shamir–Adleman** is an algorithm employed by modern computers to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys. This is also called public-key** **cryptography because one among the keys are often given to anyone. The other is the **private key** which is kept private. The algorithm is predicated on the very fact that finding the factors of an outsized number is difficult: when the factors are prime numbers, the matter is named prime factorization. It is also a key pair (public and personal key) generator.

Attention reader! Don’t stop learning now. Get hold of all the important **Java Foundation** and Collections concepts with the **Fundamentals of Java and Java Collections Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

**Example:**

Generating Public Key1. Select two prime no's. Suppose P = 53 and Q = 59. Now First part of the Public key : n = P*Q = 3127. 2. We also need a small exponent say e : But e Must be -An integer. -Not be a factor of n. -1 < e < Φ(n) [Φ(n) is discussed below], Let us now consider it to be equal to 3. The public key has been made of n and eGenerating Private Key1. We need to calculate Φ(n) : Such that Φ(n) = (P-1)(Q-1) so, Φ(n) = 3016 2. Now calculate Private Key, d : d = (k*Φ(n) + 1) / e for some integer k 3. For k = 2, value of d is 2011. The private key has been made of d

**Implementation of RSA Algorithm:**

- Consider two prime numbers p and q.
- Compute n = p*q
- Compute ϕ(n) = (p – 1) * (q – 1)
- Choose e such gcd(e , ϕ(n) ) = 1
- Calculate d such e*d mod ϕ(n) = 1
- Public Key {e,n} Private Key {d,n}
- Cipher text C = Pe mod n where P = plaintext
- For Decryption D = Dd mod n where D will refund the plaintext.

Below is the implementation of the above approach:

## Java

`// Java Program to Implement the RSA Algorithm` `import` `java.math.*;` `import` `java.util.*;` `class` `RSA {` ` ` `public` `static` `void` `main(String args[])` ` ` `{` ` ` `int` `p, q, n, z, d = ` `0` `, e, i;` ` ` `// The number to be encrypted and decrypted` ` ` `int` `msg = ` `12` `;` ` ` `double` `c;` ` ` `BigInteger msgback;` ` ` `// 1st prime number p` ` ` `p = ` `3` `;` ` ` `// 2nd prime number q` ` ` `q = ` `11` `;` ` ` `n = p * q;` ` ` `z = (p - ` `1` `) * (q - ` `1` `);` ` ` `System.out.println(` `"the value of z = "` `+ z);` ` ` `for` `(e = ` `2` `; e < z; e++) {` ` ` `// e is for public key exponent` ` ` `if` `(gcd(e, z) == ` `1` `) {` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `System.out.println(` `"the value of e = "` `+ e);` ` ` `for` `(i = ` `0` `; i <= ` `9` `; i++) {` ` ` `int` `x = ` `1` `+ (i * z);` ` ` `// d is for private key exponent` ` ` `if` `(x % e == ` `0` `) {` ` ` `d = x / e;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `System.out.println(` `"the value of d = "` `+ d);` ` ` `c = (Math.pow(msg, e)) % n;` ` ` `System.out.println(` `"Encrypted message is : "` `+ c);` ` ` `// converting int value of n to BigInteger` ` ` `BigInteger N = BigInteger.valueOf(n);` ` ` `// converting float value of c to BigInteger` ` ` `BigInteger C = BigDecimal.valueOf(c).toBigInteger();` ` ` `msgback = (C.pow(d)).mod(N);` ` ` `System.out.println(` `"Decrypted message is : "` ` ` `+ msgback);` ` ` `}` ` ` `static` `int` `gcd(` `int` `e, ` `int` `z)` ` ` `{` ` ` `if` `(e == ` `0` `)` ` ` `return` `z;` ` ` `else` ` ` `return` `gcd(z % e, e);` ` ` `}` `}` |