JEE ADVANCED SELECTED QUESTIONS: 2017

Tuesday 19 September 2017

Decision Tree Program

Decision Tree Program for Classification

Program : -


#include<bits/stdc++.h>

using namespace std;

//STRUCTURE OF A NODE IN DECISION TREE

struct TreeNode

{

    string splitAttr;

    string label;

    bool isleaf;

    vector<vector<string> >Table;

    vector<TreeNode*>children;

};

//Print a Table

void printTable(vector<vector<string> >&Table)

{

    for(int i=0;i<Table.size();i++)

    {

        char arr[30];

        for(int j=0;j<Table[i].size();j++)

            printf("%-15s ",strcpy(arr,Table[i][j].c_str()));

        cout<<endl;

    }

}

//Splitting Function

TreeNode *createTree(TreeNode *node,vector<vector<string> >&input)

{

    node->isleaf=false;

    node->Table=input;

    int rows=input.size(),col=input[0].size(),cnt=0;

    map<string,int>mp;

    for(int i=1;i<rows;i++) mp[input[i][col-1]]++,cnt++;

    //Base case (When all class is same.)

    if(cnt==mp[input[1][col-1]])

    {

        TreeNode *temp=new TreeNode();

        temp->isleaf=true;

        temp->label=input[1][col-1];

        temp->splitAttr="LeafNode";

        node->splitAttr="Final";

        node->children.push_back(temp);

        return node;

    }

    //Distribution Information Gain.

    double infoGain=0.0,tot=cnt,temp;

    for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++)

        temp=it->second,infoGain+=-temp/tot*log2(temp/tot);

    //Calculation of Information & gain of each attribute.

    double mx=-1.0; int cl_num=-1;

    for(int i=0;i<col-1;i++)

    {

        map<string,vector<string> >mps;

        for(int j=1;j<rows;j++) mps[input[j][i]].push_back(input[j][col-1]);

        double gain=0.0;

        for(map<string,vector<string> >::iterator it=mps.begin();it!=mps.end();it++)

        {

            map<string,int>mpss; cnt=0;

            for(int k=0;k<it->second.size();k++) mpss[it->second[k]]++,cnt++;

            map<string,int>::iterator its=mpss.begin();

            if(its->second==cnt) continue;

            double infoAttr=0.0; tot=cnt;

            for( ;its!=mpss.end();its++)

                temp=its->second,infoAttr+=-temp/tot*log2(temp/tot);

            gain+=((double)it->second.size()/((double)(rows-1)))*infoAttr;

        }

        gain=infoGain-gain;

        if(gain>mx) mx=gain,cl_num=i;

        //cout<<input[0][i]<<" "<<gain<<endl;

    }

    //Splitting attribute. (Decided on the basis of maximum gain value.

    node->splitAttr=input[0][cl_num];

    set<string>st;

    for(int i=1;i<rows;i++)

        st.insert(input[i][cl_num]);

    for(set<string>::iterator it=st.begin();it!=st.end();it++)

    {

        TreeNode *tmp=new TreeNode();

        tmp->label=*it;

        vector<vector<string> >nyatable;

        for(int i=0;i<rows;i++)

        {

            vector<string>tts;

            if(i==0 || input[i][cl_num]==*it)

            {

                for(int j=0;j<col;j++)

                    if(j!=cl_num) tts.push_back(input[i][j]);

                nyatable.push_back(tts);

            }

        }

        cout<<"===================================================================\n";

        cout<<"--------------Splitting attribute : "<<node->splitAttr<<"------------\n";

        cout<<"--------------Label : "<<tmp->label<<"------------\n";

        printTable(nyatable);

        tmp=createTree(tmp,nyatable);

        node->children.push_back(tmp);

    }

    return node;

}

//Predicting the decision.

string prediction(TreeNode *node,map<string,string>mp)

{

    if(node->isleaf) return node->label;

    string label=mp[node->splitAttr];

    if(node->splitAttr.compare("Final")==0) return node->children[0]->label;

    for(int i=0;i<node->children.size();i++)

    {

        if(label.compare(node->children[i]->label)==0)

            return prediction(node->children[i],mp);

    }

    return "Can't be predicted\n";

}

int main()

{

    //Training File Input to the InputTable.

    char buff[1000];

    FILE *fp=fopen("Train.txt","r");

    if(!fp) { cout<<"No training data found.\n"; return 0;}

    if(fgets(buff,1000,fp)==NULL) { cout<<"Training file is empty.\n"; return 0;}

    vector<vector<string> >InputTable;

    vector<string>temp; string tt="";

    for(int i=0;i<strlen(buff);i++)

    {

        if(buff[i]==' '||buff[i]=='\t'||buff[i]=='\n')

        {

            temp.push_back(tt); tt="";

            while(buff[i]==' '||buff[i]=='\t'||buff[i]=='\n') i++; i--;

        }

        else    tt+=buff[i];

    }

    temp.push_back(tt);

    InputTable.push_back(temp);

    temp.resize(0); tt="";

    while(fgets(buff,1000,fp)!=NULL)

    {

        for(int i=0;i<strlen(buff);i++)

        {

            if(buff[i]==' '||buff[i]=='\t'||buff[i]=='\n')

            {

                temp.push_back(tt); tt="";

                while(buff[i]==' '||buff[i]=='\t'||buff[i]=='\n') i++; i--;

            }

            else    tt+=buff[i];

        }

        temp.push_back(tt);

        InputTable.push_back(temp);

        temp.resize(0); tt="";

    }

    for(int i=0;i<InputTable.size()-1;i++) InputTable[i].pop_back();

    cout<<"-----------Input Matrix------------\n";

    //Creating Decision tree.

    TreeNode *root=new TreeNode();

    root->label="Input_Table";

    cout<<"------------Label = "<<root->label<<"---------------\n";

    printTable(InputTable);

    root=createTree(root,InputTable);

    //Prediction.

    int samp; cout<<"Enter number of prediction : "; cin>>samp;

    while(samp--)

    {

        map<string,string>mp;

        string inp;

        for(int i=0;i<InputTable[0].size()-1;i++)

            cout<<"Enter "<<InputTable[0][i]<<" : ",cin>>inp,mp[InputTable[0][i]]=inp;

        cout<<"Predicted value : "<<prediction(root,mp)<<endl;

        cout<<"=============================================================\n";

    }

    fclose(fp);

    return 0;

}

Training File :-

1.First row should be attribute name with space separated and it should be followed by n rows (tuples). Each tuple must have all the attribute value.

2.This program can't accept empty value of any attribute.

3.Class variable should be the last column of the training set file.

Input correct value is necessary for prediction :-

Friday 11 August 2017

Key Stroke Program (SMARTPRIX QUESTION)

Quen. Write a program to simulate a keyboard with given keys and their operation. You need to print the final text to STDOUT.

Type of Keys:

Each key affects the movement of the cursor on editor. The cursor position is identified by row and column.
alpha numeric space => this key inserts their respective symbol at cursors position and shift cursor.
@ => [CAPS Lock] toggles caps lock, i.e., if CapsLock is 'ON' after this key press it will be 'OFF' and vice versa. Initially CAPS Lock in 'OFF'.
# => [ENTER/New Line] inserts a new line character at cursor position and shift cursor position.
< => [LEFT arrow] moves cursor to one step left (if available). If cursor is at the starting of the row, it moves to end of the row above (if available).
> => [RIGHT arrow] moves cursor to one step right (if available). If cursor is at a row end it moves to starting of the row below (if available).
/ => [Backspace] deletes one character from the left of the cursor and move cursor one step left. It follows same direction rules as LEFT arrow key (<).
? => [Down arrow] If cursor is on last row nothing changes. The cursor moves to original column in next row if there are not enough characters in next row, cursor shifts to the end of the new row. Note: If key is pressed continuosly original column will not change with every key press.
^ => [UP arrow] If cursor is on first row nothing changes. The cursor moves to the original column (current) of the previous row, if there are not enough characters in previous row cursor shifts to the end of the previous row. Note: If key is pressed continuosly original column will not change with every key press.

Solution :

#include<bits/stdc++.h>

using namespace std;

int main()

{

string inp;

getline(cin,inp);

vector<string> out; //Array of output string

out.push_back("");

bool caps=0; //Caps lock flag initially in off mode

int curi=0,curj=0; //Cursor position variable ( curi = x-direction cursor, curj = y-direction cursor)

for(int i=0;i<inp.length();i++)

{
/* If current input character is alphanumeric character or space character then store it at cursor
position and shift cursor by one. ( Before storing, check for caps lock) */

if((inp[i]>='a' && inp[i]<='z')||(inp[i]>='A' && inp[i]<='Z') || (inp[i]>='0' && inp[i]<='9')||inp[i]==' ')

{

char t;

if(caps && (inp[i]>='a' && inp[i]<='z')) t=inp[i]-'a'+'A';

else t=inp[i];

if(curj==out[curi].length()) out[curi].push_back(t);

else out[curi].insert(out[curi].begin()+curj,t);

curj++;

}
/* If current input character is '#', then insert a new line character at current cursor
position and if there are some character right to the cursor in a row, then move them
to new line. Update the cursor position.*/

else if(inp[i]=='#')

{

curi++;

out.insert(out.begin()+curi,out[curi-1].substr(curj));

out[curi-1]=out[curi-1].substr(0,curj);

curj=0;

}
// If current input character is '@', then invert the caps lock flag.

else if(inp[i]=='@')

caps=(caps+1)%2;
/* If current character is '<', then shift the current cursor to one step left (if available). If cursor is at the starting of the row, it moves to end of the row above (if available)*/

else if(inp[i]=='<')

{

if(curi==0 && curj==0) continue;

if(curj>0) { curj--; continue;}

curi--;

curj=out[curi].length();

}
/* If current character is '>', then shift the current cursor to one step right (if available). If cursor is at a row end it moves to starting of the row below (if available). */

else if(inp[i]=='>')

{

if(curi==out.size()-1 && curj==out[curi].length()) continue;

if(curj<out[curi].length()) curj++;

else if(curi<out.size()-1) curi++,curj=0;

}
/* If current character is '/', then deletes one character from the left of the cursor and move cursor one step left. It follows same direction rules as LEFT arrow key (<). */

else if(inp[i]=='/')

{

if(curi==0 && curj==0) continue;

if(curj>0) { out[curi].erase(out[curi].begin()+curj-1),curj--; continue;}

string t=out[curi];

out.erase(out.begin()+curi);

curi--;

curj=out[curi].length();

out[curi]+=t;

}

else if(inp[i]=='^')

{

if(curi==0){ while(inp[i]=='^') i++; i--; continue;}

while(inp[i]=='^' && curi>0) curi--,i++;

while(inp[i]=='^') i++;

if(curj>out[curi].length()) curj=out[curi].length();

if(out[curi].length()==0) curj=0;

i--;

}

else if(inp[i]=='?')

{

if(curi==out.size()-1) { while(inp[i]=='?') i++; i--; continue;}

while(inp[i]=='?' && curi<out.size()-1) curi++,i++;

while(inp[i]=='?') i++;

if(curj>out[curi].length()) curj=out[curi].length();

if(out[curi].length()==0) curj=0;

i--;

}

for(int i=0;i<out.size();i++) cout<<out[i]<<endl;

return 0;

}

Example :

Input = asdf#q#pqr^^23

Output :

asd23f

pqr

Input = asdf1# @qwe^23

Output :

asdf231
 QWE

Input = asdf1#@ qwe<<<//23

Output :

asdf123QWE

Friday 3 March 2017

DATA ENCRYPTION STANDARD

DATA ENCRYPTION STANDARD PROGRAM in C++ for both Encryption and Decryption :-

/*=====================================================|
|    AUTHOR :- RAVI SHANKAR KUMAR                                                          |
|    FROM :- SITAMARHI(BIHAR),INDIA                    |
|    Email :- ravisk.cs.14@gmail.com                    |
|    NIT JALANDHAR, CSE PRE-FINAL YEAR                                                 |
|====================================================*/
/*PROGRAM CHECKER INPUT
19 52 87 121 155 188 223 241
   1 35 69 103 137 171 205 239
*/
#include<bits/stdc++.h>
using namespace std;
//IP is Initial Permutation Block for Plain Text
//============================INPUT BLOCK============================
static const int IP[64]={58,50,42,34,26,18,10, 2,
                     60,52,44,36,28,20,12, 4,
                     62,54,46,38,30,22,14, 6,
                     64,56,48,40,32,24,16, 8,
                     57,49,41,33,25,17, 9, 1,
                     59,51,43,35,27,19,11, 3,
                     61,53,45,37,29,21,13, 5,
                     63,55,47,39,31,23,15, 7};
//IIP is inverse of initial permutation block.
//Note :- It can be generated by IP also.
static const int IIP[64]={40,8,48,16,56,24,64,32,
                     39,7,47,15,55,23,63,31,
                     38,6,46,14,54,22,62,30,
                     37,5,45,13,53,21,61,29,
                     36,4,44,12,52,20,60,28,
                     35,3,43,11,51,19,59,27,
                     34,2,42,10,50,18,58,26,
                       33,1,41, 9,49,17,57,25};
//C0 and D0 for 64bit key to 56bit key generation and rotation to get
//the permuted key of 48 bit using Compression Block of permutation.
static const int c0[28]={57,49,41,33,25,17, 9, 1,
            58,50,42,34,26,18,10, 2,
            59,51,43,35,27,19,11, 3,
            60,52,44,36};
static const int d0[28]={63,55,47,39,31,23,15, 7,
            62,54,46,38,30,22,14, 6,
            61,53,45,37,29,21,13, 5,
            28,20,12, 4};
static const int compression[48]={14,17,11,24, 1, 5, 3,28,15, 6,21,10,
                23,19,12, 4,26, 8,16, 7,27,20,13, 2,
                41,52,31,37,47,55,30,40,51,45,33,48,
                44,49,39,56,34,53,46,42,50,36,29,32};
//EXPANSION BOX used to expand 32 bit Plain text to 48 bit for Xor operation
//with key for the current round
static const int expansion[48]={32, 1, 2, 3, 4, 5,
                4, 5, 6, 7, 8, 9,
                8, 9,10,11,12,13,
                                 12,13,14,15,16,17,
                                 16,17,18,19,20,21,
                           20,21,22,23,24,25,
                           24,25,26,27,28,29,
                           28,29,30,31,32, 1};
//8 S-box will be used in Each round of encryption and decryption.
static const int sbx[8][4][16]={//S1 BOX
                    14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7,
                   0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8,
                   4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0,
                   15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13,
                   //S2 BOX
                   15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10,
                   3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5,
                   0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15,
                   13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9,
                   //S3 BOX
                10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8,
                   13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1,
                   13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7,
                     1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12,
                   //S4 BOX
                   7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15,
                   13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9,
                   10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4,
                   3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14,
                   //S5 BOX
                   2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9,
                   14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6,
                   4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14,
                   11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3,
                   //S6 BOX
                   12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11,
                   10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8,
                   9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6,
                   4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13,
                   //S7 BOX
                   4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1,
                   13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6,
                   1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2,
                   6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12,
                   //S8 BOX
                    13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7,
                   1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2,
                   7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8,
                   2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11};
static const int straightPer[32]={16, 7,20,21,29,12,28,17,
                        1,15,23,26, 5,18,31,10,
                        2, 8,24,14,32,27, 3, 9,
                     19,13,30, 6,22,11, 4,25};
//================================HELPER FUNCTION=======================
/*
Here Function char_to_binary takes input as integer
equivalent of character and returns the number equivalent
in base b; Generally we needed b=2 in DES.
*/
char *char_to_binary(int num,int b)
{
char *bin=new char[9]; int k=7;
while(k>=0)
{
      bin[k--]=num%b+'0';
      num/=b;
}
bin[8]='\0';
return bin;
}
/*
Here Function binary_to_char takes character array as input,
convert them into decimal ascii value and return corresponding character
*/
char binary_to_char(char a[])
{
int num=0;
for(int i=0;i<8;i++)
    num=(num*2)+(a[i]-'0');
char ans=num;
return ans;
}
/*
Here function Initial_Permute will permute the 2d char array
input according to Initial_Permutation block IP and will return
Permuted 2d char array output.
*/
char **Initial_Permute(char **input)
{
   //Declaration of 2d char array.
   char **output=new char*[8];
   for(int i=0;i<8;i++) output[i]=new char[9];
   //Mapping of input to output using IP
   for(int i=0;i<8;i++)
      for(int j=0;j<8;j++)
         {
            int row=(IP[i*8+j]-1)/8,col=(IP[i*8+j]-1)%8;
            output[i][j]=input[row][col];
         }
   return output;
}
/*
Here function Initial_Permute will permute the 2d char array
input according to Initial_Permutation block IP and will return
Permuted 2d char array output.
*/
char **Inv_Initial_Permute(char **input)
{
   //Declaration of 2d char array.
   char **output=new char*[8];
   for(int i=0;i<8;i++) output[i]=new char[9];
   //Mapping of input to output using IP
   for(int i=0;i<8;i++)
      for(int j=0;j<8;j++)
         {
            int row=(IIP[i*8+j]-1)/8,col=(IIP[i*8+j]-1)%8;
            output[i][j]=input[row][col];
         }
   return output;
}
//This function is very simple.
char xors(char a,char b)
{
if(a==b) return '0';
else return '1';
}
//================================KEY GENERATION=======================
/*
Here function will convert 64 bit character of key to 56 bit char key
using C0 and D0 block.
*/
void convert_64_to_56(char **input,char **output)
{
   //Maping using C0 and D0 block.
   for(int i=0;i<28;i++)
   {
      int row=(c0[i]-1)/8,col=(c0[i]-1)%8;
      output[0][i]=input[row][col];
      row=(d0[i]-1)/8,col=(d0[i]-1)%8;
      output[1][i]=input[row][col];
   }
   output[0][28]=output[1][28]='\0';
   return;
}
/*
Here function left_shift will shift 56bit key by one bit.
You need to call it twice if you want to shift left by 2 bit.
*/
void left_shift(char **input)
{
   char temp1=input[0][0],temp2=input[1][0];
   for(int i=0;i<27;i++)
      {
         input[0][i]=input[0][i+1];
         input[1][i]=input[1][i+1];
      }
   input[0][27]=temp1; input[1][27]=temp2;
   return;
}
void key_generation(char key[],char **keys)
{
   //Declare a 2d character array to store 64bit keys
   char **binary=new char*[8];
   for(int i=0;i<8;i++) binary[i]=new char[9];
   //Initialize 64bit key by calling char_to_binary converter.
   for(int i=0;i<8;i++)
        binary[i]=char_to_binary(key[i],2);
   //Call Initial Permutation of 64-bit Key.
   //binary=Initial_Permute(binary);
   //Call convert_64_to_56
   char **output=new char*[2];
   output[0]=new char[29];
   output[1]=new char[29];
   convert_64_to_56(binary,output);
   //16 round key generation.
   for(int i=0;i<16;i++)
   {
       //Call one time shift if round=1,2,9 or 16
       //Else call twice.
       if(i==0||i==1||i==8||i==15) left_shift(output);
       else left_shift(output),left_shift(output);
       //MAP shifted 2d array to round key using fin block
       for(int k=0;k<48;k++)
       {
          int row=(compression[k]-1)/28,col=(compression[k]-1)%28;
          keys[i][k]=output[row][col];
       }
       keys[i][48]='\0';
   }
   return;
}
//================================ENCRYPTION=======================
char *use_SBox(char inp[])
{
   char *ans=new char[33];
   char *temp=new char[9];
   int row,col,indx=0,pos;
   //USE all S-Box to compress each 6-bit into 4bit
   for(int i=0;i<8;i++)
   {
      pos=i*6;
      row=(inp[pos]-'0')*2+(inp[pos+5]-'0'); //First and last bit for row index
      //Second,Third,Fourth and fifth bits for column index
      col=(inp[pos+1]-'0')*8+(inp[pos+2]-'0')*4+(inp[pos+3]-'0')*2+(inp[pos+4]-'0');
      temp=char_to_binary(sbx[i][row][col],2);
      ans[indx++]=temp[4],ans[indx++]=temp[5],ans[indx++]=temp[6],ans[indx++]=temp[7];
   }
   return ans;
}
char *Encryption(char pt[],char **keys)
{
   //Declare a 2d character array to store 64bit PlainText
   char **binary=new char*[8];
   for(int i=0;i<8;i++) binary[i]=new char[9];
   //Initialize 64bit array by calling char_to_binary converter.
   for(int i=0;i<8;i++)
        binary[i]=char_to_binary(pt[i],2);
   //Call Initial Permutation of 64-bit Key.
   binary=Initial_Permute(binary);
   //Break 64bit block into left and right block of 32bit each
   char *left=new char[33];
   char *right=new char[33];
   char *temp=new char[33];
   for(int i=0;i<4;i++)
      for(int j=0;j<8;j++)
        {
           left[i*8+j]=binary[i][j];
           right[i*8+j]=binary[i+4][j];
        }
   left[32]=right[32]='\0';
   //Apply all 16 rounds to get final output.
   for(int k=0;k<16;k++)
   {
     //Take copy of right part.
     for(int i=0;i<32;i++) temp[i]=right[i];
     temp[32]='\0';
     //Expand 32bit right part to 48bit using expansion box
     char *expands=new char[49];
     for(int i=0;i<48;i++) expands[i]=temp[expansion[i]-1];
     expands[48]='\0';
     //XOR it with kth key block of 48 bit.
     for(int i=0;i<48;i++) expands[i]=xors(expands[i],keys[k][i]);
     //Apply all 8 S-box upon it to get 32bit output.
     temp=use_SBox(expands);
     //Apply stright permutation box
     for(int i=0;i<32;i++) expands[i]=temp[straightPer[i]-1];
     //XOR this output with left 32bit
     for(int i=0;i<32;i++) left[i]=xors(left[i],expands[i]);
     //SWAPS between left and right
     for(int i=0;i<32;i++)
       temp[i]=left[i],left[i]=right[i],right[i]=temp[i];
   }
   //SWAPS left and right because we don't have to swap in the last
   //round but we have got the swapped value.
   for(int i=0;i<32;i++)
       temp[i]=left[i],left[i]=right[i],right[i]=temp[i];
   //Make this 64 bit 1D to 2D array
   for(int i=0;i<32;i++)
    binary[i/8][i%8]=left[i],binary[(i+32)/8][(i+32)%8]=right[i];
    //Apply inverse permutation box by calling Inv_Initial_Permute function
    binary=Inv_Initial_Permute(binary);
    //Convert this binary 64bit to 8 charactes.
    for(int i=0;i<8;i++)
      pt[i]=binary_to_char(binary[i]);
    return pt;
}
//================================DECRYPTION=========================
char *Decryption(char pt[],char **keys)
{
   //Declare a 2d character array to store 64bit PlainText
   char **binary=new char*[8];
   for(int i=0;i<8;i++) binary[i]=new char[9];
   //Initialize 64bit array by calling char_to_binary converter.
   for(int i=0;i<8;i++)
        binary[i]=char_to_binary(pt[i],2);
   //Call Initial Permutation of 64-bit Key.
   binary=Initial_Permute(binary);
   //Break 64bit block into left and right block of 32bit each
   char *left=new char[33];
   char *right=new char[33];
   char *temp=new char[33];
   for(int i=0;i<4;i++)
      for(int j=0;j<8;j++)
        {
           left[i*8+j]=binary[i][j];
           right[i*8+j]=binary[i+4][j];
        }
   left[32]=right[32]='\0';
   //Apply all 16 rounds to get final output.
   for(int k=0;k<16;k++)
   {
     //Take copy of right part.
     for(int i=0;i<32;i++) temp[i]=right[i];
     temp[32]='\0';
     //Expand 32bit right part to 48bit using expansion box
     char *expands=new char[49];
     for(int i=0;i<48;i++) expands[i]=temp[expansion[i]-1];
     expands[48]='\0';
     //XOR it with kth key block of 48 bit.
     for(int i=0;i<48;i++) expands[i]=xors(expands[i],keys[15-k][i]);
     //Apply all 8 S-box upon it to get 32bit output.
     temp=use_SBox(expands);
     //Apply stright permutation box
     for(int i=0;i<32;i++) expands[i]=temp[straightPer[i]-1];
     //XOR this output with left 32bit
     for(int i=0;i<32;i++) left[i]=xors(left[i],expands[i]);
     //SWAPS between left and right
     for(int i=0;i<32;i++)
       temp[i]=left[i],left[i]=right[i],right[i]=temp[i];
   }
   //SWAPS left and right because we don't have to swap in the last
   //round but we have got the swapped value.
   for(int i=0;i<32;i++)
       temp[i]=left[i],left[i]=right[i],right[i]=temp[i];
   //Make this 64 bit 1D to 2D array
   for(int i=0;i<32;i++)
    binary[i/8][i%8]=left[i],binary[(i+32)/8][(i+32)%8]=right[i];
    //Apply inverse permutation box by calling Inv_Initial_Permute function
    binary=Inv_Initial_Permute(binary);
    //Convert this binary 64bit to 8 charactes.
    for(int i=0;i<8;i++)
      pt[i]=binary_to_char(binary[i]);
    return pt;
}
//================================MAIN FUNCTION=======================
int main()
{
//Declare and take input key string of 8 characters
char *key=new char[9];
cout<<"Enter a key string : ";
cin>>key;
//Declare 2d keys array to store all 16 round keys
char **keys=new char*[16];
for(int i=0;i<16;i++) keys[i]=new char[49];
//Call key Generation function
key_generation(key,keys);
for(int i=0;i<16;i++)
     printf("Key for round %2d : %s\n",i+1,keys[i]);
//Declare and take input plain text string of 8 characters
char *pt=new char[9];
cout<<"Enter plain text of 8 character : ";
cin>>pt;
//Call Encryption function to encrypt the plain text
pt=Encryption(pt,keys);
cout<<"Encrypted text = "<<pt<<endl;
//Call Decryption function to decrypt the encrypted text
pt=Decryption(pt,keys);
cout<<"Decrypted text = "<<pt<<endl;
return 0;
}

Monday 27 February 2017

Simplified Data Encryption Standard (Symmetric Block Cipher)

Simplified Data Encryption Standard (S-DES)

C++ Simple Program to understand Simplified version of Data Encryption Standard.

/*======================================================= |
|    AUTHOR :- RAVI SHANKAR KUMAR |
|    FROM :- SITAMARHI(BIHAR),INDIA |
|    Email :- ravisk.cs.14@gmail.com |
|    NIT JALANDHAR, CSE PRE-FINAL YEAR |
|=======================================================*/
#include<iostream>
#include<cstring>
using namespace std;
//KEY PERMUTATION BLOCKS
const int p10[10]={3,5,2,7,4,10,1,9,8,6};
const int p8[8]={6,3,7,4,8,5,10,9};
//PLAIN TEXT PERMUTATION BLOCKS
const int IP[8]={2,6,3,1,4,8,5,7}; //Initial Permutation block
const int p4[4]={2,4,3,1};
const int IIP[8]={4,1,3,5,7,2,8,6}; //Inverse of Initial permutation block
const int EP[8]={4,1,2,3,2,3,4,1}; //Expansion block
//S-Box
const int sbx[2][4][4]={//First S-Box
            1,0,3,2,
                3,2,1,0,
                0,2,1,3,
                3,1,3,2,
                //Second S-Box
                0,1,2,3,
                2,0,1,3,
                3,0,1,0,
                2,1,0,3
               };
void key_generation(char *input,char **output)
{
   char *temp=new char[11];
   //Apply P10 on input
   for(int i=0;i<10;i++) temp[i]=input[p10[i]-1];
   temp[10]='\0';
   //Shift left temp array by 1-bit in left and right part
   //of 5-bit each
   char msb1=temp[0],msb2=temp[5];
   for(int i=0;i<4;i++) temp[i]=temp[i+1],temp[i+5]=temp[i+6];
   temp[9]=msb2,temp[4]=msb1;
   //Apply P8 to get first key
   for(int i=0;i<8;i++) output[0][i]=temp[p8[i]-1];
   //Shift left temp array by 2-bit in left and right part
   //of 5-bit each
   msb2=temp[1];msb1=temp[0];
   for(int i=0;i<4;i++) temp[i]=temp[i+2];
   temp[3]=msb1; temp[4]=msb2;
   msb2=temp[6];msb1=temp[5];
   for(int i=0;i<4;i++) temp[i+5]=temp[i+7];
   temp[8]=msb1; temp[9]=msb2;
   //Apply P8 to get second key
   for(int i=0;i<8;i++) output[1][i]=temp[p8[i]-1];
   return;
}
void xors(char *inp1,char *inp2)
{
int len=strlen(inp1);
for(int i=0;i<len;i++)
{
     if(inp1[i]==inp2[i]) inp1[i]='0';
     else inp1[i]='1';
}
return;
}
char *sboxes(char *inp)
{
char *out=new char[5];
int row,col,value;
for(int i=0;i<2;i++)
{
    row=(inp[0+i*4]-'0')*2+(inp[3+i*4]-'0');
    col=(inp[1+i*4]-'0')*2+(inp[2+i*4]-'0');
        value=sbx[i][row][col];
    if(value==0) out[0+i*2]=out[1+i*2]='0';
    else if(value==1) out[0+i*2]=0,out[1+i*2]='1';
    else if(value==2) out[0+i*2]='1',out[1+i*2]='0';
    else out[0+i*2]=out[1+i*2]='1';
}
return out;
}
void Encryption(char *pt,char **keys)
{
   //Apply Initial Permutation IP
   char *temp=new char[9];
   for(int i=0;i<8;i++) temp[i]=pt[IP[i]-1];
   //==========================ROUND-FIRST=====================
   //Divide into two parts
   char *left=new char[5];
   char *right=new char[5];
   for(int i=0;i<4;i++)
       left[i]=temp[i],right[i]=temp[i+4];
   //Apply expansion on right part
   char *expands=new char[9];
   for(int i=0;i<8;i++) expands[i]=right[EP[i]-1];
   //XOR with first key;
   xors(expands,keys[0]);
   //USE S-Boxes
   right=sboxes(expands);
   //Apply P4
   for(int i=0;i<4;i++) expands[i]=right[p4[i]-1];
   //Xor it with left part
   xors(left,expands);
   //Swap between right part and output of above
   for(int i=0;i<4;i++)
     temp[i]=temp[i+4],temp[i+4]=left[i];
   //========================ROUND-SECOND======================
   for(int i=0;i<4;i++)
       left[i]=temp[i],right[i]=temp[i+4];
   //Apply expansion on right part
   for(int i=0;i<8;i++) expands[i]=right[EP[i]-1];
   //XOR with second key;
   xors(expands,keys[1]);
   //USE S-Boxes
   right=sboxes(expands);
   //Apply P4
   for(int i=0;i<4;i++) expands[i]=right[p4[i]-1];
   //Xor it with left part
   xors(left,expands);
   for(int i=0;i<4;i++)
       temp[i]=left[i];
   //Apply IP Inverse on output
   for(int i=0;i<8;i++) pt[i]=temp[IIP[i]-1];
   return;
}
void Decryption(char *ct,char **keys)
{
//Apply Initial Permutation IP
   char *temp=new char[9];
   for(int i=0;i<8;i++) temp[i]=ct[IP[i]-1];
   //==========================ROUND-FIRST=====================
   //Divide into two parts
   char *left=new char[5];
   char *right=new char[5];
   for(int i=0;i<4;i++)
       left[i]=temp[i],right[i]=temp[i+4];
   //Apply expansion on right part
   char *expands=new char[9];
   for(int i=0;i<8;i++) expands[i]=right[EP[i]-1];
   //XOR with second key;
   xors(expands,keys[1]);
   //USE S-Boxes
   right=sboxes(expands);
   //Apply P4
   for(int i=0;i<4;i++) expands[i]=right[p4[i]-1];
   //Xor it with left part
   xors(left,expands);
   //Swap between right part and output of above
   for(int i=0;i<4;i++)
     temp[i]=temp[i+4],temp[i+4]=left[i];
   //========================ROUND-SECOND======================
   for(int i=0;i<4;i++)
       left[i]=temp[i],right[i]=temp[i+4];
   //Apply expansion on right part
   for(int i=0;i<8;i++) expands[i]=right[EP[i]-1];
   //XOR with first key;
   xors(expands,keys[0]);
   //USE S-Boxes
   right=sboxes(expands);
   //Apply P4
   for(int i=0;i<4;i++) expands[i]=right[p4[i]-1];
   //Xor it with left part
   xors(left,expands);
   for(int i=0;i<4;i++)
      temp[i]=left[i];
   //Apply IP inverse on output
   for(int i=0;i<8;i++) ct[i]=temp[IIP[i]-1];
   return;
}
int main()
{
   //Take Plain text input
   cout<<"Enter Plain Text (8-bit binary) : ";
   char *pt=new char[9];
   cin>>pt;
   //Take Key input
   cout<<"Enter Key (10-bit binary) : ";
   char *key=new char[11];
   cin>>key;
   //Declare storage for key to be generated
   char **keys=new char*[2];
   keys[0]=new char[9];
   keys[1]=new char[9];
   //Call key generation method
   key_generation(key,keys);
   cout<<"First round keys : "<<keys[0]<<endl;
   cout<<"Second round keys : "<<keys[1]<<endl<<endl;
   //Call Encryption method
   Encryption(pt,keys);
   cout<<"Encrypted text is : "<<pt<<endl;
   //Call Decryption method
   Decryption(pt,keys);
   cout<<"Decrypted text is : "<<pt<<endl;
   return 0;
}