Question

you will create a program with Java to implement a simplified version of RSA cryptosystems. To complete this project, you may follow the steps listed below (demonstrated in Java code) to guide yourself through the difficulties.

Step I Key-gen: distinguish a prime number (20 pts)

The generation of RSA's public/private keys depends on finding two large prime numbers, thus our program should be able to tell if a given number is a prime number or not. For simplicity, we define both prime numbers p and q within range 0 < p, q < 10,000,000 so that a 64 bits primitive type (e.g. long in Java) should be sufficient to handle most arithmetics calculations involved. Therefore, your first step is to implement a method that takes such a number in the range as input and output boolean  type value to indicate whether it's a prime number:

/**

Verifies if given { num} is a prime

* [hint]: If a number has a factor greater than the square root of itself,

* then it must has a factor less than that square root.

    * e.g. Number 16 has factor 8 (> sqrt(16) == 4), thus it also has a factor 2 ( <

@paramnum

@return true if @codenum si a prime number, o.w. false

public static bollean isprime(longnum) {

}

Step II Key-gen: find a coprime number (20 pts)

From Step 1, one can easily compute n = p * q to be used as the modulus for both the public and private keys; and the nLambda = (p - 1) * (q - 1) from Carmichael's totient function for n. Then we need to find another number e such that 1 < e < nLambda and gcd(e, nLambda) == 1, that is, e and nLambda are coprime.

For this, we need to implement the gcd method that finds the greatest common divisor given two integers

/** return GCD for {@code m} and {@code n}

* [Hint] you may implement this in whichever way you prefer:

* (1) Through prime factorizations

* (2) Enclis's algorithm

     * (3) Lehmer's GCD algorithm

     * (4) Binary GCD algorithm

     * Or others that computes the correct value

* @param m

*@param n

*@return

public static long gcd(long m, long) {

}

Step III Key-gen: find the modular multiplicative inverse

Next, we need to determine d as d= e-1 (mod nLambda) ;that is, d is the modular multipication inverse of e modulo nLambda. This means: solve for d the equation d e=1(mod nLambda):

/**

     * Compute d s.t. ed ≡ 1 (mod nLambda)

* [Hint] Brutal force solution is also accepted

* @param e

*@param nLambda

* @return

*/

public static long inverse(long e, long nLambda){

}

Step IV Key Distribution: calculate power (20 pts)

Suppose that Bob wants to send information M (in this project, you can use a 64 bits integer to represent the message, for example, long in Java) to Alice. At first, Bob must know Alice's public key to encrypt the message and Alice must use her private key to decrypt the message. For example, after Bob gets public key (e and

n) from Alice, he then can computes the ciphertext c through M^e ≡ c (mod n) and

send c to Alice; And when Alice gets the ciphertext, she can use her private key (d and n) by computing c^d ≡ (M^e)^d ≡ M (mod n) to recover the original message.

Thus in this step, we need to a method to calculate the modula power as such:

/**

* computes the modular power number {@code base}^{@code power} % {@code mod}

*[Hint}

     * (1) Pay attention to type overflow with the power operation

* (2) FYI, Java BigInteger provides a modpow() API to be used directly

*@param base

*@param power

*@param mod

*@return

*/

public static long pow(long base, long power, long mod){

}

Step V: Wrap up your solution

Use the methods defined above to implement the main method. Your code should be able to:

Find the number p as the first prime number greater than 1000; and q as the first prime number greater than 2000;

Output p, q, n, nLambda, e and d defined in the previous steps; Use any integer number to represent the message to be sent in this example, output the ciphertext encrpyted by your public key and then output the original message decyphered by your private key.

public static void main (string[] args) {

//For RSA, the bigger the prime is, the harder to crack (for regular computers)

long x=1000; //lower bound of 1st picked prime number

long y=2000; //lower bound of 2nd picked prime number

long message = 521; //plain text

long p,q,n,nLamda,e,d; //nLambda ==> f(n), Carmichael's totient function

//Step (1): Pick up two big prime numbers

/*---> insert your code here <---*/

        System.out.println("p:" +p);

System.out.println("q:" +q);

//Step (2): calc n = p * q

/*---> insert your code here <---*/

        System.out.println("n:" +n);

//Step (3): calc f(n)=(p-1)(q-1)

/*---> insert your code here <---*/

System.out.println("nLamda:" +nLambda);

//Step (4): find a number e st e coprime to f(n) and 1<e<f(n)

/*---> insert your code here <---*/

System.out.println("e:" +e);

//Step (5): Compute d, the modular multiplicative inverse of e, st ed ≡ 1 (mod f(n))

//d = e^-1 mod (f(n))

/*---> insert your code here <---*/

System.out.println("d:" +d);

//print out plain text, public key and private key

        System.out.println("message:" + message);

        System.out.println("pub-key(n,e):"+"(" + n + "," + e + ")");

        System.out.println("pri-key(n,d):" + "("+ n+ "," +d + ")");

//Encryption: C=M^e(mod n)

/*---> insert your code here <---*/

        System.out.println("Encryption: Cipher Text = " + cipherText);

//Decryption: M=C^d(mod n)

/*---> insert your code here <---*/

System.out.println("Decryption: Pain Text = "+ decodedPlainText);

if (message != decode) {

System.out.println("Error!");

} else{

System.out.println("Succed");

}

}

Answer 1

package com.sanfoundry.setandstring;

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 bitlength = 1024;
private Random r;

public RSA()
{
r = new Random();
p = BigInteger.probablePrime(bitlength, r);
q = BigInteger.probablePrime(bitlength, r);
N = p.multiply(q);
phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
e = BigInteger.probablePrime(bitlength / 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;
}

@SuppressWarnings("deprecation")
public static void main(String[] args) throws IOException
{
RSA rsa = new RSA();
DataInputStream in = new DataInputStream(System.in);
String teststring;
System.out.println("Enter the plain text:");
teststring = in.readLine();
System.out.println("Encrypting String: " + teststring);
System.out.println("String in Bytes: "
+ bytesToString(teststring.getBytes()));
// encrypt
byte[] encrypted = rsa.encrypt(teststring.getBytes());
// decrypt
byte[] decrypted = rsa.decrypt(encrypted);
System.out.println("Decrypting Bytes: " + bytesToString(decrypted));
System.out.println("Decrypted String: " + new String(decrypted));
}

private static String bytesToString(byte[] encrypted)
{
String test = "";
for (byte b : encrypted)
{
test += Byte.toString(b);
}
return test;
}

// Encrypt message
public byte[] encrypt(byte[] message)
{
return (new BigInteger(message)).modPow(e, N).toByteArray();
}

// Decrypt message
public byte[] decrypt(byte[] message)
{
return (new BigInteger(message)).modPow(d, N).toByteArray();
}
}

Hope this helpful

Please please kindly dont downvote please