%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution to A2: Data Encryption,  CSC148H, Summer96
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Written by Phil Edmonds, May 24, 1996
%

%---------------------------------------------------------------------------
%  CONSTANTS and DATA TYPES
%

%
% These two constants define the alphabet to be the range of values
% (or letters) between FIRST_LETTER and LAST_LETTER.
% Only these letters will be encrypted.
% Obviously, the range is a contiguous set of ASCII symbols
%
const FIRST_LETTER := "a"
const LAST_LETTER := "z"

% The size of the alphabet is calculated here
%
const ALPHA_SIZE := ord (LAST_LETTER) - ord (FIRST_LETTER) + 1

% the 'null' string is just an empty string
%
const NULL := ""

%
% A frequency table is a list of characters in the alphabet with their
% frequencies of occurrence (integers).
%
% Note that a frequency table will in general be ordered from highest to
% lowest frequency, so the frequency column is sometimes irrelevant
%
type freqTableEntry :
    record
        letter : string (1)
        freq : int
    end record

type freqTableType : array 1 .. ALPHA_SIZE of freqTableEntry

% define an array and initialize it for the frequency data
% for normal English text (ordered).  Frequency numbers are not needed.
%
const freq_normal : freqTableType := init (
    init ("e", 0), init ("a", 0), init ("n", 0), init ("t", 0),
    init ("o", 0), init ("i", 0), init ("r", 0),
    init ("h", 0), init ("s", 0), init ("l", 0), init ("u", 0),
    init ("d", 0), init ("c", 0), init ("w", 0), init ("g", 0),
    init ("y", 0), init ("p", 0), init ("f", 0), init ("m", 0),
    init ("b", 0), init ("v", 0), init ("k", 0), init ("q", 0),
    init ("x", 0), init ("z", 0), init ("j", 0))

%
% A substitution table is an array of entries where each entry maps a
% character of the alphabet from its plaintext value (plain)
% to its ciphertext value (cipher)
%
% Note that in this implementation the table will be ORDERED according to
% the plain text letter.  That means that the plain text letter is
% redundant information, because we could easily map between it to its
% position in the table.
%
type subsTableEntry :
    record
        plain : string (1)
        cipher : string (1)
    end record

type subsTableType : array 1 .. ALPHA_SIZE of subsTableEntry

%--------------------------------------------------------------------------
% UTILITY SUBPROGRAMS : these are used the major subprograms below
%

% CONVERT FROM LETTERS TO TABLE ENTRY NUMBERS
% two functions to convert back and forth between characters and their
% position in the range 1..ALPHA_SIZE.  Makes use of the ASCII conversion
% functions ord() and chr().
%
function letter_to_entry (letter : string (1)) : int
    result (ord (letter) - ord (FIRST_LETTER) + 1)
end letter_to_entry

function entry_to_letter (entry : int) : string (1)
    result chr (entry + ord (FIRST_LETTER) - 1)
end entry_to_letter

%
% MAP A PLAINLETTER TO A CIPHERLETTER
% This returns the cipher text letter corresponding to the plain text
% letter.  It is the mapping plain -> cipher, which can be implemented by a
% direct table lookup only because the table is ordered by plaintext letter
%
function plain_to_cipher (subs_table : subsTableType, plainletter :
        string (1)) : string (1)
    result subs_table (letter_to_entry (plainletter)).cipher
end plain_to_cipher

%
% MAP A CIPHERLETTER TO A PLAINLETTER
% This is the inverse mapping cipher -> plain.
% It is implemented as a search on the table with cipher letter as key.
% This is needed because the table is not sorted for cipher text letters,
% but is very inefficient compared to the forward mapping.
% A more efficient technique would be to generate the inverse mapping
% first by sorting the substitution table by cipher letter, and then
% swapping the two elements of the record  (exchange the domain and range),
% to get a true inverse.  Then we wouldn't even need decryption code, because
% we could (re-)use the encryption code.
%
function cipher_to_plain (subs_table : subsTableType, cipherletter :
        string (1)) : string (1)

    var entry : int := 1
    loop
        exit when (entry > ALPHA_SIZE or
            subs_table (entry).cipher = cipherletter)
        entry := entry + 1
    end loop
    if (entry > ALPHA_SIZE) then
        result NULL % should never happen if table is valid
    else
        result subs_table (entry).plain
    end if
end cipher_to_plain

%---------------------------------------------------------------------------
%  SUBPROGRAMS (required by the assignment)
%

% special function for loop invariant in verify_table
% it returns the number of trues in the array
%
function number_of_trues (A : array 1 .. * of boolean) : int
    var count : int := 0
    for i : 1 .. upper (A)
        if A (i) = true then
            count := count + 1
        end if
    end for
    result count
end number_of_trues
%
% VERIFY
% This function will verify that a substitution table is valid.
% It will return true if so, false otherwise.
% The two boolean arrays, verify_plain and verify_cipher, are filled in
% with true for each plaintext letter and ciphertext letter in the
% substitution table.  (Note: the array indexes refer to the position in
% the alphabet in the range 1..ALPHA_SIZE of each letter, where ALPHA_SIZE
% is a constant whose value is the size of the alphabet---26 letters).
%
% If, during this, an entry in either array is already true, then the
% table is invalid.  Why?
%
% The only parameter is the substitution table of type subsTableType.
% YOU HAVE TO DEFINE THIS TYPE%
%
function verify_table (subs_table : subsTableType) : boolean
    var verify_plain : array 1 .. ALPHA_SIZE of boolean
    var verify_cipher : array 1 .. ALPHA_SIZE of boolean

    % initialize the arrays to all false
    for j : 1 .. ALPHA_SIZE
        verify_plain (j) := false
        verify_cipher (j) := false
    end for

    %%%%%%%%% MAIN LOOP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % loop through all entries in the substitution table,
    % i refers to the current entry (which contains a mapping from
    % a single plaintext letter to a ciphertext letter (e.g., "a"->"h"))
    %
    var i : int := 1
    var valid := true % <---------------NEW

    % PRECONDITION
    assert (valid and
        number_of_trues (verify_plain) = 0 and
        number_of_trues (verify_cipher) = 0 and
        i = 1)

    % loop through the entries
    loop
        % LOOP INVARIANT  valid <=> #of_trues = i-1
        invariant (
            (valid = (number_of_trues (verify_plain) = i - 1
                      and number_of_trues (verify_cipher) = i - 1))
            and i >= 1 and i <= ALPHA_SIZE + 1 )

        exit when ( (not valid) or (i > ALPHA_SIZE))

        % THE PART IN [] DEPENDS ON YOUR DEFINITION OF THE subsTableType
        % var index_plain := [position in alphabet of the plaintext letter
        %                     in the ith table entry]
        var index_plain := letter_to_entry (subs_table (i).plain)
        if verify_plain (index_plain) then
            valid := false % <------------------NEW
        else
            verify_plain (index_plain) := true
        end if

        % var index_cipher := [position in alphabet of the ciphertext letter
        %                      in the ith table entry]
        var index_cipher := letter_to_entry (subs_table (i).cipher)
        if verify_cipher (index_cipher) then
            valid := false % <------------------NEW
        else
            verify_cipher (index_cipher) := true
        end if

        i := i + 1
    end loop

    % POSTCONDITION
    assert (valid = (number_of_trues (verify_plain) = ALPHA_SIZE
                     and number_of_trues (verify_cipher) = ALPHA_SIZE) )

    %
    %%%%%%% end of MAIN LOOP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    % if any entry is still false, then the table is invalid

    result valid
end verify_table

%---------------------------------------------------------------------------
%
% CAESAR CIPHER
% This procedure generates a substitution table based on the Caesar cipher
% Each letter is `shifted' by adding the key (mod the size of the alphabet)
%
proc gen_caesar_cipher (key : int, var subs_table : subsTableType)

    for entry : 1 .. ALPHA_SIZE
        subs_table (entry).plain := entry_to_letter (entry)
        %
        % shift entry over by key, and mod by the alphabet size
        %
        var caesar := entry_to_letter ( (entry + key - 1) mod ALPHA_SIZE
            + 1)
        subs_table (entry).cipher := caesar
    end for
end gen_caesar_cipher

%---------------------------------------------------------------------------
%
% RANDOM CIPHER
% This procedure generates a random substitution table
% Each letter maps to a random other letter.
% The key supplies the seed to the random number generator
% It works by filling the array by dummy characters, then it loops through
%  the alphabet, choosing random entries in the table to put them
%
proc gen_random_cipher (key : int, var subs_table : subsTableType)

    % initialize the table, put NULL in an entry to say we haven't assigned
    %   to it yet.
    %
    for entry : 1 .. ALPHA_SIZE
        subs_table (entry).plain := entry_to_letter (entry)
        subs_table (entry).cipher := NULL
    end for

    % for each letter in 1 .. ALPHA_SIZE, find it a random entry in the table
    % (by choosing a random number).  May have to loop through several random
    % numbers before we find an entry we haven't assigned yet.
    %
    % NOTE: There are ways to improve on this algorithm so that it runs
    % in exactly O(n).
    %
    var r : real
    var random_entry : int

    % seed the random numbers with the key, then randnext
    % will give the same set of numbers for the same key
    randseed (key, 1)

    % loop over each cipher letter
    for i : 1 .. ALPHA_SIZE
        % loop until we find a position that has not been assigned yet
        loop
            randnext (r, 1)
            random_entry := floor (r * ALPHA_SIZE) + 1
            exit when (subs_table (random_entry).cipher = NULL)
        end loop
        subs_table (random_entry).cipher := entry_to_letter (i)
    end for

end gen_random_cipher


%---------------------------------------------------------------------------
%
% ENCRYPT:  plaintext ---> ciphertext
%
% This is the procedure to encrypt a file
% It reads a file character by character and converts each character
%   (if its in the suitable range a-z) to its encrypted partner by
%   using the susstitution table
%
proc encrypt (plaintext : string, ciphertext : string, subs_table :
        subsTableType)

    var plainfile : int
    var cipherfile : int
    var plainletter : string (1)
    var cipherletter : string (1)

    open : plainfile, plaintext, get
    open : cipherfile, ciphertext, put

    loop
        exit when eof (plainfile)
        get : plainfile, plainletter : 1

        % if the plainletter is in the right range, then find its
        % corresponding cipherletter, otherwise leave it alone
        %
        if (plainletter >= FIRST_LETTER and plainletter <=
                LAST_LETTER) then
            cipherletter := plain_to_cipher (subs_table, plainletter)
        else
            cipherletter := plainletter
        end if

        put : cipherfile, cipherletter ..
    end loop

    close : plainfile
    close : cipherfile
end encrypt

%---------------------------------------------------------------------------
%
% DECRYPT:   ciphertext  --->  plaintext
%
% This is the procedure to decrypt a file
% It is the just the opposite of the encrypt procedure
%
proc decrypt (ciphertext : string, plaintext : string, subs_table :
        subsTableType)

    var plainfile : int
    var cipherfile : int
    var plainletter : string (1)
    var cipherletter : string (1)

    open : plainfile, plaintext, put
    open : cipherfile, ciphertext, get

    loop
        exit when eof (cipherfile)
        get : cipherfile, cipherletter : 1

        % if the cipherletter is in the proper range, then
        % finds its corresponding plainletter, otherwise
        % leave it alone
        %
        if (cipherletter >= FIRST_LETTER and cipherletter <=
                LAST_LETTER)
                then
            plainletter := cipher_to_plain (subs_table, cipherletter)
        else
            plainletter := cipherletter
        end if

        put : plainfile, plainletter ..
    end loop

    close : plainfile
    close : cipherfile
end decrypt

%---------------------------------------------------------------------------
%
% CODE BREAK
%
% There are 4 steps:
%  1. initialize the frequency table for the cipher text
%  2. count the frequencies by going through the file
%  3. sort the frequency table into descending order (the same as the
%           freq_normal data)
%  4. build the substitution table by matching up the two frequency tables
%
proc code_break (ciphertext : string, freq_normal : freqTableType, var
        subs_table : subsTableType)


    var freq_cipher : freqTableType

    % initialize frequency array for counting frequencies in the cipher text
    for entry : 1 .. ALPHA_SIZE
        freq_cipher (entry).letter := entry_to_letter (entry)
        freq_cipher (entry).freq := 0
    end for

    % count frequencies in ciphertext
    var cipherfile : int
    var cipherletter : string (1)

    open : cipherfile, ciphertext, get

    loop
        exit when eof (cipherfile)
        get : cipherfile, cipherletter : 1

        if (cipherletter >= FIRST_LETTER and cipherletter <=
                LAST_LETTER)
                then
            freq_cipher (letter_to_entry (cipherletter)).freq :=
                freq_cipher (letter_to_entry (cipherletter)).freq + 1
        end if
    end loop

    close : cipherfile

    % sort the frequency table
    % This is a BUBBLE SORT adapted (to sort in decreasing order)
    %    from BHH page 470-471
    %
    % Note, the sort key is the frequency element, but it
    % swaps whole records.
    %
    for i : 1 .. ALPHA_SIZE - 1
        for decreasing j : ALPHA_SIZE .. i + 1
            if freq_cipher (j - 1).freq < freq_cipher (j).freq then
                % swap the two elements
                var temp : freqTableEntry := freq_cipher (j - 1)
                freq_cipher (j - 1) := freq_cipher (j)
                freq_cipher (j) := temp
            end if
        end for
    end for

    % build substitution table by going through the two frequency tables
    % one by one.  The freq_normal letter becomes the plain letter, and
    % the corresponding freq_cipher letter is the cipher letter
    %
    for i : 1 .. ALPHA_SIZE
        var normal_entry : int :=
            letter_to_entry (freq_normal (i).letter)
        subs_table (normal_entry).plain := freq_normal (i).letter
        subs_table (normal_entry).cipher := freq_cipher (i).letter
    end for

end code_break

%
%---------------------------------------------------------------------------
% PRINT out a substitution table
%
proc print_table (subs_table : subsTableType)
    for i : 1 .. ALPHA_SIZE
        put " ", subs_table (i).plain ..
    end for
    put ""
    for i : 1 .. ALPHA_SIZE
        put " |" ..
    end for
    put ""
    for i : 1 .. ALPHA_SIZE
        put " V" ..
    end for
    put ""
    for i : 1 .. ALPHA_SIZE
        put " ", subs_table (i).cipher ..
    end for
    put ""
end print_table

%
%---------------------------------------------------------------------------
% MAIN CODE
%

% this is a very simple user interface, no error checking is done
% on any input values


var code : subsTableType
var option : int
var key : int
var plaintextfile, ciphertextfile : string

loop
    put ""
    put "Options:"
    put " 1. generate Caesar cipher"
    put " 2. generate random cipher"
    put " 3. verify the table generated"
    put " 4. print the table generated"
    put " 5. encrypt a plaintext file using table generated"
    put " 6. decrypt a ciphertext file using table generated"
    put " 7. attempt to break the code"
    put " 8. exit"

    put "Enter Option: " ..
    get option
    put ""

    case option of
        label 1 :
            put "Caesar cipher: enter key: " ..
            get key
            gen_caesar_cipher (key, code)
            put ""
            print_table (code)
        label 2 :
            put "Random cipher: enter key: " ..
            get key
            gen_random_cipher (key, code)
            put ""
            print_table (code)
        label 3 :
            if (verify_table (code)) then
                put "Table is valid."
            else
                put "Table is invalid!"
            end if
        label 4 :
            print_table (code)
        label 5 :
            put "Encryption: Enter original-filename ciphertext-filename: "
                ..
            get plaintextfile, ciphertextfile
            encrypt (plaintextfile, ciphertextfile, code)
            put plaintextfile, " ---> ", ciphertextfile, " done."
        label 6 :
            put "Decryption: Enter ciphertext-filename plaintext-filename: "
                ..
            get ciphertextfile, plaintextfile
            decrypt (ciphertextfile, plaintextfile, code)
            put ciphertextfile, " ---> ", plaintextfile, " done."
        label 7 :
            put "Code breaker: Enter ciphertext-filename: " ..
            get ciphertextfile
            code_break (ciphertextfile, freq_normal, code)
            put ""
            print_table (code)
        label 8 :
            exit
        label :
            put "Unknown command..."
    end case
end loop