Asymmetric Key Cryptosystem for Image Encryption by Elliptic Curve over Galois Field

1  Introduction

Communication technology, multimedia data technology, and Internet protocol communication via wireless networks have experienced rapid growth in this decade. However, the transmission of sensitive information over an open wireless network like the internet poses a security risk. Therefore, it is crucial to develop new methods that can guarantee the confidentiality of sensitive information transmitted over such networks. It takes a variety of encryption methods, including substitution box (S-box) and chaotic maps in all three dimensions, to protect the security of data being transmitted via communication channels. The three main techniques for securing information—steganography, watermarking, and encryption—are used to hide data from unauthorized readers. Additionally, there are two categories of key cryptosystems in cryptography: symmetric (also known as a private key) and asymmetric (also known as the public key). One key is used in a symmetric key cryptosystem to perform both encryption and decryption. The private key used by each user in an asymmetric cryptosystem, in contrast, is distinct from the private key used by the other user. In recent years, digital information technology and multimedia data have rapidly evolved, and security has become a crucial factor in sharing confidential information. Utilising standard-based cryptosystems and using photos as a base is one trustworthy way to accomplish this. Images are frequently employed for ordinary or unique actions in personal, institutional, military, medical, and other contexts where they are required. Hence, to prevent cyber-attacks, the images should be protected from attackers [1]. Several algorithms have been developed to guarantee secure image transmission, including the image encryption scheme based on the two-dimensional (2D) Salomon map, a two-dimensional hyperchaotic system using optimization benchmark functions, and the 2D eπ-map which is a 2D chaotic map based on Euler and Pi numbers [2–5] by Erkan et al. Moreover, various algorithms have been proposed for encrypting and decrypting digital audios and images [6–9] by Gao et al. In these algorithms, the sender converts the original data to an enciphered data before transmitting it to the other user over the internet (receiver) and the receiver decrypts the ciphered data and restores it to its original state. Also, ECC was suggested separately by [10,11] as an example of an effective public-key cryptography technique [12] because ECC has the advantages of small key size, fast computation, and better security [13]. Furthermore, ECC is promoted because the same security level is possible with shorter keys, less computation, and less memory usage. ECC’s 160-bit key is as a 1024-bit Rivest-Shamir-Adleman (RSA) key but provides ten times better speed when using a 128-bit key. Furthermore, ECC uses mathematical problems that are harder to solve than those used by RSA, making it more difficult for attackers to break the encryption. ECC is also simpler and uses smaller keys, which require less storage without sacrificing security. Binary extension fields have been suggested as an alternative to prime fields for ECC, which can reduce the amount of computation needed [14].

1.1 Related Work

The HC technique is one of the symmetric algorithms used to encrypt a picture in numerous researches because of its straightforward structure and speedy computations. In order to address the problem with the inverse key matrices, which are typically not available in HC algorithms, Acharya et al. [15] introduced the picture encryption utilising an advanced HC approach, obviating the need for the receiver to compute the inverse key. With the aid of interlacing and iterations, Acharya et al. [16] enhanced the original HC by adding an unconscious key. However, because the solution was limited to one grayscale image, the analysis was faulty and the outcome was unreliable. In order to increase the security of the original HC technique, Hamissa et al. [17] proposed a unique encoder-decoder approach for picture encryption employing logistic map due functions. To increase the entropy of the encrypted image, researchers developed a system with three phases, including the HC. First, the two original images’ pixel values are transformed to eight binary bits each, after which some fixed k bits are rotated and inverted. The lower nibbles of the image’s pixels are then switched. The pixel values are then subjected to the HC method [18]. The ciphertext’s numerical values are converted into points on the ECC via scalar multiplication using the HC algorithm, which is also utilised to produce another innovative encryption method. This strategy increases security while lengthening computation time [19]. The HC was further improved by Mahmoud et al. [20] to defend against assaults utilising statistics, brute force, and plaintext ciphertext. Later, Sun et al. [21] combined the contourlet-based steganography technique with the HC in their proposed picture encryption technology. Simultaneously, Naveenkumar et al. [22] offered a hybrid of Chaos and HC-based picture encryption that incorporates permutation and diffusion techniques as a different option to the traditional HC algorithm. Additionally, Sazaki et al. [23] integrated the advanced HC with the affine transform. The method used in [23] is slightly updated in [24] by Goutham et al. with regard to the 128-bit key utilised. Due to the fact that the HC uses the same key for both encoding and decoding, it offers a low level of security. To fix this weakness, Hamissa et al. [17] introduced a revolutionary image encryption algorithm called Elliptic Curve Cryptosystem with Hill Cipher (ECCHC). This combination method results in the asymmetry of the ECCHC method. A binary extension field-based ECC system was subsequently proposed by Rabah [14] as a result. In this article, the fundamental EC and Diffie-Hellman design concepts are discussed. According to Farwa et al. [25], the group rule stated over the rational points of an EC over the GF also provides remarkable benefits when applied to block ciphers for the byte replacement process. A specific EC over the GF(24) that has the same order as that of F24 is chosen for this. GF is used to handle large primes, which increases computational effort.

1.2 Motivation

The following are the primary justifications for suggesting this approach to boost the HC’s speed and effectiveness by combining it with the EC over the GF.

•   The fundamental flaw in the original HC technique was that it occasionally failed to recover plaintext since there was not a key matrix inverse because not all matrices could be inverted.

•   Because the encryption and decryption operations used the same key, the HC also had the drawback of offering insufficient security.

•   Agrawal et al. [19] suggested employing scalar multiplication to initially produce the ciphertext using numerical values before translating them into points on the ECC. Although the computing time was increased by this concept, the security level was increased.

•   Although ECC was a novel and effective method, using big primes to achieve the required results increases computation time and complicates the algorithm [25].

1.3 Our Contribution

In order to increase security and create a new approach that follows the idea presented in [12], we offered a novel idea for image encryption that combines ECC over GF and HC with a modification in the key matrix utilised for the encoding and decoding process. According to [25], it stands to reason that the issue of handling large primes in ECC should be approached from a different angle. By using prime power fields, particularly binary extension fields, and a few certain elliptic curves, we can boost complexity while requiring little additional computation, avoiding this problem. This motive is the driving force for the method presented in this paper, which produces the private and public keys using ECC over the binary extension field as opposed to a prime field. The secret key can then be generated by both the sender and the receiver without being shared online or over an unsecured communication route. One of the critical problems in the HC method is that the inverse of the key matrix does not always exist. The decryption procedure will therefore fail and the receiver will not be able to recover the original data if the key matrix is not invertible. This method solves the issue of locating the inverse of the key matrix for decryption even though it uses the XOR operation because the same key matrix is utilised for both encryption and decryption. Additionally, the algorithm is strengthened against different cryptographic attacks by using the inverse function of the appropriate GF. The proposed scheme is presented in Section 3 of the remaining work, which also discusses the building of the Galois field, EC over the GF, and the original HC algorithm. We assessed the suggested algorithm performance indices in Section 4 and contrasted them to other existing S-boxes. Moreover, Section 4 provides an illustration of the suggested approach. The final segment will cover the conclusion.

2  Preliminaries

This section will discuss some basic definitions and concepts regarding EC and HC.

2.1 Elliptic Curve over a Finite Field

An EC over a field Fp (which is a prime field, and here p is a large prime), is defined by the Weierstrass equation

E: y2=x3+Ax+B, (mod p)(1)

where A,B∈Fp and 4A3+27B2≠0(mod p). Points of an EC over a finite field make a finite additive group that satisfies the property of an abelian group. All of the points that satisfy the EC and the infinity point O make an elliptic curve group [26,27].

2.1.1 Point Addition

Let P′(x1,y1) and Q′(x2,y2) be two points of the above EC satisfying its equation, then the addition of these two points P′+Q′=R′(x3,y3) can be defined as

x3=t2−x1−x2 (mod p)

y3=t(x1−x3)−y1 (mod p)

where  t=y2−y1x2−x1 (mod p).

2.1.2 Point Doubling

Let P′(x1,y1) be a point on E (Fp) satisfying its equation, then P′+P′=2P′(x2,y2) can be calculated as follows:

x2=t2−2x1 (mod p)

y2=t(x1−x2)−y1 (mod p)

where  t=3x1+C2y1 (mod p).

2.2 Galois Field

The binary field F2n is described as F2[X]⟨f(X)⟩ where ⟨f(X)⟩ would be a maximal ideal of F2[X] such that an irreducible polynomial f(X) having degree n generates it. As for GF F24, the irreducible primitive polynomial is given as f(X)=x4+x+1. Elements of F24 form a cyclic group G under multiplication with order 15. Each element of this group is represented as a power of α that is a primitive element, just like α2=0100.

2.3 Elliptic Curve over F24

EC over the binary extension field is of the form

y2+xy=x3+Ax2+B(2)

where A,B∈F2n, and B≠0. Here, we take a special curve

E: y2+xy=x3+α4x2+1(3)

This curve has unique characteristics because of its rational points. The above curve has total 15 points including a point at infinity.

2.4 Group Law

An EC makes an additive group that adds points using group law [28]. Here, we discuss only the point doubling and the point addition laws for the EC over the GF.

2.4.1 Point Doubling

Let P′(xP′,yP′)  be the point lying on the curve  y2+xy=x3+Ax2+B over F2n, then by point doubling operation, we get 2P with coordinates.

x2P′=s2+s+A

y2P′=xP′2+(s+1)x2P′

where s=xP′+yP′xP′ is the slope of a line which is a tangent over P′. This operation is very useful in point multiplication as 9P′=2(2(P′+P′))+P′.

2.4.2 Point Addition

Let P′(xP′,yP′)  and Q′(xQ′,yQ′)  be two distinct points. The coordinates of P′+Q′ are given by

xP′+Q′=S2+S+xP′+xQ′+A

yP′+Q′=S(xP′+xP′+Q′)+xP′+Q′+yP′

where S=yP′+yQ′xP′+xQ′, is the slope of a line that passes through the given two points.

2.5 Hill Cipher

The symmetric block cipher algorithm known as the HC was created by Lester Hill in 1929 [29]. Both the sender and the receiver use the same key matrix for ciphering and decoding. The fundamental idea is to give each letter a numerical value, such as a = 0, b = 1, …, z = 25. Depending on the size of the key matrix having order m×m, the plaintext should then be divided into blocks of the same size  m. If m=2 then the plaintext block (P2×1) will have a size 2 and the key matrix (k2×2) will have order 2×2. The encryption process ends by producing a ciphertext block with the following two values (C2×1) [11].

2.5.1 Encryption

If  P=[a1a2] and K=[k11k12k21k22], then

C=[b1b2]=[k11k12k21k22][a1a2] mod 26

=[(k11p1+k12p2)mod 26(k21p1+k22p2)mod26]

2.5.2 Decryption

For decryption, the receiver must find K−1 such that  K− 1⋅K=I  where I is the 2×2 identity matrix [27]. So, decryption can be done as given

 P=K−1⋅C mod 26

3  Proposed Algorithm

This section provides a novel proposed technique that combines EC over the GF with HC, which is more efficient and secure than the original HC method. This technique has the important benefit of avoiding the difficult calculations involved in matrix multiplication using XOR which speeds up decryption computations by removing the need to compute the inverse of the key matrix. Additionally, employing GF operations expedites the procedure and strengthens the suggested scheme. Let us assume that the sender (a) chooses to use this approach to send an image to the recipient (b) across an insecure channel. First, they should agree on the EC function E, and then the domain parameters {A,B,n,G} should be shared by the two users where A,B are the EC coefficients and n  is the power of binary extension field GF(2n) such that n cannot be greater than the number of bits of the highest image pixel value, and G is the generator point. Then, each partner must choose his private key randomly from a given interval [1, 2n−1], say na the private key of the sender (a) and nb the recipient (b), after which they compute their public keys in the way shown below.

3.1 Key Generation

The Public key for a is Pa=na⋅G and Pb=nb⋅G for b. To get the initial key Km, each user gets a product of their private key with the public key of the other user.

Km=na⋅Pb=nb⋅Pa=na⋅nb⋅G=(x,y)

Then it evaluates

K1=x⋅G=(k11′,k12′)

K2=y⋅G=(k21′,k22′)

The above values generate the initial key matrix that is given as

K=[k11′k12′k21′k22′]

The sender and the receiver then work together to construct the key matrix. Subsequently, an encrypted message cannot be decoded by the recipient because it is not always possible to create an invertible key matrix. However, the inverse key matrix will not need to be evaluated because this suggested method uses the XOR for encryption and decryption. In this technique, the image will be divided into sixteen pixel-sized chunks, which are then converted into a matrix of size 4×4 whose entries are then transferred into the elements of GF(2n). Then it is computed with a key matrix KM of the same size which can be constructed using the initial key matrix as follows:

KM=[k11′k12′k21′k22′ k13′k14′k23′k24′k31′k32′k41′k42′k33′k34′k43′k44′]

over GF(2n) which is consist of 4 matrices of size 2×2 such that KM=[K11K12K21K22]. If  K11=K=[k11′k12′k21′k22′], then the others can be calculated as K12=K⋅K=K2, K21=K−1, and K22=(K2)−1. Hence KM is given by

KM=[KK2K−1(K2)−1]

over GF(2n).

3.2 Encryption

After dividing the values of image pixels into 16 size blocks that are transformed into the size of a 4×4 matrix which is (P1, P2,P2,…) with entries converted into the elements of GF(2n), each 4×4 matrix of plaintext (Image) is then multiplied by KM using XOR, producing a 4×4 matrix of ciphertext. This procedure may be described as

Ci=KM⊕Pi where i=1,2,3,…

For i=1

C1=KM⊕P1

C1=[k11′k12′k21′k22′ k13′k14′k23′k24′k31′k32′k41′k42′k33′k34′k43′k44′]⊕[a11a12a21a22 a13a14a23a24a31a32a41a42a33a34a43a44]=[b11b12b21b22 b13b14b23b24b31b32b41b42b33b34b43b44]

An inverse map is applied after assessing each 4×4 matrix of the plain picture,

φ:Ci→Ci

such that

φ(x)=x−1   ifx∈GF(2n)/{0}=x    if     x=0

Here, n  is the power of binary extension field GF(2n) such that n cannot be greater than the number of bits of the highest image pixel value. Moreover, the collected data is integrated into a single matrix that contains the ciphered information.

3.3 Decryption

The decryption procedure can start after the encrypted image has been received. Because we utilise XOR instead of matrix multiplication, we can skip computing the inverse key matrix. First, we arrange all of the 4×4 matrices of ciphered image (C1,C2,C3, …) and then use an inverse map

φ:Ci→Ci

such that

φ−1(x)=x−1   ifx∈GF(2n)/{0}=x     if  x=0

where n  is the power of binary extension field GF(2n) such that n cannot be greater than the number of bits of the highest image pixel value. Following that, we apply the XOR function to each matrix Ci with the key matrix KM to produce the 4×4 matrix below that contains the original image’s pixel values.

Pi=KM⊕Ci where i=1,2,3,…

For i=1

P1=KM⊕C1

P1=[k11′k12′k21′k22′ k13′k14′k23′k24′k31′k32′k41′k42′k33′k34′k43′k44′]⊕[b11b12b21b22 b13b14b23b24b31b32b41b42b33b34b43b44]=[a11a12a21a22 a13a14a23a24a31a32a41a42a33a34a43a44]

After evaluating Pi, they are combined into a single matrix to get the original image.

3.4 Proposed Technique Using ECC

3.4.1 Key Generation

User (a)

1.    Choose a private key na∈[1,2n−1]

2.    Calculate the public key Pa=na⋅G

3.    Evaluate initial key Km=na⋅Pb=na⋅nb⋅G=(x,y).

4.    Compute K1=x⋅G=(k11′,k12′) and K2=y⋅G=(k21′,k22′). 

5.    Here K=K11=[k11′k12′k21′k22′] is the initial key matrix, then K12=K2=[k13′k14′k23′k24′], K21=K−1=[k31′k32′k41′k42′], and K22=(K2)−1=[k33′k34′k43′k44′].

6.    Then finally, the key matrix of size 4×4 is generated as follows:

KM=[KK2K−1(K2)−1]=[k11′k12′k21′k22′ k13′k14′k23′k24′k31′k32′k41′k42′k33′k34′k43′k44′]

over GF(2n).

User (b).

1.    Select a private key nb∈[1,2n−1]

2.    Calculate the public key Pb=nb⋅G= 

3.    Evaluate initial key Km=nb⋅Pa=nb⋅na⋅G=(x,y).

4.    Compute K1=x⋅G=(k11′,k12′) and K2=y⋅G=(k21′,k22′). 

5.    Here K=K11=[k11′k12′k21′k22′]  is the initial key matrix, then K12=K2=[k13′k14′k23′k24′],  K21=K−1=[k31′k32′k41′k42′], and K22=(K2)−1=[k33′k34′k43′k44′]

6.    Then finally, the key matrix of size 4×4 is generated as given below

KM=[KK2K−1(K2)−1]=[k11′k12′k21′k22′ k13′k14′k23′k24′k31′k32′k41′k42′k33′k34′k43′k44′]

over GF(2n).

3.4.2 Encryption

1.    Divide 256×256  pixel values of the image into blocks of size 16 and convert them into the matrix of size 4×4(Pi). Entries of that matrix are then converted into elements of GF(2n) as

P1=[a11a12a21a22 a13a14a23a24a31a32a41a42a33a34a43a44]

2.    Apply the operation of XOR to each Pi with KM one by one to get the data in the form of

C1=KM⊕P1

C1=[k11′k12′k21′k22′ k13′k14′k23′k24′k31′k32′k41′k42′k33′k34′k43′k44′]⊕[a11a12a21a22 a13a14a23a24a31a32a41a42a33a34a43a44]

C1=[b11b12b21b22 b13b14b23b24b31b32b41b42b33b34b43b44]

3.    After obtaining C1, apply an inverse function under the GF(2n) to each entry of that matrix to get the matrix in the form of

C1′=[b11b12b21b22 b13b14b23b24b31b32b41b42b33b34b43b44]−1

4.    Similarly, apply the same technique to all of the 4×4 matrices of the plain image Pi to get the resultant 4×4 matrices Ci′ and combine them to get the ciphered image.

3.4.3 Decryption

1.    Separate 256×256  pixel values of the ciphered image into blocks of size 16 and convert them into the matrix of size 4×4(Ci′) whose entries are from GF(2n) as

C1′=[b11b12b21b22 b13b14b23b24b31b32b41b42b33b34b43b44]−1

2.    Apply an inverse function under GF(2n) to each entry of the matrix C1′ to get the matrix such that

C1=[b11b12b21b22 b13b14b23b24b31b32b41b42b33b34b43b44]

3.    Similarly, take all matrices of size 4×4(Ci′) and apply this technique to each matrix to get the data in the form of Ci.

4.    Apply XOR operation to each Ci with the key matrix KM one by one to get values of the form

P1=KM⊕C1

P1=[k11′k12′k21′k22′ k13′k14′k23′k24′k31′k32′k41′k42′k33′k34′k43′k44′]⊕[b11b12b21b22 b13b14b23b24b31b32b41b42b33b34b43b44]

 P1=[a11a12a21a22 a13a14a23a24a31a32a41a42a33a34a43a44]

5.    Finally, combine all of the matrices Pi of size 4×4 to get the required ciphered image of 256×256.

3.5 Example

Let a person (a) want to deliver an image M to the other person (b), and they both agree on the EC function given by

E: y2+xy=x3+α4x2+1

over GF(24), where A=α4 and B=1. Let us define the 15 elements of this field that can be expressed as a power of primitive root as well as binary form, as shown in Table 1.

For the chosen curve, we get a generator point G=(α3, α8),  all other points can be found using group law and can be expressed as a multiple of G(xG, yG). Let us calculate 2G(x2G, x2G).

s=xG+yGxG=α3+α8α3=α3+α5=α11,

x2G=s2+s+A

x2G=(α11)2+α11+α4

x2G=α5

y2G=xG2+(s+1)x2G

y2G=(α3)2+(α11+1)⋅α5

y2G=α3

2G=G6

All other points are given in Table 2.

As the generator point is G(α3, α8), other domain parameters are {A,B, 24−1,G}={α4,1,15,(α3, α8)}. If a person (a) desires to deliver an image of size 256×256 to person (b), they should use the proposed method.

3.5.1 Key Generation

User (a)

1.    Select a random value as a private key na=6∈[1,15]

2.    Calculate the public key Pa=na⋅G=6(α3, α8) 

3.    Evaluate initial key Km=na⋅Pb=na⋅nb⋅G=6.11(α3, α8)=6(α3, α8)=(α10, α)=(7,2)=(x,y)

4.    Compute  K1=x⋅G=7(α3, α8)=(α12, α12)=(k11,k12) and K2=y⋅G=2(α3, α8)=(α5, α3)=(k21,k22)

5.    Here K=K11=[α12α12α5α3] =[151568] is the initial key matrix, then K12=K2=[α11α7α0α3]=[141118],K21=K−1=[α10α4α12α4]=[73153] and K22=(K2)−1=[α2α6α14α10]=[41297]

6.    Then finally, the key matrix of size 4×4 is generated as follows:

KM=[α12α12α5α3α11α7α0α3α10α4α12α4α2α6α14α10]=[1515681411187315341297]

User (b)

1.    Select a private key nb=11∈[1,15]

2.    Calculate the public key Pb=nb⋅G=6(α3, α8) 

3.    Evaluate initial key Km=nb⋅Pa=nb⋅na⋅G=11.6(α3, α8)=6(α3, α8)=(α10, α)=(7,2)=(x,y)

4.    Compute  K1=x⋅G=7(α3, α8)=(α12, α12)=(k11,k12) and K2=y⋅G=2(α3, α8)=(α5, α3)=(k21,k22)

5.    Here K=K11=[α12α12α5α3]=[151568] is the initial key matrix, then K12=K2=[α11α7α0α3]=[141118],K21=K−1=[α10α4α12α4]=[73153] and K22=(K2)−1=[α2α6α14α10]=[41297]

6.    Then finally, the key matrix of size 4×4 is generated as follows:

KM=[α12α12α5α3α11α7α0α3α10α4α12α4α2α6α14α10]=[1515681411187315341297]

3.5.2 Encryption

1.    Choose an image of size 256×256  and divide the pixel values into blocks of size 16 and convert them into the matrix of size 4×4(Pi). Entries of that matrix then converted into elements of GF(28) As

P1=[165161163160157157158159161159159158158160157158]

2.    Apply the operation of XOR to P1 with KM to get the matrix of the form

C1=KM⊕P1

C1=[1515681411187315341297]⊕ [165161163160157157158159161159159158158160157158]=[170174165168147150159151166156144157154172148153]

3.    Likewise, apply the same procedure to each matrix Pi to get the matrices Ci.

4.    Apply an inverse function under the GF(28) to each element of the matrix C1 such that

 C1′=[170174165168147150159151166156144157154172148153]−1

C1′=[131941902061701241729791621592189155156220]

5.    Similarly, take all of the matrices Ci and apply an inverse function under the GF(28) to get all the 64 matrices Ci′ of size 4×4 and combined them to get the encrypted image of 256×256.

3.5.3 Decryption

1.    Separate 256×256  pixel values of the encrypted image into a block of size 16 and convert them into a matrix of size 4×4 (Ci′), whose entries are from GF(28). Firstly, we take the matrix C1′ such that