 Open Access
 Total Downloads : 525
 Authors : P. A. Jyotirmie, A. Chandra Sekhar, S. Uma Devi
 Paper ID : IJERTV2IS50533
 Volume & Issue : Volume 02, Issue 05 (May 2013)
 Published (First Online): 22052013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Application Of Mealy Machine And Recurrence Relations In Cryptography

A. Jyotirmie1, A. Chandra Sekhar2, S. Uma Devi3
1Department of Engineering Mathematics, Andhra University, Visakhapatnam, INDIA
2Department of Mathematics, GIT, GITAM University, Visakhapatnam, INDIA
3Department of Engineering Mathematics, Andhra University, Visakhapatnam, INDIA
1. ABSTRACT
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 ecommerce. It is essential to protect the information from hackers and eavesdroppers. Secret sharing schemes are ideal for storing information that is highly sensitive. The motivation for secret sharing is secure key management.In this paper, with the help of finite state machine (Mealy machine) and recurrence matrices a secret sharing scheme is developed for secure communication which is designed for encryption and also maintains secrecy of the message.
Key words: Mealy Machine, Recurrence matrix, Fermats and Mersennes sequence.

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


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. Secret sharing schemes were discovered independently by Blakley and Shamir. The motivation for secret sharing is to have secure key management. In some situations, there is usually one secret key that provides access to many important files, if such a key is lost then all the important files become inaccessible. The basic idea in secret sharing is to divide the secret key into pieces and distribute the pieces to different persons so that certain subsets of the persons can get together to recover the key.[7][1]
In Mealy Machine every finite state machine has a fixed output. Mathematically Mealy machine is a sixtuple machine and is defined as :
0
0
M= ( Q, , , , ' , q )
Q : 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.
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
' : Is a mapping function which 1
maps Q x to , giving the output associated with each transition.
q0 : 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 [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
1 +1
Rn= +1 1 +2
+2 1
Rn is a symmetric matrix.
where n 0 and s are either taken from Fermats sequence or Mersennes sequence.

Proposed Algorithm
Encryption
Step 1
Represent plain text with P
Step 2
Divide the plain text into n number of texts i.e into square matrices.
Step 3
Define a Finite state machine through public channel.
Step 4 Define input. Step 5
Get output through finite state machine.
Step 6
Define recurrence matrix and choose recurrence relation.
Step 7
Define the value of n of recurrence relation. Step 8
Define cipher text at each stage for all the plain texts.
Step 9
Send the cipher text to the respective receivers.
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 this plain text.
4. Security analysis
Extracting, the original information from the Cipher text is difficult due to the selection of the
5 Implementation
We assign 1 to letter a, 2 to letter b and so on and 26 to the letter z. We assign 27 to full stop and 0 to space.
Let us encrypt the Birds are singing.
This sentence has eighteen characters which include space and full stop.
Step 1
P= BIRDS ARE SINGING
Step 2
As per the algorithm, we construct two plain texts
2 
9 18 

A= 
= 4 
19 0 

1 
18 5 
recurrence matrix, secret key and chosen finite state
0 19 9
machines. Brute force attack on key is also difficult
And B= = 14 7 9
because of the key size.
.
14 7 27
Table 1 Security analysis
Now, we apply the remaining algorithm to plain texts A and B.
Step 3
S. N o 
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 tet 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. 
S. N o 
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. 
Mealy machine is publicized through public channel.
Step 4
All the elements of both the plain texts are added and converted into binary form. This is the input.
The sum of all the elements of plain text A is equal to 76 = (1001100)
2
And B is equal to 106 = (1101010)2 Step 5
The output of the above key is found with the help of Mealy machine.
Step 6
The recurrence matrix is defined as
1 +1
Rn =
+1 1
+2
+2 1
S l. N o 
In Pu t 
Out put / Tra nsiti on 
N 
Key values 
Cipher text 

1 
1 
1 
1 
1 3 
3 1 
1 7 
3 7 
12 20 
19 7 
1 
7 
1 
2 
25 
6 

2 
0 
2 
2 
1 9 5 
9 1 17 
5 7 1 
4 16 7 
21 21 42 
24 24 7 
3 
0 
4 
4 
1 33 
33 1 
17 65 
5 49 
54 22 
41 89 
17 
65 
1 
24 
117 
8 

4 
1 
3 
3 
1 15 
15 1 
7 31 
6 64 
69 23 
48 1240 
7 
31 
1 
31 
138 
9 

5 
1 
1 
1 
1 3 
3 1 
1 7 
7 67 
72 24 
49 127 
1 
7 
1 
32 
145 
1 

6 
0 
2 
2 
1 9 
9 1 
5 17 
8 76 
81 25 
54 144 
5 
17 
1 
37 
162 
11 

7 
0 
4 
4 
1 33 
33 1 
17 65 
9 109 
114 26 
71 209 
17 
65 
1 
54 
227 
12 
S l. N o 
In Pu t 
Out put / Tra nsiti on 
N 
Key values 
Cipher text 

1 
1 
1 
1 
1 3 
3 1 
1 7 
3 7 
12 20 
19 7 
1 
7 
1 
2 
25 
6 

2 
0 
2 
2 
1 9 5 
9 1 17 
5 7 1 
4 16 7 
21 21 42 
24 24 7 
3 
0 
4 
4 
1 33 
33 1 
17 65 
5 49 
54 22 
41 89 
17 
65 
1 
24 
117 
8 

4 
1 
3 
3 
1 15 
15 1 
7 31 
6 64 
69 23 
48 1240 
7 
31 
1 
31 
138 
9 

5 
1 
1 
1 
1 3 
3 1 
1 7 
7 67 
72 24 
49 127 
1 
7 
1 
32 
145 
1 

6 
0 
2 
2 
1 9 
9 1 
5 17 
8 76 
81 25 
54 144 
5 
17 
1 
37 
162 
11 

7 
0 
4 
4 
1 33 
33 1 
17 65 
9 109 
114 26 
71 209 
17 
65 
1 
54 
227 
12 
The elements of recurrence matrix are taken from
S/p> l. N o 
In Pu t 
Out put / Tra nsiti on 
N 
Key values 
Cipher text 

1 
1 
1 
1 
1 3 
3 1 
1 7 
1 17 
22 8 
10 16 
1 
7 
1 
15 
14 
28 

2 
1 
3 
3 
1 15 
15 1 
7 31 
2 32 
37 9 
17 47 
7 
31 
1 
22 
45 
29 

3 
0 
0 
0 
1 3 
3 1 
2 5 
3 35 
40 10 
19 52 
2 
5 
1 
24 
50 
30 

4 
1 
1 
1 
1 3 
3 1 
1 7 
4 38 
43 11 
20 59 
1 
7 
1 
25 
57 
31 

5 
0 
2 
2 
1 9 
9 1 
5 17 
5 47 
52 12 
25 76 
5 
17 
1 
30 
74 
32 

6 
0 
5 
2 5 
1 63 5 
63 1 17 
31 127 1 
6 110 35 
115 10 97 
56 203 33 
7 
0 
4 
4 
1 33 
33 1 
17 65 
7 143 
148 14 
73 268 
17 
65 
1 
52 
156 
34 
S l. N o 
In Pu t 
Out put / Tra nsiti on 
N 
Key values 
Cipher text 

1 
1 
1 
1 
1 3 
3 1 
1 7 
1 17 
22 8 
10 16 
1 
7 
1 
15 
14 
28 

2 
1 
3 
3 
1 15 
15 1 
7 31 
2 32 
37 9 
17 47 
7 
31 
1 
22 
45 
29 

3 
0 
0 
0 
1 3 
3 1 
2 5 
3 35 
40 10 
19 52 
2 
5 
1 
24 
50 
30 

4 
1 
1 
1 
1 3 
3 1 
1 7 
4 38 
43 11 
20 59 
1 
7 
1 
25 
57 
31 

5 
0 
2 
2 
1 9 
9 1 
5 17 
5 47 
52 12 
25 76 
5 
17 
1 
30 
74 
32 

6 
0 
5 
2 5 
1 63 5 
63 1 17 
31 127 1 
6 110 35 
115 10 97 
56 203 33 
7 
0 
4 
4 
1 33 
33 1 
17 65 
7 143 
148 14 
73 268 
17 
65 
1 
52 
156 
34 
a recurrence relation.
Receiver 2
9 114 71
Step 7
Let Ci+1 be the cipher text at Ci+ith state and is defined as
Ci+1 = Ci+Rn
Where Rn depends on the input.
Fermats sequence when input=0
Rn = Mersennes sequence when input = 1
Step 8
Calculate cipher text at each state.
Then the cipher text at each state is as follows:
Receiver 1
Send cipher text 109 26 209 to receiver 1
54 227 12
7 148 73
And cipher text 143 14 268 to receiver 2.
52 156 34
Concluding Remarks
Algorithm proposed, is based on finite state machine and operations on matrices. Secrecy is maintained at four levels

The secret key.

The chosen finite state machine

The different operations

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

B.Krishna Gandhi, A.Chandra Sekhar, S.Srilakshmi
Cryptographic scheme for digital signals using finite state machine
International journal of computer applications (September 2011).

Adesh K.Pandey. Reprint 2009 – An introduction to automata theory and formal languagesS.K.Kararia & sons. New Delhi.

A.Menezed, P.Van Oorschot – Hand book of Applied and S.Vanstone Cryptography eBook.

John E.Hopcroft, Rajeev Motwain, Jeffrey D.Ulman Introduction to automata theory, language, and computation Vanstone3rd impression, 2007 CRC Press., Dorling Kindersley (India) Pvt. Ltd.

http://www.certicom.com/index.php/eccctutorial

ELGamal. A public key Cryptosystem and a signature scheme based on discrete logarithms.
In Advances in Cryptology (CRYPTO 1984), Springer.

W.Diffi and M.E.Helman New directions in Cryptography. IEEE Transactions on Information theory, 22, 644654, 1976.

A Course in Number Theory and Cryptography by Neal Koblitz.

Theory of Computations by Mishra and Chandrashekharan.