Text Encryption Using Pell Sequence and Elliptic Curves with Provable Security

Sumaira Azhar,Naveed Ahmed Azamand Umar Hayat

1Department of Mathematics,Quaid-i-Azam University,Islamabad,45320,Pakistan

2Department of Applied Mathematics and Physics,Graduate School of Informatics,Kyoto University,Kyoto,606-8501,Japan

Abstract:The demand for data security schemes has increased with the significant advancement in the field of computation and communication networks.We propose a novel three-step text encryption scheme that has provable security against computation attacks such as key attack and statistical attack.The proposed scheme is based on the Pell sequence and elliptic curves,where at the first step the plain text is diffused to get a meaningless plain text by applying a cyclic shift on the symbol set.In the second step, we hide the elements of the diffused plain text from the attackers.For this purpose, we use the Pell sequence, a weight function, and a binary sequence to encode each element of the diffused plain text into real numbers.The encoded diffused plain text is then confused by generating permutations over elliptic curves in the third step.We show that the proposed scheme has provable security against key sensitivity attack and statistical attacks.Furthermore,the proposed scheme is secure against key spacing attack,ciphertext only attack,and known-plaintext attack.Compared to some of the existing text encryption schemes,the proposed scheme is highly secure against modern cryptanalysis.

Keywords: Text encryption; pell numbers; elliptic curves; key sensitivity;statistical cryptanalysis

1 Introduction

There is a high demand for data security schemes due to the recent advancement in the fields of computation and communication technologies.Cryptography and steganography are the two main branches of data security schemes.Cryptography is the study of data security schemes where secret data is transformed into an unreadable data[1].Steganography is the study of data security schemes where secret data is embedded into host data so that the attackers cannot detect the existence of secret data[2].

Different data security schemes have been proposed based on different mathematical structures such as elliptic curves [3–9], algebraic structures [10–15], chaotic maps [16–21] and fuzzy set theory[22,23].Security and privacy of the text messages are major concerns of the users while communicating on popular messaging platforms such as WhatsApp and Signal.So, the security of the text messages gained great attention now a days.We briefly review some of the recent text encryption schemes.Abdullah et al.[23] proposed a cryptosystem based on fuzzy logic where triangular fuzzy numbers are used to represent plain text and ciphertext.Gupta et al.[24] proposed a data security algorithm based on logical and shifting operations.Pattanayak et al.[25]used linear congruences and extended Euclidean algorithm to design a text encryption scheme.By utilizing 8-bit code values of alphabets, Agrawal et al.[26] proposed an efficient algorithm for text encryption.Ghrare et al.[27]designed a hidden encrypted symmetric key algorithm by hiding the secret key inside the ciphertext.Linear recurrences such as generalized Fibonacci numbers, Pell numbers and Pell-Lucas numbers have many applications in the field of mathematics and computer science [28–30].The schemes in[31–33] used linear recurrences for cryptography purpose.Luma et al.[31] explored a relationship between Fibonacci and Lucas sequence and used it for encryption and decryption purpose.Overmars et al.[32]proposed an efficient method to compute the golden ratio to avoid cryptographic breaches.Agarwal et al.[33]proposed a data encryption scheme based on Fibonacci numbers.Recently,DNA sequences are also used to generate secret keys for data security[34–36].Clelland et al.[34]combined a DNA based technique and the microdot to send messages secretly.Abbasy et al.[36] employed useful features of DNA sequences for data hiding.Chaotic maps are used to develop new security schemes due to their high sensitivity to the initial condition [37–42].Murillo-Escobar et al.[37]proposed a new text encryption scheme based on a logistic map.Similarly,elliptic curves(ECs)received great attention in the field of cryptography for image encryption [43–47], text encryption [48–53]and signcryption[54–56]due to comparable security against modern cryptanalysis with low key size.Sunneetha et al.[48] proposed a secure algorithm using elliptic curves and algebraic operations to transmit messages.Naji et al.[49]proposed a novel text encryption scheme by representing characters of the plain text with the affine points on an EC.Agrawal et al.[50] designed a text encryption method using ECC and Hill cipher with better security and complexity.Keerthi et al.[51]proposed a novel text encryption scheme where the hexadecimal form of the ASCII values of plain text are mapped to affine points of an ECs.Kumar et al.[52] used paired ASCII values corresponding to the plain text as an input for the elliptic curve.Singh and Singh developed an algorithm that can be used for encryption and decryption of any size of text message with given ASCII values.Ullah et al.[54]provided a critical review of hyper elliptic curves based signcryption algorithms.A hyper elliptic curve based signcryption scheme more suitable for emerging resource constraints environment is proposed by Ullah et al.[56].

Most of the text encryption schemes available in the literature such as the schemes presented in[23–27,33,34,36,37,48–51,53]are not secure against well know attacks including key spacing,key sensitivity,statistical attack,ciphertext only attack and known-plaintext attack.The aim of this paper is to propose a novel text encryption scheme that has high security against modern cryptanalysis including key spacing, key sensitivity, statistical attack, ciphertext only attack and known-plaintext attack as compared to the existing text encryption schemes[23–27,33,34,36,37,48–51,53].The proposed scheme is based on the Pell sequence and elliptic curves and has three main steps,where we first diffuse the plain text.Then an encoding procedure is applied to the diffused plain text based on the Pell sequence in step 2.Finally,the encoded diffused plain text is confusedin step 3 based on ECs.The rest of the paper is organized as follows.Section 2 contains some preliminaries.We discuss a novel text encryption scheme in Section 3.Security analysis and a detailed comparison of the proposed scheme with the existing text encryption schemes[23–27,33,34,36,37,48–51,53]is discussed in Section 4.A conclusion is drawn in Section 5.

2 Preliminaries

2.1 Pell Sequence

For initial valuesP0= 0 andP1= 1, then-th termPnof the Pell sequence is defined with the recurrence relation

The first six terms of the Pell sequence are 0,1,2,5,12,and 29.By[30]it is known that fori→∞it holds that

2.2 Elliptic Curves(EC)

For a finite prime field Fpwith characteristic other than 2 and 3,primepand two integersa,b∈[0,p-1]such that 4a3+27b20(modp),the short Weiestrass form elliptic curveEp,a,bover the field Fpis the set

whereδis the identity element of the EC.We call the integersp,aandbthe parameters of the ECEp,a,b.

By [57], whena= 0 andp≡ 2(mod 3), the ECEp,a,bhas exactlyp+ 1 points with no repetition in their y-coordinates.Azam et al.[4]defined three orderings on an ECEp,a,bthat have good cryptographic properties.These orderings are natural ordering N,diffusion ordering D,and modulo diffusion ordering M such for any two points(x,y)and(x′,y′)on an ECEp,0,bit holds that

The key features of these orderings are:(i)they diffuse the y-coordinates of the ordered EC;and(ii)the ordered ECs generated by these orderings are highly uncorrelated.Furthermore,it can be observed from Fig.1 that the three orderings are non-equivalent and are capable of generating randomness.Due to these properties,Azam et al.[4,5]showed that these orderings are cryptographically suitable for generating a large number of secure permutations over ECs.

Figure 1:EC E29,0,1 and the effect of the natural,diffusion and modulo ordering on the EC E29,0,1:(a)Points of the EC E29,0,1 are shown w.r.t.non-decreasing x-coordinate from left to right;(b)y-coordinates of the points of the ordered EC E29,0,1 with natural ordering; (c) y-coordinates of the points of the ordered EC E29,0,1 with diffusion ordering;(d)y-coordinates of the points of the ordered EC E29,0,1 with modulo ordering

3 The Proposed Scheme

For an encryption scheme,it is essential to diffuse and confuse the plain text up to a certain level[2].Therefore,our scheme consists of three main steps where we first diffuse the plain text followed by an encoding procedure and then create confusion in the encoded diffused plain text.The diffusion step is performed by permuting the symbol set of the plain text.We use a restricted Pell sequence,a weight function,and a binary sequence to encode each element and its position in the diffused plain text with real numbers.Due to the sensitivity of the ECs over its parameters,we generate permutations over ECs to create confusion in the encoded diffused plain text.We discuss these three steps in detail below.

LetSbe a finite symbol set of sizem,and fori∈[0,m-1],letS(i)denote thei-th element ofS.Suppose that the sender wants to send the plain textT=T(1)···T(i)···T(n)of lengthnwhich is a sequence overSwhereT(i),i∈[1,n]denotes thei-th element ofTandT(i)∈S.In this scheme,we encode plain text to real numbers in the interval[-1, 1]with at mostβ≥14 digits after the decimal.

3.1 Encryption Procedure

Step 1.Diffuse plain text:We select an integerk∈[0,m-1]and permute the entries ofSby using the permutationψk:S→Sdefined as

i.e.,ψkmaps thei-th entry ofSon its(i+k) (modm)-th entry.Now generate a diffused plain textT′=T′(1)···T′(i)···T′(n)by using the permutationψksuch that thei-th elementT′(i)=ψk(T(i),i∈[1,n].The diffusion step is similar to the Caesar cipher[58].

Step 2.Encode diffused plain text:To encode the elements of the diffused plain textT′,we generate a restricted Pell sequence,a weight function,and a binary sequence as follows.

Select two positive integershandh′such thath ＜h′andh′-h+1 ≤β,and generate the restricted Pell sequenceQh,h′=q1···qi···qm,if it exists,such that for each integeri∈[1,m]the following hold:

-qi= log(Pi/Pi-1)andqihas exactlyh′-h+1 digits fromh-th digit toh′-th digit after the decimal,wherePiis thei-th entry of the Pell sequence,and

- all entries ofQh,h′are distinct, i.e., for any two distincti,j∈[1,m], it holds thatqiqj.We apply this condition so that each symbol in the diffused plain text can be encoded uniquely.

Observe that the entries of the restricted Pell sequenceQh,h′are in the closed interval[0, 1]sincePi/Pi-1→1+(2)1/2asi→∞by[30].We added the constrainth′-h+1 ≤βto generate a restricted Pell sequence to control the length of the ciphertext and increase the key size,since for a fixed integerτ,there exists different pairsh,h′such thath′-h+1=τ,and hence different restricted Pell sequences.

Generate aweight function w: {1,2,···,n} →[-1, 1] which is an injection, i.e., for any twoi,j∈ {1,2,···,n} such thatij, it holds thatw(i)w(j).The aim of this weight function is to uniquely encode the position of each element ofT′.

Generate abinary sequence α=α1···αi···αn.Based on thei-th entryαiofα, decide if we use weightw(i)withqjorqj-1,j∈[1,n]during the encoding procedure.

Now,generate an encoded diffused plain text(C,D)=(c1,d1)···(ci,di)···(cn,dn)such that thei-th elementT′(i)ofT′is encoded(ci,di)as with

whereT(i)=S(j),for somej∈[1,m]andT′(i)=ψk(S(j))=S((j+k)(modm)).

3.2 Ciphertext

Transmit the confused sequenceσ(C)as a ciphertext of the plain textT.

3.3 Secret Keys

The integersh,h′andk,the weight functionwand the encoded sequenceσ′(D)are the secret keys of our encryption scheme.The integersh,h′andkare used to get the representation of symbols inS,the weight functionwis used to get the index of the symbols in the plain text,and the sequenceσ′(D)is used to getw.

Note that for a givenβ,the proposed scheme can encrypt a plain text over a symbol setSwith size at most |Qh=1,h′=β|, i.e., for the proposed scheme it holds thatm≤|Qh=1,h′=β|.Furthermore, the proposed scheme can encrypt a plain textTof any arbitrary size,since it encodes each symbol ofTindividually.

3.4 Decryption Procedure

Assume that the channel between sender and receiver is noiseless, and therefore the receiver receives the ciphertextG=σ(c1)σ(c2)···σ(cn).Letgbe thel-th element ofG.We find the position ofgin the plain text by using the keysσ′(D)=σ′(d1)σ′(d2)···σ′(dn)and weight function as follows.Compute a reald∈σ′(D)such that

for somer=w(i)∈[-1,1] withi∈[1,n].Observe that for eachgsuch a realdalways exists by Eq.(7).The integeriis the position of the element of the plain text corresponding to the elementgof the ciphertext.By using the secret keyh,compute the restricted Pell sequenceQh,h′and compute the inverse→Sdefined as

of the permutation by using the secret keyk.To get the plain textT(i)at thei-th position of the plain textT,find the realqt∈Qh,h′such thatg=qt or d=1-qtfor some indext.Find the indextby using Tab.1,and finally get thei-th plain textT(i)asT(i)=corresponding to thel-th elementgofG.

By repeating the above procedure for eachg∈G,we get the plain textT.The proposed encryption and decryption scheme is illustrated in Fig.2.

Figure 2:Flowchart of the proposed encryption and decryption scheme

We demonstrate our proposed encryption and decryption procedures in detail in Example 1.

3.5 Example 1

3.5.1 Encryption

Let the ordered symbol setSbe the set of the capital English alphabet including blank-space and full-stop.This set is listed in the fourth column of Tab.1.Letβ=14,and forh=18 andh′=22,the entriesqiof the restricted Pell sequenceQh,h′are listed in the second column of Tab.1,while the third column of Tab.1 contains 1-qi.Select integerk= 6 to generate a permutationψk=6on the symbol setS.The entries ofψk=6are listed in the fifth column of Tab.1.

Table 1:Entries S(i),ψk=6(S(i)),and qi of an ordered symbol set S,the permuted symbol set ψk=6(S),and the restricted pell sequence Qh =18, h′=22,respectively

Suppose the sender wants to send the plain text T=STAY SAFE with nine elements.For each integeri∈[1,9],thei-th elementT(i)of the plain textT,thei-th elementT′(i)of the diffused plain text,weight valuew(i),binary valueαiandi-th element(ci,di)of the encoded plain text are listed in Tab.2.

Table 2:Entries T(i), T′(i), w(i), αi and(ci,di)of a plain text T,diffused plain text T′,weight function w,binary sequence αi,and encoded diffused plain text(C,D),respectively

To permute the encoded diffused plain text,we generated the ordered ECsE11,0,9andE11,0,4using natural and diffusion orderings respectively.The sequencesHandH′generated by these ordered ECs are listed in Tab.3.

Table 3: Permutations due to the ordered ECs E11,0,9 and E11,0,4 with natural and diffusion ordering,respectively

The confused encoded plain textσ(C)andσ′(D)are listed in Tab.4.

Table 4: Entries of σ(ci)and σ′(di)of the confused plain text σ(C)and σ′(D),respectively

Table 4:Continued

3.5.2 Decryption

We demonstrate the decryption procedure for the 5-th element g =σ(c5)= 0.45662 of the ciphertext G.Note thatg+d=r+ 1 holds ford=σ(d2)= 0.70638,r=w(i)= 0.163 withi= 6.This implies thatgis the(i=6)-th element of the plain text.The realqtfor which it holds thatg= 1-qthas indext= 3 in the third columnQh=18,h′=22of Tab.1.We get the(i=6)-th element=Sof the plain textTfrom the fourth column of Tab.1.

4 Security Analysis and Comparison

To analyze the security of the proposed scheme,we apply some well-known security tests including key spacing analysis,key sensitivity analysis,histogram test,information entropy analysis,ciphertext only attack and known-plaintext attack.We briefly explain these tests and their results for the proposed scheme in Sections 4.1–4.5.Furthermore,we give a detailed comparison of the security of the proposed scheme and some of the existing text encryption schemes in Section 4.6.

4.1 Key Spacing Analysis

Brute-force attack is commonly used by cryptanalysts to decrypt ciphertext.Key spacing analysis is used to analyze the security of an encryption scheme against brute-force attack.For an encryption scheme, key spacing is defined to be the number of distinct secret keys that it can generate.An encryption scheme is secure if its key spacing is at least 2100by [59].The proposed scheme has five secret keys, three integersk,h, andh′, a weight functionwand the sequenceσ′(D), where the keyσ′(D)depends onm,h,h′,k, andw, by Eq.(7).There aremchoices forkand(10β)nchoices forw,when the plain text is encoded to real numbers with at mostβ≥14 digits after the decimal andnis the size of the plain text.This implies that the key spacing of the proposed scheme is at leastm(10β)n ＞2100forn≥4,m≥1 andβ≥14.This implies that the proposed scheme satisfies key spacing analysis.In particular,when computation accuracy is 10-14,m= 5,β= 14 andn≥4,then there are 88 choices for selecting a pair of integershandh′such thath′-h+1 ≤βand there exists a restricted Pell sequence.This implies that the key spacing of the proposed scheme in this case is at least 5·88·(1014)4＞2194.

4.2 Key Sensitivity Analysis

An encryption scheme is secure if it can generate a significantly different ciphertext for the same plaintext when the secret keys are slightly changed.In the next lemma,we show that for any plain text our scheme can generate a different ciphertext when any of the secret keysk,h,h′,andwis changed.

Lemma 1.LetTbe a plain text of sizenover symbol setSof sizemandG=σ(c1)σ(c2)...σ(cn)be a ciphertext ofTthat is obtained by the proposed scheme using the secret keysk,h,h′and weight functionw.

(i) The ciphertextG′generated by the proposed scheme by usingk′/k,k′∈[0,m-1],h,h′,andwis not equal toG.

(ii) The ciphertextG′generated by the proposed scheme by usingk,th or t′h′that satisfies conditions of step 2,andwis not equal toG.

(iii) Ifαi= 1,i∈[1,n],the ciphertextG′generated by the proposed scheme by usingk,h,h′,andw′such thatw′(i)w(i),for alli∈[1,n],is not equal toG.

Proof.Let

By Lemma 1, our scheme is highly sensitive to the secret keysk,h,h′, andw.We demonstrate Lemma 1 with an example by generating ciphertexts for the plain textT=STAY SAFE by slightly changing one key and fixing all other keys.The ciphertext fork= 6,h= 18,h′= 22, and weight functionwlisted in Tab.2,ordered MECE11,0,4with diffusion ordering is listed in the first column of Tab.5.The ciphertext generated by only changing the integerkto 7 following Lemma 1(i) is listed in the third column of Tab.5.The ciphertext generated by only changing integerh′to 23 following Lemma 1(ii)listed in the second column of Tab.5.The ciphertext generated by only changing weight function tow′(i)=w(i)+10-4following Lemma 1(iii) is listed in the fourth column of Tab.5.The ciphertext generated by only changing ECE11,0,5parameterbto 5 with diffusion ordering is listed in the fifth column of Tab.5.From Tab.5 it is evident that the ciphertext generated by slight changes in the secret keys are totally different.Hence,the proposed scheme satisfies the key sensitivity analysis.

Table 5: Different ciphertexts generated by the proposed scheme for a fixed plain text

Table 5:Continued

4.3 Statistical Analysis

An encryption scheme is highly secure against statistical attacks if it can generate a highly random ciphertext.Histogram analysis and entropy analysis are the two commonly used tests to analyze the security of a scheme against statistical attacks.A scheme is secure against statistical attacks if it can generate ciphertexts with uniform histogram and optimal entropy.

LetXbe a data set over a symbol setΩand forω∈Ω,f(ω)denotes the frequency ofwinX.The entropyH(X)ofXis defined to be

In the following result,we show that for each plain text,our scheme can generate a ciphertext with a uniform histogram and optimal entropy.

Lemma 2.For any plaint text,there exists at least one weight function w such that the frequency of each element in the ciphertext generated by the proposed scheme is 1.

By Lemma 2, it follows that for each plain text, the proposed scheme can generate a ciphertext with uniform histogram and optimal entropy by using the weight functionwconstructed in Lemma 2 andαi=1 for eachi.Hence the proposed scheme has provable security against statistical attacks.We demonstrate the claim in Lemma 2 in Tab.6 by generating a ciphertext for the plain textT=STAY SAFE with secret keysk= 6,h= 18,h′= 22,ordered ECsE11,0,4with diffusion ordering and weight functionwlisted in Tab.6.

Table 6:A ciphertext generated by the proposed scheme with uniform histogram and optimal entropy

4.4 Ciphertext Only Attack

In ciphertext only attack, the cryptanalyst has access to some ciphertexts and try to get secret keys and hence the plain text.The cryptanalyst cannot reveal the plain text without the secret keys of the proposed scheme.Furthermore,there are at least 2100keys for a fixed plain text of size at least 4,as discussed in Section 4.1, and therefore the brute-force attack requires lots of time to decrypt the ciphertext without keys.Hence by[53]the proposed scheme is secure against ciphertext only attack.

4.5 Known-plaintext Attack

In this attack,the attacker knows a pair of plain text and ciphertext and tries to generate secret keys.In our scheme, the attacker tries to generateh,h′,k,wandσ(D′).The plain text consists of symbols inSand the ciphertext consists of real numbers with at mostβdigits after the decimal in our scheme,and therefore there is no relationship between the plain text and the keysh,h′,kandw.Recall thatw(i)∈[-1, 1],and therefore it is not necessary thath′-h+1 is at most the minimum number of digits after the decimal in the ciphertext.Thus, the attacker needs to try all possibilities forh,h′such thath′-h+1 ≤βand there exists a restricted Pell sequence of the size|S|,andkto know the representation of symbols inS,the weight functionwto know the index of the symbols in the plain text, andσ(D′)which depends on the latter keys.Furthermore, for a given plain text the proposed scheme can generate a completely different ciphertext when keys are changed,as discussed in Section 4.3.Hence the proposed scheme is highly secure against known-plaintext attack by[53].

4.6 Security Comparison

The proposed scheme has five secret keys,the three integersh,h′and k,the weight functionw,and the encoded sequenceσ′(D).The secret key depends onσ′(D)the choice ofh,h′,k,wand the plain text.The main purpose ofσ′(D)is to get the weight valuew(i), and hence the indexiwhenαi= 0.However, ifαi= 1 for alli, then the weightw(i)are in the ciphertext by Eq.(7), and therefore the keyσ′(D)is not necessary to get the weight function.More precisely,whenαi= 1 for alli,we solve Eq.(8)ford=1-qi,whereqi∈Qh,h′to getw.This implies that in the case ofαi=1 for alli,k,h,h′andware sufficient keys to decrypt a ciphertext.Note that these keys are independent of the plain text.Furthermore,the proposed scheme also satisfies the key spacing analysis,key sensitivity analysis,statistical analysis,ciphertext only attack and known-plaintext attack for the case ofαi=1 for allias discussed in Sections 4.1–4.5.

We compared the security strength of the proposed scheme whenαi= 1 for alli, the case where all secret keys are independent of the plain text, and the schemes in [23–27,33,34,36,37,48–51,53] against key spacing attack, key sensitivity attack, statistical attack, ciphertext only attack and known-plaintext attack in Tab.7.We write “No” (resp.“NA”) in the second, fifth and sixth columns of Tab.7 if the corresponding scheme is not secure(resp.the analysis of the scheme against key spacing attack,ciphertext only attack and known-plaintext attack is not available.)Similarly,we write “No” in the third and fourth columns of Tab.7 if the corresponding scheme does not have provable security against key sensitivity attack and statistical attack.From Tab.7 observe that the security of the schemes in [23–27,33,34,36,37,48–51,53] is suspected against key spacing attack, key sensitivity attack, statistical attack, ciphertext only attack and known-plaintext attack.Therefore from Sections 4.1–4.5,the proposed scheme is more secure against listed attacks as compared to the schemes[23–27,33,34,36,37,48–51,53].

Table 7: Security comparison of the proposed scheme with the existing schemes

The schemes in [49] and [53] do not have provable security against key sensitivity attack and statistical attack.By Sections 4.2 and 4.3,the proposed scheme has high security against key sensitivity and statistical attacks as compared to the security of the schemes in[49]and[53].

5 Conclusion

We proposed a secure text encryption scheme.The scheme has three main steps, where we first diffuse the plain text by permuting the symbol set to convert the plain text into a meaningless message.In the second step,the diffused plain text is encoded with real numbers based on the Pell sequence,a weight function,and a binary sequence to hide the diffused plain text.In the third step,the scheme creates confusion in the encoded diffused plain text by generating permutations over ECs.We analyzed the security of the proposed scheme against several modern attacks including key spacing attack,key sensitivity attack,statistical attacks,ciphertext only attack and known-plaintext attack.From the analysis it is clear that the proposed scheme has high resistance against modern attacks.Furthermore,we compared the security strength of the proposed scheme with the existing text encryption schemes in[23–27,33,34,36,37,48–51,53].It is evident from the comparison that the proposed scheme is more secure as compared to the existing scheme against modern cryptanalysis.

By this scheme,we gave an application of the Pell sequence and ordered ECs in cryptography.In this scheme, we used binary sequence and weight function, which can be generated by any available method.

An interesting future direction would be to generate binary sequence and weight function by using ordered EC and propose an encryption scheme that can provide provable confidentiality and integrity.

Funding Statement:This research is funded through JSPS KAKENHI Grant Number 18J23484,QAUURF 2015 and HEC project NRPU-7433.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.