Showing posts with label Data Structure and Algorithm. Show all posts
Showing posts with label Data Structure and Algorithm. Show all posts

Sunday, November 3, 2013

Rijndael Symmetric Algorithm - Encryption and Decryption

In this article we are going to see how to encrypt and decrypt the data using symmetric algorithm Rijndael.
User text can be encrypted using a password using  different format of bytes like 128,192 and 256.
So we have get the PasswordDerivedBytes , The Keybytes,InitVectorbytes and symmetric mode are important one to set in object of RijndaelManaged.

Symmetric algorithm means, same password is used to encrypt and decrypt the input string. i.e one format string into the another format

Encryption :
Code :
            Console.WriteLine("Enter the input string to encrypt");
            string input = Console.ReadLine();
            Console.WriteLine("Enter the password to encrypt the input string.");
            string password = Console.ReadLine();
            string encstring= RijndaelAlgo.Encrypt(input, password);
            Console.WriteLine("String after Encryption :"+Environment.NewLine + encstring);
            Console.ReadLine();


Output:
Enter the input string to encrypt
Computer science

Enter the password to encrypt the input string.
rajesh

String after Encryption :
qVWbRozCX1680RYmkHIy8vOsctlnanCZP+cnC7I459A=


Decryption:
Code :
            Console.WriteLine("Enter the input string to decrypt");
            string input = Console.ReadLine();
            Console.WriteLine("Enter the password to decrypt the input string.");
            string password = Console.ReadLine();
            string encstring= RijndaelAlgo.Decrypt(input, password);
            Console.WriteLine("String after Decryption :"+Environment.NewLine + encstring);
            Console.ReadLine();



Output:
Enter the input string to decrypt
qVWbRozCX1680RYmkHIy8vOsctlnanCZP+cnC7I459A=

Enter the password to decrypt the input string.
rajesh

String after Decryption :
Computer science

Code for RijndaelAlgo :

  public class RijndaelAlgo
    {

        static stringsaltValue = "s@!tVal*e";
        static stringhashAlgorithm = "SHA1";
        static intpasswordIterations = 2;
        static stringinitVector = "@1B2c3!@)#$%@#X6g7FG";
        static int keySize = 256;

        public static string Encrypt(stringplainText, string passPhrase)
        {

            byte[] initVectorBytes = Encoding.ASCII.GetBytes(initVector);
            byte[] saltValueBytes = Encoding.ASCII.GetBytes(saltValue);
            byte[] plainTextBytes = Encoding.UTF8.GetBytes(plainText);

            PasswordDeriveBytes password = new PasswordDeriveBytes(
                                                            passPhrase,
                                                            saltValueBytes,
                                                            hashAlgorithm,
                                                            passwordIterations);


            byte[] keyBytes = password.GetBytes(keySize / 8);

            RijndaelManaged symmetricKey = new RijndaelManaged();
            symmetricKey.Mode = CipherMode.ECB;
            ICryptoTransform encryptor = symmetricKey.CreateEncryptor(keyBytes, initVectorBytes);
            MemoryStream memoryStream = new MemoryStream();
            CryptoStream cryptoStream = new CryptoStream(memoryStream, encryptor, CryptoStreamMode.Write);
            cryptoStream.Write(plainTextBytes, 0, plainTextBytes.Length);
            cryptoStream.FlushFinalBlock();
            byte[] cipherTextBytes = memoryStream.ToArray();
            memoryStream.Close();
            cryptoStream.Close();
            string cipherText = Convert.ToBase64String(cipherTextBytes);
            return cipherText;
        }

        public static string Decrypt(stringcipherText, string passPhrase)
        {

            byte[] initVectorBytes = Encoding.ASCII.GetBytes(initVector);
            byte[] saltValueBytes = Encoding.ASCII.GetBytes(saltValue);
            byte[] cipherTextBytes = Convert.FromBase64String(cipherText);

            PasswordDeriveBytes password = new PasswordDeriveBytes(passPhrase, saltValueBytes, hashAlgorithm, passwordIterations);

            byte[] keyBytes = password.GetBytes(keySize / 8);
            RijndaelManaged symmetricKey = new RijndaelManaged();
            symmetricKey.Mode = CipherMode.ECB;
            ICryptoTransform decryptor = symmetricKey.CreateDecryptor(keyBytes, initVectorBytes);
            MemoryStream memoryStream = new MemoryStream(cipherTextBytes);
            CryptoStream cryptoStream = new CryptoStream(memoryStream, decryptor, CryptoStreamMode.Read);
            byte[] plainTextBytes = newbyte[cipherTextBytes.Length];

            // Start decrypting.
            intdecryptedByteCount = cryptoStream.Read(plainTextBytes, 0, plainTextBytes.Length);
            memoryStream.Close();
            cryptoStream.Close();
            string plainText = Encoding.UTF8.GetString(plainTextBytes, 0, decryptedByteCount);

            // Return decrypted string.  
            return plainText;
        }
    }




I Hope from this article you can learn how to encryption and decryption using symmetric algorithm

Sunday, October 27, 2013

IMEI Number and Check digit Algorithm

This purpose of this article is used to explain the IMEI Number and Check digit Algorithm which is  normally added as last digit in the IMEI number.

what is IMEI ?
                International Mobile Equipment Identity used to identify the mobile phones and some of the satellite phones. IMEI number is normally present in the box of the phone. To Use the IMEI number by typing *#06# or *#0000# on some phones. The IMEI number is used by rthe GSM network to identify a valid device.

What is Check digit ?
      Check digit is present in the Last of the IMEI number it is generated based on LUHN 's Algorithm, To check a Valid Device. This algorithm is invented by an IBM scientist.

Algorithm :

IMEI : 256533912774352

1. Start from the right double every second digit.
2. Add the second digit if it gives double digit on multiply
3. Now add all number and modulus with 10 , If remaining present other than 0 minus with 10 result value is check digit otherwise 0 is check digit.





Program in c#:


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication8
{
    class Program
    {
        static void Main(string[] args)
        {

            Console.WriteLine("Is Valid IMEI " + IsValidIMEI("256533912774354"));
            Console.Read();
        }

        static boolIsValidIMEI(string imei)
        {
            int []n=new int[imei.Length];
            for (int i = 0; i < imei.Length; i++)
            {
                n[i] =  int.Parse(imei[i].ToString());
            }

            for(inti=0;i<imei.Length-1;i++)
            {
                if(i %2==1)
                {
                    n[i] = n[i]*2;
                }
            }

            for(inti=0;i<imei.Length-1;i++)
            {
                if(i %2==1)
                {
                    if(n[i].ToString().Length>1)
                    n[i] = int.Parse(n[i].ToString()[0].ToString()) + int.Parse(n[i].ToString()[1].ToString());
                }
            }
            
            int total=0;
            for(inti=0;i<imei.Length-1;i++)
            {
             total+=n[i];  
            }

            int mod = total %10;

            if(mod>0)
            {
                mod=10-mod;
            }
        
        return (n[imei.Length-1]==mod);
        }

    }
}




Output : 

ISValid IMEI : True


From this article , you will learn what is the algorithm use to calculate the check digit.


Tuesday, September 3, 2013

Generic Quick Sorting - C#

In this article we are going to see the Generic Quick Sorting implementation using C#.

Quick Sort :




Quick Sort is a Divide and conquer algorithm, It divides the collection int to two sub sets based on the pivot element selected, one subset is a collection elements which is smaller than pivot, another subset is collection of elements consists of larger than pivot.then each subsets are undergoes following steps again.Entire sort can be done in O(log n)

Steps :
1. Consider a element as Pivot from the List.
2. ReOrder the list so the elements which are lesser than pivot arrange previous in the order of the pivot and     the elements which are higher than pivot arrange next in the order of the pivot.
3. Recursively apply the above steps to each two subsets individually.


Algorithm :

function quicksort('array')
      if length('array')1
          return 'array' 
      for each 'x' in 'array'
          if 'x''pivot' then append 'x' to 'less'
          else append 'x' to 'greater'

      returnconcatenate(quicksort('less'),list('pivot'), quicksort('greater'))


Now Let we see this implementation in C#

        First Derive a Generic List<T> which is comparable, Then add collection to it ,Add a additional method to it as Order to order a collection based on the Quick Sort by implementing the algorithm. Following type in Generic so any data type can be sorted using this.


class Quicksort<T>:List<T> whereT : IComparable
    {
        public List<T> Order()
        {           
            return SortList(this.ToList<T>());
        }

        public  List<T> SortList(List<T> values)
        {
            List<T> _left = newList<T>();
            List<T> _right = newList<T>();

            if (values.Count() > 1)
            {
                T pivot = values[values.Count - 1];
                values.RemoveAt(values.Count - 1);

                foreach (T each invalues)
                {
                    if (each.CompareTo(pivot) == 1)
                    {
                        _right.Add(each);
                    }
                    else
                    {
                        _left.Add(each);
                    }
                }
                return MergeList(SortList(_left), pivot, SortList(_right));
            }
            return values;
        }

        private List<T> MergeList(List<T> left, T pivot, List<T> right)
        {
            left.Add(pivot);
            left.AddRange(right);
            return left;
        }

    }


 Now create a Two list one with int type other with string type and order the collection using Quick sort.

class Program
    {
        static void Main(string[] args)
        {
            Quicksort<int> _sorting = new Quicksort<int>();
            _sorting.AddRange(new int[] { 3,1,8,45,2,5,7});
            Console.WriteLine("Ordering the numbers using Quick Sort");
            foreach (int s in _sorting.Order())
            {
                Console.WriteLine(s);
            }

            Quicksort<string> _names = new Quicksort<string>();
            _names.AddRange(new string[]{"Rajesh","Suresh","Pavi","Anna","Ganesh","Sathish","Kani","Hanish","Babu","Dilli"});
            Console.WriteLine();
            Console.WriteLine("Ordering the names using Quick Sort");
            foreach (string s in_names.Order())
            {
                Console.WriteLine(s);
            }
            Console.Read();
        }
    }



Output :




From this article you can learn the Generic Quick Sorting algorithm in C# and the process of algorithm.

Sunday, July 14, 2013

Microsoft .Net Framework - PreOrder, PostOrder, InOrder Traversal in Binary Tree C#

















                                                                                                                                                   

Binary Tree   
      Binary search Tree is a Data Structure having following Properties .

    1. Left Node value must be less than root node value
    2. Right Node value must be greater than root node value
    3. Each Node must be Unique.

Normally this algorithm is used to search the Data present in the collection.
























                  
        This binary Tree have three traversal to visit the nodes. PreOrder, PostOrder,InOrder to iterate the elements from collections, Normally it is used to search the item. When using Binary Search we can reduce the search time to O(Log n),

Now we See the Count Property, Insert, Exists, Search, PreOrder, PostOrder, InOrder Traversal Methods.
Insert the int data into the Tree in the order : 8,3,4,12,10,13,1

InOrder
1. First visit the Left Child
2. Second visit the parent node
3. Third visit the Right Child

PostOder
1. First visit the Left Child
2. Second visit the Right Child
3. Third visit the Parent node.

PreOrder
1. First visit the Parent node
2. Second visit the Left Child 
3. Third visit the Right Child







































Output :





Let we see now the Implementation of BinaryTreeNode<T>
    enum Child
    {
        Left,
        Right
    }

    enum Order
    {
        InOrder,
        PostOrder,
        PreOrder
    }

 [Serializable]
    class BinaryTreeNode<T> where  T : IComparable<T>
    {
        public T Value
        {
            set;
            get;
        }

        public BinaryTreeNode<T>Left;

        public BinaryTreeNode<T>Right;      

        public BinaryTreeNode(T value)
        {
            this.Value = value;
        }
    }


Now the Implementation of the Calling Part of the Collection.

class Program
    {
        static void Main(string[] args)
        {
            BinarySearchTree<int> tree = new BinarySearchTree<int>();
            tree.Insert(8);
            tree.Insert(3);
            tree.Insert(4);
            tree.Insert(12);
            tree.Insert(10);
            tree.Insert(13);          
            tree.Insert(1);
            Console.WriteLine("Total Nodes in Tree is {0}", tree.Count);          
            BinaryTreeNode searchnode = tree.Search(12);
            Console.WriteLine("\nSearch Node {0} : Left Child : {1}, Right Child : {2}",
                searchnode.Value, searchnode.Left.Value, searchnode.Right.Value);
            Console.WriteLine("\n{0} Node Exists in Tree {1} : ", 13, tree.Exists(13));
            Console.WriteLine("\nInOrder Traversal");
            foreach (BinaryTreeNode v in tree.InOrder())
            {
            Console.WriteLine("Node : "+v.Value);
            }
            Console.WriteLine();
            Console.WriteLine("PreOrder Traversal");
            foreach (BinaryTreeNode v in tree.PreOrder())
            {
            Console.WriteLine("Node : "+v.Value);
            }
            Console.WriteLine();
            Console.WriteLine("PostOrder Traversal");
            foreach (BinaryTreeNode v in tree.PostOrder())
            {
            Console.WriteLine("Node : "+v.Value);
            }
            Console.Read();
        }
    }  

Now the Implementation Of BinaryTree With Insert, PostOrder, PreOrder, InOrder, Search, Exists Methods and Count Property


 [Serializable]
    class BinarySearchTree<T>where T  : IComparable<T>
    {
        private BinaryTreeNode<T> root;
     
        public int Count { set; get; }

        public void Insert(T value)
        {
            BinaryTreeNode<T> node = new BinaryTreeNode<T> (value);
            if (root == null)
            {
                root = node;
            }
            else
            {
                PlaceNode(root, node);
            }
            Count++;
        }

        public void PlaceNode(BinaryTreeNode<T> root, BinaryTreeNode<T> newnode)
        {
            BinaryTreeNode<T> ponode=root;
            BinaryTreeNode<T> tree = null;
            Child pos = Child.Left;
            do
            {
                 pos = CheckNode(ponode, newnode);
                tree = ponode;
                if (pos == Child.Left)
                {
                    ponode = tree.Left;                  
                }
                else
                {
                    ponode = tree.Right;
                }              
            }
            while (ponode != null);
         
            if(pos==Child.Left)
                tree.Left = newnode;
            else
                tree.Right =newnode;

        }

        private Child CheckNode(BinaryTreeNode<T> root, BinaryTreeNode<T> newnode)
        {
            if (newnode.Value.CompareTo(root.Value) < 0)
            {
                return Child.Left;
            }
            else if (newnode.Value.CompareTo(root.Value) > 0)
            {
                return Child.Right;
            }
            else
            {
                throw new ArgumentException("Node is Duplicated");
            }
        }

        public bool Exists(T value)
        {
            BinaryTreeNode<T> node=Search(value);
            if(node!=null)
                return true;
            else
                return false;
        }

        public BinaryTreeNode<T> Search(T value)
        {
            BinaryTreeNode<T> node = root;
            while (node != null)
            {
                if (node.Value.CompareTo(value) == 0)
                {
                    return node;
                }
                else if (node.Value.CompareTo(value) > 0)
                {
                    node = node.Left;
                }
                else
                {
                    node = node.Right;
                }
            }
            return null;
        }
     
        private IEnumerable<BinaryTreeNode<T> > Ordering(BinaryTreeNode<T> node,Order ord)
        {
            BinaryTreeNode<T> first = null;
            BinaryTreeNode<T> secon = null;
            BinaryTreeNode<T> third = null;
            if (node != null)
            {              
                if (ord == Order.InOrder)
                {
                    foreach (BinaryTreeNode<T> firstiter in Ordering(node.Left, ord))
                    {
                        yield return firstiter;
                    }
                    yield return  node;
                    foreach (BinaryTreeNode<T> firstiter in Ordering(node.Right, ord))
                    {
                        yield return firstiter;
                    }
                 
                }
                else if(ord == Order.PostOrder)
                {
                    foreach (BinaryTreeNode<T> firstiter in Ordering(node.Left, ord))
                    {
                        yield return firstiter;
                    }
                    foreach (BinaryTreeNode<T> firstiter in Ordering(node.Right, ord))
                    {
                        yield return firstiter;
                    }
                    yield return node;                              
                }
                else if (ord == Order.PreOrder)
                {
                    yield return  node;
                    foreach (BinaryTreeNode<T> firstiter in Ordering(node.Left, ord))
                    {
                        yield return firstiter;
                    }
                    foreach (BinaryTreeNode<T> firstiter in Ordering(node.Right, ord))
                    {
                        yield return firstiter;
                    }              
                }              
            }
        }

        public IEnumerable<BinaryTreeNode<T> > PreOrder()
        {
            return Ordering(root, Order.PreOrder);
        }

        public IEnumerable<BinaryTreeNode<T> > PostOrder()
        {
            return Ordering(root, Order.PostOrder);
        }

        public IEnumerable<BinaryTreeNode<T> > InOrder()
        {
            return Ordering(root, Order.InOrder);
        }
    }


From this article we can learn how to create a traversal in Binary Tree and Insert Method and Exists Method.