Friday, November 25, 2016

Notes on Data Structure

Download Notes on  Data Structure

Data structure Demo using C program

Data structure Demo using C program
    1.   Download  Application
    2.   Download Source1 (header file)
    2.   Download Source2

Tree Demo with menus using C Program
    1.   Download  Application
    2.   Download Source

Double Linked List Demo with menus using C Program
    1.   Download  Application
    2.   Download Source

Simple Encryption and Decryption program in C

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<string.h>

void decrypt(char a[],int n)
{
 int i;
 for(i=0;i<strlen(a);i++)
 {
  a[i]=a[i]-n;
  }
 }

 void encrypt(char a[],int n)
 {
  int i;
  for(i=0;i<strlen(a);i++)
  {
   a[i]=a[i]+n;
   }
  }

  void main()
  {
   char name[100];
   clrscr();
   cout<<"enter a string\n";
  // cin>>name;
  gets(name);
   cout<<"original string:"<<name<<"\n";
   encrypt(name,4);
   cout<<"encrypted string:"<<name<<"\n";
   decrypt(name,4);
   cout<<"decrypted string:"<<name<<"\n";
   getch();
  }

C Program to find given IP Address belongs to which Class(A,B,C,D,E)


#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int check_digit_dot(char ipstr[])
{
 for(int i=0;i<strlen(ipstr);i++)
 {
  if((ipstr[i]>=48 && ipstr[i]<=57)||(ipstr[i]=='.'))
  {
   //i++;
  }
  else
     return 0;   }
  }
   return 1;
}

int check_ip(char ipstr[])
{
 char temp[20];
 int a,num,dot=0,j=0,numcount=0;
 a=check_digit_dot(ipstr);
 temp[0]='\0';
 if(a==0)
  return 0;
  else
   {
    for(int i=0;i<=strlen(ipstr);i++)
    {
      if(ipstr[i]!='.')
       {
             temp[j]=ipstr[i];
             j++;
             temp[j]='\0';
       }
      else
       {
             num=atoi(temp);
            // cout<<"num="<<num<<"\n";
             dot++;
             if((num>=0 && num<=255) && strlen(temp)>0)
             {  numcount++; }
             //cout<<"numcount="<<numcount<<"\n";
             j=0;
             temp[j]='\0';
       }
    }
    // after last dot
    num=atoi(temp);
   // cout<<"num="<<num<<"\n";
    if ((num>=0 && num<=255) && strlen(temp)>0)
    { numcount++; }
   // cout<<"numcount="<<numcount<<"\n";
  }

  //cout<<"dots="<<dot<<"  numcount="<<numcount<<"\n";
  if(dot==3 && numcount==4)
    return 1;
  else
    return 0;
 }

 

void main()
{
 clrscr();
 char a[50],temp[50];
 int check,j=0,num;
 cout<<" enter ip address\n";
 cin>>a;
 check=check_ip(a);
 if(check==0)
 {
  cout<<"not valid ip address\n";
  }
  else
  {
   cout<<" valid  ip address\n";
   temp[0]='\0';
   for(int i=0;i<strlen(a);i++)
   {
    if(a[i]=='.')
     {     break;       }
    else
     {
      temp[j]=a[i];
      j++;
      temp[j]='\0';
     }
   }

    num=atoi(temp);
    cout<<"num:"<<num<<"\n";

    if((num>=0)&&(num<128))
    cout<<"given ip address is class A\n";
    else if((num>=128)&&(num<192))
    cout<<"given ip address is class B";
    else if((num>=192)&&(num<224))
    cout<<"given ip address is class C";
    else if((num>=224)&&(num<240))
    cout<<"given ip address is class D";
    else
    cout<<"given ip address is class E";
  }

  getch();
 }

C Program to find given IP Address is Valid or not


#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int check_digit_dot(char ipstr[])
{
 for(int i=0;i<strlen(ipstr);i++)
 {
  if((ipstr[i]>=48 && ipstr[i]<=57)||(ipstr[i]=='.'))
  {
   //i++;
  }
  else
  {
   return 0;
   }
  }
   return 1;
}

int check_ip(char ipstr[])
{
 char temp[20];
 int a,num,dot=0,j=0,numcount=0;
 a=check_digit_dot(ipstr);
 temp[0]='\0';
 if(a==0)
  return 0;
  else
   {
    for(int i=0;i<=strlen(ipstr);i++)
    {
      if(ipstr[i]!='.')
       {
             temp[j]=ipstr[i];
             j++;
             temp[j]='\0';
       }
      else
       {
             num=atoi(temp);
             cout<<"num="<<num<<"\n";
             dot++;
             if((num>=0 && num<=255) && strlen(temp)>0)
             {  numcount++; }
             cout<<"numcount="<<numcount<<"\n";
             j=0;
             temp[j]='\0';
       }
    }

    // after last dot
    num=atoi(temp);
    cout<<"num="<<num<<"\n";
    if ((num>=0 && num<=255) && strlen(temp)>0)
    { numcount++; }
    cout<<"numcount="<<numcount<<"\n";
  }

  cout<<"dots="<<dot<<"  numcount="<<numcount<<"\n";
  if(dot==3 && numcount==4)
    return 1;
  else
    return 0;
 }

void main()
{
 clrscr();
 char a[50];
 int check;
 cout<<" enter ip address\n";
 cin>>a;
 check=check_ip(a);
 if(check==1)
 {
  cout<<"valid ip address";
  }
  else
  {
   cout<<"not valid address";
  }

  getch();
 }

RSA Encryption and Decryption with Numerical Example and C Program on RSA Encryption and Decryption


To generate the encryption and decryption keys, we can proceed as follows.

1. Generate randomly two “large” primes p and q.

2. Compute n = pq and  ϕ= (p − 1)(q − 1).

3. Choose a number e so that gcd(e, ϕ) = 1.

4. Find the multiplicative inverse of e modulo ϕ, i.e., find d so that ed ≡ 1 (mod ϕ).

This can be done efficiently using Euclid’s Extended Algorithm.

The encryption public key is KE = (n, e) and the decryption private key is KD = (n, d).

The encryption function is   E(M) = Me mod n.

The decryption function is   D(M) = Md mod n.

These functions satisfy  D(E(M)) = M and E(D(M)) = M for any 0 ≤ M ≤ n.

*****
Let’s look at a numerical example.

1. Let p = 7 and q = 13 be the two primes.

2. n = pq = 91 and ϕ = (p − 1)(q − 1) = 72.

3. Choose e. Let’s look among the primes.

            • Try e = 2;  gcd(2, 72) = 2 (does not work)
            • Try e = 3;  gcd(3, 72) = 3 (does not work)
            • Try e = 5;  gcd(5, 72) = 1 (it works)
            We choose e = 5.

4. Let’s find d. We want to find d such that  ed   1 (mod ϕ) which is equivalent to find d such that   ed + ϕ k = 1 for some integer k. Recall that gcd(e, ϕ) = 1.

            We can use the Extended Euclid’s Algorithm to find integers x and y such that
                         ex + ϕy = gcd(e, ϕ).

            If  e = 5 and ϕ = 72, we find x = 29 and y = −2. 
            Indeed, 5(29) + 72(−2) = gcd(5,      72) = 1.    Then,         d = 29.    

            In general, we use d = x mod ϕ.

5. The encryption function is  E(M) = Me mod n = M5 mod 91.

    The decryption function is D(M) = Md mod n = M29 mod 91.

6. Suppose the message is M = 10.

            E(M) = E(10) = 105 mod 91 = 82

           Here 82 is called as CipherText

           D(E(M)) = D(82) = 8229 mod 91 = 10

7. Let’s see how to compute efficiently 8229 mod 91 using the square-and-multiply algorithm.

            (82)1     82 (mod 91)
            (82)2    81 (mod 91)
            (82)4  (81)2 9 (mod 91)
            (82)8  (9)2    81 (mod 91)
            (82)16 (81)2 9 (mod 91
 
            Since 29 = 16 + 8 + 4 + 1 (in binary 29 is 11101),  we deduce that
            8229      (82)16(82)8(82)4(82)1 (mod 91)
                        (9)(81)(9)(82) (mod 91)
                         10 (mod 91)
 
            We conclude that 8229 mod 91 = 10 (Original Message).

 

Consider an another example
1. Let p = 19 and q = 23 be the two primes.

2. n = p*q = 437 and ϕ = (p − 1)*(q − 1) = 396.

3. Choose e. Let’s look among the primes.

            • Try e = 2;  gcd(2, 396) = 0 (does not work because it has factors)
            • Try e = 3;  gcd(3, 396) = 0 (does not work because it has factors)
            • Try e = 5;  gcd(5, 396) = 1 (it works)
             We choose e = 5.

4. Let’s find d. We want to find d such that  ed   1 (mod ϕ) which is equivalent to find d such that   ed + ϕ k = 1 for some integer k. Recall that gcd(e, ϕ) = 1.

            We can use the Extended Euclid’s Algorithm to find integers x and y such that
                         ex + ϕy = gcd(e, ϕ).  i.e.  5x+396y=1
                                                                   x= (1-396y)/5

            If  e = 5 and ϕ = 396,
            we find x = 317 and y = −4.  Indeed, 5(317) + 396(−4) = gcd(5, 396) = 1.
            Then,         d = 317.    

            In general, we use d = x mod ϕ.

5. The encryption function is  E(M) = Me mod n = M5 mod 437.

    The decryption function is  D(M) = Md mod n = M317 mod 437.

6. Suppose the message is M = 7.

            E(M) = E(10) = 75 mod 437 = 201

           Here 201 is called as CipherText

            D(E(M)) = D(201) = 201317 mod 437 = 7 (Original Message)

 
 
 
 
C program on RSA Encryption and Decryption
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int prime( int n)
{
 int i,r;
  for(i=2;i<n-1;i++)
  {
   r=n%i;
   if(r==0)
    {  return 0;  }
  }
  return 1;
 }
int gcd(int a, int b)
{
  int r=0;
  while(b>a)
  {
   r=b%a;
   if(r==0){ break;}
     b=a;
     a=r;
  }
   return a;
}
 
 void main()
 {
  clrscr();
  int n,pi,x,y,privatekey, publickey,p,q,primecheck,gcdvalue;
  cout<<"enter two prime numbers"<<"\n";
  cin>>p>>q;
  if (prime(p)==0 || prime(q)==0 ||p==q)
  {
     cout<<" one of the number is not prime or both numbers are same"<<"\n";
  }
  else
  {
   n=p*q;
   pi= (p-1)*(q-1);
   for(int e=3; e<pi-1; e++)
   {
      if (prime(e)==1)
       {
             if (gcd(e,pi)==1)
             {
               publickey= e;
               break;
             }
       }
   }
   cout<<"Public Key="<<publickey<<"\n";
   y=1;
   while(1)
   {
      x= (1-(pi*(-y)))/publickey ;
      if (publickey*x+pi*(-y)==1) { break; }
      y++;
   }
   privatekey=x;
   cout<<"private key="<< privatekey<<"\n";
   cout<<"enter message"<<"\n";
   int msg;
   cin>>msg;
   long ctext=1,i;
   for (i=0;i<publickey; i++)
    ctext=(ctext*msg)%n;
 
   ctext=ctext%n;
   cout<<"ciphertext or encrypt="<<ctext<<"\n";
   long ptext=1,j;
   for(j=0;j<privatekey;j++)
     ptext=(ptext*ctext)%n;
   ptext=ptext%n;
   cout<<"plain Text="<<ptext<<"\n";
  }
   getch();
 }