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
Recent Comments