A block cipher using linear congruences

Journal of Computer Science,  July, 2007  by V.U.K. Sastry,  V. Janaki

• E-mail
• Print
• Link

INTRODUCTION

In the literature of cryptography Hill cipher (1) has been a prominent block cipher. Considering only 26 alphabetic characters a to z, Hill developed a block cipher whose encryption can be described by the equation

C=KP mod 26, (1.1)

where K is a key matrix of size nxn, P is a plaintext vector, and C is the ciphertext vector both having n components. The decryption of the cipher is carried out by using the relation

P = [K.sup. - 1]Cmod26 (1.2)

where [K.sup.-1] is the modular arithmetic inverse (2) of the key matrix K.

From the cryptanalysis of the cipher it is seen that it cannot be broken by bruteforce attack when the size of the matrix is large. However, in the case of the known plaintext attack, it is clearly established that the cipher can be broken by taking appropriately n column vectors of plaintext and ciphertext.

In the present paper our objective is to modify the Hill cipher by introducing an additional key. To this end, we use linear congruences, in the column vector of the plaintext, wherein the congruences contain the numbers corresponding to the plaintext characters. Here, we consider a plaintext, which includes characters that can be represented by ASCII code. Thus, we use mod 128 instead of mod 26 used in the Hill cipher. From the cryptanalysis developed in this paper, we find that the cipher cannot be broken by any cryptanalytic attack.

In section 2 of this paper, we have discussed the development of the cipher. In section 3, we have described the algorithms for encryption, decryption and presented a procedure for the modular arithmetic inverse of a matrix. In section 4, we have illustrated the cipher by considering an example. The cryptanalysis for this cipher has been carried out in section 5.In section 6, we have extended the analysis to a larger block by interlacing and iteration. Then, in section 7, we have examined the avalanche effect. Finally in section 8, we have presented the computations and conclusions.

DEVELOPMENT OF THE CIPHER

Consider a plaintext vector, which can be represented in the form

p = [([p.sub.1][,p.sub.2][,p.sub.3],.................[p.sub.n]).sup.T]. (2.1)

Let us suppose that we choose a key matrix K given by

K=[[K.sub.ij]], i=1 to n, j=1 to n, (2.2)

where the matrix K is non singular, and its determinant is relatively prime to 128.

The aforementioned conditions are to be satisfied for the existence of the modular arithmetic inverse of K with respect to mod 128.

Let C = [([C.sub.1],[C.sub.2],[C.sub.3]..............[C.sub.n]).sup.T] be theciphertext vector. (2.3)

Let us now introduce n linear congruences given by

[P.sub.i] = ([a.sub.i][p.sub.i] + [b.sub.i]) mod 128, i = 1 to n, (2.4)

where [a.sub.i] and [b.sub.i] are constants, chosen appropriately, as mentioned below.

In the process of encryption, the ciphertext C can be written as

C = KP mod 128, (2.5)

where P = [([P.sub.1][,P.sub.2][,P.sub.3],.................[P.sub.n]).sup.T].

Here the components of the plaintext vector [p.sub.i] (i =1 to n) are obtained from the consecutive n characters of the given plaintext.

Here in (2.4), we choose each one of the [a.sub.i]s as an odd integer, which lies between 0 and 127, and each one of the bis as any integer lying between 0 and 127.The reason for this choice of the values of ai and [b.sub.i], will be clear very soon. When [a.sub.i], [b.sub.i] and pi are known to us we can readily calculate Pi by using (2.4). On the other hand, when the Pi is known to us, pi can be determined by solving (2.4). As we have assumed that bi is an integer which lies between 0 and 127, we can write (2.4) in the form

[P.sub.i] - [b.sub.i] = [a.sub.i] [p.sub.i] mod 128. (2.6)

As [a.sub.i] is an odd integer, which lies between 0 and 127, it is relatively prime to 128.

Thus we obtain [d.sub.i], the multiplicative inverse if ai, such that

[a.sub.i] [d.sub.i] mod 128=1 (2.7)

where [d.sub.i] is the multiplicative inverse of [a.sub.i] . From (2.6) and (2.7), we get

[P.sub.i]=([P.sub.i] - [b.sub.i]) [d.sub.i] mod 128 (2.8)

Now let us consider the process of decryption. From the equation (2.5) we get

P = [K.sup.[ - 1]] C mod 128 (2.9)

where [K.sub.-1] is the modular arithmetic inverse of K. On using (2.9) and (2.8) we get pi, the components of the plaintext as we have indicated in the aforementioned discussion.

The problem of the encryption, given by the equation (2.5) can be written in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2.10)

Here firstly we have to obtain [P.sub.i] where [P.sub.i] =([a.sub.i] [P.sub.i]+[b.sub.i]) mod 128.For this we require the values of ai, and bi(i=1 to n).To this end we introduce a key comprising the numbers [a.sub.1],[a.sub.2]...... an and [b.sub.1],[b.sub.2]...[b.sub.n] and call this as the inner key. Subsequently we have to apply the key matrix K for obtaining C. Thus we consider this key as the outer key. Here it is to be noted that in the process of decryption firstly the outer key is to be applied and then the inner key is to be used. Thus both the keys are to be supplied by the sender in a secret manner to the receiver.