Computer Science
CSCI 352 Project #1 Understanding RSA
In this project assignment, you will create a program with any high-level programming
languages as you prefer (e.g. Java/C++/Python/Go …) 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 range
as input and output a boolean type value to indicate whether it’s a prime number:
/**
* Verifies if given {@code num} is a prime
*
* [hint]: If a number has a factor greater than 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 ( <
4)
* @param num
* @return true if {@code num} is a prime number, o.w. false
*/
public static boolean isPrime(long num) {
//your implementation
}
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:
/**
* Returns GCD for {@code m} and {@code n}
* [Hint] you may implement this in whichever way you prefer:
* (1) Through prime factorizations
* (2) Euclid’s algorithm
* (3) Lehmer’s GCD algorithm
* (4) Binary GCD algorithm
* Or others that computes the correct value
* @param m
* @param n
https://en.wikipedia.org/wiki/RSA_(cryptosystem)
https://en.wikipedia.org/wiki/Prime_number
https://en.wikipedia.org/wiki/Modular_arithmetic
https://en.wikipedia.org/wiki/Carmichael_function
https://en.wikipedia.org/wiki/Coprime_integers
https://en.wikipedia.org/wiki/Greatest_common_divisor
* @return
*/
public static long gcd(long m, long n) {
//your implementation
}
Step III Key-gen: find the modular multiplicative inverse (20 pts)
Next, we need to determine d as d ≡ e−1 (mod nLambda) ; that is, d is the modular
multiplicative 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) {
//your implementation
}
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) {
//your implementation
}
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, nLambda, 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(“nLambda:” + nLambda);
//Step (4): find a number e st e coprime to f(n) and 1 /*—> 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(“Succeed!”);
}
}