Consider RSA with a large enough modulus n (it is assumed that n cannot be facto

Question

Consider RSA with a large enough modulus n (it is assumed that n cannot be factored within reasonable amount of time) which is used for encryption as follows. Each letter is converted to the corresponding number in Z26 and then encrypted. (a) Show how messages encrypted in this way can be easily decrypted (without factoring the modulus) (b) Apply your method to the following ciphertext, where you know n = 683806699669 and b = 283: 559999161068 198630371233 514736791635 168910308971 188012129537 457048963928 Remember that you are not allowed to factor n; show your computations.

Explanation / Answer

#include<stdio.h>
#include<math.h>

int gcd(int a, int h)
{
int temp;
while (1)
{
temp = a%h;
if (temp == 0)
return h;
a = h;
h = temp;
}
}

int main()
{

double p = 3;
double q = 7;

double n = p*q;

double e = 2;
double phi = (p-1)*(q-1);
while (e < phi)
{

if (gcd(e, phi)==1)
break;
else
e++;
}

int k = 2;
double d = (1 + (k*phi))/e;

double msg = 20;

printf("Message data = %lf", msg);

double c = pow(msg, e);
c = fmod(c, n);
printf(" Encrypted data = %lf", c);

double m = pow(c, d);
m = fmod(m, n);
printf(" Original Message Sent = %lf", m);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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