Thursday, December 31, 2015

Autokey Cipher

Autokey encryption and decryption

Plaint text = "FOLLOWDIRECTION"
Autokey = P

This Autokey is polyalphabet Substitution cipher. In this cipher, the key is a stream of subkeys which is each subkey is used to encrypt the corresponding character in the plaintext.

For example

Plaintext --> F O L L O W D I R E C T I O N
Key       --> P F O L L O W D I R E C T I O

As shown, the key is add the first of subkeys.

Lets Encrypt


              F O L L O W D I R E C T I O N
              P F O L L O W D I R E C T I O
              -----------------------------
          (+) U T Z W Z K Z L Z V G V B W B
              -----------------------------
  
 * can use vigenere table to calculate


Lets Decrypt


Put the key first

              P
              -----------------------------
              U T Z W Z K Z L Z V G V B W B
              -----------------------------
              
Do subtraction cipher - key. ex: U - P = F . Add F plaintext letter to the end of the keystream.

              F
              P F
              -----------------------------
              U T Z W Z K Z L Z V G V B W B
              -----------------------------

Do subtraction cipher - key. ex: T - F = O . Again add O plaintext letter to the end of the keystream.

              F O
              P F O
              -----------------------------
              U T Z W Z K Z L Z V G V B W B
              -----------------------------
 
              F O L
              P F O L
              -----------------------------
              U T Z W Z K Z L Z V G V B W B
              -----------------------------

              F O L L
              P F O L L
              -----------------------------
              U T Z W Z K Z L Z V G V B W B
              -----------------------------

continue subtraction until

              F O L L O W D I R E C T I O N
              P F O L L O W D I R E C T I O
              -----------------------------
              U T Z W Z K Z L Z V G V B W B
              -----------------------------



DONE!

Change Snippet Background Color

/*
   Autokey encryption and decryption
*/
import java.util.*;
import java.lang.*;
import java.math.*;

public class Autokey{
   private static String alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   
   public static void main(String[] args){
      String text = "FOLLOWDIRECTION";
      String key = "P";  //15 - P
      
      if(key.matches("[-+]?\\d*\\.?\\d+"))
         key = ""+alpha.charAt(Integer.parseInt(key));
         
      String enc = AutoEncryption(text,key);
      System.out.println("Plaintext : "+text);
      System.out.println("Encrypted : "+enc);
      System.out.println("Decrypted : "+AutoDecryption(enc,key));

   }
   
   public static String AutoEncryption(String text,String key){
      int len = text.length();
      
      String subkey = key + text;
      subkey = subkey.substring(0,subkey.length()-key.length());
      
      String sb = "";
      for(int x=0;x<len;x++){
         int get1 = alpha.indexOf(text.charAt(x));
         int get2 = alpha.indexOf(subkey.charAt(x));
         
         int total = (get1 + get2)%26;
         
         sb += alpha.charAt(total);
      }
     
      return sb;   
   }
   
   public static String AutoDecryption(String text,String key){
      int len = text.length();
      
      String current = key;
      String sb ="";
      
      for(int x=0;x<len;x++){
         int get1 = alpha.indexOf(text.charAt(x));
         int get2 = alpha.indexOf(current.charAt(x));
         
         int total = (get1 - get2)%26;
         total = (total<0)? total + 26 : total;
         sb += alpha.charAt(total);
         
         current += alpha.charAt(total);
      }
      return sb;
   }
}

Wednesday, December 30, 2015

Random alphabet in PHP

Change Snippet Background Color
          
            
               function RandomAlpha($len){
                  $key = "";
                  for($x=0;$x<$len;$x++)
                     $key .= chr(ord('A') rand(0,25));
                 
                  return $key;
               }
               function RandomAlphaNoDuplicate($len){
                  $key = "";
                   while(strlen($key) < $len){
                     $key .= chr(ord('A') rand(0,25));
                     $key = implode('',array_unique(str_split($key)));
                   }
                  return $key;
               }
               
                echo RandomAlphaNoDuplicate(12);
            
          
        

Polyalphabet Substitution Cipher with Period

This is poly lphabet substitution with period

Example:
Plaintext : IHATEYOU
Period : 3
          ALPHABET : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
          ----------------------------------------------------------------
          PERIOD 1 : B K L Y C P X F I Z J W D A H U R N G S T V Q M O E
          PERIOD 2 : Y U N S I D V T H L C K Q B P R Z M X O J G A W E F
          PERIOD 3 : I N T Q V E W F M G J B S Y U P Z H X C A L O K R D

Those period alphabet is can be done randomly without duplicate.

Let's start
Encryption:
For the first letter of plaintext is for period 1, second letter is for period 2 and third letter for period 3, then start over fourth letter for period 1 and so on.

For example:
 
          I letter of plain text, opposite of I at period 1 is I
          H letter of plain text, opposite of H at period 2 is T
          A letter of plain text, opposite of A at period 3 is I
          .
          .
          .

          Result
          I = I
          H = T
          A = I
          T = S
          E = I
          Y = R
          O = H
          U = J

Cipher text : ITISIRHJ

Lets do decryption
Decryption:
For the encryption part, the substitution from alphabet to period.
For the decryption part, we do reverse from period to alphabet.

As we know, the first of ciphertext is from period 1 and so on. Then, by doing reverse,

          Cipher text : ITISIRHJ

          I letter of plain text, opposite of I at alphabet from period 1 is I
          T letter of plain text, opposite of T at alphabet from period 2 is H
          I letter of plain text, opposite of I at alphabet from period 3 is A
          .
          .
          .
          Result
          I = I
          T = H
          I = A
          S = T
          I = E
          R = Y
          H = O
          J = U
 

Plain text : I HATE YOU


Change Snippet Background Color
          
            
/*
   Polyalphabet Subtitution
   Create by Hafiq
*/

import java.util.*;

public class PolyAlpahbetSub{
   
   private static String alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   private static ArrayList<String> list = new ArrayList<String>(); 
   
   public static void main(String[] args){
      
      String text = "IHATEYOU";
      int period = 3;
      Period(period);
      
      System.out.println("CT:   "+alpha);
      for(int x=0;x<list.size();x++){
         System.out.println("PT"+x+":  "+list.get(x));
      }
            
      String enc = PASEncryption(text,period);
      System.out.println("\nPlaintext : "+text);
      System.out.println("Encrypted : "+enc);
      System.out.println("Decrypted : "+PASDecryption(enc,period));
   }
   
   public static void Period(int period){
      Random r = new Random();
      
      for(int x=0;x<period;x++){
         String key = "";
         for (int i = 0; i < 26;) {
             char c = (char) (r.nextInt(26) + 'A');
             if(!key.toString().contains(""+c)){
                key = key + c;
                i++;
             }
         }  
         list.add(key);    
      }
   }
   
   public static String PASEncryption(String text,int period){
      int len = text.length();
      
      String sb = "";
      
      int p = 0;
      for(int x=0;x<len;x++){
         int get = alpha.indexOf(""+text.charAt(x));
        
         if (p == period)
            p = 0;
         
         String CT = list.get(p);
         
         sb = sb + CT.charAt(get);
            
         p++;
      }
      
      return sb;
   }
   
   public static String PASDecryption(String text,int period){
      int len = text.length();
      
      String sb = "";
      
      int p = 0;
      for(int x=0;x<len;x++){
         if (p == period)
            p = 0;
         
         int get = list.get(p).indexOf(""+text.charAt(x));
         
         sb = sb + alpha.charAt(get);
            
         p++;
      }
      
      return sb;
   }

}
            
          
        

OTP with random alphabet value

This is One Time Pad Cipher with random alphabet value as shown below

A-7    B-10    C-19    D-23    E-0    F-22    G-6    H-25   I-9    J-1 
K-15   L-4     M-21    N-20    O-16   P-8     Q-17   R-5    S-24   T-3
U-11   V-12    W-14    X-2     Y-13   Z-18

Plain text = COMPUTER
KEY = SOVIET

Encryption

 FORMULA (cipher + key) % 26

        C    O    M    P    U   T   E   R
        S    O    V    I    E   T   S   O
        -----------------------------------
  (%26) 17   6    7    17   11  6   24  21
        -----------------------------------
        Q    G    A    Q    U   G   S   M


Decryption

 FORMULA = ((cipher + 26) - key) % 26
 
        Q    G    A    Q    U   G   S   M
        ------------------------------------
        17   6    7    17   11  6   24  21
  (+26) 43   32   33   43   37  32  50  47
        ------------------------------------
        S    O    V    I    E   T   S   O
        24   16   12   9    0   3   24  16
 (-KEY) 19   16   21   34   37  29  26  31
        ------------------------------------
  (%26) 19   16   21   8    11  3   0   5
        ------------------------------------
        C    O    M    P    U   T   E   R



Change Snippet Background Color
          
            
/*

*/
import java.util.*;

public class OTPCipher2{
                                //  A B  C  D  E  F G H  I J K  L M  N  O  P Q  R S  T U  V  W  X Y  Z
   private static Integer[] list = {7,10,19,23,0,22,6,25,9,1,15,4,21,20,16,8,17,5,24,3,11,12,14,2,13,18};
   private static String alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
   
   public static void main(String[] args){
      String text = "REPEAT ATTACK TONIGHT";
      String key = "SOVIET";
      String k = "";
      int len = text.length();
      if(key.length()<len){
         int count = 0;
         for(int x=0;x<len;x++){  
            if(count == key.length()) 
               count = 0;
               
            k = k+key.charAt(count);
            count++;
         }
         key = k;
      }
      
      String enc = OTPEncryption(text,key);
      System.out.println("Plaintext : "+text);
      System.out.println("Encrypted : "+enc);
      System.out.println("Decrypted : "+OTPDecryption(enc,key));
   }
   
   public static String RandomAlpha(int len){
      Random r = new Random();
      String key = "";
      for(int x=0;x<len;x++)
         key = key + (char) (r.nextInt(26) + 'A');
      return key;
   }
   
   public static String OTPEncryption(String text,String key){
      int len = text.length();
      String sb= "";
      for(int x=0;x<len;x++){
         char get = text.charAt(x);
         char keyget = key.charAt(x);
         if(Character.isUpperCase(get)){
            int index = list[alpha.indexOf(get)];
            int keydex = list[alpha.indexOf(keyget)];
            
            int total = (index + keydex) % 26;
            
            sb = sb + alpha.charAt(Arrays.asList(list).indexOf(total));
         }
         else{
            sb = sb + get;
         }
      }
      
      return sb;
   }
   public static String OTPDecryption(String text,String key){
      int len = text.length();
      
      String sb = "";
      for(int x=0;x<len;x++){
         char get = text.charAt(x);
         char keyget = key.charAt(x);
         if(Character.isUpperCase(get)){
            int index = list[alpha.indexOf(get)];
            int keydex = list[alpha.indexOf(keyget)];

            int total = (index + 26) - keydex;
            total = total % 26;
            
            sb = sb + alpha.charAt(Arrays.asList(list).indexOf(total));
         }
         else{
            sb = sb + get;
         }
      }
      return sb;
   }   
}      
          
        

Wednesday, December 16, 2015

Find the Closest Pair of Coordinate using Brute Force and Divide n Conquer

We are given an array of n points , and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for distance between two points p and q.

The Brute force solution is O(n^2), compute the distance between each pair and return the smallest. For faster solution to find smallest distance in O(nLogn) time using Divide and Conquer strategy.

In this case, Brute force produce must faster if the list of Coordinate we want to compare is less than 50.

But,

Divide and Conquer strategy can process large amount > 50 of list more faster than brute force.

This is the time execution for both method

1000 list
Brute force (462 ms)
Divide and conquer (56 ms)

500 list
Brute force (147 ms)
Divide and conquer (14 ms)

100 list
Brute force (10 ms)
Divide and conquer (8 ms)

50 list
Brute force (3 ms)
Divide and conquer (5 ms)

10 list
Brute force (1 ms)
Divide and conquer (3 ms)


Change Snippet Background Color
   

import java.io.*;
import java.util.*;

public class ClosestCoorFinder {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String line = System.getProperty("line.separator");
        scan.useDelimiter(line);

        List<Coordinate> points = new ArrayList<>();
        Random random = new Random();
        for (int x=0;x<1000;x++){
            points.add(new Coordinate(random.nextInt(),random.nextInt()));
        }


        long startTime = System.currentTimeMillis();
        CoordinateDetail bruteForceClosestPair = bruteForce(points);
        long elapsedTime = System.currentTimeMillis() - startTime;
        System.out.println("Brute force (" + elapsedTime + " ms): " + bruteForceClosestPair);
        startTime = System.currentTimeMillis();
        CoordinateDetail dqClosestPair = divideAndConquer(points);
        elapsedTime = System.currentTimeMillis() - startTime;
        System.out.println("Divide and conquer (" + elapsedTime + " ms): " + dqClosestPair);
    }


    private static class Coordinate {
        private double x;
        private double y;

        public Coordinate(int id, double x, double y) {
            this.id = id;
            this.x = x;
            this.y = y;
        }

        public int getId() {
            return id;
        }

        public double getX() {
            return x;
        }

        public double getY() {
            return y;
        }

        public String toString() {
            return "(" + x + ", " + y +")";
        }
    }

    private static class CoordinateDetail {
        private Coordinate point1 = null;
        private Coordinate point2 = null;
        private double distance = 0.0;

        public CoordinateDetail(Coordinate point1, Coordinate point2, double distance) {
            this.point1 = point1;
            this.point2 = point2;
            this.distance = distance;
        }

        public Coordinate getPoint1() {
            return point1;
        }

        public Coordinate getPoint2() {
            return point2;
        }


        public double getDistance() {
            return distance;
        }


        public void set(Coordinate point1, Coordinate point2, double distance) {
            this.point1 = point1;
            this.point2 = point2;
            this.distance = distance;
        }

        public String toString() {
            return getPoint1() +" "+getPoint2()+" : distance = "+getDistance();
        }
    }

    private static double calDistance(Coordinate p1, Coordinate p2) {
        double xdist = p2.getX() - p1.getX();
        double ydist = p2.getY() - p1.getY();
        return Math.hypot(xdist, ydist);
    }

    // much faster than DnV for list of Coordinate is less than 100
    private static CoordinateDetail bruteForce(List<Coordinate> points) {
        int coorSize = points.size();
        if (coorSize < 2)
            return null;

        CoordinateDetail coorPoint = new CoordinateDetail(points.get(0), points.get(1),calDistance(points.get(0), points.get(1)));
        if (coorSize > 2) {
            for (int i = 0; i < coorSize - 1; i++) {
                Coordinate point1 = points.get(i);
                for (int j = i + 1; j < coorSize; j++) {
                    Coordinate point2 = points.get(j);
                    double distance = calDistance(point1, point2);
                    if (distance < coorPoint.getDistance())
                        coorPoint.set(point1, point2, distance);
                }
            }
        }
        return coorPoint;
    }

    private static void sortByX(List<Coordinate> points) {
        Collections.sort(points, new Comparator < Coordinate > () {
            public int compare(Coordinate point1, Coordinate point2) {
                if (point1.getX() < point2.getX())
                    return -1;
                if (point1.getX() > point2.getX())
                    return 1;
                return 0;
            }
        });
    }

    private static void sortByY(List<Coordinate> points) {
        Collections.sort(points, new Comparator <Coordinate> () {
            public int compare(Coordinate point1, Coordinate point2) {
                if (point1.getY() < point2.getY())
                    return -1;
                if (point1.getY() > point2.getY())
                    return 1;
                return 0;
            }
        });
    }

    // much faster than bruteforce for list of Coordinate is more than 100
    public static CoordinateDetail divideAndConquer(List<Coordinate> points) {
        List<Coordinate> listofSortedX = new ArrayList<> (points);
        sortByX(listofSortedX);
        List<Coordinate> listofSortedY = new ArrayList<> (points);
        sortByY(listofSortedY);
        return divideAndConquer(listofSortedX, listofSortedY);
    }

    private static CoordinateDetail divideAndConquer(List<Coordinate> listofSortedX, List<Coordinate> listofSortedY) {
        int coorSize = listofSortedX.size();
        if (coorSize <= 3)
            return bruteForce(listofSortedX);

        int index = coorSize >>> 1;
        List<Coordinate>leftOfCenter = listofSortedX.subList(0, index);
        List<Coordinate>rightOfCenter = listofSortedX.subList(index, coorSize);

        List<Coordinate>tempList= new ArrayList<>(leftOfCenter);
        sortByY(tempList);

        CoordinateDetail closestPair = divideAndConquer(leftOfCenter, tempList);

        tempList.clear();

        tempList.addAll(rightOfCenter);
        sortByY(tempList);

        CoordinateDetail closestPairRight = divideAndConquer(rightOfCenter, tempList);

        if (closestPairRight.getDistance() < closestPair.getDistance())
            closestPair = closestPairRight;

        tempList.clear();

        double shortestDistance = closestPair.getDistance();
        double centerX = rightOfCenter.get(0).getX();
        for (Coordinate point: listofSortedY)
            if (Math.abs(centerX - point.getX()) < shortestDistance)
                tempList.add(point);

        for (int i=0; i<tempList.size()-1;i++) {
            Coordinate point1 = tempList.get(i);
            for (int j=i+1;j<tempList.size();j++) {
                Coordinate point2 = tempList.get(j);
                if ((point2.getY() - point1.getY()) >= shortestDistance)
                    break;
                double distance = calDistance(point1, point2);
                if (distance < closestPair.getDistance()) {
                    closestPair.set(point1, point2, distance);
                    shortestDistance = distance;
                }
            }
        }
        return closestPair;
    }

}
   

Tuesday, December 15, 2015

Affine Cipher

Remember: 
Formula to encrypt : ax + b % 26
Formual to decrypt : IN * (x - b) mod 26


There are 2 key:
for example : 17 , 20

Text = TWENTYFIFTEEN

A B C D E F G H I J K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
-------------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

To encrypt :

T  W  E  N  T  Y  F  I  F  T  E  E  N
19 22 4  13 19 24 5  8  5  19 4  4  13

By using formula encryption ax+b % 26.
a = first key
b = second key
x = is the each letter



--------------------------------------
T  W  E  N  T  Y  F  I  F  T  E  E  N
--------------------------------------
19 22 4  13 19 24 5  8  5  19 4  4  13
5  4  10 7  5  12 1  0  1  5  10 10 7   <== ax+b % 26
--------------------------------------
F  E  K  H  F  M  B  A  B  F  K  K  H 
--------------------------------------

To decrypt :
 
F  E  K  H  F  M  B  A  B  F  K  K  H 
5  4  10 7  5  12 1  0  1  5  10 10 7

By using formula decryption.
a = first key
b = second key
x = 0 - infiniti

by using first key, find the inverse modular which firstkey * x mod 26 must equal to 1.


17 * 0 mod 26 != 1
17 * 1 mod 26 != 1
.
.
.
17 * 23 mod 26 == 1  <--- 23 is the modular inverse

by using 23,
b = second key
x = is the each letter encrypted letter

23 *(x-b) mod 26
--------------------------------------
F  E  K  H  F  M  B  A  B  F  K  K  H 
--------------------------------------
5  4  10 7  5  12 1  0  1  5  10 10 7
19 22 4  13 19 24 5  8  5  19 4  4  13 <== 23 *(x-b) mod 26
--------------------------------------
T  W  E  N  T  Y  F  I  F  T  E  E  N
--------------------------------------


Done!

Here the source code


Change Snippet Background Color
          
            
import java.util.*;
import java.lang.*;
import java.math.*;

public class Test{
   public static void main(String[] args) {
       String input = "TWENTYFIFTEEN";
       int x = 17;
       int y = 20;
       String enc = encrypt(input,x,y);
       String dec = decrypt(enc,x,y);
       System.out.println("Input:     " + input);
       System.out.println("Decrypted: " + enc);
       System.out.println("Decrypted: " + dec);
   }
   
   public static String encrypt(String input,int FK,int SK) {
       String str = "";
       for (int in = 0; in < input.length(); in++) {
           char get = input.charAt(in);
           if (Character.isLetter(get)) {
               // ax + b % 26
               get = (char) ((FK * (int)(get + 'A') + SK) % 26 + 'A');
           }
           str +=get;
       }
       return str;
   }
   
   public static String decrypt(String input,int FK,int SK) {
       String str = "";
       int x = 0;
       int inverse = 0;
       
       // find 1 by using modular inverse
       // 17 * IN mod 26 == 1
       // IN is 0 - infiniti
       // if total == 1, then IN is the inverse modular
       while(true){
         inverse = FK * x % 26;
            if(inverse == 1)
               break;
         x++;
       }
       
       for (int in = 0; in < input.length(); in++) {
           char get = input.charAt(in);
           if (Character.isLetter(get)) {
               // IN *(x-b) mod 26
               get = (char)(x * ((get + 'A') - SK) % 26 + 'A');
           }
           str +=get;
       }
       return str;
   }
}

          
        

Friday, December 4, 2015

Cordova Barcode Scanner with ionic

Recently found myself needing to scan barcodes in one of my apps.  After doing some searching I found that ngCordova had an extension for the Cordova plugin BarcodeScanner which has the ability to scan barcodes support many type of common format QR code, bar, EAN..etc..

Installation
cordova plugins add https://github.com/wildabeast/BarcodeScanner.git

Start by downloading the latest ngCordova release and copying the ng-cordova.min.js file into your project’s www/js directory.

Then include it in your index.html
          
<script src="js/ng-cordova.min.js"></script>
          
        
After setting index.html, go to app.js and add this ngCordova like below

          
angular.module('starter', ['ionic','ngCordova'])
          
        
It is now time, Create a controller and include the following method to initialize the barcode scanner. For this example, I did the following: Sample code Barcorde.html

   
<ion-view view-title="Barcode Scanner">
    <ion-content>
        <div class="card">
            <div class="item">
                <button class="button button-block button-balanced" ng-click="scanBarcode()">
                    <i class="icon ion-qr-scanner"></i>
                    Scan Now
                </button>
            </div>
        </div>

        <div class="card">
            <div class="item item-divider">
                Scan Results
            </div>
            <div class="item item-text-wrap">
                {{vm.scanResults}}
            </div>
        </div>
    </ion-content>
    <ion-footer>
        <div class="tabs-striped tabs-color-assertive">
            <div class="tabs">
                <a class="tab-item active" href="#">
                    <i class="icon ion-home"></i> Test
                </a>
                <a class="tab-item" href="#/app/viewpost">
                    <i class="icon ion-star"></i> Favorites
                </a>
                <a class="tab-item" href="#">
                    <i class="icon ion-gear-a"></i> Settings
                </a>
            </div>
        </div>
    </ion-footer>
</ion-view>
   
 
Controller.js
  
.controller("BarcodeScanner", function($scope, $cordovaBarcodeScanner, $ionicPlatform) {
    $scope.vm = [];
    $scope.scanBarcode = function() {
        $ionicPlatform.ready(function() {
            $cordovaBarcodeScanner
                .scan()
                .then(function(result) {
                    // Success! Barcode data is here
                    $scope.vm.scanResults = "Barcode\n" +
                        "Result: " + result.text + "\n" +
                        "Format: " + result.format + "\n" +
                        "Cancelled: " + result.cancelled;
                }, function(error) {
                    // An error occurred
                    $scope.vm.scanResults = 'Error: ' + error;
                });
        });
    }
})
  
 


Change Snippet Background Color