Application Of Mealy Machine And Recurrence Computer Science Essay

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

1. INTRODUCTION

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=

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

Encryption

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.

Decryption

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

S.No

Name of the attack

Possibility of the attack

Remarks

1

Cipher text attack

It is difficult to crack the cipher text.

Because of the chosen finite state machine and the key.

2

Known plain text attack

Difficult

Because of the chosen finite state machines and key.

3

Chosen plain text attack

Difficult

Because of the chosen finite state machine and key.

4

Adaptive chosen plain text attack

Difficult

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

5

Chosen cipher text attack

Difficult to crack Cipher text

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

6

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:

P==

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

n

Key values

Cipher text

1

1

1

1

2

1

3

3

3

1

1

1

4

0

2

2

5

1

5

5

6

1

5

5

7

0

4

4

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.