1. You have to write a program (in the language of your choice) which will trace

Question

1. You have to write a program (in the language of your choice) which will trace the execution of the RSA cryptosystem on a simple example. Make sure that you take modulo after every operation i.e. it is not enough just to take the modulo after a long string of operations because the numbers can get so big that you get an overflow error.

(a) Alice choses her two primes to be p = 29 and q = 11 and multiplies them to obtain n = 319.. Next, Alice randomly choses e = 17. Alice makes e and n public.

(b) You first need to calculate what Alice’s secret d will be. Your program should compute (n) = (p1)(q 1), and then your program should find the unique integer d (using brute force search here is OK) such that d is between 1 and n 1 and d.e mod (n) = 1.

(c) The cleartext message Bob wishes to send to Alice is M = 36. Bob looks up Alice’s public e and n, and then calculates (your program should do this) C = Me mod n. For full credit you should implement the fast divide and conquer modular exponential method discussed in class and the textbook; you will get partial credit if you implement the simple, inefficient and straightforward method for modular exponentiation.

(d) Alice receives the ciphertext C. She will then use her secret d to decipher Bob’s message by calculating (your program should do this) M0 = C d mod n. If you have done this correctly, the decoded message M0 should come out equal to the original message M. Again, for full credit you should implement the fast, divide and conquer modular exponential method.

(e) Your program should print out the following values; p, q, n, (n), e, d, M, C, M0 .

Question is from algorithm design and analysis course

Explanation / Answer

The program with the given specifications including the fast divide and conquer modular exponential method has been implemented. Please upvote my answer if you find it useful. Have a nice day!

------------------Program--------------------

#include <iostream>
#include <math.h>

using namespace std;

typedef long long int lli;

lli fastDivideAndConquerModularExponential(lli text, lli key, lli n)
{
if(key == 1)
return text%n;
if(key%2 == 0)
{
lli ans = pow(fastDivideAndConquerModularExponential(text,key/2,n),2);
return ans%n;
}
else
{
lli temp = pow(fastDivideAndConquerModularExponential(text,(key-1)/2,n),2);
return (text*(temp%n))%n;
}
}

int main()
{
lli p = 29, q = 11, n = 319, e = 17, d = -1, temp;
lli phi_n = (p-1)*(q-1);

for(int i=0; i<n; i++)
{
temp = (i*e)%phi_n;
if(temp == 1)
{
d = i;
break;
}
}
if(d == -1)
{
cout<<"Could not find d."<<endl;
return -1;
}

lli M = 36, C, M0;

C = fastDivideAndConquerModularExponential(M,e,n);
M0 = fastDivideAndConquerModularExponential(C,d,n);
  
cout<<"p: "<<p<<" q: "<<q<<" n: "<<n<<" phi(n): "<<phi_n<<endl;
cout<<"e: "<<e<<" d: "<<d<<" M: "<<M<<" C: "<<C<<" M0: "<<M0<<endl;
  
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.