In: Computer Science
This is an intro to java question. Please answer with pseudocode and code.
Problem 2: RSA Public Key (10 points) (Cyber Security)
RSA is an asymmetric encryption scheme, where a public key is used to encrypt data and a different, private key decrypts that data. RSA public/private keys are generated from two prime numbers, typically very large ones. The idea behind RSA is based on the fact that its difficult to factorize very large integers. RSA public key generation is done in part by using the composite number (n) between two prime numbers (p,q), and some other coprime number (e) which is not a divisor of n. Determine if two seed numbers and the given e are valid for generating a RSA key, and if so, calculate n, the basis for generating private/public keys.
Facts RSA Public/Private key generation requires:
● p, one of the given numbers, it must be prime.
● q, one of the given numbers, it must be prime.
● n is a composite number where p * q
● totient(n) = (p - 1) * ( q - 1)
● e is a coprime to n (i.e. not divisible), and must be between 1 < totient(n).
● Consider using long data types instead of int
Input
First line represents the number of test cases. Each line there after, consists of three positive integers. The first integer represents the p terms, the second integer represents the q term, the third integer represents the e term.
Output
For each pair of integers, determine if they are not valid for key generation. if not, either print "Invalid n for RSA Key!" or "Invalid e for RSA Key!" depending on which is not valid. Otherwise, print "RSA Public Key: n=%d e=%d" with n and e respectively.
Sample Input
4
5 3 7
33 7 5
131101 524269 17
5 3 17
Sample Output
RSA Public Key: n=15 e=7
Invalid n for RSA Key!
RSA Public Key: n=68732190169 e=17
Invalid e for RSA Key!
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Task4 {
public static boolean isPrime(int n) {
if (n == 1)
return false;
for (long i = 2; i * i < (long)n; i++) {
if (n % i == 0)
return false;
}
return true;
}
public static String checkValidKeys(int p, int q, int e) {
if (!isPrime(p)||!isPrime(q)) {
return "Invalid n for RSA Key!";
}
long n = ((long)p) * q;
long totientN = ((long)(p - 1)) * (q - 1);
if (e <= 1 || e >= totientN || n % e == 0 || e % n == 0) {
return "Invalid e for RSA Key!";
}
return "RSA Public Key: n=" + n + ", e=" + e;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
String message[] = new String[T];
for (int i = 0; i < T; i++) {
String line = br.readLine();
String words[] = line.split(" ");
int p = Integer.parseInt(words[0]);
int q = Integer.parseInt(words[1]);
int e = Integer.parseInt(words[2]);
message[i] = checkValidKeys(p, q, e);
}
br.close();
for (int i = 0; i < T; i++) {
System.out.println(message[i]);
}
}
}