|Computers, Materials & Continua |
Text Encryption Using Pell Sequence and Elliptic Curves with Provable Security
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
*Corresponding Author: Naveed Ahmed Azam. Email: email@example.com
Received: 17 September 2021; Accepted: 11 November 2021
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
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 . 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 .
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.  proposed a cryptosystem based on fuzzy logic where triangular fuzzy numbers are used to represent plain text and ciphertext. Gupta et al.  proposed a data security algorithm based on logical and shifting operations. Pattanayak et al.  used linear congruences and extended Euclidean algorithm to design a text encryption scheme. By utilizing 8-bit code values of alphabets, Agrawal et al.  proposed an efficient algorithm for text encryption. Ghrare et al.  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.  explored a relationship between Fibonacci and Lucas sequence and used it for encryption and decryption purpose. Overmars et al.  proposed an efficient method to compute the golden ratio to avoid cryptographic breaches. Agarwal et al.  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.  combined a DNA based technique and the microdot to send messages secretly. Abbasy et al.  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.  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.  proposed a secure algorithm using elliptic curves and algebraic operations to transmit messages. Naji et al.  proposed a novel text encryption scheme by representing characters of the plain text with the affine points on an EC. Agrawal et al.  designed a text encryption method using ECC and Hill cipher with better security and complexity. Keerthi et al.  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.  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.  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. .
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 instep 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.1 Pell Sequence
For initial values and , the -th term of 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  it is known that for
2.2 Elliptic Curves (EC)
For a finite prime field with characteristic other than 2 and 3, prime p and two integers such that , the short Weiestrass form elliptic curve over the field is the set
where is the identity element of the EC. We call the integers and b the parameters of the EC .
By , when and , the EC has exactly points with no repetition in their y-coordinates. Azam et al.  defined three orderings on an EC that have good cryptographic properties. These orderings are natural ordering N, diffusion ordering D, and modulo diffusion ordering M such for any two points and ( on an EC it 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.
3 The Proposed Scheme
For an encryption scheme, it is essential to diffuse and confuse the plain text up to a certain level . 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.
Let S be a finite symbol set of size m, and for , let denote the -th element of S. Suppose that the sender wants to send the plain text of length n which is a sequence over S where denotes the -th element of T and . In this scheme, we encode plain text to real numbers in the interval with at most digits after the decimal.
3.1 Encryption Procedure
Step 1. Diffuse plain text: We select an integer and permute the entries of S by using the permutation defined as
i.e., maps the -th entry of S on its -th entry. Now generate a diffused plain text by using the permutation such that the i-th element , ]. The diffusion step is similar to the Caesar cipher .
Step 2. Encode diffused plain text: To encode the elements of the diffused plain text , we generate a restricted Pell sequence, a weight function, and a binary sequence as follows.
Select two positive integers h and such that and , and generate the restricted Pell sequence , if it exists, such that for each integer the following hold:
- and has exactly digits from -th digit to -th digit after the decimal, where is the i-th entry of the Pell sequence, and
- all entries of are distinct, i.e., for any two distinct it holds that 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 sequence are in the closed interval since as by . We added the constraint 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 pairs such that , and hence different restricted Pell sequences.
Generate a weight function which is an injection, i.e., for any two such that it holds that . The aim of this weight function is to uniquely encode the position of each element of .
Generate a binary sequence . Based on the -th entry of , decide if we use weight with or , during the encoding procedure.
Now, generate an encoded diffused plain text such that the -th element of is encoded as with
where , for some and .
Step 3. Confuse encoded plain text: In this step, we create confusion in the encoded plain text . For this purpose, we generate two bijections and by using ordered subsets of two ECs. These ordered subsets are such that each integer in appears exactly once as y-coordinates of the points. The existence of such subsets is ensured by considering the ECs with and . Finally, the i-th entries of C and D are mapped on some entries of C and D whose indices are determined by the y-coordinates of the i-th points in the ordered sets. More precisely, select two primes with and , two integers and , and two orderings ≺ and . Compute the ordered subsets and ordered w.r.t. the orderings ≺ and , where for each it holds that and , respectively. From these ordered subsets, get the sequences and . Now, generate a confused encoded plain text by using the permutations and such that and .
Transmit the confused sequence as a ciphertext of the plain text T.
3.3 Secret Keys
The integers and k, the weight function w and the encoded sequence are the secret keys of our encryption scheme. The integers and k are used to get the representation of symbols in S, the weight function w is used to get the index of the symbols in the plain text, and the sequence is used to get w.
Note that for a given , the proposed scheme can encrypt a plain text over a symbol set S with size at most, i.e., for the proposed scheme it holds that . Furthermore, the proposed scheme can encrypt a plain text T of any arbitrary size, since it encodes each symbol of T individually.
3.4 Decryption Procedure
Assume that the channel between sender and receiver is noiseless, and therefore the receiver receives the ciphertext . Let g be the -th element of G. We find the position of g in the plain text by using the keys and weight function as follows. Compute a real such that
for some with . Observe that for each g such a real d always exists by Eq. (7). The integer i is the position of the element of the plain text corresponding to the element g of the ciphertext. By using the secret key h, compute the restricted Pell sequence and compute the inverse defined as
of the permutation by using the secret key k. To get the plain text at the -th position of the plain text T, find the real such that for some index t. Find the index t by using Tab. 1, and finally get the -th plain text as corresponding to the -th element g of G.
By repeating the above procedure for each , we get the plain text The proposed encryption and decryption scheme is illustrated in Fig. 2.
We demonstrate our proposed encryption and decryption procedures in detail in Example 1.
3.5 Example 1
Let the ordered symbol set S be 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 , and for and , the entries of the restricted Pell sequence are listed in the second column of Tab. 1, while the third column of Tab. 1 contains . Select integer to generate a permutation on the symbol set S. The entries of are listed in the fifth column of Tab. 1.
Suppose the sender wants to send the plain text T = STAY SAFE with nine elements. For each integer , the -th element of the plain text T, the -th element of the diffused plain text, weight value , binary value and -th element of the encoded plain text are listed in Tab. 2.
To permute the encoded diffused plain text, we generated the ordered ECs and using natural and diffusion orderings respectively. The sequences H and generated by these ordered ECs are listed in Tab. 3.
The confused encoded plain text and are listed in Tab. 4.
We demonstrate the decryption procedure for the 5-th element of the ciphertext . Note that holds for with . This implies that g is the th element of the plain text. The real for which it holds that has index in the third column of Tab. 1. We get the -th element of the plain text T from 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 by . The proposed scheme has five secret keys, three integers and , a weight function w and the sequence , where the key depends on and w, by Eq. (7). There are m choices for k and choices for w, when the plain text is encoded to real numbers with at most digits after the decimal and n is the size of the plain text. This implies that the key spacing of the proposed scheme is at least for and . This implies that the proposed scheme satisfies key spacing analysis. In particular, when computation accuracy is and then there are 88 choices for selecting a pair of integers h and such that and there exists a restricted Pell sequence. This implies that the key spacing of the proposed scheme in this case is at least .
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 keys and w is changed.
Lemma 1. Let T be a plain text of size n over symbol set S of size m and be a ciphertext of T that is obtained by the proposed scheme using the secret keys and weight function w.
(i) The ciphertext generated by the proposed scheme by using , and w is not equal to G.
(ii) The ciphertext generated by the proposed scheme by using that satisfies conditions of step 2, and w is not equal to G.
(iii) If the ciphertext generated by the proposed scheme by using , and such that , for all is not equal to G.
(i) The integer used at step 1 of the proposed scheme is to shift the elements of the symbol set S. Then for all it holds that This implies that for each in Eq. (7), where . This implies that for each and hence .
(ii) For any integer or that satisfies conditions of Step 2, the restricted Pell sequence , since the length of the elements of is different from the length of the elements of . This implies that for each . This implies that , and hence , , from which it follows that .
(iii) Since and therefore for each in Eq. (7), where . This implies that , and hence .
By Lemma 1, our scheme is highly sensitive to the secret keys and w. We demonstrate Lemma 1 with an example by generating ciphertexts for the plain text T = STAY SAFE by slightly changing one key and fixing all other keys. The ciphertext for , and weight function w listed in Tab. 2, ordered MEC with diffusion ordering is listed in the first column of Tab. 5. The ciphertext generated by only changing the integer k to following Lemma 1(i) is listed in the third column of Tab. 5. The ciphertext generated by only changing integer to 23 following Lemma 1(ii) listed in the second column of Tab. 5. The ciphertext generated by only changing weight function to following Lemma 1(iii) is listed in the fourth column of Tab. 5. The ciphertext generated by only changing EC parameter b to 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.
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.
Let X be a data set over a symbol set and for , f(ω) denotes the frequency of w in X. The entropy of X is 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 such that the frequency of each element in the ciphertext generated by the proposed scheme is 1.
Proof. Let T be a plain text of size n over a symbol set S and be the -th element of T. Our proof will complete if we show that there exists at least one weight function w such that for any two distinct it holds that the , where and are generated by Eq. (7). Let for , where , for some and . Let be an ordering of such that for . Let w be a mapping such that is a real in the open interval and for . Note that w is an injection since for each . Furthermore, for each it holds that , since and for each . This implies that for each and hence is a strictly decreasing sequence.This implies that for each distinct from which the proof follows.
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 function w constructed in Lemma 2 and for each i. 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 text T = STAY SAFE with secret keys , ordered ECs with diffusion ordering and weight function w listed in Tab. 6.
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 keys 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  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 generate and . The plain text consists of symbols in S and 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 keys and w. Recall that and therefore it is not necessary that is at most the minimum number of digits after the decimal in the ciphertext. Thus, the attacker needs to try all possibilities for such that and there exists a restricted Pell sequence of the size , and k to know the representation of symbols in S, the weight function w to know the index of the symbols in the plain text, and 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 .
4.6 Security Comparison
The proposed scheme has five secret keys, the three integers , the weight function w, and the encoded sequence . The secret key depends on the choice of and the plain text. The main purpose of is to get the weight value , and hence the index i when . However, if for all i, then the weight are in the ciphertext by Eq. (7), and therefore the key is not necessary to get the weight function. More precisely, when for all i, we solve Eq. (8) for , where to get w. This implies that in the case of for all and w are 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 for all i as discussed in Sections 4.1–4.5.
We compared the security strength of the proposed scheme when for all i, 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].
The schemes in  and  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  and .
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, QAU- URF 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.
|This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.|