Implement RSA encryption-decryption algorithm in c.

Introduction:

RSA was developed by Ron Rivest, Adi Shamir and Len Adleman in 1997 at MIT. Rivest-Shamir-Adleman (RSA) is most widely accepted and implemented general purpose approach to public key encryption.

RSA Scheme is a block cipher in which plaintext and cipher text are integers between 0 and n-1 for some n. A typical size of n is 1024 bits or 309 decimal digits. That is n is less than 2¹⁰²⁴. Plaintext is encrypted in blocks, with each block having binary value less than some number n. that is block size must be less than or equal to log2(n). In practice block size is I bits, where 2i<n≤ 2i+1.

     RSA Scheme: -

1)         Select two prime numbers p, q such that p ≠ q (p and q must be kept private).

2)         Now calculate n = p*q (n can be made public)

3)         Calculate Ø(n) = (p-1)(q-1)

4)         Select a integer e such that gcd(e,Ø(n)) = 1 & 1 < e < Ø(n) (e cam be made public).

5)         Calculate d = e^-1 mod Ø(n).

6)         Select M < n and calculate C = M^e mod n

7)      Given C at receiver it can calculate M = C^d mod n.

C code:

// RSA encryption-decryption algorithm.

#include<stdio.h>

#include<conio.h>

#include<math.h>

long int power(long int a, long int j, long int c)

{

            long int f,i;

            f=1;

            for(i=1;i<=j;i++)

            {

                        f=(f*a)%c;

            }

            f=f%c;

            return f;

}

long int ext_eucledian(long int m,long int b)

{

            int a1=1,a2=0,a3=m,b1=0,b2=1,b3=b,q,t1,t2,t3;

            while(1)

            {

                        if(b3==0)

                        {

                                    return 0; 

             }

                        if(b3==1)

                        {

                                    if(b2<0)

                                                b2+=m;

                                    return b2;

                        }

                        q=a3/b3;

                        t1=a1-(q*b1);

                        t2=a2-(q*b2);

                        t3=a3-(q*b3);

                        a1=b1;

                        a2=b2;

                        a3=b3;

                        b1=t1;

                        b2=t2;

                        b3=t3;

            }

}

void main()

{

                        long int n,p,q,e,m,fi,ct,d,pt,pub_key,priv_key;

                        clrscr();

                        printf("enter the value of p:");

                        scanf("%ld",&p);

                        printf("enter the value of q:");

                        scanf("%ld",&q);

                        n=p*q;

                        printf("the value of n:%ld",n);

                        fi=(p-1)*(q-1);

                        printf("\nvalue of fi:%ld",fi);

                        printf("\nenter the value of e:");

                        scanf("%ld",&e);

                        d=ext_eucledian(fi,e);

                        printf("value of d:%ld",d);

                        printf("\nenter the value of m:");

                        scanf("\n%ld",&m);

                        ct=power(m,e,n);

                        printf("cipher text:%ld",ct);

                        printf("\n");

                        pt=power(ct,d,n);

                        printf("plain text:%ld",pt);

                        printf("\npublic key (e,n):%ld %ld",e,n);

                        printf("\nprivate key (d,n):%ld %ld",d,n);

getch();

}

Output:

 

THANK YOU!!!!