#! /usr/bin/perl 

# Created By Dimitrios Georgoulas 2003-2004
# Department of Computing, Surrey University

# A Perl script for cryptanalysis of the Vigenere Algorithm
# Uses automatic and manually keyword selection 
# Decryption Option Available Only.
# Available as an open source. For any modifications/alterations please reference
# the author.
# All rights reserved Surrey University 2003-2004  
 
# References Algorithm/Structure:

# 1) Begginers Guide to Cryptography available at
# http://www.murky.org/classical/vigenere.shtml
# 2) Vigenere Cipher Applet Demonstration available at
# http://islab.oregonstate.edu/koc/ece575/02Project/Mun+Lee/VigenereCipher.html
# 3) Cryptanalysis of the Vigenere cipher available at 
# http://mywebpages.comcast.net/erfarmer201/vigenere/
# 4) JaVi v1.0 - Java Vigenere available at
# http://it.geocities.com/teutoburgo/java/javi/JaViManual.html
# 5) "Cryptography", by Stinson (p. 31-41) 
# 6) Breaking the Vigenere cipher available at
# http://raphael.math.uic.edu/~jeremy/crypt/The Index of Coincidence.htm

################################################################################
#########################VINGENERE CRYPTANALYSIS################################
################################################################################


################################################################################
##########################START OF THE SUBROUTINES##############################
################################################################################
# Used as part of the decryption part. Responsible for decrypting a single 
# letter of ciphertext(first letter) given the ciphertext and the keyword.
# Perl function used: ord--> This function returns the numeric value (ASCII) of
# the first character and is assigned by the value "A"  and 
# chr --> This function returns the character represented by a number and is 
# opposite of the ord function.
 
sub decrypt_letter{
#Local Variables 
my ($cipher, $row) = @_;
my $plain;

   $row     = ord(($row))    - ord('A');# enable mod 26
   $cipher = ord(($cipher)) - ord('A');# enable mod 26
   $plain  = ($cipher - $row) % 26;
   $plain = chr($plain + ord('A'));

    return ($plain);   
}
################################################################################
# The main subroutine of part 3 of  our crypatnalysis that will decrypt the 
# string of ciphetext given the ciphertext and the keyword.
# Returns the desired plaintext.
#Perl functions used: length-->The function length will returns the length in 
#characters of the scalar value and substr-->The function substr will extract a
# substring out of a string and returns it. In our case used as a replacement

sub decrypt_string{
# Local Variables
my ($ciphertext, $Keyword) = @_;# Pass the parameters as a flat list of scalars 
#as array _@.
my $plaintext;

   $Keyword = $Keyword x (length($ciphertext) / length($Keyword) + 1); 
   
            for( my $i=0; $i<length($ciphertext); $i++ ){

            $plaintext .=
            decrypt_letter( (substr($ciphertext,$i,1)),(substr($Keyword,$i,1)));            
    }
    
    return $plaintext;
}
################################################################################
# The Index of Coincidence subroutine is used to calculate the keyword length.
# Applied to a string of characters (ciphertext)
# Hint: The ciphertext is shifted against itself and the number of matches
# between letters is counted. A random shift will give a low number, a shift 
# which is a multiple of the key length will give a high number.
# Syntax:: indexOfCoincidence \@charArray 

sub indexOfCoincidence 
{
#Local Variables 
my $index = shift; 
my $sum = 0; 

   foreach $i ( @$index ) 
   {$sum += $i ** 2;} #store the exponeniate commonalities per shift  
   $index = ""; 
   
return $sum; 

} 
################################################################################
# The Mutual Index of Concidence subroutine is used to find the Keyword itself.
# Applied to two arrays of characters (ciphertext) 
# Hint: The mutual index of coincidence for two blocks of text is the
# probability that two randomly selected letters, one from each block, will be 
# identical.  The utility of this metric is based on the following claim: if two 
# blocks of ciphertext are encrypted with the same key letter, 
# the mutual index of coincidence of the blocks will be significantly greater 
# than if they are encrypted with two different key letters.  
# By successively "shifting" the letters in one of the blocks, and noting the
# shift which results in the greatest mutual index of coincidence, 
# the relationship between the two corresponding key letters may be determined.  
# By examining all pairs of ciphertext blocks, the key letters may almost be 
# derived directly. 
# Syntax:: MutualIndexOfCoincidence \@array1 \@array2 $someShift
 
sub MutualIndexOfCoincidence 
{
#Local Variables 
my $indexA = shift;#For the first block
my $indexB = shift;#For the second block 
my $distance = shift;#The distance between them 
my $sum = 0; 
my $countA = 0; 
my $countB = 0; 

   for $i (0 .. 25) 
   { 
   $sum += @$indexA[$i] * @$indexB[$i-$distance % 26]; 
   $countA += @$indexA[$i]; 
   $countB += @$indexB[$i]; 
   }  
 
 return $sum / $countA / $countB;
  
} 
################################################################################
# This subroutine calculates the frequency of each character in the string(cipher)
# Syntax:: freqOfChar @file 

sub freqOfChar 
{ 

  while (@_)
   
   {push @file, shift;} 
         foreach $i (0..25) 
                 {$freq[$i]=0;}
                  
my $char = shift @file; # Local Variable
 
   while ($char && $char ne "\n") 
   { 
     $index = ord($char) - 65; 
     $freq[$index]=($freq[$index]+1); 
     $char = shift @file; 
   } 
return @freq; 
   } 
################################################################################
# This subroutine return the frequency of each character in the string as 
# a percentatge  
# Syntax:: freqPercentage @file 

sub freqPercentage 
{
# Local Variables 
my $sum = 0; 
my @freqs = freqOfChar @_; #call above function 

   foreach $i (0..25) 
   {$sum += $freqs[$i];} 
           foreach $i (0..25) 
           {$freqs[$i] = $freqs[$i]/$sum;} 
           
return @freqs; 

} 
################################################################################
# This subroutine will be used as part of finding the keyword length as well as
# the actuall keyword and separates the file into "n" separate files 
# Syntax:: sep $keySize @FILE 

sub separateFile 
{
# Local Variables  
my $keySize = shift; 
my $pos = 0; 
my @file = ();
 
 while (@_) 
 {push @file, shift;} 
 my @splitFile = (); 

my $char = shift @file; 
   while ($char && $char ne "\n") 
   { 
   $splitFile[$pos].=$char; 
   $pos++; 
   
   if($pos == $keySize) 
   {$pos=0;} 
   $char = shift @file; 
   } 
   
   return @splitFile; 
} 
################################################################################
# This subroutine will be used as part of finding the keyword length as well as
# the actuall keyword and turns a string into an array of characters (ciphertext) 
# Syntax:: stringtoarray $String 

sub stringtoarray 
{ 
#Local Variables
my @array = (); 
my $string = shift; 

   while($string ne "") 
   { 
   $string =~ /[A-Z]/o; 
   push @array, $&; 
   $string = $'; 
   } 
   
return @array; 

} 
################################################################################
# This subroutine adds an amount to each key character and returns the string form 
# Syntax:: keyword $amountToShift /@relativeShiftArray 
sub keyword 
{
#Local Variables 
my $string = undef; 
my $mov = shift; 
my $keyShift=shift; 

   foreach $i (0..$#$keyShift) 
   {$string .= chr( (($$keyShift[$i]+$mov)%26) + 65);} 
   
return $string;
 
}
################################################################################
##############################FINISH OF THE SUBROUTINES#########################
################################################################################

################################################################################
###############################BEGIN THE MAIN PROGRAM###########################
################################################################################

####################################STEP 1######################################
#FIND THE KEYWORD LENGTH
################################################################################
#Step 1a) Open the file that contains the ciphertext
################################################################################ 
open( DATA, "data.txt" ) || die "PLEASE OPEN THE FILE THAT CONTAINTS THE CIPHERTEXT: $!\n";
# Read the entire file to a string 
  while (read DATA, $fileText, 1 != 0) 
  {push @text, $fileText;} 
  close DATA; 
################################################################################
#Step 1b) Find the keyword length Hint: Ref 5) top of the page 1
################################################################################
@separated = (); 
$shift = 0; 
$prevshift = 1; 
$stop = 0; 
$a = 0;#Increment by one per shift 
$key = 0;
$IndexOfCoincidence =0; 

     while ($stop == 0) 
     { 
     $key++; 
     $prevshift = $shift if $key > 1; 
     $ave = 0; 
     $a = 0; 
     @separated = separateFile $key, @text;
      
      foreach $string (@separated) 
      {      
      if ($string ne "\n") 
      {      
      @stringArray = stringtoarray($string); 
      @tempa = freqPercentage(@stringArray); 
      $tempsum = indexOfCoincidence( \@tempa ); 
      $shift = ($shift * $a + $tempsum) / ++$a;
      }  
      } 
      $IndexOfCoincidence = ($shift - $prevshift);
      
print "Index Of Coincidence is $IndexOfCoincidence.\n";           
print "SHIFT is $shift%.\n"; 
print "PREVIOUS SHIFT is $prevshift%.\n";

      if($shift - $prevshift > .019) #We are close to the probabilistic value
      {$stop = 1; }                  #of 0.065 so stop shifts
      } 

###############################################################################
print "Key is $key letters long.\n";#We found the keyword length!!!!
################################################################################

##################################STEP 2########################################
################################################################################
#FIND THE ACTUAL KEYWORD
################################################################################
#Step 2a)
################################################################################
# using the mutual index of coincidence to find relative shifts 
# between key char "a" and key char "b" 
my @multArr = ();
 
 foreach $i (1 .. $key-1) 
{ 
         foreach $j ($i+1 .. $key) 
         {         
                   @tmp = stringtoarray(@separated[$i-1]); 
                   @tempA = freqOfChar( @tmp ); 
                   @tmp = stringtoarray(@separated[$j-1]); 
                   @tempB = freqOfChar( @tmp ); 
                          inner : foreach $distance (0 .. 25) 
                          { 
                            $temp = MutualIndexOfCoincidence(\@tempA,\@tempB, $distance); 
                                  if ($temp > .061 ) 
                                  {                                  
                                  push @multArr, [$i, $j,- $distance]; 
                                  last inner; 
                                  } 
                            } 
         } 
} 

################################################################################
#Step 2b)
################################################################################
# initialize @k for use 
my @k = (); #To be used to store the relative shifts of the key
   foreach $i ( 0 .. $key -1) 
   {$k[$i] = -1;} 
   $k[0] = 1; 
################################################################################
#Step 3c)
################################################################################
# used to find out if we know all 
# of the relative shifts in the key 
# Syntax:: knownShifts @k 
sub knownShifts 
    { 
      foreach $item ( @_ ) 
      { 
        if ($item == -1) 
        {return 1;} 
        }               
        return 0; 
        } 
################################################################################
#Step 3d)
################################################################################
# Apply 26 cyclic shifts according with the keyword length
# Hint: Ref 3) top of the page 1
$temp = 0; 
      while ( knownShifts(@k) == 1 ) 
      { 
      $temp = shift @multArr;  
            if ( $k[ $$temp[0] - 1] == -1) 
            { 
# nothing known... we die. 
                   die "Oh no....$temp\n" if ($k[$$temp[1] - 1] == -1); 
                   $k[$$temp[0]-1] = $k[$$temp[1]-1] + (- $$temp[2] % 26); 
                   } 

                   elsif ($k[$temp[1] - 1] == -1) 
                   {$k[$$temp[1] - 1] = $k[$$temp[0] - 1] + $$temp[2];} 
# failed both conditions, so they are both known. 
      } 

################################################################################
#Step 3c)
################################################################################
#Obtaine the total of keywords for the 26 cyclic shifts (see above) and select
#the one that fits better the requirements
# Hint: Ref 5) top of the page 1

$maxfrequency = 0; 
$maxfrequencyE = 0; 
               foreach $i ( 0 .. 25 ){ 
                       @text = (); 
                       $Keyword = keyword ($i,\@k); 
                       $sum = 0; 
               foreach $j (0..$#text) 
               {if($text[$j] eq "E") {$sum++;}} #Assign the higest frequency to 
                                              #Letter "E". 
                           if ($sum/$#text > $maxfrequency) { 
                              $maxfrequency = $sum/$#text; 
                              $maxfrequencyE = $i; 
                              }                             
print " Available Keys : $Keyword \n" #Print all the available keys                            
}


$Keyword = keyword($maxfrequencyE,\@k);###########AUTOMATIC SELECTION###########
################################################################################
print " Automated Key Selection : $Keyword \n";#We found the actual keyword!!!!!
################################################################################

#####################################STEP 3#####################################
################################################################################
#RECREATE THE PLAINTEXT
################################################################################
$ciphertext ='PLEASE ENTER YOUR CIPHER TEXT HERE';
#########################MANUAL SELECTION CURRENT DISABLED######################
#$Keyword = 'DISABLE THE AUTOMATIC SELECTION AND ADD HERE THE KEYWORD YOU WISH"
$derived_plaintext;
$derived_plaintext=decrypt_string( $ciphertext, $Keyword );
print "Ciphertext          :$ciphertext\n";#The original ciphertext
################################################################################
print "Recreated plaintext :$derived_plaintext\n";#WE CRACK VIGENERE CIPHERTEXT!
################################################################################
##################################END OF PROGRAM################################
################################################################################