Application Of Mealy Machine And Recurrence Computer Science Essay


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

Cryptography is the study of techniques for ensuring the secrecy and authentication of the information, public key encryption schemes are secure only if the authenticity of the public key is ensured. The importance of security of data is ever expanding with increasing impact of internet as means of communication and e-commerce. It is essential to protect the information from hackers and eavesdroppers. In this paper, with the help of finite state machine (mealy machine) a secure communication method is designed for encryption and decryption.

Many mathematical models are taking an active role in the process of encryption and inverse of an element or of a function resulting in decryption process. The main idea behind such constructions is designing a mathematical function in such a way that tracing the inverse of the function is not easy. Cryptography is the art of coding & decoding information. It is used as security mechanism in electronic communication. The message we want to send is called 'plain text' and the disguised message is called the cipher text. The process of converting plain text into cipher text is called 'encryption' and the reverse process is called 'decryption'.


There is a scope for a wide range of application of automaton theory in the field of cryptology. In automata theory, a branch of theoretical computer science, a deterministic finite automaton (DFA)-also known as deterministic finite state machine-is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string. 'Deterministic' refers to the uniqueness of the computation. In search of simplest models to capture the finite state machines, McCulloch and Pitts were among the first researchers to introduce a concept similar to finite automaton in 1943. The finite automaton is a mathematical model of a system with discrete inputs and outputs. The system can be one of a finite number of internal configurations or states [2][9]. The finite automaton is a mathematical model or a system, with discrete inputs and outputs. When the finite automata is modified to allow zero, one, or more transitions from a state on the same input symbol then it is called a nondeterministic finite automata. For deterministic automata the outcome is a state, i.e., an element of Q. For nondeterministic automata the outcome is a subset of Q, where Q is a finite nonempty set of states. 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.

In this paper, new secret sharing scheme is proposed using finite state machines.

A finite state machine or finite-state automaton is a mathematical model of computation used to design both computer programs and sequential logic circuits [9]. 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.

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 Mealy Machine every finite state machine has a fixed output. Mathematically Mealy machine is a six-tuple machine and is defined as :

M= ( )

: A nonempty finite set of state in Mealy machine

: A nonempty finite set of inputs.

: A nonempty finite set of outputs.

: It is a transition function which takes two arguments one is input state and

another is input symbol. The output of this function is a single state.

: Is a mapping function which maps x to, giving the output associated

with each transition.

: Is the initial state in

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

Now, we consider a Mealy machine [4][8][9].

Fig 1 Mealy machine

..In the above diagram 0/1 represent input/output.

Recurrence Matrix

Recurrence matrix is a matrix whose elements are taken from a recurrence relation [1].

The recurrence matrix in this paper is defined as


Rn is a symmetric matrix.

where n and 's are .either taken from Fermat's sequence or Mersenne's sequence.

The sequence 0, 1, 3, 7, 15, 31, . . . is the Mersenne sequence, and 2, 3, 5, 9, 17, 33, . . . is the Fermat sequence. These are just powers of 2 plus or minus 1

2. Proposed Algorithm


Step 1

Let the plain text P be a square matrix of order n, n>0.

Here, a 9 lettered word is represented as a square matrix of order 3.

Step 2

Define Finite state machine through public channel.

Here Mealy machine is publicized.

Step 3

All the elements of the plain text are added and converted into binary form. This is the input.

Step 4

With the help of mealy machine output is found.

Step 5

Define cipher text at each stage.

.cipher text at qi+1thstage = cipher text at qith stage + recurrence matrix.

The elements of recurrence matrix differ at each stage.

When input=0,the elements of recurrence matrix are taken from Fermat's sequence and when input =1,elements of recurrence matrix are from Merssen's sequence.

The value of n of the recurrence matrix at each = output at each stage

Step 6

.Residue mod 26 is calculated for the cipher text at the end.

Step 8

The numbers are again converted into alphabets and sent to the receiver.


The message is decrypted using the inverse operation and key to get the original message.

3 Performance analysis

Mathematical analysis

Algorithm proposed, is a simple application of addition of two matrices. But the recurrence matrix and elements of recurrence matrix are different at each stage depending on the input and output. 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 the sum of all the elements of the plain text.

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 ( (sum of output for '1' bit) (sum of output for '0' bit)

4. 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.

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 machine and the key.


Known plain text attack


Because of the chosen finite state machines and key.


Chosen plain text attack


Because of the chosen finite state machine and key.


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 machine , key and the recurrence matrix.


Adaptive chosen cipher text attack

Difficult to crack Cipher text

Because of the chosen finite state machine, key and chosen recurrence matrix at each stage.

5 Implementation

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

Let us encrypt the word 'WONDERFUL'.

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


Where, let 'P' be the plain text.

The sum of all the elements of plain text is equal to 118 = (1110110)2

This is the key. The output of the above key is found with the help of Mealy machine.

The recurrence matrix is

Rn =

The elements of recurrence matrix depends as defined in the algorithm.

The value of n depends on output at each stage.

Then the cipher text at each state is as follows:

Sl. No

In Put

Out put / Transition


Key values

Cipher text





























On calculating residue modulus 26 for the

matrix we get

Thus, 'WONDERFUL' takes the form 'DDUSLKMNR'.

Concluding Remarks

Algorithm proposed, is based on 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 if the algorithm is known.

Writing Services

Essay Writing

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.