RSA cryptography problems
Number Theory, RSA
- What is the prime factorization of 589449600?
- What is φ(589449600)?
- Using Fermat’s Theorem, determine 345625190 mod 2099.
- Using Euler’s Theorem, determine 266051 mod 2664.
- In an RSA scheme, p = 13, q = 31 and e = 127. What is d?
- One of the primitive roots (also called generators) mod 29 is 2. There are 11 other primitiveroots mod 29. One way to list these is 2a1 mod 29, 2a2 mod 29, … 2a12 mod 29, where 0 < a1 < a2< … < a12. (Note: it’s fairly easy to see that a1 = 1, since 2 is a primitive root.) Find the values ofa10, a11 and a12 and the corresponding values 2a10 mod 29, 2a11 mod 29, and 2a12 mod 29.
- In the Diffie-Hellman Key Exchange, let the public keys be p = 29, g = 19, and the
secret keys be a = 11 and b = 13, where a is Alice’s secret key and b is Bob’s secret key. Whatvalue does Alice send Bob? What value does Bob send Alice? What is the secret key they share? - In El Gamal, Alice chooses YA = αXA mod q. Bob, who is sending a message, calculates
a value K = YAk, where k is randomly chosen with 0 < k < q. Is it possible that for different choicesof k, Bob will calculate the same value K, or will each unique value of k be guaranteed to producea different value for K? Give a brief rationale for your answer. - Write a program that prompts the user to enter an integer, n, in between 1 and 1012 and calculatesφ(n).
(Please write your program in either python or Java, which supports large integers.
Please submit phi.py or phi.java.)
- Using your program from question 1, write a program that determines if (a) an input value inbetween 1 and 1012 is prime, and (b) if so, asks the user to enter an integer in between 1 and theprime number minus 1 and determines if that value is a primitive root. Your program should workas follows:
Calculate each unique prime factor qi of p – 1, and calculate x(p-1)/qi mod p for each qi. If none ofthese are equal to 1, then x is a primitive root.
(Please write your program in either python or Java, which supports large integers. Pleasesubmit primroot.py or primroot.java) - A primitive root, α, of a prime, p, is a value such that when you calculate the remainders of α,α2, α3, α4 , … , αp-1, when divided by p, each number from the set {1, 2, 3, …, p-1} shows up exactlyonce. Prove that a prime p has exactly φ(p-1) primitive roots. In writing your proof, you mayassume that at least one primitive root of p exists.
- Alice and Bob are using Diffie-Hellman to exchange a secret key. They are using the primenumber p = 1234577 and the generator g = 1225529. Alice picks a secret value a and sends ga =654127 to Bob. Bob picks a secret value b and sends gb = 221505 to Alice. What is the secret keythey share?
- Decrypt the following message:
20429835450828679741350
26022799626812591980567
30572114224921561344399
14180424833673414562055
19539282983393676142312
These 5 blocks of cipher text were created with a set of RSA public keys that follow:
n = 43767782750765499923141
e = 986321785648512635467
When you decrypt, you’ll initially get numbers, but those numbers can be converted into blocks of16 letters each.
Solution
phi.java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class phi {
public static List<Long> primeFactors(long number) {
long n = number;
List<Long> factors = new ArrayList<>();
for (long i = 2; i <= n; i++) {
while (n % i == 0) {
factors.add(i);
n = n / i;
}
}
return factors;
}
public static void main(String[] args) {
System.out.println(“Please, input number between 1 and 10^12”);
Scanner scanner = new Scanner(System.in); // user input a number
long n = scanner.nextLong(); // write user input to long variable
List<Long> primeFactors = primeFactors(n); // find list of prime factors
System.out.println(primeFactors); // print list of prime factors
}
}
primroot.java
import java.util.List;
import java.util.Scanner;
public class primroot {
public static boolean checkIsPrime(long n) {
return phi.primeFactors(n).size() == 1;
}
public static long findPrimRoot(long number) {
List<Long> primeFactors = phi.primeFactors(number);
boolean isPrimRoot = false;
for (long x = 2; x <= number; number++) {
for (Long primeFactor : primeFactors) {
if ((Math.pow(x, (number / primeFactor)) % (number + 1)) == 1) {
isPrimRoot = true;
break;
}
}
if (!isPrimRoot) { // if ‘if’ condition was not return 1 and we found a prime root
return x;
}
}
return -1; // if prime root was not found
}
public static void main(String[] args) {
System.out.println(“Please, input number between 1 and 10^12”);
Scanner scanner = new Scanner(System.in); // user input a number
long n = scanner.nextLong(); // write user input to long variable
List<Long> primeFactors = phi.primeFactors(n); // find list of prime factors
if (!checkIsPrime(n)) {
System.out.println(“Number \'” + n + “\’ is not prime.\n” +
” It has prime factors: ” + primeFactors);
} else {
System.out.println(“Number \'” + n + “\’ is prime”);
System.out.println(“Input number between 1 and ” + (n – 1));
long number = scanner.nextLong();
long primRoot = findPrimRoot(number);
if (primRoot == -1) {
System.out.println(“There is no prime root”);
} else {
System.out.println(“Prime root is \'” + primRoot + “\'”);
}
}
}
}