A Study of Logical Exclusive Operations and Linear Transformations in Cryptography
 
Deepak Kumar Sharma1*, Dr. Birendra Singh Chauhan2
1 Research Scholar, Shri Krishna University, Chhatarpur M.P.
2 Associate Professor, Shri Krishna University, Chhatarpur M.P.
Abstract - In the present study the message is encrypted in blocks and each data block is encrypted in 8 rounds. In each round different linear transformations are applied on different elements of the data block. These linear transformations are sub-key dependent. The sub-key of each round is derived from the session key of that particular data block. The session key of each data block is generated from the master key (secret key) agreed upon by the communicating parities before communicating the messages. Between two successive linear transformation operations Exclusive-OR (XOR) operation is applied on each element with its nearest four neighbors in the matrix array to ensure good avalanche.In the key scheduled algorithm proposed in this study different keys are used for encrypting different data blocks which are called session keys generated from the master key (secret key between the sender and the receiver) and the key used for the encryption of each round is different and is derived from the session key of the corresponding block which is called the sub key. As different keys are used for encrypting different data blocks cipher is less vulnerable to passive attacks. The binary bits of each element of the message matrix M in each round are rotated right in the encryption of the message. The rotation is not fixed rotation. The number of rotations of the bits of each element of the matrix M depends on the sub key of that particular round of encryption. Logical XOR operation is performed on each element between two successive rotation operations with all its nearest neighboring elements. Hence, the identical characters in the plain text are mapped to different cipher characters even though they are in the same text block or in different text blocks. So, cipher text is not easily amenable to cryptanalysis. Even the change of a single character of the message changes almost the entire cipher block, i.e., to say that the proposed algorithm of this study has achieved a good avalanche effect.
Keywords - Logical Exclusive Operations, Linear Transformations, Cryptography,linear transformations, blocks cipher.
INTRODUCTION
In the key scheduled algorithm for encryption/decryption of the data proposed in this study, the size of the data block is selected to be 64 characters. The characters of each data block are coded to hexadecimal numbers using ASCII code table and are written as an 8x8 matrix row-wise. Each hexadecimal element is encrypted in 8 rounds using linear transformation operation so that the outcome is a new element. The key used in the linear transformation operation is different for different elements in each round of encryption i.e. the linear transformation is not fixed, but depends on the sub key. The sub key is derived for each round of encryption from the session key of that particular data block. Several researchers of cryptography used the logical operation XOR in their encryption protocols. The famous Hill cipher uses the linear transformation (involutory transformation of the type z zT) operation for enciphering the messages. Xiaolin Wang et.al discussed the uses of linear transformations in cryptography based on the definition of linear transformations, the Walsh linear spectrum and cyclic spectrum and their inverse transformations.
Hence, active attacks such as chosen plain text attacks chosen cipher text attacks are quite difficult to execute. Hence, the proposed algorithms are less vulnerable to active attacks. The present encryption algorithm is secure against man-in middle attack because the entire master key is agreed upon by the sender and the receiver rather than the electronic exchange of the parts of the key. The communicating parties can securely transport the key using key transport protocols using ECC as proposed in part (i) of study 4.The proposed key scheduled algorithm in this study is less prone to timing attacks because the time required to encipher or decipher a data block is same for all data blocks since time for enciphering or deciphering is independent of characters in the data block. Even though the original message contains less than 64 characters the remaining characters are filled at random, so that each data block contains exactly 64 characters. The size of the key is 64 decimal digits where each decimal digit takes values from 0 to 7. Hence 648 different keys are possible. It is estimated that on a 4GHz single core processor the time required to encipher/ decipher a text block is 18µsec. Hence, the vulnerability to brute force attack isvery less [the life time of a human being i.e., 100years] is approximately equal to 3Gsec. The time required to try all possible keys to decipher a single cipher block by brute force method is roughly 5Gsec. This block cipher ensures high level of security if the secret key agreed upon by the communicating parties is unbreakable.
LINEAR TRANSFORMATION
Let V and W be two vector spaces over the field F. A linear transformation from V into W is a function T from V into W such that T (cα + β) = c (T α) + Tβ for all α and β in V and all scalars c in F.
PROPERTIES OF LINEAR TRANSFORMATIONS
If T is a linear transformation from the vector space V(F) to the vector space W(F) then
i). T(x) = x for all x in V, Here T is called the identity transformation
ii). (-T) x = - [T(x)], -T is the negative transformation of T
iii). T (0) = 0 where the left hand zero belongs to V and the right hand zero belongs to W
iv). T (-x) = -T(x) for all x in V
v). T(x-y) = T(x) – T(y) for all x,y in V
ALGEBRA OF LINEAR TRANSFORMATIONS
If V, W be two vector spaces over the field F andlet T and U be two linear transformations from V into W then
i). (T + U) (α) = Tα + Uα
ii). if c is a scalar in the field F then (cT) (α) = c T (α).
PROPOSED WORK
For describing the algorithm the following notation and definitions areadopted:
1 Symbols and Notation:
2 Definitions:
1)
denotes an 8x8 matrix whose elements are hexadecimal numbers. The right superscript m denotes the number of times the linear transformation operator
is performed on the elements of the matrix M. The left superscript l represents the number oftimes the logical XOR operator
is applied on the matrix M. The right subscript n indicates the number of data block that is being encrypted.
2)
represents an 8x8 matrix whose elements are the hexadecimal codes of ASCII code table excluding the null character which is called the key matrix used in the encryption operation of the (m+1)th round of the n th data block matrix m mMn using linear transformation. The right superscript m of K represents the number of round of encryption using the linear transformation on the matrix
, where m ranges from 0 to 7. The right subscript indicates the data block which is being encrypted.
3).
is the Principal Key matrix obtained from the main key matrix
round of encryption of nth data block using linear transformation.
4). The linear transformation used in the algorithm is of the form
where a∈ A and b may be any hexadecimal numbers from 0 to F. Then z can be obtained by the inverse linear transformation
For all
is defined in the following table 1 and
is defined in the table 2
TABLE 1
TABLE 2
All the elements of the matrix
are encrypted using the linear transformation and are written in the form of 8 bit binary numbers.
6).
represents the XORing of each element of the matrix
with the nearest four neighboring elements in the encryption process. With this operation the left superscript m increases by one unit. With this operation each element
of the matrix
which is in the 8 bit binary format is XORed with the nearest four neighboring elements which results in the matrix
All the elements of the matrix
which are in 8 bit binary numbers are converted into hexadecimal numbers
7.
represents the XORing of each element of the matrix
with the neighboring elements in the decryption process. With this operation the left superscript m decreases by one unit. All the elements of the matrix
are XORed with the nearest neighboring elements as
All the elements of the matrix
which are hexadecimal numbers are converted into binary numbers.
In all the above definitions i and j take values from 0 to 7. If i+1 or i-1 or j+1 or j-1or any subscript fall out of the range {0,1,2,….7} then modulo 8 of that number be considered. The session key of each data block is itself sub key for the first round of encryption of the data block. Before communicating the messages both the sender and the receiver agree upon to use the secret key which is in the form of an 8x8 matrix K (master key) whose elements are the hexadecimal numbers of ASCII code table excluding null character. This matrix K (master key) is denoted by 0 K1 in the encryption/ decryption process i.e. the master key itself is the session key for the encryption/decryption of first data block. For implementing the algorithm the entire message is divided into data blocks D1, D2, D3……Dn of 64 characters each where n is a natural number. The characters in each message block are hex coded using ASCII code table and are arranged in the form of 8x8 matrices
row wise. The number of characters in the message always may not be the integral multiple of 64. Hence, at the end of the message the sender adds three # characters (###) and ensures that the message fills integer number of text blocks by adding random different characters after the three # characters.
CONCLUSION
In the proposed algorithm the adjacency matrix and the powers to which it is raised in each round of encryption are converted into decimal numbers and are sent to the receiver as a separate communication in public channel. This makes the retrieval of the secret key matrix from cryptanalysis is very difficult. Moreover the algorithm proposed here is much secured as long as the key is secret between the communicating parties. Single round of encryption offers inadequate security but multiple rounds of encryption offers increasing security due to improvement of avalanche effect. With this the identical characters in the plain text space are mapped to different characters of the cipher text space even though they are in the same text block or different text blocks. So, cipher text is not easily amenable to cryptanalysis. Even the change of a single element of the message matrix changes almost the entire cipher block matrix, i.e., to say that the proposed algorithm has achieved a good avalanche effect. Even though the original message contains less that 49 characters the remaining characters are filled at random, so that each data block contains exactly 49 characters. Thus the algorithm provides sufficient security against timing attacks at relatively low computational overhead. In the block cipher proposed above, linear transformation (not fixed) operation is used for the encryption of each character of the message. The session key is different for different data blocks. The sub-key is also different for different rounds of encryption. The logical XOR operation on each elements of the block is carried with four different elements of data array to ensure good avalanche. Cryptanalysis of the cipher proposed is difficult and the cipher is not easily amenable to all known types of attacks.
REFERENCES
  1. Brualdi, R. A. “Introductory combinatorics”, 4th ed. New York: Elsevier, 1997
  2. Canetti R. Halevi S. and Katz J. “Chosen cipher text security from identity-based encryption”, Advances in Cryptography-EUROCRYPT 2004, Vol. 3027 of LNCS, SpringerVerlag.
  3. CarlistleAams and Stafford Tavares, “The structured design of cryptographically good s-boxes, Journal of Cryptology, 1990, Vol.3, No.1, Pages 27-41.
  4. Chandra Sekhar A., Suneetha CH., Naga Lakshmi G. “Self-encrypting data streams for digital signals”, Int. Journal computer and network security, Vol.2, No:4 April 2010, pp 111- 113.
  5. Chandra Sekhar A., Sunetha CH., Naga Lakshmi G. and Ravi Kumar B. “Fast Fourier transforms and quadratic forms for digital audio watermarking”, International Conference on Advances in Recent Technologies in communication and Computing”, Proc. IEEE Transactions, Oct 2009.
  6. Chandra sekhar A. et.al. “Some Algebraic Curves in public Key crypto systems”, International Journal of Ultra Scientist of Physical Sciences, 2007.
  7. Chandra sekhar A., Prasad Reddy PVGD., Murthy ASN, Krishna Gandhi B. “Self-encrypting data Streams using graph structures”, IETECH Journal of Advanced Computations Vol. 2, No:1, 007-009, 2008.
  8. Chen Hun-Chen, Yen Jui-Cheng and GuoJiun-In “Design of a new cryptography system”, Lecture Notes in Computer Science, 2002,Vol2532/2002,211-219
  9. Cohn, H. “Advanced topics in computational number Theory”. New York: SpringerVerlag, 2000.
  10. Daemen J. and Rijmen V. “The design of Rijedael”, Information security and Cryptography conference, Springer 2002.
  11. Darrel Hankerson, AlferedMenezes, Scott Vanstone, “A Gide to elliptic curve cryptography”, Springer, 2004.