This program involves implementing the RSA cryptosystem discussed in class and d

Question

This program involves implementing the RSA cryptosystem discussed in class and described the web at https://en.wikipedia.org/wiki/RSA (cryptosystem).For this assignment you will use built-in types to store integers, e.g., unsigned long int. For EXTRA CREDIT you can use software to do this, i.e., design a class to implement larger integers. Also, for this assignment the characters will be restricted to the blank character and the lower case letter of the alphabet. Assign blank character the value 0 and a, b z, the values 1, 2,..., 26 respectively. Then the message M will be represented by replacing each character in the message with its assigned integer base 27. For example, the message M = "test" will be represented as N = 20 5 19 20 Translating this to decimal: D = 20 + 19*27 + 5*27^2+ 20*27^3 = 397838 Note that to convert back to base 27, we simply apply the algorithm we discussed in class, i.e., the least significant digit (rightmost) is obtained by performing the operations D mod 27 and performing a recursive call with D/27. For the example above we obtain, 397838 / 27 397838 mod 27 = 14734 20 14734 / 27 14734 mod 27 20 = 545 19 20 545/27 545 mod 20 19 20 = 20 5 19 20 When testing for primarily of an integer p use naive prime testing algorithm discussed in class, but loop only to square root p Your program should prompt the user to input a positive integer representing the public key e. If the user enters a number that is not relatively prime to n = pcj, then have the user reenter and keep doing this until e and n are cop rime, i.e., gcd (e, [i) = 1. Also prompt the user to enter the message M (as a character string). For handing purposes in run your program with M = "test". Output p, q, n, M, C, P where C is the encrypted message, i.e., cyber text, and P is the decrypted message, i.e., plaintext. If your program is working correctly then M should be equal to P.

Explanation / Answer

#include <stdio.h>
unsigned long int find_d(unsigned long int phi, unsigned long int e);
unsigned long int isprime(unsigned long int ele);
unsigned long int gcd ( unsigned long int a, unsigned long int b );
unsigned long int convert_message(char m[]);
void get_message(char m[],unsigned long int mt);
unsigned long int encrypt(unsigned long int mt, unsigned long int n, unsigned long int e);

int main()
{
char m[10],c[10],dm[10];
unsigned long int n,p,e,d,q,phi,mt,ct,dt;
while(1)
{
printf("enter p value ");
scanf("%ul",&p);
if(isprime(p))
break;
printf("P is not prime, enter other value ");
}
while(1)
{
printf("enter q value ");
scanf("%ul",&q);
if(isprime(q))
break;
printf("q is not prime, enter other value ");
}
n=p*q;
while(1)
{
printf("enter e value ");
scanf("%ul",&e);
if(gcd(e,n)==1)
break;
printf("e is not co-prime to n, enter other value ");
}
phi = (p-1)*(q-1);
d=find_d(phi,e);
printf("p= %u, q=%u, e=%u,d=%u, phi=%u ",p,q,e,d,phi);
printf("enter message ");
scanf("%s",&m);
printf("message = %s ",m);
mt=convert_message(m);
printf("%u ",mt);
ct=encrypt(mt,n,e);
//get_message(c,ct);
printf("%u %s ",ct,c);
/*
dt=encrypt(ct,n,d);
get_message(dm,dt);
printf("decrypted message = %s ",dm);
*/
}
unsigned long int find_d(unsigned long int phi, unsigned long int e)
{
unsigned long int d =1,s;
do
{
s = (d*e) % phi;
d++;
}
while(s!=1);
return d;
}
unsigned long int isprime(unsigned long int ele)
{
unsigned long int i=1,count =0;
for(i=2;i*i<=ele;i++)
{
if(ele % i == 0)
return 0;
}
return 1;
}
unsigned long int gcd ( unsigned long int a, unsigned long int b )
{
int c;
while ( a != 0 ) {
c = a;
a = b%a;
b = c;
}
return b;
}
unsigned long int convert_message(char m[])
{
unsigned long int i,res = 0;
for(i=0;m[i];i++)
{
res*=27;
if(m[i]!=' ')
res+=m[i]-'a'+1;
}
return res;
}
void get_message(char m[],unsigned long int mt)
{
int i=0;
while(mt)
{
m[i]=mt%27;
mt/=27;
i++;
}
m[i]='';
}
unsigned long int encrypt(unsigned long int mt, unsigned long int n, unsigned long int e)
{
unsigned long int i,ct=1;
for(i=0;i<e;i++)
{
ct=(ct*mt)%n;
}
return ct;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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