RSA Algorithm code in C

!! RSA !! Public Key Cryptography

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int mrpt(int n)//miller robbin primility test
{
int s,t,x,i;
if(n > 2)
{
if(n%2==0)
return 0;
else
{
int temp=1;
s=0;
t=n-1;
while(t%2==0)
{
s=s+1;
t=t/2;
}
x=0;
while(x==0)
x=rand()%(n-1);
//printf("x==%d\n",x);
for(i=1;i < =t;i++)
{
//calculate x't mod n=temp
temp=(temp*x)%n;
}
//printf("x't mod n==%d\n",temp);
int i,stemp=1,pow=1;
for(i=1;i<=s;i++)
{
pow=pow*2;
}
for(i=1;i<=pow;i++)
{
stemp=(stemp*temp)%n;
}
if(stemp==1)
return 1;
else return 0;
}
}
else return 0; 
}
int gcd(int a,int b)//compute gcd of a,b
{
if(b==0)
 return a;
gcd(b,a%b);
}
int main()
{
   int i, num[2],p=5,q,phn,n,e,d;
   time_t t;
   //change base value and fix range of p and q
   int base=100;
   printf(" ______________\n|      RSA     |\n ----------
----\nGenerate prime Nums in range 1 to %d\n",base);
   //generate random numbers p and q   
   srand((unsigned) time(&t)); 
   for(i=0;i<2;i++)
   {
   while(1){
   num[i]=rand()%base;
   if(mrpt(num[i])&num[i]!=p)
   break;}
   p=num[i];
   }
   //choose p,q as large distinct prime number
   p=num[0];
   q=num[1];
   printf("\np is : %d\nq is : %d\n",p,q);
   //calculate phy(n)=p-1*q-1;
   phn=(p-1)*(q-1);
   printf("phy(n) : %d \n",phn);
   //calculate n=p*q;
   n=p*q;
   printf("n is : %d \n",n);
   //choose e such that 1<e<phn and gcd(e,phn)=1
   while(gcd(phn,e)!=1)
   e=rand()%phn;
   printf("e is : %d\n",e);
   //compute d such as multiplicative inverse of e.d=1mod phn
   for(i=1;(phn*i+1)%e!=0;i++);
   d=(phn*i+1)/e;
   printf("d is : %d\n",d);
   //publish (N,e) as public key
   //keep (p,q and d) secreatly
   printf("\nPublic key (N,e)    :( %d,%d )\n",n,e);
   printf("Secreat key (p,q,d) :( %d,%d,%d )\n",p,q,d);
   printf("Thanks !! End of program !!\n");
  return(0);
}

Compile By : gcc -o a rsa.c (In LINUX environment)
run : ./a
Special thanks : Sunil_Kumar

Thank you for sight !

Extended Euclidean algorithm code in python

#EXTENDED EUCLIDEAN ALGORITHM TO FIND GCD(M,B)
m=int(raw_input("ENTER M OR mod M = : "))
b=int(raw_input("ENTER B = : "))
# A1,A2,A3 <---(1,0,M)
a1=1
a2=0
a3=m
# B1,B2,B3 <---(0,1,B)
b1=0
b2=1
b3=b
while 1 :
# if B3=0 return A3=GCD(M,B) and B has no inverse 
      if b3==0 :
         gcd_MB=a3
         invrs_b=0
         break
# if B3=1 return B3=GCD(M,B) and B2=B(inverse) mod M
      if b3==1 :
         gcd_MB=b3
         invrs_b=1
         break
# Q=A3/B3 
      q=a3/b3
# (T1,T2,T3) <--- [(A1-QB1),(A2-QB2),(A3-QB3)] 
      t1=a1-q*b1
      t2=a2-q*b2
      t3=a3-q*b3
# (A1,A2,A3) <--- (B1,B2,B3) 
      a1=b1
      a2=b2
      a3=b3
# (B1,B2,B3) <--- (T1,T2,T3) 
      b1=t1
      b2=t2
      b3=t3

if invrs_b==0 :
        print "\nGCD(B,M) = : ",gcd_MB,"\n"
        print "\n", b,"HAS NO MULTIPLICATIVE INVERSE IN mod",m,"\n"

if invrs_b==1 :
#FIND THE MULTIPLICATIVE INVERSE OF B IN mod M by traditional method......
        c=1    
        while ((b*c)%m)!=1 :
                            c=c+1
                            if c>m :
                                    break


#FIND MULTIPLICATIVE INVERSE OF B IN mod M BY value of b2....... 
#c=1
#while c%m!=b2 :
#            c++
#            if (c>m) :
#                  break

        if c<m :
             print  "\nGCD(B,M) = :",gcd_MB
             print  "\nMULTIPLICATIVE INVERSE OF",b, " = " ,c, " in mod",m,"\n"
        else:
             print "\nGCD(B,M) = : ",gcd_MB 
             print "\n",b," HAS NO INVERSE IN mod",m,"\n"

Compile and run in a single command :
system path> python eea.py
It will compile as well as run the program.

Extended Euclidean algorithm code in C

/*EXTENDED EUCLIDEN ALGORITHM FOR FIND GCD OF TWO NUMBERS */
#include < stdio.h >
main(){
int m,b,a1,a2,a3,b1,b2,b3,gcd_MB,invrs_b,q,t1,t2,t3;
char ch='a';
while(ch!='q'){
printf("ENTER M OR mod M= : ");
scanf("%d",&m);
printf("ENTER B = : ");
scanf("%d",&b);
/*A1,A2,A3 <---(1,0,M)*/
a1=1;
a2=0;
a3=m;
/*B1,B2,B3 <---(0,1,B)*/
b1=0;
b2=1;
b3=b;
while(1){
/*if B3=0 return A3=GCD(M,B) and B has no inverse */
if(b3==0){
gcd_MB=a3;
invrs_b=0;
break;
}
/*if B3=1 return B3=GCD(M,B) and B2=B(inverse) mod M*/
if(b3==1){
gcd_MB=b3;
invrs_b=1;
break;
}
/* Q=A3/B3 */
q=a3/b3;
/*(T1,T2,T3) <--- [(A1-QB1),(A2-QB2),(A3-QB3)] */
t1=a1-q*b1;
t2=a2-q*b2;
t3=a3-q*b3;
/*(A1,A2,A3) <--- (B1,B2,B3) */
a1=b1;
a2=b2;
a3=b3;
/*(B1,B2,B3) <--- (T1,T2,T3) */
b1=t1;
b2=t2;
b3=t3;
}
if(invrs_b==0){
printf("\nGCD(B,M) = : %d",gcd_MB);
printf("\n %d HAS NO MULTIPLICATIVE INVERSE IN mod %d \n",b,m);
}
if(invrs_b==1)
{
/*FIND THE MULTIPLICATIVE INVERSE OF B
 IN mod M by traditional method......*/
int c=1;
while(((b*c)%m)!=1)
{
c++;
if(c>m)
break;
}

/*FIND MULTIPLICATIVE INVERSE OF B IN mod M BY value of b2 
int c=1;
while(c%m!=b2){
c++;
if(c>m)
break;
}*/
if(c < m)
{
printf("\nGCD(B,M) = : %d",gcd_MB);
printf("\nMULTIPLICATIVE INVERSE OF %d = %d in mod %d\n",b,c,m);
}
else
{
printf("\nGCD(B,M) = : %d",gcd_MB); 
printf("\n %d HAS NO INVERSE IN mod %d\n",b,m);
}}
scanf("%c",&ch);
}
}

Compile in LINUX environment by:
Compile : gcc -o eea eea.c
Run     :./eea
here gcc is a c/c++ compiler and eea.c is a c sourcecode file.

chinese remainder theorem in c

Chinese_remainder_theorem code in C

#include <stdio.h>
main()
{

int a[10],m[10],M[10],y[10];
int ml=1,n,i,j,x=0;

printf("\nEnter value of a and m as follows : \n");
printf("x mod m1=a1 mod m1\n");
printf("x mod m2=a2 mod m2\n");

printf("what is the value of n less than 10 : ");
printf("\t.\n\t.\n\t.\n\t.\n\t.\n");
printf("x mod mn=an mod mn\n");
scanf("%d",&n);

for(i=1;i<=n;i++)
//enter m1,m2,m3,m4...........mn
printf("\nEnter m1,m2,m3,m4,............,mn\n");
{
printf("m %d : ",i);

for(i=1;i<=n;i++)
scanf("%d",&m[i]);
}
//enter a1,a2,a3,a4,...........an
printf("\nEnter a1,a2,a3,a4,............,an\n");
{

//compute M1,M2,M3,M4...........Mn
printf("a %d : ",i);
scanf("%d",&a[i]);
}
//compute M ?
for(i=1;i<=n;i++)
{
ml=ml*m[i];
}
for(i=1;i<=n;i++)
{

if((y[i]*j)%m[i]==1)
M[i]=ml/m[i];
}
//compute y1,y2,y3,y4...........yn
for(i=1;i<=n;i++)
{
y[i]=M[i]%m[i];
j=1;
while(1)          //find MI
{
break;

printf("\nFinal value of x : %d ans",x);
else j++;
}
y[i]=j;
}
for(i=1;i<=n;i++)
{
x=x+(a[i]*y[i]*M[i])%ml;
}
x=x%ml; //final x is here
printf("\nThank u \n");
return 0;

}

Compiled By :gcc compiler in ubuntu LINUX
copy the code and give name crt.c and follow :

:gcc -o a crt.c    (compile the code).
:./a               (run the program).