Novel Encryption Of Finite State Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Invention of public key cryptography is the greatest revolution in the history of cryptography. Two factors influence the security of the public key cryptography 1.length of the key and 2.computational overhead to break the cipher. Public key cryptography suffers with two types of problems symmetric encryption and key distribution. Whitefield Diffie and Martin Hellman published an interesting solution to the problem of the key agreement and key exchange in 1976 called differ key exchange protocol.

Diffie-Hellman key exchange (D-H)[nb 1] is a specific method of exchanging cryptographic keys. It is one of the earliest practical examples of key exchange implemented within the field ofcryptography. The Diffie-Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communicationschannel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

The scheme was first published by Whitfield Diffie and Martin Hellman in 1976, although it had been separately invented a few years earlier within GCHQ, the British signals intelligence agency, by Malcolm J. Williamson but was kept classified. In 2002, Hellman suggested the algorithm be called Diffie-Hellman-Merkle key exchange in recognition of Ralph Merkle's contribution to the invention of public-key cryptography (Hellman, 2002).

Although Diffie-Hellman key agreement itself is an anonymous (non-authenticated) key-agreement protocol, it provides the basis for a variety of authenticated protocols, and is used to provideperfect forward secrecy in Transport Layer Security's ephemeral modes (referred to as EDH or DHE depending on the cipher suite).

The method was followed shortly afterwards by RSA, an implementation of public key cryptography using asymmetric algorithms.


The finite state automaton is a mathematical model of a system with discrete outputs and outputs. The system can be in any one of a finite number of internal configuration or states. The state of the system summarizes the information.

Cryptology is the art of coding & decoding information. It requires tremendous amount of computational power. Nowadays, the security of most cryptographic systems is determined by the complexity of its corresponding attacks which are believed to be impracticable for actual cryptosystems and size of the key. Automata theory is the study of abstract computing devices or machines. It is a behavior model composed of a finite number of states, transition between those states and actions in which one can inspect the way logic runs when certain conditions are met. Recently finite state machines are used in cryptography, not only to encrypt the message, but also to maintain secrecy of the message.

The finite automaton is a mathematical model of a system with discrete input and outputs. In computer science finite state machine or finite-state automaton is a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of the finite states. The machine is only in one state at a time, the state it is in at any given time is called the current state. It can change from one state to another when initiated by triggering event or condition, this called a transition.

The finite automata is a mathematical model of a system, with discrete inputs and outputs in computer science one can find many examples of finite state systems. The theory of automata is a design tool for the systems .A finite automaton consists of finite set of states and a set of transitions from state to state that occur on input symbols chosen from the alphabet ∑.

When the finite automaton model is modified to allow zero, one, or more transitions from a state on the same input symbol then it is called non-

Deterministic finite automaton. Deterministic finite automaton is a special case of nondeterministic finite automaton. One limitation of finite automaton is limited to a binary signal: 'accept' / 'don't accept'.

Automata theory is a key to software for verifying systems of all types that have a finite number of distinct states, such as communication protocols or protocol for secure exchange of information. In Moore Machine every finite state machine has a fixed output. [1][2][4] Mathematically Moore machine is a six-tuple machine and is defined as:

M= (,,,,λ, )

: A nonempty finite set of state in Moore machine

: A nonempty finite set of inputs.

: A nonempty finite set of outputs.

: It is a transition function ∑ X Q Q

λ : Is a mapping function which maps to, giving the

output associated with each transition.

: Is the initial state in

Moore machine can also be represented by transition table, as well as transition diagram.

The following is the transition diagram of Moore machine which calculates residue mod 4.


Fig 1 Moore machines which calculates residue mod 4.

Recurrence relation

.A recurrence relation relates the nth element of a sequence to its predecessors .recurrence relations are related to recurssive algorithms. A "recursive relation" for the sequence a0, a1, a2, ................ is an equation that relates to certain

preceding terms a0, a1, a2 ,................. with initial conditions for the sequence a0, a1, a2 ,................ are explicitly given for a finite number of the terms of the sequence.

Fibonacci numbers

The Fibonacci numbers are the terms of the sequence 0, 1,1,2,3,5,……wherein each term is the sum of the two preceding terms, and we get things started with 0 and 1 as and .

Properties of Fibonacci sequence

Fibonacci numbers are given by the following recurrence relation

Fn+1 = Fn + Fn-1

With the initial conditions

F1 = F2 = 1

It is often useful to extend the Fibonacci sequence backward with negative subscripts. The Fibonacci recurrence can be written as Fn = Fn+2 - Fn-1 which allows us to do this.

n : …….-7,-6,-5,-4,-3,-2,-1,0,1,0,1,2,3,4…..

Fn :…….13,-8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3

Sequences such as the Fibonacci sequence which can be extended infinitely in both directions are called "bilate".

3. Recurrence Matrix

Recurrence matrix is a matrix whose elements are taken from a recurrence relation. Here the recurrence matrix is defined as:

Rn= where n=0,1,2…

We know that "The recurrence matrix is a secret key if and only if it is non-singular."

4. Offset Matrix

We apply the offset rule by adding 2 to the output of each entry which decides the value of n of the recurrence matrix obtained from Fibonacci relation.

5. Proposed Algorithm

With the help of Finite state machine, recurrence matrices and offset rule an algorithm is developed for encrypting messages. The sender and the receiver has to agree upon certain parameters like the key, the choice of the recurrence relation and how the recurrence matrix is to be defined.

Step 1

Select a square matrix of order n, where n≥0 as plain text P.

Step 2

Define a finite state machine through public channel.

Step 3

Define recurrence relation and recurrence matrix R (n), n≥0.

Step 4

Define value of n for the elements of R (n).


Step 5

Set sum of the elements of any specific row or column in binary form of defined recurrence matrix as key.

Here sum of the elements of first column is taken as the key.

Step 6

Define Cipher Text at q (i+1)th state.

Cipher text at q (i+1)th state depends on the input bit. If input bit is '0'then cipher text at q (i+1)th state is equal to cipher text at q(i)th state +Rn .

Where n=output+2 at each stage. If input is not zero select the operation 'multiplication'.

Step 7

Send the cipher text at the final stage to the receiver.

The sender and the receiver agree upon how the matrix is to be defined, choice of the recurrence relation, how to get the key from the plain text and hoe the cipher text is defined at each stage.


Decrypt the message using the inverse operation and key to get the original message.

6. Performance analysis

Mathematical analysis

Algorithm proposed, is a simple application of addition or multiplication of two matrices. But the operations are different depending on secret key. It is very difficult to break the cipher text without proper key, defined operation and the chosen finite state machine.

The key is defined as sum of the elements of specific row or column of the recurrence matrix which again depends on the recurrence relation. It is very difficult to trace the secret key even when finite state machine is known.

Time complexity

Let the sum of the output of the finite state machine for k bit secret key is r, let

be the time required for each multiplication and be the time required for each addition. Let secret k bit key consists of number of '0's and number of '1's. Then the total time required for k bit secret key is ( (sum of output for '1' bit) (sum of output for '0' bit)

7. Security analysis

Extracting the original information from the Cipher text is difficult due to the selection of the recurrence matrix, secret key and chosen finite state machines. Brute force attack on key is also difficult because of the key size. The following table shows the difficulty level of cracking the code.

Table 1 Security analysis


Name of the attack

Possibility of the attack



Cipher text attack

It is difficult to crack the cipher text.

Because of the chosen finite state machines and different individual keys.


Known plain text attack


Because of the chosen finite state machines and different individual keys.


Chosen plain text attack


Because of the chosen finite state machines and different

individual keys.


Adaptive chosen plain text attack


Because of the chosen finite state machines and different individual keys.


Chosen cipher text attack

Difficult to crack Cipher text

Because of the chosen finite state machines, different individual keys and matrix multiplication.


Adaptive chosen cipher text attack

Difficult to crack Cipher text

Because of the chosen finite state machines, different individual keys and matrix multiplication.

8. Implementation/Example

We assign 1 to letter a, 2 to letter b and so on and 26 to the letter z.

Let us encrypt the word 'PROFESSOR'.

As per the algorithm, we construct a square matrix of order n as under :

Where, let 'P' be the plain text .

The recurrence matrix R(n) = , where

.fn's are taken from Fibonacci sequence and n≥0

Secret key = sum of elements in first column=41= (101001)2

The value of n at each stage depends on the output.

Cipher text at q(i+1) th state depends on the input bit .

If input bit is '0' then cipher text at q(i+1)th state is equal to cipher text at q(i)th state +recurrence matrix depending on output, otherwise select the operation 'multiplication.

Then the cipher text at each state is as follows :

Sl. No



Previous state







































Table 2.8 Example

is the cipher text.


Algorithm proposed, is based on chosen finite state machine and different operations on matrices. Secrecy is maintained at four levels the secret key, the chosen finite state machine, the different operations, and the recurrence matrix.

The obtained cipher text becomes quite difficult to break or to extract the original information even when the algorithm is known.