BCH Codes with computational approach and its applications in image encryption

Abstract

Accelerated adventures in computer Science and technology has made digital technology, a need of the day. Academicians, researchers, and technologists are anxious to share their secret data through the communication channel along with its security. The security of data, transmission rate, and error correction capability are the fundamental questions against the data transmission through any algebraic code dependent communication channel. Though, data security is always questioned due to the synchronized encoding and decoding algorithms. In this paper, a novel approach is developed to ensure the data security issues occurred due to synchronized encoding-decoding of a BCH code and for data transmission, a computational technique is designed by which data can be encoded and transmitted by using Field-Linear BCH code or a Ring-Linear BCH code of the same dimension, designed distance and code length. Although the Ring-Linear BCH code is preferable for encoding, on the other hand decoding of data is adept by Field-Linear BCH code. Accordingly, a computational technique of Barlekamp Massey Algorithm is utilized for the purpose. This scheme provides a quick code selection of the desired level of transmission rate and error correction capability during the communication. Thus, it also addresses the dimension issue of primitive BCH code. In addition, for the data security perspective we utilize a BCH code in round key addition and mixed column matrix steps in AES algorithm and then put on this modified AES algorithm to image encryption. The image encryption quality permits to incorporate this alteration in AES.

Keywords

Primitive BCH-code Galois ring Galois field generator polynomial AES algorithm

1 Introduction

The vital role of digital technology in academic and daily life like online banking, blue tooth, twitter, WhatsApp, Facebook, mobile communication and many social and business accounts has made it a very important subject of the day. For the security of digital data and data recovery, we use cryptography and error correcting codes. Cryptography is the science of protecting the information in computer systems and theory of coding is the science of correcting errors which occur during transmission through the noisy channel. At this time, cryptography has played a vital role in information security, embedded system design, the usage of mobile communication and the internet. Moreover, it is incorporating steps in wide-ranging areas. The number of its users are increasing besides unauthorized users applying the technique to fetch the data. Here the problem of data security arises. To handle such conditions, the data is encrypted with the technique, incomprehensible for the unauthorized user by using error correcting code.

Error correcting codes are very useful to secure the data transmission, particularly the BCH codes [21].

Designing BCH codes, we used the mathematical structures of a Galois field and a Galois ring.

The linear codes over the finite rings have been explained in a sequence of papers by Blake [1, 2]. He introduced the concepts of the BCH codes and special kind of BCH codes which are Reed-Solomon codes, over arbitrary integer residue modulo rings. Spiegel [3, 4] presented that codes over the finite local ring can be defined in terms of codes over the finite field. In continuation, through a $ℤ_{m}$ p reduction map Shankar [5] connected the idea of BCH codes having symbols from the finite field to the finite local ring. For error correction in BCH codes through a noisy channel, we use the Barlekamp-Massey decoding algorithm. An extraordinary development about Barlekamp-Massey decoding algorithm for BCH codes over finite rings was given by Interlando et al. [6]. They extended this decoding algorithm to the modified Barlekamp-Massey algorithm. The structure of maximal cyclic subgroup of group of units of Galois ring with computational approach is given by Shah et al. [7]. The magma software calculates the linear codes of length up to 256 for specific value, however, in this study we give a computational approach in constructing generator polynomial of any finite length BCH code over Galois ring by using the maximal cyclic subgroup. Thus, for any length n encoded message can be decoded by an n length BCH code over Galois field using Barlekamp-Massey algorithm computationally.

Data can be transferred via any of the scheme of BCH codes over Galois ring or Galois field. This selection of a coding scheme is based on the choice of better code rate or better error correction capability of the selected BCH code. The dimension of two classes of primitive BCH codes are addressed in [21], but in this paper, we calculate computationally the dimension of any length primitive BCH codes. A list of dimensions of the BCH codes are explained in Table 1. The narrow-sense primitive BCH codes form the well-studied subclass of BCH codes, which have been examined in a series of literature, including [8 –22]. The reader is referred to [13] for an association between primitive and non-primitive BCH codes. For fast transmission the high code rate is required, however, we can choose the fixed length of the code and optimal error correction capability by changing the designed distance.

For the data security viewpoint, we exploit a BCH code in round key addition and mixed column matrix steps in AES algorithm and then pretend this modified AES algorithm to image encryption. The image encryption quality certificates to include this modification in AES.

This paper is organized as follows: In Section 2, a brief overview of the Galois ring, Galois field, and construction of maximal cyclic subgroup of the group of units of a Galois ring is discussed. In Section 3, an explanation of the special type of the BCH codes through the Galois ring is given, moreover encoding of BCH codes over Galois ring with the computational approach is explained. The dimension of primitive BCH code is also explained in this section. In Section 4, a novel approach to the decoding of BCH codes over Galois field by using Barlekamp-Massey algorithm in computational way is explained. Decoding procedure with the flow chart and pseudo code is explained. Also, the description of Barlekamp-Massey algorithm with the help of example is assured. In Section 5, BCH codes are utilized in Mix column matrix and round key addition steps of the AES algorithm. In Section 6, the application of BCH codes in image encryption and analyses of image encryption technique with comparison to the original AES algorithm are explained. Consequently, Section 7 concludes the findings and future work opportunities. References are presented at the end of the paper.

2 Maximal cyclic subgroup of the group of units of Galois ring

2.1 Unit elements

Let R be a ring with the unity which is commutative. An element u ∈ R is unit if there exists an element v ∈ R such that u · v = 1, here 1 is an identity in R.

2.2 Local ring

Let R be a commutative ring with the unity is said to be the local ring if and only if it’s all non-unit elements form an abelian group under addition. For instance, Galois ring is a local ring.

2.3 Zero divisors

Let R be a commutative ring with unity. A non-zero element r₁ ∈ R is a zero divisor if there exists a non-zero element r₂ ∈ R such that r₁ · r₂ = 0

2.4 Basic irreducible polynomial

Let R be a commutative local ring with unity and M be the maximal ideal of R. A polynomial f (x) ∈ R [x] over R is called basic irreducible polynomial if it is an irreducible polynomial over the corresponding field $K = \frac{R}{M}$ .

2.5 Galois ring and Galois field

Let $R = \frac{Z_{p^{j^{| x |}}}}{< g (x) >}$ be the residue classes of polynomials in the variable x over $ℤ_{p^{j}}$ modulo g (x). Therefore, R = {d₀+ … + $d_{m - 1} x^{m - 1} : d_{i} \in ℤ_{p^{j}} \forall i = 0, 1 \dots m - 1}$ is called Galois ring extension of $ℤ_{p^{j}}$ and it is denoted as GR (p^j, m) This ring is commutative with identity, for m = 1 Galois ring GR (p^j, 1) is isomorphic to $ℤ_{p^{j}}$ and for j = 1 Galois ring $GR (p, m) = \frac{Z_{p} | x |}{< g (x) >}$ is isomorphic to K = GF (p^m) which is the Galois field extension of $ℤ_{p}$ , having p^m elements, where $\bar{g (x)} = R_{p} (g (x))$ is a polynomial which has the coefficients modulo p Let R^* and K^* be the group of units under multiplication in R = GR (p^j, m) and K = GF (p^m) respectively.

The following theorem is taken from [5, Theorem 2].

2.6 Theorem

Let R^* be the multiplicative group of units, it has only one maximal cyclic subgroup whose order is relatively prime to p. This cyclic subgroup has order p^m - 1.

2.7 Example

Let f (x) =1 + x + x³ be the basic irreducible polynomial over $ℤ_{8}$ . We have to calculate the maximal cyclic subgroup of the group of units of GR (8, 3) which is isomorphic to K^* = GF (8) ∖ {0}. Let α be the primitive root of the polynomial f (x) so α³ + α + 1 =0 and α³ = - α - 1 =7α + 7 now by calculating the powers of α until we get 1. The order of α in GR (8, 3) is 28. Accordingly, the generator of maximal cyclic subgroup G_s is α⁴,_. and by using Theorem 2.6 the order of G_s is 7 because m = 3 and p = 2 Thus, it can be written as G₇ =< β = α⁴ >.

This implies that G₇ ={ 1, β, β², β³, β⁴, β⁵, β⁶ } and all these elements are roots of x⁷ - 1 modulo 8. If we construct maximal cyclic subgroup of the highest order, then it is a very difficult and time-consuming process to construct manually, so for this problem we have developed an algorithm to find the maximal cyclic subgroup of any finite order and further utilize this maximal cyclic subgroup in the construction of the BCH codes. Our purposed algorithm gives us a very fast calculation of the maximal cyclic subgroup. Nowadays it has many applications in the field of cryptography and coding theory.

3 Encoding of BCH codes over Galois ring

BCH codes can detect and correct multiple errors.

It is a generalized form of Hamming code. RS (Reed Solomon) codes are a subclass of BCH codes. RS codes are non-binary cyclic codes. Nowadays BCH codes have too many applications in disk drives, satellite communication, compact disk player, DVDs, and two-dimensional bar codes. According to the paper [22], BCH codes are better than RS codes under the binary environment in Rayleigh Fading Communication Channel.

The encoding of BCH codes is used for secure data transmission through the communication channel. The construction of a BCH code in the Galois ring GR (p^k, m) is same as to the BCH code in GF (p, m) which is explained in [5]. Assume that a BCH code with parameters c, d, n, q, where all these parameters are positive integers such that 2 ≤ d ≤ n with gcd(n, q) =1 where q is power of some prime p and n = p^m - 1, m is the degree of basic irreducible polynomial f (x) in $ℤ_{p^{k}}$ . Let $\bar{α} = μ (a)$ be a primitive element in the Galois field GF (p^m) then the corresponding element α has order d (p^m - 1) in R^*, where R^* is the group of unit elements of the Galois ring extension GR (p^k, m) of $ℤ_{p^{k}}$ , for some integer d ≥ 1. The element α^d generates the maximal cyclic subgroup G_p^m-1 of R^*. Let β = α^d be a primitive element of G_p^m-1 if β^{e
₁}, β^{e
₂}, …, β^{e
_j} are roots of the polynomial g (x) then we can compute a BCH code over GR (p^k, m) with the help of generator polynomial, $g (x) = lcm (M_{e_{1}} (x), M_{e_{2}} (x), \dots, M_{e_{j}} (x))$ where M_{e
_i} (x) is minimal polynomial corresponding to β^{e
_i}. We call it a primitive BCH code over GR (p^k, m). Furthermore $\bar{g (x)} = R_{p} (g (x)), R_{p}$ (g (x)) = lcm (m_{e
₁} (x) , m_{e
₂} (x) , …, m_{e
_j} (x)), Where R_p (g (x)) is modulo p of the coefficients of g (x) and m_{e
_i} (x) is minimal polynomial of R_p (β^{e
_j}) which generates a BCH code over GF (p^m). Using p reduction map, we can easily shift the data from Galois ring to the Galois field. Because we decode the data using the primitive BCH code over the Galois field.

If there is mis correction during transmission of the data, then we change the length of BCH code or design distance and select the optimal code for transmission of data which corrects multiple errors. Every detectable error need not be corrected so for this purpose, we select those BCH codes which correct most errors. Table 1 shows the parameters of BCH Codes. In this table dimension of BCH codes are given against different length of primitive BCH code. If we choose a large length of BCH codes, then it corrects multiple errors, but the transmission will be very slow. So, we select the feasible length of code which corrects at most errors with the fast transmission of the data.

Table 1
Parameters of BCH Codes over GF (2^m)

n k d m q Optimality

15 6 6 4 2 Yes

15 7 5 4 2 Yes

15 10 4 4 2 Yes

15 11 3 4 2 Yes

31 10 12 5 2 Yes

31 15 8 5 2 Yes

31 11 11 5 2 Yes

31 16 7 5 2 No

63 9 28 6 2 Yes

63 10 27 6 2 Yes

63 16 23 6 2 Yes

127 14 56 7 2 Yes

255 20 112 8 2 Yes

511 484 7 9 2 Yes

511 241 73 9 2 Yes

1023 863 33 10 2 Yes

242 16 134 5 3 No

n	k	d	m	q	Optimality
15	6	6	4	2	Yes
15	7	5	4	2	Yes
15	10	4	4	2	Yes
15	11	3	4	2	Yes
31	10	12	5	2	Yes
31	15	8	5	2	Yes
31	11	11	5	2	Yes
31	16	7	5	2	No
63	9	28	6	2	Yes
63	10	27	6	2	Yes
63	16	23	6	2	Yes
127	14	56	7	2	Yes
255	20	112	8	2	Yes
511	484	7	9	2	Yes
511	241	73	9	2	Yes
1023	863	33	10	2	Yes
242	16	134	5	3	No

3.1 Example

Let p (x) = x⁸ + x⁴ + x³ + x² + 1 be the basic irreducible polynomial over $ℤ_{8}$ and suppose that we have to find the BCH codes with best- known parameters [255, 9, 120] according to paper [21] over the Galois field $GF (2^{8}) = \frac{Z_{2} [x]}{< x^{8} + x^{4} + x^{3} + x^{2} + 1 >}$ and Galois ring $GR (8, 8) = \frac{Z_{8} [x]}{< x^{8} + x^{4} + x^{3} + x^{2} + 1 >}$ . Let α be the root of this polynomial p (x) in the Galois ring. By using the Theorem 2.6 generator of maximal cyclic subgroup of the group of units of Galois ring GR (8, 8) is G₂₅₅ =< β = α⁴ >, where β is the primitive element of group G₂₅₅. Now we find generator polynomial of BCH codes of length n = 255 by using the maximal cyclic subgroup G₂₅₅. Manually it is very difficult and time-consuming process to construct maximal cyclic subgroup of order 255. Our purposed algorithm gives output very fast which reduces the human effort. The coefficients of the elements of the maximal cyclic subgroup in descending order are shown in following Table 2.

Table 2
Elements of Maximal cyclic subgroup of order 255

00010000 00077707 77001101 23221100 74112366 30207377 40253060 74015363

60360307 25761252 73701512 23002510 00456500 65477343 10537441 63617535

14433427 27140145 60211574 37717767 45505017 17357330 63017453 13471407

00014641 46407707 35250240 52246663 17535264 42157635 30456173 36024343

12333006 25261355 74406562 72725440 63450416 23421043 73320346 11764356

31402112 75151740 23753673 11342013 16430354 74270745 14700561 70260410

15001262 04057300 77473703 41616241 25115627 37204277 10363160 20276252

40115161 15172777 11027471 62565506 75317032 04415257 56563347 60460432

26100242 62335270 72404355 52075640 07574701 40464231 06372242 24326351

45401256 51050340 35626203 32265126 24345062 32577054 43361731 50153752

62745373 73067214 00733702 37106515 33654170 13322023 14332356 16541155

02166634 64031072 36537105 40275735 13543161 25556134 42754633 00650113

01305323 52675750 00016721 67207707 12160160 76270072 13030361 77234205

54014665 75502307 37754330 11251413 02530263 00710335 03450717 04237043

74623165 46511226 50326137 14326656 51552256 54231233 41026165 24122506

07173276 33770271 54207611 25631460 75125025 64556176 07000733 00440100

01400444 03774740 44272611 66743561 51307614 20000750 65306000 05207350

76616360 76332127 34233755 00440165 01250444 03141263 17233174 21502665

03671730 14203621 21335460 31010455 50134607 71237575 05574465 47444431

01424544 44752546 65560713 24137532 57422175 55705746 05324310 46163156

77215472 66706067 04323210 36273256 01274361 42377061 32552751 72353133

40711153 55234717 75556065 74567633 03346632 63501154 30745530 22152414

00440173 01330444 03052455 21253003 15337263 64501055 36645430 23403624

11152540 13111273 06265477 56710462 31443117 05165344 56601572 42665220

14620022 73767226 00164712 47031272 57401605 42027140 33642406 76413124

44114147 01312377 22324657 22601456 70360620 17070252 72540201 11260234

70737162 02007515 73730600 14737215 65575115 76146431 77564674 50426332

16245646 47321664 53007756 27533500 14216635 51464367 75441142 25451744

70165643 67442272 45632544 64563025 56367632 23532452 07376235 63146251

01315174 50374657 71551151 21067233 57040102 35477504 45442441 63744744

66467114 15140442 76502774 32514230 15107537 67416370 06645047 52076624

17334701 37541655 64654534 63357723 16602053 11071220 00000001

By taking LCM of all the minimal polynomials using the maximal cyclic subgroup G₂₅₅, we get generator polynomial of the BCH code with parameters [255, 9, 33]. Its vectorial form is as under. $\begin{matrix} g = 170757525011600427050105620755114411343 \\ 63225445634204427660073023462264552323 \\ 23145077765341045071360330407144041152210 \\ 67153055507422345624612034604433334650176 \\ 67676054032365133143320212611415235203733 \\ 37006563725756001312331111365465332046165351 \end{matrix}$

This generator polynomial generates a BCH code of 255 length with designed distance 120 over Galois ring GR (8, 8). If we want to construct the BCH codes over Galois field GF (2⁸) then just take modulo 2 to the coefficients of generator polynomial over the Galois field.

Its vectorial form is as under. $\begin{matrix} \bar{g} = 11011110101100000101010100011111001110 \\ 1010011001101000000100001100100010001101 \\ 0101101011101101001011100110001100001110 \\ 01001111011101000101000010010000011110010 \\ 110010100100101011111011000100110110110011 \\ 1111000101101110001110111111101001110000101111 \end{matrix}$

Now we can find simply dimension of BCH codes over Galois field with the support of the degree of the generator polynomial. So, the dimension of BCH codes of length 255 over Galois field with designed distance δ = 120 is, k = 255 - 246 = 9 over GF (2⁸). Similarly we can find the dimension of primitive BCH code of any length by using degree of generator polynomial. It is very challenging to construct BCH codes of the large length over Galois ring and Galois field manually so for this problem, we develop an algorithm which reduces the human effort. Our proposed algorithm also gives the dimension of BCH codes over Galois field, corresponding to any designed distance. So, another goal is completed. The dimension of the code gives us, how much length of message can be sent through encoder. If we have sent a k length message through a noisy channel, then attach n - k parity check digits or redundant digits to each block to obtain n length code word. Now the code word can be send through the noisy channel then there are two possibilities in transmitted code word either received word is code word or not, if the received word is not code word then during transmission there must be an error occurred and then receiver request to the transmitter that the word would be retransmitted after correction the error but if the received word is code word then there is no error occur. It is noted that error correction capabilities of word is less than or equal to the error detection. For secure data transmission we encode the message through encoder of BCH code.

3.2 Example

By using 2.7 example, suppose we want to find the generator polynomial of BCH code over Galois ring GR (8, 3) for designed distance δ = 4. So, for this construct the minimal polynomial for β^I where i = 1, 2, 3. Since β, β², β⁴ has the same minimal polynomial so, hence, vectorial form of minimal polynomial is,m₁ = 1657

Now β³, β⁶, β⁵ have same minimal polynomial so hence its vectorial form is m₁ = 1327

Therefore, g = 1111111 is vectorial form of generator polynomial of BCH code corresponding to Galois ring GR (8, 3).

3.3 Transmission of message

Now suppose that we want to send message m = 10 to intelligence agency through encoder of Galois ring GR (8, 3) with designed distance δ = 4. For transmission of the data, firstly we encode the message. So, code polynomial is c (x) = m (x) g (x), c = 1111111 this code word can be sent through communication channel. Now if we want to transmit this message 1111111 instead of 10 through communication channel during transmission error may be occurring then we apply decoder of BCH code to correct the errors. Flow chart of the encoding of BCH Codes over Galois ring is given in Fig. 1.

Fig.1

Flow chart of construction of BCH codes over galois ring.

4 BCH code over Galois field: Decoding

If code word c (x) = c⁰ + c¹x + c²x² + … + c_n-1X^-1 is sent through noisy channel, then let error e(x) occurs during transmission so the received code polynomial is r (x) = c (x) + e (x) = r⁰ + r¹x + r²x² + … r_n-1x^-1 .

To decode this received polynomial first we find the syndromes by formula S_i = r (ξⁱ) here i = 1, 2, 3, …, 2t.

Since c (x) is code word so c (ξⁱ) =0 therefore, S_i = r (ξⁱ) = e (ξⁱ).

Suppose that e (x) = x^1₁ + x^1₂ + … + x^1_ν here 0 ≤ l₁ < l₂ < l₃ < … l_ν < n, S₁ = r (ξ¹) = e (ξ¹) = ξ^1₁ + ξ^1₂ + … ξ^1_ν, here ν denotes the errors introduced by the channel. $\begin{matrix} S_{1} = ξ^{1_{1}} + ξ^{1_{2}} + \dots + ξ^{1_{ν}} \\ S_{2} = (ξ^{1_{1}})^{2} + (ξ^{1_{2}})^{2} + \dots + (ξ^{1_{ν}})^{2}, \\ ⋮ \\ S_{2 t} = (ξ^{1_{1}})^{2 t} + (ξ^{1_{2}})^{2 t} + \dots + (ξ^{1_{ν}})^{2 t} \end{matrix} .$

Here ξ^1₁, ξ^1₂, ξ^1₃, …, + ξ^1_ν are unknowns, any method for solving these equations and find the unknowns is called decoding algorithm for BCH codes.

If we find ξ^1₁, ξ^1₂, ξ^1₃, …, + ξ^1_ν then powers l₁, l_2, … , lν denotes the error positions in the received message.

Suppose for simplification γk = ξ^jk be the error location numbers, here 1 ≤ k ≤ ν. $\begin{matrix} S_{1} = (γ_{1}) + (γ_{2}) + \dots + (γ_{υ}) \\ S_{2} = (γ_{1})^{2} + (γ_{2})^{2} + \dots + (γ_{ν})^{2} \\ S_{3} = (γ_{1})^{3} + (γ_{2})^{3} + \dots + (γ_{ν})^{3} \\ ⋮ \\ S_{2 t} = (γ_{1})^{2 t} + (γ_{2})^{2 t} + \dots + (γ ν)^{2 t} \end{matrix}$

Now we define error locator polynomial as, $\begin{matrix} σ (x) = (1 + γ_{1} x) (1 + γ_{2} x) (1 + γ_{3} x) \dots (1 + γ_{ν} x), \\ σ (x) = σ_{0} + σ_{1} x + σ_{2} x^{2} + \dots + σ_{ν} x^{ν} . \end{matrix}$

Here the coefficients of x are elementary symmetric functions we defined as, $\begin{matrix} σ_{0} = 1 \\ σ_{1} = γ_{1} + γ_{2} + \dots γ_{ν} \\ σ_{2} = γ_{1} γ_{2} + γ_{2} γ_{3} + \dots γ_{ν - 1} γ_{ν} \\ ⋮ \\ σ ν = γ_{1} γ_{2} γ_{3} γ_{4} \dots γ_{ν} . \end{matrix}$

4.1 Remark

The inverses of roots of σ(x) are error location numbers.

We can relate elementary symmetric functions with the syndromes by using the Newton identities as follows, $\begin{matrix} S_{1} + σ_{1} = 0 \\ S_{2} + σ_{1} S_{1} + 2 σ_{2} = 0 \\ S_{3} + σ_{1} S_{2} + 2 σ_{2} S_{1} + 2 σ_{3} = 0 \\ ⋮ \\ S_{ν} + σ_{1} S_{ν - 1} + \dots + σ_{ν - 1} S_{1} + ν σ_{ν} = 0 \\ S_{ν + 1} + σ_{1} S_{ν} + \dots + σ_{ν - 1} S_{2} + σ_{ν} S_{1} = 0 \end{matrix}$

We decode any received message over Galois field is as follows,

Step 1. Find the syndromes from received polynomial.

Step 2. Calculate Error locator polynomial σ (x).

Step 3. Find error location numbers by finding the inverses of roots of σ (x).

Step 4. Correct the errors.

Our main step is to calculate σ (x) and this can be calculated by Barlekamp Massey (BM) algorithm.

This is a very fast decoding algorithm and it is used for binary and non-binary BCH codes. We start this algorithm by following initial conditions as shown in Table 3.

Table 3
BM Algorithm

μ σ^μ (x) d _μ l _μ μ - l_μ

–1 1 1 0 –1

0 1 S ₁ 0 0

1

2

·

·

·

2t

μ	σ^μ (x)	d _μ	l _μ	μ - l_μ
–1	1	1	0	–1
0	1	S ₁	0	0
1
2
·
·
·
2t

Here d_μ is nth discrepancy, l_μ is the degree of σ^μ (x), S₁ is first nonzero syndrome, t is error correction capability. The following steps are performed to calculate error locator polynomial (σ^2t (x).

Step 1. If d_μ = 0 then σ^μ+1 (x) = σ^μ (x) and l_μ+1 = l_μ.

Step 2. If d_μ ≠ 0 then find m < μ such that d_m ≠ 0 and m - l_m has largest value in last column of the table then,

$σ^{μ + 1} (X) = σ^{μ} (x) + d_{μ} d_{m}^{- 1} x^{μ - m} σ^{(x)}$

and $l_{μ + 1} = max (l μ, lm + μ - m)$

Step 3. To find discrepancy, use formula $d_{μ + 1} = S_{μ + 2} + σ_{1}^{(μ + 1)} S_{μ + 1} + \dots + σ_{1 μ + 1}^{(μ + 1)} S_{μ + 2 - 1 μ + 1}$

After finding the σ^2t (X), calculate the roots of this polynomial and take inverses of those roots, we call it error location numbers and powers of the error location numbers shows error positions in received code. To correct these errors, subtract error vector from received vector. If wants to find the message word, then divide corrected code word by generator polynomial g (x).

4.2 Decoding of BCH code example

Suppose that [7 , 4] BCH code generated by g (x) = x⁶ + x⁵ + x⁴ + x³ + x² + x + 1 and a code word c = 1111111 is sent through the channel. Suppose that the error occurs during transmission and received vector is r = 1101111. We want to find the error in this received vector and then determine corrected code word also find the message word.

Here n = 7, k = 2, d = 4 so t = [(d - 1)/2)] = [(4 - 1)/2)] =1 and $GF (2^{3}) = \frac{ℤ_{2} [X]}{< x 3 + x + 1 >}$ , here x3 + x + 1 is primitive polynomial and let α be the primitive root of this polynomial so, 1 + α + α³ = 0. The received vector in the form of polynomial is, r (x) = x⁶ + x⁵ + x⁴ + x³ + x + 1

First, we construct Galois field for decoding of BCH codes. $\begin{matrix} α^{1} = α \\ α^{2} = α^{2} \\ α^{3} = α + 1 \\ α^{4} = α^{2} + α \\ α^{5} = α^{2} + α + 1 \\ α^{6} = α^{2} + 1 \\ α^{7} = 1 \end{matrix}$

Step 1:

Calculate syndromes by using the formula S_i = r (αⁱ) here i = 1, 2, 3.

S₁ = r (α) =1 + α + α³ + α⁴ + α⁵ + α⁶ mod (1 +α + α³) = α² (from the elements of Galois field)

S₂ = r (α²) = α² + α = α⁴

S₃ = r (α³) = α² + 1 = α⁶

Step 2:

Now we use Barlekamp Massey Algorithm to find error locator polynomial σ (x) σ (x).

This algorithm starts with following initial conditions, $\begin{matrix} μ = - 1, σ^{- 1} (x) = 1, d_{- 1} = 1, l_{- 1} = 0, μ - 1_{μ} = - 1, \\ μ = 0, σ^{0} (x) = 1, d_{0} = S_{1} = α^{2}, l_{0} = 0, μ - l_{μ} = 0 - 0 = 0, \end{matrix}$

In this Algorithm we use the following formulas,

$σ^{μ + 1} (X) = σ^{μ} (x) + d_{μ} d_{m}^{- 1} x^{μ - m} σ^{m} (x)$

$d_{μ + 1} = S_{μ + 2} σ^{(μ + 1)} S_{μ + 1} + \dots + σ 1_{μ + 1}^{(μ + 1)} S_{μ + 2 - 1 μ + 1}$ .

l_μ+1 = max(lμ, lm + μ - m)

To find σ¹ (x) put μ = 0 and m = -1 in formula (1). $\begin{matrix} σ^{1} (x) = σ^{0} (x) + d^{0} d^{- 1 - 1} x^{1} σ^{0} (x) \\ σ^{1} (x) = 1 + α^{2} (1)^{- 1} x (1) = 1 + α^{2} x, \end{matrix}$

Also put n = 0 and m = -1 in formula (2) then $l_{1} = max {l_{0}, l_{- 1} + 0 + 1} = max {0, 1} = 1$

Now find d₁ = ?

Put μ = 0 in formula (2) we get, $d_{1} = S_{2} + σ_{1}^{(1)} S_{1} = α^{4} + α^{2} . α^{2} = 0$ , here $σ_{1}^{(1)}$ is coefficient of x in σ¹ (x).

Since d₁ = 0 so σ² (x) = σ¹ (x) and l₂ = l₁ this implies that σ² (x) =1 + α²x and l₂ = 1.

Now we find d₂ = ? ?

Put μ = 1 in formula (2) then

$d_{2} = S_{3} + σ_{1}^{(2)} S_{2} + σ_{2}^{(2)} S_{1} = α^{6} + α^{2} . α^{4} = 0$ , here $σ_{1}^{(2)}$ is coefficient of x in σ⁽²⁾ (x) and $σ_{1}^{(2)}$ is coefficient of x² in σ⁽²⁾ (x)

Now the required error locator polynomial is shown in the last row of the Table 4.

Table 4
BM Algorithm

μ σ^μ (x) d _μ l _μ μ - l_μ

–1 1 1 0 –1

0 1 α ² 0 0

1 1 + α²x 0 1 0

2 1 + α²x 0 1 1

μ	σ^μ (x)	d _μ	l _μ	μ - l_μ
–1	1	1	0	–1
0	1	α ²	0	0
1	1 + α²x	0	1	0
2	1 + α²x	0	1	1

Hence, σ^2t (x) = σ² (x) =1 + α²x is the error locating polynomial.

Step 3: Find the roots of error locating polynomial by substituting the non-zero elements of Galois field, here Galois field is GF (2³) so by substituting α, α², α³, α⁴, α⁵, α⁶, α⁷ we get α⁵ as a root of error locator polynomial. Now to find the error location number we take inverses of this roots so (α⁵) ^-1 = α² this implies that α² is the error location numbers and power 2 shows that error position in received vector. The error vector is e (x) = x².

Step 4: The corrected code polynomial is

c (x) = r (x) - e (x), so $\begin{matrix} c (X) = x^{6} + x^{5} + x^{4} + x^{3} + + x + 1 - x^{2} \mod 2 \\ = x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1 \end{matrix}$

c = 1111111 is corrected code word.

To find message word divide the corrected code polynomial by generated polynomial, $u (x) = \frac{c (x)}{g (x)} = 1,$

This implies that u = 10 is original message word of k = 2 length which was transmitted after encoding through noisy channel. It is very difficult and time-consuming process to encode message over Galois ring and decode our message of large length manually. So, for this problem we develop an algorithm with the help of computer language C# which gives us output without human effort. Our proposed algorithm gives the fast transmission of data to the communication channel. Existing software Magma and MATLAB works for some small length of BCH code over Galois field and Galois ring, but this novel scheme gives transmission of data through Galois ring and recovers data through Galois field with the computational approach. For encoding the message, we use Galois ring and for decoding the received message we used Galois field. The pseudo codes of Barlekamp Massey decoding algorithm are explained in algorithm1, algorithm2, algorithm3 and flow chart of algorithms are displayed in Fig. 2,

Fig.2

Flow chart of decoding of BCH codes using barlekamp massey algorithm.

5 Modified AES algorithm using BCH codes

In AES algorithm, mixed column matrix is an MDS (maximum distance separable) matrix which is constructed using Galois field GF (2⁸). We also constructed in our article BCH codes over Galois field GF (2⁸) So, we utilize BCH codes in the construction of mixed column matrix. That’s why we choose AES.

AES algorithm consists of four steps,

Substitute byte

Shift Rows

Mix Columns

Add Round Keys

We modified the AES algorithm with the help of BCH codes have the following steps.

Step 1. Convert 128 bits of data into 16 data bytes and write these 16 bytes in a 4 * 4 state matrix.

Step 2. The generator polynomial of BCH code is used as a round key. This key is served as the secret key and the current state matrix is XOR with this key in each add round key step.

Step 3. Now the entries of the current state matrix are substituted with the S-box entries.

Step 4: Then perform the circular shift on each row of the current state matrix. Row 0 is shifted 0 byte left, row 1 is shifted 1 byte left, row 2 is shifted 2 bytes left and row 3 shifted 3 bytes left and so on.

Step 5: Now the current state matrix is multiplied with the mix column matrix which is constructed by using the BCH code. The multiplication is modulo multiplication with respect to the corresponding Galois field.

Step 2 to Step 5 comprises a round. Repeat these steps ten times for AES-128 encryption results for image data. We call this proposed scheme is AES-C.

5.1 Construction of round keys by using BCH codes

By using the proposed algorithm of encoding of BCH codes over Galois ring and Galois field we construct generator polynomial of BCH codes in example 3.1 with parameters [n = 255, k = 9, δ = 120] as follows, the coefficients of generator polynomials are, $\begin{matrix} 110111101011000001010101000111110011101010 \\ 011001101000000100001100100010001101010110 \\ 101110110100101110011000110000111001001111 \\ 011101000101000010010000011110010110010100 \\ 100101011111011000100110110110011111100010 \\ 1101110001110111111101001110000101111 \end{matrix}$

Algorithm 1: Decoding of BCH Code

Algorithm 2: Decoding of BCH Codes

Algorithm 3: Decoding of BCH Codes

Take 128-bits from these coefficients as a key which is used as a round key in AES algorithm.

10011110 11101000 10100001 00100000 11110010 11001010 01001010 11111011 00010011 01101100 11111100 01011011 10001110 11111110 10011100 00101111

In decimal form: 158 232 161 32 242 202 74 251 19 108 252 91 142 254 156 47

5.2 Construction of mixed column matrix using BCH Code

By using proposed scheme of BCH code, we construct the mixed column matrix for AES algorithm. Then this matrix is used for security of image data. Matrix A is the mix column matrix which is constructed with the help of example 3.1 over BCH code [n = 255, k = 9, δ = 120]. $A = [\begin{matrix} 244 & 57 & 127 & 113 \\ 142 & 37 & 192 & 201 \\ 179 & 43 & 159 & 21 \\ 89 & 149 & 207 & 138 \end{matrix}]$

This mixed column matrix creates diffusion in the AES algorithm. Using our newly designed matrix A and Key in AES algorithm in the image encryption scheme, we observe better results for the security of image data as compared to the original AES algorithm. The analyses of the quality of proposed scheme are explained in the next step. For this, we apply different attacks on encrypted image quality.

6 Statistical analyses of image encryption

Texture, along with color, is one of the most advantageous features of material defining the look of its surface. The modest analysis is stimulating as it is established to be related to the way the human visual system perceives texture, a very first line to texture, and it is broadly used in image segmentation. By this process is possible to compute, among others, five features which are proposed to describe texture: Contrast, Homogeneity, Correlation, Energy and Entropy.

6.1 Contrast

Contrast is a measure used to classify objects in an image. A strong encryption method produces a high level of contrast. It is the difference in color or in luminance that makes an object distinguishable. It is determined by the difference in brightness and color of the object and other objects within the same field of view.

6.2 Correlation

For encryption effect of the proposed method, we perform correlation analysis on both the plain and the encrypted images. It is quite clear that for efficient encryption, the correlation of the encrypted image should be reduced as compared to the plain image. The correlation coefficient is given by, $rxy = \frac{E ((x - μ_{x}) (y - μ_{y}))}{\sqrt{δ x δ y}}$ , where, μ and δ represent the expected value and variance. The value of the correlation coefficient close to zero guarantees better encryption quality.

6.3 Energy

In this analysis, we measure the energy of the encrypted images as processed by various S-boxes. This measure gives the sum of squared elements in the gray level co-occurrence matrix ∑_i,jp (i, j) ², Where p (i, j) is the number of gray-level co-occurrence matrices. Energy describes the quality of encryption.

6.4 Homogeneity

Gray level co-occurrence matrix (GLCM) shows the ability of arrangements of pixel brightness results in tabular form. The closeness of the distribution in the (GLCM) to its diagonal is measured through the homogeneity analysis. If the homogeneity is small as much possible then encryption is better.

6.5 Entropy

Entropy is a statistical measure of randomness that can be used to characterize the texture of the image. Entropy is defined as $H = - \sum_{i = 1}^{n} p (x) {log}_{b} p (x_{i})$ , where P (x_i) contains the histogram counts. Entropy must be close to the 8 for better image quality.

6.6 Application of BCH Code in image encryption

Now we utilize the modified AES-C for the image encryption scheme. Figure 3 shows that original Lena image, Figs. 4, and 5 shows encrypted image by original AES and modified AES-C respectively. From Figs. 4 & 5 and Table 5, it is analyzed that, the encrypted image by AES-C is better than encrypted image by AES. The detail is explained in next section.

Fig.3

Original lena image.

Fig.4

Image by AES.

Fig.5

Image by AES-C.

Table 5

Statistical analyses of 256 × 256 Lena ciphered image under AES and AES-C

	Contrast	Correlation	Energy	Homogeneity	Entropy
AES Ciphered image	0.4074	0.9178	0.1354	0.8653	7.7878
AES-C Ciphered image	5.1311	0.0779	0.0266	0.4661	7.7959
(Red Channel)
AES Ciphered image	0.4153	0.9261	0.0973	0.8661	7.7878
AES-C Ciphered image	5.3257	0.0854	0.0250	0.4620	7.7959
(Green Channel)
AES Ciphered image	0.3989	0.8489	0.1594	0.8662	7.7878
AES-C Ciphered image	5.0775	0.0756	0.0271	0.4672	7.7959
(Blue Channel)

6.7 Statistical analyses

The statistical analyses of encrypted Lena image by using original AES algorithm and proposed algorithm

AES-C are shown in Table 5.

The Table 5 shows that the comparison of encryption technique with original AES algorithm and proposed AES algorithm (AES-C) for three different channels (Red, Green, Blue). The results of proposed scheme AES-C are better in each channel because correlation and energy are close to zero in each case as compared original AES algorithm and homogeneity by the proposed scheme (AES-C) is decreases in each channel. If Contrast is greater then it means that image encryption quality is strong. It is observed that contrast is greater by AES-C as compared to original AES algorithm in each channel, and the most important part of the quality of image encryption technique is an entropy, in each channel proposed AES-C gives entropy close to 8 which give high security of our secret image. it is concluded that the proposed scheme is better as compared to the original AES algorithm. Using this scheme, we encrypt the image then send it through a channel by using BCH codes over Galois ring and channel may be noisy, so the error may occur during transmission so for this problem we used computational scheme of BCH codes over Galois field which corrects errors during transmission. We apply the encoding scheme to each block of 128 bits of pixels of the encrypted image and then decode the received vector by using the computational technique of Barlekamp Massey Algorithm. If data loss during the transmission then decoder of BCH code corrects the error, so this causes high security to the data. It means that if there is an error in encrypted data during transmission then there is no secure decryption. So, for this purpose we apply decoder of BCH codes which corrects the errors in encrypted data and then we can decrypt the data and attain original message.

6.8 Histogram analyses

An image histogram illustrates how pixels in an image are distributed by graphing the number of pixels at each color intensity level. The histogram of the encrypted image is uniform and significantly different from the respective histograms of the original image and hence does not provide any clue to employ any statistical attack on the proposed image encryption.

Figure 6 Shows that the histogram analyses of original and encrypted image by proposed encryption algorithm (AES-C) through different channels (Red, Green, Blue). The histogram analyses show that the histogram of the ciphered image is uniform and is significantly different from the original image. The encryption algorithm has covered up all the characters of the plain image and has complicated the statistical relationship between the plain image and its ciphered version. So, from the histogram and statistical analyses, we conclude that our proposed encryption scheme is better than as compared to the original AES algorithm.

Fig.6

Histogram through RGB (Red, Green, Blue) channel.

7 Conclusion

The following are the outcomes of the study, The link between two types of BCH codes over Galois ring and Galois field is developed computationally in such a way that the data can be transmitted through either by BCH codes over Galois ring or BCH codes over Galois field. Then a transmitted code can be decoded using the computational approach of Barlekamp Massey algorithm for Galois field-based BCH code. The number of codewords in the BCH code over Galois ring is greater than the BCH code over the Galois field. Therefore, we, have a variety of messages that can be transmitted through the communication channel. We can correct maximum errors of BCH codes computationally by changing the designed distance in the input algorithm because the minimum distance is always greater than or equal to designed distance. Our proposed algorithm gives the faster output of Barlekamp Massey algorithm. It is a convenient technique to use for encoding and decoding the messages. This novel approach gives us generator polynomial of BCH codes over Galois ring of each degree as desired without human effort which can be used for the security of data. With the proposed computational technique, construction of generator polynomial of BCH code also gives the dimension of the code, so another goal is achieved. We modified the AES algorithm using the BCH codes which gives better results of image encryption scheme and enhance the security level. Hence, with the help of different tests, it is concluded that our proposed scheme gives better image encryption results as compared to the original AES algorithm. In future we can use this scheme for video, audio and text encryption and Security can be increased by BCH codes if we use different MDS (maximum distance separable) matrices which are constructed over BCH codes for each round in mixed column operation step of AES-C algorithm. This will create more diffusion in the proposed algorithm.

References

Ian

, Blake, Codes over certain rings, Information and Control 20(4) (1972), 396–404.

Ian

, Blake, Codes over integer residue rings, Information and Control 29(4) (1975), 295–300.

Spiegel

, Codes over

ℤ_{m}

, Information and Control 35(1) (1977), 48–51.

Spiegel

, Codes over

ℤ_{m}

, revisited, Information and Control 37(1) (1978), 100–104.

Shankar

, On BCH codes over arbitrary integer rings (Corresp.), IEEE Transactions on Information Theory 25(4) (1979), 480–483.

Interlando, Carmelo

, Palazzo

and Elia

, On the decoding of Reed-Solomon and BCH codes over integer residue rings, IEEE ransactions on Information Theory 43(3) (1997), 1013–1021.

Shah , Tariq , et al., Maximal cyclic subgroups of the groups of units of Galois rings: A computational approach, Computational and Applied Mathematics 36(3) (2017), 1273–1297.

De Andrade , Aparecido

and Palazzo

Jr . Construction and decoding of BCH codes over finite commutative rings, Linear Algebra and Its Applications 286(1-3) (1999), 69–85.

de Andrade , Aparecido

, Shah

and Khan

, A note on linear codes over semigroup rings, Trends in Applied and Computational Mathematics 12(2) (2011), 79–89.

10.

Ansari , Shaheen

Asma

and Shah

, An association between primitive and non-primitive BCH codes using monoid rings, EURASIP Journal on Wireless Communications and Networking 2016(1) (2016), 38.

11.

Cazaran

, et al., An algorithm for computing the minimum distances of extensions of BCH codes embedded in semigroup rings, Semigroup Forum 73(3) (2006). Springer-Verlag.

12.

Kelarev

Andrei V.

, Ring constructions and applications. 9 (2002), World Scientific.

13.

Kelarev

, An algorithm for BCH codes extended with finite state automata, Fundamenta Informaticae 84(1) (2008), 51–60.

14.

Kelarev

Andrei V.

, Algorithms for computing parameters of graph-based extensions of BCH codes, Journal of Discrete Algorithms 5(3) (2007), 553–563.

15.

Nagpaul

S.R.

, Topics in applied abstract algebra, American Mathematical Soc 15, 2005.

16.

Shah , Tariq and de Andrade

Antonio Aparecido

, A method for improving the code rate and error correction capability of a cyclic code, Computational and Applied Mathematics 32(2) (2013), 261–274.

17.

Shah , Tariq and de Andrade

Antonio Aparecido

, Cyclic codes through

B [X; \frac{a}{b} Z_{⩾ 0}] (\frac{a}{b} \in Q^{+}, b = a + 1

) and Encoding, Discrete Mathematics, Algorithms and Applications 4(04) (2012), 1250059.

18.

Shah , Tariq and de Andrade

Antonio Aparecido

, A decoding procedure which improves code rate and error corrections, Journal of Advanced Research in Applied Mathematics (2012), 37–50.

19.

Shah , Tariq , Khan

and Andrade

A.A.

, Encoding through generalized polynomial codes, Computational & Applied Mathematics 30(2) (2011), 349–366.

20.

Ding , Cunsheng and Zhou

, Binary cyclic codes from explicit polynomials over GF (2m), Discrete Mathematics 321 (2014), 76–89.

21.

Ding , Cunsheng , Fan

and Zhou

, The dimension and minimum distance of two classes of primitive BCH codes, Finite Fields and Their Applications 45 (2017), 237–263.

22.

Lone , Cunsheng , Rasheed

Faisal

, Puri

and Kumar

, Performance comparison of reed solomon code and BCH code over rayleigh fading channel, arXiv preprint arXiv:1307.6930 (2013).

00010000	00077707	77001101	23221100	74112366	30207377	40253060	74015363
60360307	25761252	73701512	23002510	00456500	65477343	10537441	63617535
14433427	27140145	60211574	37717767	45505017	17357330	63017453	13471407
00014641	46407707	35250240	52246663	17535264	42157635	30456173	36024343
12333006	25261355	74406562	72725440	63450416	23421043	73320346	11764356
31402112	75151740	23753673	11342013	16430354	74270745	14700561	70260410
15001262	04057300	77473703	41616241	25115627	37204277	10363160	20276252
40115161	15172777	11027471	62565506	75317032	04415257	56563347	60460432
26100242	62335270	72404355	52075640	07574701	40464231	06372242	24326351
45401256	51050340	35626203	32265126	24345062	32577054	43361731	50153752
62745373	73067214	00733702	37106515	33654170	13322023	14332356	16541155
02166634	64031072	36537105	40275735	13543161	25556134	42754633	00650113
01305323	52675750	00016721	67207707	12160160	76270072	13030361	77234205
54014665	75502307	37754330	11251413	02530263	00710335	03450717	04237043
74623165	46511226	50326137	14326656	51552256	54231233	41026165	24122506
07173276	33770271	54207611	25631460	75125025	64556176	07000733	00440100
01400444	03774740	44272611	66743561	51307614	20000750	65306000	05207350
76616360	76332127	34233755	00440165	01250444	03141263	17233174	21502665
03671730	14203621	21335460	31010455	50134607	71237575	05574465	47444431
01424544	44752546	65560713	24137532	57422175	55705746	05324310	46163156
77215472	66706067	04323210	36273256	01274361	42377061	32552751	72353133
40711153	55234717	75556065	74567633	03346632	63501154	30745530	22152414
00440173	01330444	03052455	21253003	15337263	64501055	36645430	23403624
11152540	13111273	06265477	56710462	31443117	05165344	56601572	42665220
14620022	73767226	00164712	47031272	57401605	42027140	33642406	76413124
44114147	01312377	22324657	22601456	70360620	17070252	72540201	11260234
70737162	02007515	73730600	14737215	65575115	76146431	77564674	50426332
16245646	47321664	53007756	27533500	14216635	51464367	75441142	25451744
70165643	67442272	45632544	64563025	56367632	23532452	07376235	63146251
01315174	50374657	71551151	21067233	57040102	35477504	45442441	63744744
66467114	15140442	76502774	32514230	15107537	67416370	06645047	52076624
17334701	37541655	64654534	63357723	16602053	11071220	00000001

BCH Codes with computational approach and its applications in image encryption

Abstract

Keywords

1 Introduction

2 Maximal cyclic subgroup of the group of units of Galois ring

2.1 Unit elements

2.2 Local ring

2.3 Zero divisors

2.4 Basic irreducible polynomial

2.5 Galois ring and Galois field

2.6 Theorem

2.7 Example

3 Encoding of BCH codes over Galois ring

3.3 Transmission of message

4.1 Remark

Table 3 BM Algorithm μ σ μ (x) d μ l μ μ - l μ –1 1 1 0 –1 0 1 S 1 0 0 1 2 · · · 2t

Table 4 BM Algorithm μ σ μ (x) d μ l μ μ - l μ –1 1 1 0 –1 0 1 α 2 0 0 1 1 + α2x 0 1 0 2 1 + α2x 0 1 1

5.1 Construction of round keys by using BCH codes

5.2 Construction of mixed column matrix using BCH Code

6 Statistical analyses of image encryption

6.1 Contrast

6.2 Correlation

6.3 Energy

6.4 Homogeneity

6.5 Entropy

6.6 Application of BCH Code in image encryption

6.8 Histogram analyses

References

Table 3
BM Algorithm

μ σ^μ (x) d _μ l _μ μ - l_μ

–1 1 1 0 –1

0 1 S ₁ 0 0

1

2

·

·

·

2t

Table 4
BM Algorithm

μ σ^μ (x) d _μ l _μ μ - l_μ

–1 1 1 0 –1

0 1 α ² 0 0

1 1 + α²x 0 1 0

2 1 + α²x 0 1 1