See discussions, stats, and author profiles for this publication at: [Link]

net/publication/274601877

Hill Cipher Modification based on Pseudo-Random Eigenvalues

Article in Applied Mathematics & Information Sciences · March 2014

DOI: 10.12785/amis/080208

CITATIONS READS

39 1,490

1 author:

Ahmed Mahmoud
Al-Azhar University – Gaza
25 PUBLICATIONS 350 CITATIONS

SEE PROFILE

All content following this page was uploaded by Ahmed Mahmoud on 01 June 2016.

The user has requested enhancement of the downloaded file.

Appl. Math. Inf. Sci. 8, No. 2, 505-516 (2014) 505
Applied Mathematics & Information Sciences
An International Journal

[Link]

Hill Cipher Modification based on Pseudo-Random

Eigenvalues
Ahmed Mahmoud1,2,∗ and Alexander Chefranov1
1 Computer Engineering Department, Faculty of Engineering, Eastern Mediterranean University, North Cyprus
2 Information Technology Department, Faculty of Engineering and Information Technology, AlAzhar University, Gaza, Palestine

Received: 12 Mar. 2013, Revised: 12 Jul. 2013, Accepted: 14 Jul. 2013

Published online: 1 Mar. 2014

Abstract: The Hill cipher is resistant to brute-force and statistical attacks, but it can be broken with a known plaintext-ciphertext attack
(KPCA). In this paper, we propose a modification of the Hill cipher, HCM-PRE, which is still resistant to brute-force and statistical
attacks, and is resistant also to KPCA due to dynamic encryption key matrix generating. With the modification, the new HCM-PRE
can be applied widely in the systems which need high security (e.g., image encryption). Experimental results show that the proposed
modification is significantly more effective in the encryption quality of images than original Hill cipher and its known modifications
(HCM-PT, HCM-H, HCM-HMAC, and HCM-EE) in the case of images with large single colour areas, and slightly more effective
otherwise. HCM-PRE is about two times faster than HCM-EE and HCM-HMAC and four times faster than HCM-H in the frame of our
experiments.

Keywords: Keywords: Hill cipher, matrix, eigenvalue, diagonal matrix, exponentiation, pseudo-random number, dynamic key, image
encryption

1 Introduction communicating parties use a pseudo-random permutation

generator, and only the consecutive number of the
The Hill cipher (HC) [1] and [2] is a well-known necessary permutation is transferred to the receiver. It has
symmetric cryptosystem that multiplies a plaintext vector good computational complexity and the number of its
by a key matrix to get the ciphertext. It is very attractive dynamic keys is the same as for HCM-PT.
due to its simplicity and high throughput [3] and [4] ; it is Another HC modification [8], HILLMRIV, also uses
resistant to the frequency letter analysis, but it can be dynamic key matrices: it modifies each row of the matrix
broken by the known plaintext-ciphertext attack (KPCA) key by multiplying the current key by a secret initial
[5]. It has a large key space [3]. HC modification [4], vector. But HILLMRIV is still vulnerable to KPCA [9]
HCM-PT, uses a dynamic key matrix obtained by and [10]. Another HC modification [6], HCM-H, also
permutations of rows and columns from the master key uses dynamic key matrix produced with the help of a one
matrix to get every next ciphertext, and transfers it way hash function applied to an integer picked up
together with an HC-encrypted permutation to the randomly by the sender to get the key matrix, and a vector
receiving side. Thus, in HCM-PT, each plaintext vector is added to the product of the key matrix with a plain text.
encrypted by a new dynamic key matrix that prevents the HCM-H is vulnerable [11] to chosen-ciphertext attack
KPCA; the number of possible dynamic keys is equal to because the selected random number is transmitted in
the number of permutations of the key matrix rows, and it clear over the communication link and is repeated. To
may be used as a characteristic of its security. But avoid this random number transfer, a modification of
permutations in HCM-PT are transferred HC-encrypted, HCM-H [11], HCM-HMAC, uses only a seed value
which means that master key matrix can be revealed by secure transfer, and then both parties generate necessary
the KPCA on the transferred encrypted permutations [6]. numbers synchronously, where HMAC is a hash function,
Modification [7], HCM-NPT, works as HCM-PT does, e.g., MD5 [12], SHA-1[13]. The difference between
but without permutations transfer; instead, both HCM-H and HCM-HMAC is similar to the difference
∗ Corresponding author e-mail: ahmed@[Link]
c 2014 NSP
Natural Sciences Publishing Cor.
506 A. Mahmoud, A. Chefranov: Hill Cipher Modification based on Pseudo-Random Eigenvalues

between HCM-PT and HCM-NPT. In [14], we introduce (K −1 )t = (Kt )−1 [4] from K −1 , and then reveals the
a modification of the HC, HCM-EE, based on the use of plaintext by (2), using (K −1 )t instead of K −1 . The
eigenvalues for matrix exponentiation to a number of dynamic keys used in HCM-PT is
pseudo-random power for a new key matrix generating
for each plaintext block. In this paper we propose a new NDK(HCM − PT ) = m! (4)
modification of HC, HCM-PRE, based on the use of
pseudo-random eigenvalues to construct a key matrix [15] HCM-NPT [7] uses the same initialization and the
and modify it for each new plaintext. same encryption/decryption technique as HCM-PT does.
The rest of the paper is organized as follows. Section But HCM-NPT assumes that the sender, A, and the
2 briefly introduces the Hill cipher, HCM-PT, HCM-NPT, receiver, B, share a secret seed value, SEED, which is
HCM-H, HCM-HMAC, and HCM-EE. Section 3 is used to generate a pseudo-random sequence of
devoted to the proposed modification HCM-PRE. permutations. In order to encrypt a plaintext, the sender,
Experimental results of image encryption quality and the A, selects a number r, and calculates
performance of the proposed modification versus the
known ones are presented in Section 4. Security and tr = PRPermutationG(SEED, r), (5)
statistical analysis of the proposed HCM-PRE are
discussed in Section 5. Finally, the conclusion is getting the r-th output permutation from the
presented in section 6. In the Appendix, description of pseudo-random permutation generator PRPermutationG
used encryption quality measures is given. (r can be a block number in the sequence of transmitted
blocks, or its function). Sender A then gets a ciphertext C
as in HCM-PT, and sends to receiver B both C and r. In
order to decrypt, B calculates tr according to (5), and then
2 Overview of the Hill Cipher and its gets the plaintext as in HCM-PT. The number of dynamic
Mmodifications keys used in HCM-NPT, NDK(HCM-NPT), is the same
as NDK(HCM-PT) (4).
All matrices considered throughout the paper are m x m Proposed in [6], another HC modification, HCM-H,
sized with entries over ZN = {0, 1, ...N − 1} , hence all the works as follows. The sender, A, and the receiver, B, share
operations in encryption/decryption algorithms are an invertible matrix K. To encrypt the plaintext P, A,
assumed mod N, where m (block size) and N (alphabet selects a random integer a, where 0 < a < N, and applies
cardinality) are selected positive integers (e.g., N=256 for a one way hash function to compute the parameter
gray scale images). Also, we assume that two parties, A b = f (a k k11 k k12 ... k kmm ), where k11 , k12 ..., kmm are the
and B, want to communicate securely, and A is a sender, elements of K; b is used to select the ki j from K, where i
and B is a receiver. and j can be calculated according to (6)
First, we introduce HC, HCM-PT, HCM-NPT,
HCM-H, HCM-HMAC and then we describe HCM-EE.    
When HC is used, A and B share an invertible key b−1 b−1
i= .(modm) + 1, j = b − .m. (6)
matrix K. Sender A encrypts a plaintext vector, P: m m

C = K × P. (1) Then, A generates a vector V = [v1 , v2 , ..., vm ]

according to (7)
The receiver, B, decrypts the ciphertext vector C by

P = K −1 ×C, (2) v1 = f (ki j )modN,

v2 = f (v1 )modN = f 2 (ki j )modN, (7)
where K −1 is the key inverse. For existence of K −1 , we
require ...,
gcd(det(K)modN, N) = 1, (3) vm = f (vm−1 )modN = f m (ki j )modN.
where gcd is the greatest common divisor and det(K) Then, A encrypts the plaintext P by
denotes the determinant of K.
HCM-PT [4] differs from HC in the following. To C = ki j × P × K +V, (8)
encrypt a plaintext P, A randomly selects a permutation, t,
of Zm , and permutes the rows and columns of a key and sends together C and a to B. The decryption process is
matrix K according to t producing a new key-matrix done by
Kt = t(K). HCM-PT encryption is then performed by (1), P = ki−1
j × (C −V ) × K .
−1
(9)
but using Kt instead of K. Additionally, sender A encrypts
t by (1) using K and getting u as a ciphertext, and sends C The number of dynamic keys used in HCM-H is
and u together to the receiver. In order to decrypt the
ciphertext, B decrypts t from u by (2), gets NDK(HCM − H) = min(m2 , N). (10)

c 2014 NSP
Natural Sciences Publishing Cor.
Appl. Math. Inf. Sci. 8, No. 2, 505-516 (2014) / [Link]/[Link] 507

Proposed in [11], HCM-HMAC, works as follows. In then calculates

order to transfer a seed value, the sender, A, transmits the
seed value a according to the Hughes key-exchange Ei = {elji }tr , 1 ≤ j ≤ m, 1 ≤ i ≤ n, (19)
protocol [16]. Then the seed value a0 can be used to
generate the chain of pseudo-random numbers where e j ∈ E, n is the number of blocks, and the random
synchronously by the both parties; a can be calculated by permutation tr can be obtained by (5). Finally, A calculates

at = HMACk′ (at−1 ),t = 1, 2, ..., (11) KMi = Q × Di × Q−1 , (20)

where k′ is the secret key of the hash function, k′ can where Di is a diagonal matrix, diagonal elements of which
calculated by are from Ei after exponentiation to li and permutation tr
are performed and
k′ = (k11 k k12 k k13 k ... k kmm k at−1 )mod2q , (12) ϕ (N) ϕ (N)
i= .r + s, 0 ≤ s < . (21)
where k denotes the concatenation, q is the number of bits 2 2
required for the hash function, and at is used in recursive The plaintext Pi is encrypted as follows
calculations of the vector V = [v1 , v2 , ..., vn ], calculated for
the encryption of t-th block, v0 = 1 , if at ≡ 0(mod p) Ci = KMi × Pi + diag(Di ), (22)
otherwise v0 = at mod p , p is a prime number.
where dig(Di ) is a vector of the main diagonal elements of
vi = ki j + v̄i−1 at mod p, i = 1, 2, ..., m, and Di .
j = (vi−1 mod m) + 1 (13) In order to decrypt the ciphertext, B computes li
according to (18), tr according to (5) and (21), Ei
v̄i−1 is calculated by
according to (19), and
r
 r

v̄i−1 = 2⌈ 2 ⌉ + vi−1 mod2⌈ 2 ⌉  , γ = ⌊log2 vi−1 ⌋ + 1
(14) (KMi )−1 = (Q × Di × Q−1 )−1 = Q × D−1 −1
i ×Q .
where γ = ⌊log2 vi−1 ⌋ + 1 denotes the bit length of vi−1 . Then, B retrieves the plaintext:
Then, A encrypts the plaintext Pt by
Pi = KMi−1 × (Ci − diag(Di )). (23)
Ct = v0 × Pt × K +V mod p, (15)
It is appropriate to mention that for computing KMi we
and sends together Ct and a to B, t=1,2,.... The receiver B
use a diagonal matrix, and only the diagonal entries of Di
calculates the required parameters by using (10)-(15), and
are exponentiated to the power li , requiring O(mlog2 li )
then gets the plaintext by
multiplications. On the other hand, to get D−1 i , we
Pt = v−1 −1
0 × (Ct −V ) × K mod p. (16) calculate the inverse of m numbers only. Note also that
Q−1 and D−1 i are calculated only once. The diagonal
HCM-EE [14] works as follows. Sender A selects a set −1
elements of Di belong to the group G of numbers
E = {e1 , e2 , ..., em } ⊂ ZN − {0}, gcd(e j , N) = 1, gcd is the co-prime to N. Based on Theorem 10.3 [17] we see that
greatest common divisor, 1 ≤ j ≤ m; at least one e j should
for N=256, 64 = ϕ (N)
2 is the maximal order of elements of
have the maximal order which is ϕ (N) 2 for N being a power G (odd numbers in Z256 ). In HCM-EE, we select at least
of 2 [17], ϕ (N) is the Eulers totient function [5], giving one element in the diagonal with the maximum order to
the number of positive integers less than N and co-prime to guarantee the maximum period of the diagonal elements.
it. Then A constructs an invertible matrix Q and calculates The number of dynamic keys of HCM-EE is estimated as
the key matrix K [15]:
LB · m! ≤ NDK(HCM − EE) ≤ ϕ (N) · m! (24)
K = Q × D × Q−1 , (17)
where LB is the maximum order of the diagonal elements
where D is a diagonal matrix, diagonal elements of which
in Di . If N is a power of 2, LB = ϕ (N)
2 .
are its eigenvalues from E. Note that Q and D satisfy (3);
A and B share them securely. Additionally, they share the
secret values, SEEDl and SEEDt; SEEDl is used to
generate the set of pseudo-random numbers 3 The Proposed Scheme
l = {l1 , l2 , ..., ln } by (18), li 6= 0 and li ∈ {2, ..., ϕ (N) − 1},
1 ≤ i ≤ n, n is the number of blocks. SEEDt is used to The proposed HCM-PRE uses the same
generate a pseudo-random sequence of permutations t. In encryption/decryption technique as HCM-EE [14] does.
order to encrypt the i-th plaintext block , A selects But HCM-PRE differs from the HCM-EE in the key
construction. It uses pseudo-random eigenvalues instead
li = PRNG(SEEDl, i) > 0, (18) of static eigenvalues exponentiated to pseudo-random

c 2014 NSP
Natural Sciences Publishing Cor.
508 A. Mahmoud, A. Chefranov: Hill Cipher Modification based on Pseudo-Random Eigenvalues

powers in HCM-EE. If the sender, A, and the receiver, B, L = N × M . Then, the so obtained three vectors represent
want to communicate using HCM-PRE, they share a the plaintext P(3 × L) which will be encrypted using the
secret value, SEED, that is used to generate block size m=16.
pseudo-randomly a sequence of eigenvalue sets, We examine the encryption quality for three different
E = (Ei ), 1 ≤ i ≤ n: images containing very large single colour areas:
[Link] (Fig. 1), [Link] (Fig. 2), and
E = PRSetGSEED (n, m), (25) [Link] (Fig. 3). Also we examined the encryption
where Ei = {ei j } ⊏ ZN − {0} is is a set of eigenvalues of quality for an image that does not contain many high
the matrix to be constructed, ei j is relatively prime to N, frequency components: [Link] (Fig. 4). The [Link]
1 ≤ j ≤ m, 1 ≤ i ≤ n, for positive integers n and m , n is (Fig. 5) is used as an example of an image containing
the number of blocks; PRSetGSEED (n, m) is a many high frequency components. Each image is
pseudo-random set sequence generator (using e.g., RC4 encrypted using HCM-PT, HCM-H, HCM-HMAC,
initialized by SEED) returning n sets, each of which HCM-EE, and HCM-PRE.
contains m numbers. The quality of encryption of these images is studied
Sender A then constructs an invertible matrix Q as in by visual inspection (Figs. 1-5) and quantitavely (Table 1,
HCM-EE. The key matrix is calculated by (17) but, used irregular deviation based quality measure ID [8, 19,
instead of D, diagonal matrix Di is used, diagonal 20] is explained in the Appendix).
elements of which are all the eigenvalues from Ei , Based on visual inspection, it is obvious that the HCM-
1 ≤ i ≤ n. HCM-PRE uses a different set of diagonal PRE and HCM-EE are better than the HCM-PT, HCM-H,
elements for every plaintext. It may be easily shown that and HCM-HMAC in hiding all the features of the image
KMi is invertible modulo N since Q and Di have (by containing large single colour areas (Figs. 1-3).
construction) determinants relatively prime to N. Based on the numerical evaluation of encryption
Finally, the plaintext Pi is enciphered by (22). quality measure ID (Table 1), we note that the proposed
scheme HCM-PRE versus HCM-EE give better
To decrypt a ciphertext, receiver B computes E encryption quality. Table 1 shows also that the proposed
according to (25), and finds scheme HCM-PRE is more effective in encryption quality
than HCM-PT, HCM-H, and HCM-HMAC. On the other
(KMi )−1 = (Q × Di × Q−1 )−1 = Q × D−1 −1
i × Q . (26) hand, HCM-PT, HCM-H, HCM-HMAC, HCM-EE, and
HCM-PRE are all good in encrypting images containing
Note that to get D−1
i , we calculate the inverse of m many high frequency components; all the algorithms give
numbers only, and that Q and Q−1 are constructed only nearly the same results but the HCM-PRE and HCM-EE
once. Receiver B then retrieves the plaintext by (23). To are the most effective ones (Table 1, rows 4-5).
generate an invertible key matrix Di , the eigenvalues must We examined the encryption time for the [Link]
be in the multiplicative group of ZN , the number of image having pixels and 45KB size. The encryption time
possible eigenvalues in the multiplicative group of ZN is measured when applying HCM-PT, HCM-H,
ϕ (N). Hence the number of dynamic keys of HCM-PRE HCM-HMAC, HCM-EE, and HCM-PRE is shown in
is Table 2. In our implementation, HCM-EE and HCM-PRE
  were used with RC4 [5] for the pseudo-random
m Period(RC4) 
NDK(HCM − PRE) = min ϕ (N) ,

  permutation generator (5), pseudo-random number
m

(27) generator (18) for HCM-EE, and pseudo-random set
where Period(RC4) is overwhelmingly likely to be greater generator (25) for HCM-PRE. We implemented HCM-H
than 10100 [18]. with SHA-1 [13] since the latter has been used in [6], and
the built-in HMAC from C # with HCM-HMAC-SHA-1.
Table 2 shows that HCM-PRE has the best execution
time; it is roughly two times faster than HCM-EE and
4 Image Encryption Quality and HCM-HMAC, and four times faster than HCM-H.
Performance of the HCM-PRE Versus HCM-EE roughly is twice better than HCM-H and it has
Known Ones nearly the same execution time as of HCM-HMAC but
HCM-EE has better encryption quality (Figs. 1-5, and
We developed programs for simulating the encryption Table 1). Table 2 shows that HCM-PT is faster than
schemes in C# on an Intel(R) Core(TM) 2 Duo 1.8 GHz HCM-EE but equations (4) and (24) show that
processor with 2-GB RAM and Windows XP. NDK(HCM-EE) is greater than NDK(HCM-PT), hence
In our experiments, several RGB images are HCM-EE is more secure than HCM-PT. Equation (27)
encrypted. Firstly, the image, P, of size N × M is shows that NDK(HCM-PRE) is greater than
converted into its RGB components. Afterwards, each NDK(HCM-EE). Hence HCM-PRE is more secure and is
colour matrix (R, G, B) is converted into a vector of more effective in the encryption time than HCM-PT,
integers within {0, 1, ...,255}. Each vector has the length HCM-H, HCM-HMAC and HCM-EE.

c 2014 NSP
Natural Sciences Publishing Cor.
Appl. Math. Inf. Sci. 8, No. 2, 505-516 (2014) / [Link]/[Link] 509

Table 1: ID for encrypted images using HCM-PT, HCM-H, HCM-HMAC, HCM-EE and HCM-PRE, m=16.

Image/Algorithm HCM-PT HCM-H HCM-HMAC HCM-EE HCM-PRE

[Link] 23980.79 13171.75 9983.87 2656.62 1338.04
[Link] 10482.25 5755.68 4830.91 2378.07 1874.30
[Link] 34036.28 18511.62 11491.48 3285.25 1328.63
[Link] 10256 10518.66 10469.33 10172.66 10201.33
[Link] 11459.55 10472.61 10336.77 9942.21 9913.25

Table 2: Encryption time (msec) of [Link] with HCM-

PT, HCM-H, HCM-HMAC, HCM-EE and HCM-PRE.

HCM-PT HCM-H HCM-HMAC HCM-EE HCM-PRE

103 425 214 200 98

Fig. 3: a) [Link] encrypted by: b) HCM-PT, c)

HCM-H, d) HCM-HMAC, e) HCM-EE, f) HCM-PRE.

Fig. 1: a) [Link] encrypted by: b) HCM-PT, c) HCM-

H, d) HCM-HMAC, e) HCM-EE, f) HCM-PRE.

Fig. 4: a) [Link] encrypted by: b) HCM-PT, c) HCM-

H, d) HCM-HMAC, e) HCM-EE, f) HCM-PRE.

Fig. 2: a) [Link] encrypted by: b) HCM-PT, c)

HCM-H, d) HCM-HMAC, e) HCM-EE, f) HCM-PRE.

c 2014 NSP
Natural Sciences Publishing Cor.
510 A. Mahmoud, A. Chefranov: Hill Cipher Modification based on Pseudo-Random Eigenvalues

5.3 Statistical Analysis Resistance

In [25], it is mentioned that in [26] Shannon said it is
possible to solve many kinds of ciphers by statistical
analysis. A good cipher should be robust against any
statistical attack. To prove the robustness of the proposed
scheme, the statistical analysis has been performed. It is
usually evaluated by the following measures [21, 23, 27,
28, 29]; calculating the histograms of the encrypted
images and the correlation of two adjacent pixels in the
plain/encrypted image demonstrating their superior
confusion and diffusion property. The obtained results
show that our scheme strongly withstands statistical
attacks.
Fig. 5: a) [Link] encrypted by: b) HCM-PT, c) HCM-H,
d) HCM-HMAC, e) HCM-EE, f) HCM-PRE. 5.3.1 Histograms of encrypted images

We have calculated and analyzed the histograms of

several encrypted images as well as their original images.
5 SECURITY AND STATISTICAL Two typical examples are given in Figs. 6-7. The
ANALYSIS histograms of the encrypted images are very close to
uniform distribution; they are significantly different from
those of the original image, and bear no statistical
The ability to withstand all kinds of cryptanalysis and
resemblance to the original image.
attacks [21, 22, 23, 24] is a good measure of the
performance of a cryptosystem. Robustness against
attacks is used to evaluate the security of our scheme. It is
5.3.2 Correlation of Two Adjacent Pixels
shown that our proposed scheme is secure from the
strongly cryptographic viewpoint. The results show the
There is a very good correlation between adjacent pixels
satisfactory security of the HCM-PRE as explained and
in the plain-image ([Link]: Figs. 1 and 8, [Link]:
discussed in the following subsections.
Figs. 4 and 9. We studied the correlation between two
adjacent pixels in plain-image and encrypted image in
three different orientations (horizontal, vertical and
5.1 Key Space Analysis diagonal). We use the following procedure: first 1000
pairs of two adjacent pixels in three different orientations
are selected randomly from image to test correlation, then
Key space is the total number of different keys that can be we calculate the correlation coefficient C.C of each pair.
used in encryption. For a secure encryption scheme, the Figs. 8 and 9 show the correlation coefficients (explained
key space should be large enough to make brute force in the Appendix) of two adjacent pixels in [Link] and
attacks infeasible. For the HCM-PRE, the key space is the [Link] encrypted by HCM-EE, HCM-PRE,
same as that of HC [3] and [4]. Therefore the key space of HCM-NPT, HCM-H and HCM-HMAC in three different
the scheme is large; hence it is secure against brute force orientations as a practical example for different image
attack. types; Table 3 shows the numerical evaluation of the
calculated correlations. It is clear that, the neighboring
pixels in the plain-image have a very high correlation
while they have a very small correlation (the closer to
5.2 Known Plaintext-Ciphertext Attack zero, the better) for encrypted images. This proves that
the proposed encryption scheme HCM-PRE satisfies very
The KPCA is effective if a same key is used to encrypt small correlation and is better than other inspected
many plaintexts. Similar to HCM-PT [4], our proposed schemes in the case of images with large single colour
scheme HCM-PRE is secure against the KPCA since each areas. We also note that the proposed scheme HCM-PRE
plaintext is encrypted by a different key, and the number versus HCM-EE gives alternately better correlation. On
of such dynamic keys is significantly large (27). the other hand, the correlation values in Table 3 show that
Equations (4), (24), and (27) show that the the examined schemes give nearly the same results in
NDK(HCM-PRE) (27) is larger than the NDK(HCM-PT) images containing many high frequency components.
(4) and NDK(HCM-EE) (24); hence HCM-PRE is more
secure.

c 2014 NSP
Natural Sciences Publishing Cor.
Appl. Math. Inf. Sci. 8, No. 2, 505-516 (2014) / [Link]/[Link] 511

Fig. 6: Histogram of RGB layers for original/encrypted [Link]: a) HCM-EE-encrypted, b) HCM-PRE-encrypted, c)

histogram of the original image, d) histogram of HCM-EE-encrypted e) histogram of HCM-PRE-encrypted

Fig. 7: Histogram of RGB layers for original/encrypted [Link]: a) HCM-EE-encrypted, b) HCM-PRE-encrypted, c)

histogram of the original image, d) histogram of HCM-EE-encrypted e) histogram of HCM-PRE-encrypted

c 2014 NSP
Natural Sciences Publishing Cor.
512 A. Mahmoud, A. Chefranov: Hill Cipher Modification based on Pseudo-Random Eigenvalues

Fig. 8: Correlation coefficients of two adjacent pixels in [Link] encrypted by: HCM-EE, HCM-PRE, HCM-PT, HCM-
H, and HCM-HMAC

Table 3: Correlation coefficients of two adjacent pixels in original and HCM-PT-encrypted images, HCM-H-encrypted
images, HCM-HMAC-encrypted images, HCM-EE-encrypted images and HCM-PRE-encrypted images.

Encrypted Image
Image Direction Plain Image
HCM-PT HCM-H HCM-HMAC HCM-EE HCM-PRE
Horizontal 0.9413 0.0849 -0.0337 -0.0517 -0.0004 0.0028
[Link] Vertical 0.9031 0.1484 0.0951 -0.0134 0.0396 0.0013
Diagonal 0.9801 0.5743 -0.0602 0.0743 0.0365 0.0051
Horizontal 0.9349 -0.0074 0.0498 0.0168 0.0282 -0.0435
[Link] Vertical 0.8538 0.0037 -0.0473 0.0026 0.0272 -0.0130
Diagonal 0.8852 -0.0774 -0.0146 0.0071 -0.0095 0.0084

Table 4: ID for encrypted images using HCM-PRE and AES, m=16.

Image/Algorithm HCM-PRE AES

[Link] 7874.33 47726.75
[Link] 9214.85 25031.32
Penguin .bmp 4410.31 20745.34

c 2014 NSP
Natural Sciences Publishing Cor.
Appl. Math. Inf. Sci. 8, No. 2, 505-516 (2014) / [Link]/[Link] 513

Fig. 9: Correlation coefficients of two adjacent pixels in [Link] encrypted by: HCM-EE, HCM-PRE, HCM-PT, HCM-
H, and HCM-HMAC

6 Conclusions dynamically changing key matrices similar to other

considered here HC modifications (HCM-PT, HCM-NPT,
HCM-H, HCM-HMAC, HCM-EE) but the proposed
Thus far, we have presented a new HC modification,
HCM-PRE is more secure than HCM-H, HCM-PT,
HCM-PRE, based on the use of eigenvalues for
HCM-NPT, HCM-EE because of the significantly larger
generating a new key matrix for each plaintext block. In
number of dynamic keys generated ((27) versus (24), (10)
this paper, five modifications of Hill cipher algorithms
and (4)). Experimental analysis also shows that the
have been implemented for image encryption: HCM-PT,
HCM-EE and HCM-PRE resist the statistical attacks.
HCM-H, HCM-HMAC, HCM-EE, and proposed here
HCM-PRE. Quality of image encryption for all
algorithms is studied using visual inspection and
numerical quality measures explained in the Appendix.
From the obtained results, it follows that the proposed Appendix
HCM-PRE is more effective in encryption quality than
HCM-PT, HCM-H, HCM-HMAC, and HCM-EE.
Encryption time for all the algorithms have been
considered, the proposed HCM-PRE is about two times In the following subsections, we describe the quality
faster than HCM-EE and HCM-HMAC, and four times encryption measures that are used in this paper: the
faster than the HCM-H. The proposed modification correlation coefficient (C.C), and irregular deviation (ID)
HCM-PRE resists the KPCA because of the use of [8, 19, 20].

c 2014 NSP
Natural Sciences Publishing Cor.
514 A. Mahmoud, A. Chefranov: Hill Cipher Modification based on Pseudo-Random Eigenvalues

Correlation Based Quality Measure

A good encryption algorithm must produce an encrypted
image of totally random patterns hiding all the features of
the original image, and the encrypted image must be
independent of the original image. This means that the
two images must have a correlation coefficient very close
to zero. The correlation coefficient is given by the
following expression:
N
∑ (xi − E(x))(yi − E(y)) Fig. 10: a) [Link] encrypted by: b) HCM-PRE, c)
C.C = v i=1 . AES.
v
u N u N

∑ ∑
u u
(xi − E(x)) t (yi − E(y))2
2
u u
t
i=1 i=1

The closer C.C to zero, the better.

Irregular Deviation Based Quality Measure

This quality measuring factor is based on how much the
deviation affected by encryption is irregular [8, 19, 20].
This quality measure can be formulated as follows:
[Link] the matrix, D, which represents the absolute
value of the difference between each pixel value of the
original and the encrypted image respectively: Fig. 11: a) [Link] encrypted by: b) HCM-PRE, c)
AES.
D = |O − E|,
where O is the original (input) image and E is the
encrypted (output) image.
[Link] a histogram distribution of the D which we
get from step 1:
h=histogram (D).
[Link] the average value of how many pixels are deviated
at every deviation value by:
DC = 1
256 ∑255
i=0 hi .
[Link] this average from the deviation histogram and
take the absolute value by:
Fig. 12: a) [Link] encrypted by: b) HCM-PRE, c)
AC(i) = |hi − DC|.
AES.
[Link]:
ID = ∑255
i=0 AC(i).
The smaller ID, the better. data patterns for the images contain large single colour
areas ([Link]: Fig. 10, [Link]: Fig. 11, and
[Link]: Fig. 12). That is, the proposed HCM-PRE
HCM-PRE Versus AES has advantage in encryption of identical plaintext blocks
over the AES.
To give adequate performance comparison, we examine The numerical evaluation for encryption quality
our proposed HCM-PRE versus other well known measure ID of the HCM-PRE and AES is given in Table
algorithms (e.g. AES). We examined the encryption 4.
quality of several images. Based on visual inspection, the
proposed HCM-PRE encrypts the images with large
single colour areas (identical plaintext blocks), it
successfully hides data patterns. The AES fails to hide the

c 2014 NSP
Natural Sciences Publishing Cor.
Appl. Math. Inf. Sci. 8, No. 2, 505-516 (2014) / [Link]/[Link] 515

References [21] E. Hossam, H. Ahmed and S. Osama, An Efficient

Chaos-Based Feedback Stream Cipher (ECBFSC) for Image
[1] L. Hill, Cryptography in an Algebraic Alphabet, American Encryption and Decryption. Journal of Computing and
Mathematical Monthly, 36, 306-312 (1929). Informatics, 31, 121-129 (2007).
[2] L. Hill, Concerning Certain Linear Transformation Apparatus [22] M. Yaobin, C. Guanrong, Chaos-Based Image Encryption
of Cryptography, American Mathematical Monthly, 38, 135- in Eduardo Bayro-Corrochano, editor, Handbook of
154 (1931). Computational Geometry for Pattern Recognition, Computer
[3] J. Overbey, W. Traves and J. Wojdylo, On the Key Space of Vision, Neural Computing and Robotics. Springer-Verlag,
the Hill Cipher, Journal of Cryptologia, 29, 59-72 (2005). Heidelberg, (2004).
[4] S. Saeednia, How to Make the Hill Cipher Secure, Journal of [23] M. Yaobin, C. Guanrong and L. Shiguo, A Symmetric Image
Cryptologia, 24, 353-360 (2000). Encryption Scheme Based on 3D Chaotic Cat Maps. Chaos
[5] W. Stallings, Cryptography and Network Security Principles Solitons and Fractals, 21, 749-761 (2004).
and Practices (4th edn.). Prentice Hall: New Jersey (2006). [24] G. Alvarez, S. Li, Some Basic Cryptographic Requirements
[6] C. Lin, C. Lee and Y. Lee, Comments on Saeednias Improved for Chaos-Based Cryptosystems. International Journal of
Scheme for the Hill Cipher, Journal of the Chinese Institute Bifurcation and Chaos, 16, 2129-2151 (2006).
of Engineers, 27, 743-746 (2004). [25] E. Hossam, H. Ahmed and S. Osama, Encryption Effeciency
[7] A. Chefranov, Secure Hill Cipher Modification SHC-M, Analysis and Security Evaluation of RC6 Block Ciphers
Proc. of the First International Conference on Security of for Digital Images. International Journal of Computer and
Information and Networks (SIN2007) Gazimagusa (TRNC) Information Technology, 1, 33-39 (2007).
North Cyprus, Eli, A., Ors, B., and Preneel, B. (Eds.) Trafford [26] C. Shannon, Communication Theory of Secrecy Systems.
Publishing, Canada. 34-37 (2007). Bell Systems Technical Journal, 28, 656-715 (1948).
[8] A. Ismail, M. Amin and H. Diab, How to Repair the Hill [27] H. Cheng, L. Xiaobo, Partial Encryption of Compressed
Cipher. J. Zhejiang Univ Sci. A, 7, 2022-2030 (2006). Images and Videos. IEEE Trans. Signal Process, 48, 2439-
[9] Y. Romero, et al., Comments on How to Repair the Hill 2451 (2000).
Cipher, Journal of Zhejiang University Science, A 9, 211-214 [28] L. Marvel, G. Boncelet and C. Retter, Spread Spectrum
(2007). Image Stegnography. IEEE Trans. Signal Process, 8, 1075-
[10] C. Li, D. Zhang, and G. Chen, Cryptanalysis of an Image 1083 (1999).
Encryption Scheme Based on the Hill Cipher, Journal of [29] S. Lian, J. Sun and Z. Wong, Security Analysis of Chaos-
Zhejiang University Science A, 9, 1118-1123 (2008). Based Image Encryption Algorithm. Phys Lett A, 351, 645-
[11] T. Mohsen, F. Abolfazl, A Secure Cryptosystem Based 661 (2005).
on Affine Transformation. John Wiley & Sons, 4, 207-215
(2011).
[12] R. Rivest, The MD5 Message-Digest Algorithm. Internet
RFC 1321, April (1992).
[13] Federal Information Processing Standard (FIPS) 180-
2. Secure Hash Standard, NIST, U. S, Department of
Commerce, (2002).
[14] A. Mahmoud, A. Chefranov, Hill Cipher Modification
Based on Eigenvalues HCM-EE, Proc. of the Second
International Conference on Security of Information and
Networks (SIN2009); Gazimagusa (TRNC) North Cyprus,
Elci, A., Orgun, M., and Chefranov, A. (Eds.) ACM, New
York, USA, 2009, 164- 167 (2009).
[15] W. Galvin, Matrices with Custom-Built Eigenspaces. this
MONTHLY, 91, 308-309 (1984).
[16] B. Schneier, Applied cryptography: Protocols, Algorithms,
and Source Code in C (2nd edn), John Wiley & Sons: New
York, (1996)
[17] T. Apostol, Introduction to Analytic Number Theory
Springer, (1976).
[18] M. Robshow, Stream Ciphers. RSA Laboratories
Technical Report TR-701, July (1995)
[Link]
[19] I. Ziedan, M. Fouad and H. Salem, Application of Data
Encryption Standard to Bitmap and JPEG Images. Proc.
Twentieth National Radio Science Conference (NRSC),
Egypt, 1-16 (2003).
[20] H. Elkamchouchi, A. Makar, Measuring Encryption Quality
of Bitmaps Images with Rijndael and KAMKAR Block
Ciphers. Proc. Twenty Second National Radio Science
Conference (NRSC), Egypt, 1-8 (2005).

c 2014 NSP
Natural Sciences Publishing Cor.
 516 A. Mahmoud, A. Chefranov: Hill Cipher Modification based on Pseudo-Random Eigenvalues

Ahmed Mahmoud
received a BSc. in Computer
Science from Al-Zaytoonah
University, Amman,
Jordan in 1997, an MSc.
in Applied Mathematics and
Computer Science and PhD
in Computer Engineering
from Eastern Mediterranean
University, North Cyprus, in
2001 and 2012, respectively. From 2001 to 2006 he was a
Lecturer in the Computer Science Department at
Al-Azhar University, Gaza Strip, Palestine. From
September 2006 to September 2011 he was with
the Computer Engineering Department at Eastern
Mediterranean University, Famagusta, North Cyprus.
Since January 2012 he has been an Assistant professor in
the Information Technology Department at Al-Azhar
University, Gaza Strip, Palestine. His research interests
are in the areas of information security, discrete geometry,
parallel programming, and distributed systems

Alexander Chefranov
received a diploma of
Engineer in Applied
Mathematics, PhD,
and DSc from Taganrog
State Radio-Engineering
University, Russia, in 1978,
1984, and 1998, respectively.
Since 1999 he has been
a Professor of Software
Engineering Department of the Institute of Technology,
South Federal University, Taganrog, Russia, and,
since 2002, he has been an Associate Professor of
the Department of Computer Engineering, Eastern
Mediterranean University, Famagusta, North Cyprus. His
research interests are in the areas of information
security, parallel processing, real-time systems, database
management systems, and scientific computing.

c 2014 NSP
Natural Sciences Publishing Cor.

View publication stats