Abstract: Data encryption is very important to the security of information or valuable data. The need for highly secured communication through a transmission medium is of paramount interest, recognizing the fact that most of our business and personal matters are involved. A new highly secured data encryption technique is proposed in this study. The residue number system has been effectively applied to data encryption with (2ⁿ-1, 2ⁿ, 2ⁿ+1) moduli set, which is an adaption of the Traditional Huffman’s algorithm of encryption of data, where the frequency of occurrences are used to generate binary codes. This proposed algorithm will lead to an unreadable encrypted set of bits; except for the decoder with the moduli set can decrypt it.

INTRODUCTION

Data compression is often referred to as encoding, where a very general term is encompassing any special representation of data, which satisfies a given need. Information theory is defined to be study of efficient coding and its consequences in the form of speed of transmission and probability or error (Ingels, 1971).

Data encryption and compression may be viewed as a branch of information theory in which the primary objective is to minimize the amount of data to be transmitted or stored. A simple characterization of data compression is that it involves transforming a string of character in some representation (such as ASCII) in to a new string (of bits, for example), which contains the same information, but whose length is as small as possible. Data encryption and compression has important application in the area of data transmission and data storage. One important method of transmitting messages is to transmit the symbols in their appropriate places and sequences. If there are messages, which might be sent that have the same kinds of symbols, then some of the messages must use >1 symbol. If it is assumed that each symbol requires the same time for transmission, then the time for transmission of the message is directly proportional to the number of symbols associated with it (Connell, 1973; Faller, 1973).

Data encryption and compression is certainly important to the security or integrity of information to be transmitted through a network. The need for secured communication is more profound than ever, recognizing the fact that the conduct of almost all the business and personal matters are being carried out today by computer networks (Ammar et al., 2001). Hence, an efficient and low-complexity encryption and compression algorithm that can offer security for fast transmission and storage applications is of paramount importance to our information which must be secured against intrusion and threats that are continually increasing in frequency and sophistication.

Much of the available literature on data compression approaches the topic from the point of view of data transmission. As noted earlier, data compression is of value in data storage as well. Although, this discussion will be framed in the terminology of data transmission, encryption and decryption of data files for storage is essentially the same task as sending and receiving compressed data over a communication channel. The focus of this study is on algorithms for data compression; it does not deal with hardware aspects of data compression and transmission. Cappellini (1989) research focuses on a discussion of the techniques with natural hardware implementation.

MATERIALS AND METHODS

Shannon-Fano coding is a technique, which is constructed as follows, the source message a(i) and their probability p(a(i)) are listed in order of non-increasing probability. This is then divided in such a way as to form two groups of as nearly equal total probabilities as possible. Each in the first group receives a0 as the first digit of its codeword. The messages in the in the second half have codeword beginning with 1. Each of these

groups is then divided according to the same criterion and additional code digits are appended as presented by Fano (1949) and Shannon (1949).

Huffman (1952) modified this Shannon-Fano coding and proposed a minimum redundancy coding technique which is expressed graphically, it takes as input a list of non-negative weights (w(1), …w(n)) and construct a full binary tree a binary tree is full if every node has either zero or two children whose children leaves are labeled with the weights.

Gallager (1978) researched on the improvement of the Huffman coding technique which proved that an upper bound on the redundancy of Huffman codes of (p(n) + (log(2log e))/e, which is approximately p(n) + 0.086, where p(n) is the probability of the least source message.

A secured transmission of data through the computer network needs to be considered in some applications. One method of achieve a secured and high speed processing is to use the residue number system. The residue number system has been applied to enhance the Huffman’s coding technique in this study.

A residue number system is defined in terms of relatively prime moduli set (m_i)_i=1,...n such that GCD(m_i, m_j) for i≠j, where, GCD means Greatest Common Divisor of m_i and m_j, while M = Πⁿ_i=1 m_i is the dynamic range. The residues of a decimal number can be obtained as x_i = |X|_mi thus X can be represent in RNS as X = (x₁, x₂, x₃,...x_n), 0≤x_i<m_i.

This representation is unique for any integer in RNS, X ∈ (0, M-1). For simplicity sake X mod m_i will be represented as |X|_mi in this study is presented by Ammar et al. (2001) and Parhami (2000).

RNS is a carry-free system for addition, subtraction and multiplication operation. Given a two integer numbers K and L, RNS represented by K = (k₁, k₂, k₃,...k_n) and L = (l₁, l₂, l₃,...l_n), respectively. We note here that in this study, for simplicity sake we use the operator Θ for addition, subtraction and multiplication.

W = KΘL can be calculated as W = (w₁, w₂, w₃,...w_n), where w_i = |k_iΘl_i|m_i, for i = 1, n. This means that the complexity of the calculation of the operation Θ is determined by the number of bits required to represent the residue and not by the one required to represent the input operands (Gbolagade and Cotofana, 2008; Parhami, 2000; Wang et al., 2002).

RNS system achieves high speed computation because of the parallel computing nature of the system. In order to convert numbers from binary to residues numbers a residue-to-binary converter is required at the front end and to convert back from residue to binary a residue-to-binary converter is required at the back end. The residue-to-binary, converter usually consists of a lot of modulo operation which is very tedious. The reverse converter (residue-to-binary) is a crucial part of the RNS system. To perform the conversion of residue-to-binary that is convert the residue number (x₁, x₂, x₃,...x_n) into the binary number X, the traditional CRT is used (Gbolagade and Cotofana, 2008; Wang et al., 2003). The traditional CRT is shown in Eq. 1:

(1)

Where:

is the multiplicative inverse of M_i with respect to m_i.

RESULTS AND DISCUSSION

This algorithm consists of a simplified encoder with a very high security level and a decoder pair. The RNS is applied to the decimal number X, which is the frequency of each character which is used in the encryption process. The method of using the frequency is an adaption from the traditional Huffman’s method of data coding/encryption.

Encoder: The moduli set (2ⁿ-1, 2ⁿ, 2ⁿ+1) is used in the forward conversion process to encode the decimal number to residues, which is the process of converting the frequency of occurrence of each particular character to residues. When the frequencies are converted to residues using the three moduli set (2ⁿ-1, 2ⁿ, 2ⁿ+1), the residues are then converted to binary as the encrypted bitstreams for each particular character.

The method of converting the residues into binary is an adaption of the traditional Huffman’s method of data coding, where the end result of the coding process using the tree are zeros and ones (Fig. 1).

Decoder: The outputs of the RNS encoder are received as a small wordlength and are arranged in a certain order. The bitstream is first converted from the binary forms to residues. The residues are also converted back to the decimal number X, by the use of the modified CRT.

The modified CRT is used because the Traditional CRT has a large modulo M (dynamic range) operation and so it is not so efficient for the implementation as compared to the modified CRT. We apply the modified CRT that reduces the large modulo M presented by Wang et al. (1999, 2004) (Fig. 2).

(2)

Fig. 1:	A schematic diagram of the RNS encoder

Fig. 2:	A schematic diagram of the RNS decoder

Table 1:	Show the characters and their frequencies

Table 2:	Process of encoding using the new rns model of huffman’s coding method

Where:

Security: The encrypted bitstream are send through a transmission line. These bitstream are arranged in a certain order. The intruder or the unauthorized person who breaks through the network does not understand the coding scheme used and does not also know the moduli set used in the conversion process.

Example 1: application of RNS to Huffman’s method of secured data encryption algorithm: Table 1 and 2, are extracted from the study presented by Huffman (1952) and then modified for the process of the coding theory using RNS as a tool for the method of generating codes. The moduli set (2ⁿ-1, 2ⁿ, 2ⁿ+1), the number of bit required is 2. Dynamic range, M = 3x4x5 = 60

CONCLUSION

In this study, a data encryption scheme is using RNS proposed and tested for its security levels. This scheme proposed adapts the traditional Huffman’s method of data encryption using the frequency of occurrences of each particular character in the data or information and applying the residue number system with the moduli set (2ⁿ-1, 2ⁿ, 2ⁿ+1) to encrypt the data.

This proposed scheme achieves a highly level of security and also speed of transmission of the bit through a computer network as compared to the traditional Huffman’s method of data encryption.