# Encryption Scheme For Secure Communication Using Mealy Machine 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.

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

In this paper, we develop a finite state machine for the process of encryption.

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. 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. 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 out put

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

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

Now, we consider a Mealy machine.

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.

The recurrence matrix is a symmetric matrix defined as

Rn=

where n and 's are Catalan numbers taken from Catalan sequence, where,

Cn =2n!/(n+1)!*n!, n1.

The above formula gives us the Catalan sequence- 1, 1, 2, 5, 14, 42,132

C1, C2, C3, C4, C5 , C6, C7â€¦â€¦â€¦.

## Offset Matrix

We apply the offset rule by adding 2 to the input at each stage which decides the value of n of the recurrence matrix obtained from Catalan sequence.

Let us choose nine readings to form a 3x3 matrix P which is considered as plain text matrix.

## Encryption

Step 1

Let the plain text P be a square matrix of order n, n>0. P is factorized using one of the factorization techniques.

Crout's factorization technique is applied in this case.

Step 2

Define Finite state machine through public channel.

Here Mealy machine is publicized.

Step 3

Define recurrence relation and recurrence matrix.

The recurrence matrix and recurrence relation used in this paper has already been discussed above and n of the recurrence matrix depends on input at each stage which is,

n= input+2

Step 4

Sum of all the rows and columns is calculated and the least two among them are selected as keys. They are converted into the binary form, the least among the selected two is sent to receiver one and the other one to receiver two.

Step 5

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

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

When output =0 , cipher text at q(i+1)th state= Rn * cipher text at q(i)th state.

## Decryption

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

## 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 the sum of specific row or column elements in 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

## Remarks

1

Cipher text attack

It is difficult to crack the cipher text.

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

2

Known plain text attack

Difficult

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

3

Chosen plain text attack

Difficult

Because of the chosen finite state machines and different

individual keys.

4

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 machines, different individual keys and matrix multiplication.

6

Difficult to crack Cipher text

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

## 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 'AUTHENTIC'.

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

P==

Where, let 'P' be the plain text.

Now P is factorized into L and U, where

L= and

U=

Sum of rows and columns of matrix P

R1=42, R2=27, R3=32

C1=29, C2=35, C3=37

R2 <C1< R3< C2< C3< R1

The recurrence matrix is

Rn =

The value of n in recurrence matrix depends on input as proposed in the algorithm.

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

Input

Output

(transition)

Recurrence matrix

Cipher text

1

0

1

1

0

0

1

0

1

1

Input

Output

(transition)

Recurrence

matrix

Cipher text

1

0

1

1

1

1

0

0

1

0

Cipher text for receiver one is

Cipher text for receiver two is

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