Proceeding Of The 3rd International Conference On Informatics And Technology,
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Proceeding Of The 3rd International Conference On Informatics And Technology, as PDF for free.
More details
- Words: 2,389
- Pages: 4
Proceeding of the 3rd International Conference on Informatics and Technology, 2009
PRIVATE DATA RETRIEVAL BASED ON HYBRID-MODE ASSUMPTIONS 1
2
Eddie Shahril Ismail , Mohammad Saleh Nahar Hijazi School of Mathematical Sciences, Faculty of Science and Technology Universiti Kebangsaan Malaysia, 43600 UKM Bangi, Selangor, Malaysia Email: [email protected] and [email protected] 1,2
ABSTRACT The past years have seen many attempts to construct cryptosystems based on a single hard problem, like factoring, discrete logarithms, residuosity, and elliptic curve discrete logarithms. In the near future, those systems will no longer be secure if the solutions of these hard problems are discovered. In this paper, we propose a new cryptosystem based on hybrid-mode cryptographic assumptions; elliptic curve discrete logarithms and residuosity. The major advantage of our scheme is that it is very unlikely that two assumptions can be efficiently solved simultaneously, and therefore offers a higher security than that scheme based on a single cryptographic assumption. We show that the scheme is resistant to some attacks and the performance of the scheme requires only reasonable number of operations in both encryption and decryption. Keywords: Cryptography, cryptosystem, cryptographic assumptions 1.0
INTRODUCTION
Diffie and Hellman [12] have proposed their brilliant idea in a seminal paper on public key cryptography. They showed how to transmit a private message in an open channel so that it will arrive in the right hand. Such a system is called cryptosystem, the first of which was invented in 1978 [9]. The security of the scheme is solely based on the hardness of factoring problem (FAC). A year later, Rabin [13] designed a cryptosystem based on residuosity problem (RES). His system depends on the difficulty of finding prime divisors of a given large integer. But no concrete relationship between the FAC and RES is found. In 1985, the first discrete logarithm (DL)-based cryptosystem [10] was developed. Since then many cryptosystems have been developed based on these three assumptions or problems. One common feature of these schemes is that they are depending on a number-theoretical problem (except for RES) and thus its implementation heavily depends on modular exponentiation which is known to be time consuming and costly. In the mid-1980s, Koblizt [6] and Miller [11] independently implemented the elliptic curve into cryptography and showed how this curve can be used as a remarkable tool in designing cryptographic schemes. They proposed cryptographic schemes whose security lie on the so-called elliptic curve discrete logarithm problem (ECDL) and proved that ECDLbased scheme provides higher security and greater efficiency than both integer factorization systems and discrete logarithm systems. Their proposal became a turning point of the rigorous development of ECDL-schemes in the literature [8, 3, 4, 5, 6, 11, 1]. In this paper, we propose a new cryptosystem based on hybrid-mode assumptions, ECDL and RES with two contributions. First, the new scheme offers a higher security than that schemes based on ECDL, RES or any other assumptions since it is very unlikely for an enemy to solve the two assumptions simultaneously. The second, our scheme is efficient since it involves no modular exponentiations in each phase or stage. 2.0
BACKGROUND THEORIES
A general elliptic curve has the form π¦π¦ 2 + ππππππ + ππππ = π₯π₯ 3 + πππ₯π₯ 2 + ππππ + ππ, where ππ, ππ, ππ, ππ and ππ are real numbers. On this curve we define a special addition operation with the inclusion of a point at infinity denoted as β. Let a prime ππ be the characteristics and ππ is neither two nor three. Then we obtain an elliptic group over the Galois Field πΈπΈοΏ½πΉπΉππ οΏ½ for π¦π¦ 2 = π₯π₯ 3 + πππ₯π₯ + ππ (mod ππ) where 0 β€ π₯π₯ < ππ.
The numbers ππ, ππ < ππ are non-negative integers satisfying the condition 4ππ 3 + 27ππ2 β 0 (mod ππ).
The rules for addition over the elliptic group πΈπΈοΏ½πΉπΉππ οΏ½ are defined as follows:
(a) If three points are on a line that intersects an elliptic curve, then their sum equals the point at infinity β. (b) Let the points π΄π΄ = (ππ, π π ) and π΅π΅ = (π‘π‘, π’π’) be in the elliptic group πΈπΈοΏ½πΉπΉππ οΏ½. i. π΄π΄ + β = π΄π΄ = β + π΄π΄ and if π΅π΅ = βπ΄π΄ = (ππ, βπ π ) then π΄π΄ + π΅π΅ = β
Β©Informatics '09, UM 2009
RDT6 - 186
Proceeding of the 3rd International Conference on Informatics and Technology, 2009
ii.
iii.
If π΄π΄ β π΅π΅, then π΄π΄ + π΅π΅ = (ππ, ππ) where ππ = ππ2 β ππ β π‘π‘ (mod ππ) and ππ = ππ(ππ β ππ) β π π (mod ππ). The number ππ is calculated using the formula below: π’π’ β π π , ππ β π‘π‘ π‘π‘ β ππ ππ = οΏ½ 2 3ππ + ππ , ππ = π‘π‘, π π β 0 2π π If ππ is a positive integer, we can compute ππππ = πΆπΆ = π΄π΄ + π΄π΄ + β― + π΄π΄ (ππ times) where πΆπΆ is also in πΈπΈοΏ½πΉπΉππ οΏ½.
If π·π· is a point on the elliptic group and ππ is the smallest positive integer satisfying the equation ππππ = β, then we say that π·π· has an order ππ and is called the base point. The important part is ECDL and RES. We define them as follows: ο§ ο§
3.0
ECDL: Assume that we are given two elliptic points π΄π΄ and πΆπΆ. Then it is very difficult to obtain the positive integer ππ such that ππππ = πΆπΆ. RES: Assume that we are given a large integer πΎπΎ = ππ2 (mod ππππ) where ππ and π π are two strong primes and πΎπΎ, ππ β β€βππππ . Then it is very hard to find the number ππ.
THE PROPOSED SCHEME
We present a new cryptosystem design over an elliptic curve by utilizing a residuosity assumption. Three phases are used to establish a secured encryption mechanism between two users (sender and receiver). The scheme process is shown as follows: 3.1
Initialization
The receiver chooses the domain parameters are consists of: β’ β’ β’ β’ β’ β’ β’
The field order ππ. Two coefficients ππ, ππ β πΉπΉππ that define the equation π¦π¦ 2 = π₯π₯ 3 + πππ₯π₯ + ππ (mod ππ) of the elliptic curve πΈπΈ over πΉπΉππ . The number of points in πΈπΈοΏ½πΉπΉππ οΏ½, denoted #πΈπΈοΏ½πΉπΉππ οΏ½. Two field elements π₯π₯1 and π¦π¦1 in πΉπΉππ that define a finite point πΊπΊ = (π₯π₯1 , π¦π¦1 ). π΅π΅ has a large prime order ππ and is called the base point. Publishes a one-way hash function β(β). Parameters (ππ, ππ, π π ) as his private keys, where ππ and π π are two large strong primes. Calculates his public keys ππ = ππππ = (ππ1 , ππ2 ) and ππ = ππππ.
In order to prevent the Pohlig-Hellman attack and Pollardβs rho attack, it is necessary that #πΈπΈοΏ½πΉπΉππ οΏ½ be divisible by a sufficiently large prime number [14] and the maximum resistance to these attacks is by selecting πΈπΈοΏ½πΉπΉππ οΏ½ so that #πΈπΈοΏ½πΉπΉππ οΏ½ is prime or almost prime. 3.2
Encryption
To encrypt a message β(ππ), the sender does the following:
β’ β’ β’ β’
3.3
Selects a secret integer 1 < ππ < ππ. Computes ππ = ππππ = (ππ1 , ππ2 ) and πΎπΎ = ππππ. Calculates π€π€ = οΏ½ππ1 ππ1 + β(ππ)οΏ½ (mod ππ) and πΌπΌ = π€π€ 2 (mod ππ). Send (πΌπΌ, πΎπΎ) to the receiver. Decryption
Upon receiving the encrypted message (πΌπΌ, πΎπΎ), the receiver does the following:
β’ β’ β’
Calculates π π = ππππ = (ππ1 , ππ2 ). Extract the number π€π€ from the received πΌπΌ (refer to [13] for the extraction process for π€π€). Obtains the original message as β(ππ) = (π€π€ β ππ1 ππ1 ) (mod ππ).
Β©Informatics '09, UM 2009
RDT6 - 187
Proceeding of the 3rd International Conference on Informatics and Technology, 2009
4.0
EVALUATION OF THE SCHEME
We evaluate our presented scheme based on the exactness, security analysis and efficiency performance. For exactness we prove the following theorem. Theorem: If the Setup and Encryption processes in the above scheme run smoothly, the decrypting equation in Decryption is correct. Proof: From the received encrypted message (πΌπΌ, πΎπΎ), receiver with the information of ππ and π π can extract π€π€ = ππ1 ππ1 + β(ππ) from πΌπΌ (refer to [13] for the extraction process for π€π€). Since he possesses the private key ππ he can get the number ππ1 via π π = ππππ. Thus he can read the original message by computing π€π€ β ππ1 ππ1 = ππ1 ππ1 + β(ππ) β ππ1 ππ1 = β(ππ) since ππ1 is public.
For security analysis [2, 7] we deliver the scheme to the most common considering attacks; KEY-ONLY attack, RES attack and ECDL attack. We show that for these attacks the adversaries (Adv) would fail.
KEY-ONLY attack: Adv wishes to obtain all secret keys using all information that is available from the system. In this case, Adv needs to solve ECDLP and RES, which is clearly infeasible. RES attack: Assume that Adv can solve the RES assumption. He then knows the prime factorization of ππ and can extract the integer π€π€ from πΌπΌ = π€π€ 2 mod ππ. Obtaining the number ππ, the Adv can obtain the original β(ππ) since β(ππ) = π€π€ β ππ1 ππ1 . But this is impossible due to the hardness of ECDL assumption. Note that in this attack, the integer ππ1 should not be used more than once. If not, the Adv can have π€π€ β π€π€1 β β(ππ) = β(ππ1 ) where β(ππ1 ) = π€π€1 β ππ1 ππ1 . If the message β(ππ1 ) is his then the original β(ππ) can be generated.
ECDL attack: Now let say that Adv can solve the ECDL assumption. He then can figure out the integer ππ1 from the relation of π π = ππππ = (ππ1 , ππ2 ). Unfortunately, to read the message β(ππ) is still hard since no information on π€π€ is available.
Next, we investigate the efficiency performance of our scheme in terms of number of keys, computational complexity and communication costs. We use the following notations to analyze the performance of the scheme. β’ β’ β’ β’ β’ β’ β’ β’ β’ β’ β’ β’
ππππππ ππππππ ππππππππ ππππππππ πππ π π π π π πππ π π π π π ππππππππ ππππππππ ππππππ βππππππ ππππππ βππππππ ππππππππ ππβππππβ
is the number of secret keys, is the number of public keys, is the time complexity for executing the modular multiplication, is the time complexity for executing the modular exponentiation, is the time complexity for executing the modular square, is the time complexity for executing the modular square root, is the time complexity for executing the modular addition, is the time complexity for executing the modular inversion, is the time complexity for executing the multiplication on elliptic curve points, is the time complexity for executing the addition of two elliptic curve points, is the time complexity for selecting a random integer, is the time complexity for performing a one-way hash function, β.
The performance of our new cryptosystem is described as follows: The number of keys of the new scheme is ππππππ = 3 and ππππππ = 2. The computational complexity for encryption is given ππππππππ + 2ππππππ βππππ ππ + ππππππππ + πππ π π π π π + ππβππππβ whereas the time complexity for decryption is ππππππ βππππππ + ππππππππ + πππ π π π π π . Finally the communication costs or size of parameters for encryption and decryption are respectively given by 2|ππ| and |ππ|. 5.0
CONCLUSION
We proposed a new cryptosystem based on hybrid-mode problems; elliptic curve discrete logarithm and residuosity problems. The proposed scheme is shown secure against the three considering attacks for hybrid-mode-based cryptosystem. The adversary has to solve two hard problems in order to break the scheme and this is happen with negligible probability. Our scheme is also efficient since it requires no modular exponentiation in both encryption and decryption. ACKNOWLEDGEMENT We acknowledge the financial support received from Universiti Kebangsaan Malaysia under the Research University Grant UKM-OUP-ICT-36-177/2009 and UKM-GUP-NBT-08-29-120.
Β©Informatics '09, UM 2009
RDT6 - 188
Proceeding of the 3rd International Conference on Informatics and Technology, 2009
REFERENCES
[1]
A. Menezes, Elliptic Curve Public Key Cryptosystem. Kluwer Academic Publishers. Boston, Dordrecht, London. 1993.
[2]
A. Menezes et al., Handbook of Applied Cryptography. CRC Press, USA. 1996.
[3] [4]
C. Lawrence, Elliptic Curves Number Theory and Cryptography. CRC Press. Washington. 2003. C. Popescu, An Identification Scheme Based on the Elliptic Curve Discrete Logarithm Problem, in Proceedings th of The 4 International Conference on High-Performing Computing in the Asia-Region, Vol. 2, pp. 624-625 2000.
[5]
K. Rabah, Elliptic Curve ElGamal Encryption and Signature Schemes. Information Technology Journal 13(3). 2005, pp. 299-306.
[6]
N. Koblitz, Elliptic Curve Cryptosystems. Mathematics of Computation 48(177). 1987, pp. 203-209.
[7]
N. Koblitz and A. Menezes, Another Look at βProvable Securityβ. Journal of Cryptology 20(1). 2007, pp. 3-37.
[8]
N. Koblizt et al., The State of Elliptic Curve Cryptography. Design, Code Cryptography 19(2-3). 2000, pp. 173193.
[9]
R. L. Rivest et al., A Method for Obtaining Digital Signature and Public Key Cryptosystems. Commun. ACM 21(2). 1978, pp. 120-126.
[10]
T. ElGamal, Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithm. IEEE Trans. Inform. Theory, IT-31. 1985, pp. 469-472.
[11]
V. Miller, Uses of Elliptic Curve in Cryptography. Advances in Cryptology-Proceeding of CRYPTOβ85. Lecture Notes in Computer Sciences, 218. Springer-Verlag. 1986, pp. 417-426.
[12]
W. Diffie and M. E. Hellman, New Direction in Cryptography. IEEE Trans. Inform. Theory, 22(6). 1976, pp. 644654.
[13]
M. O. Rabin, Digitalized Signatures and Public Key Functions as Intractable as Factorization. Technical report MIT/LCS/TR-212, MIT Laboratory for Computer Science. 1979.
[14]
S. C. Pohlig and M. E. Hellman, An Improved Algorithm for Computing Logarithms Over GF(p) and Its Cryptographic Significance. IEEE Transactions on Information Theory 24(1). 1978, pp. 106-110.
BIOGRAPHY
Eddie Shahril Ismail is a senior lecturer at School of Mathematical Sciences, Faculty of Science and Technology, Universiti Kebangsaan Malaysia. He obtained his PhD in Cryptography from Universti Sains Malaysia in 2004. His research interests include digital signature, cryptosystem and threshold-like scheme. He has produced a number of articles related to these areas. He is also a member of International Association Cryptographic Research (IACR) since 2008. Mohammad Saleh Nahar Hijazi is a phD student at School of Mathematical Sciences, Faculty of Science and Technology, Universiti Kebangsaan Malaysia. He is currently working on the development of cryptosystem based on hybrid-mode problems.
Β©Informatics '09, UM 2009
RDT6 - 189
PRIVATE DATA RETRIEVAL BASED ON HYBRID-MODE ASSUMPTIONS 1
2
Eddie Shahril Ismail , Mohammad Saleh Nahar Hijazi School of Mathematical Sciences, Faculty of Science and Technology Universiti Kebangsaan Malaysia, 43600 UKM Bangi, Selangor, Malaysia Email: [email protected] and [email protected] 1,2
ABSTRACT The past years have seen many attempts to construct cryptosystems based on a single hard problem, like factoring, discrete logarithms, residuosity, and elliptic curve discrete logarithms. In the near future, those systems will no longer be secure if the solutions of these hard problems are discovered. In this paper, we propose a new cryptosystem based on hybrid-mode cryptographic assumptions; elliptic curve discrete logarithms and residuosity. The major advantage of our scheme is that it is very unlikely that two assumptions can be efficiently solved simultaneously, and therefore offers a higher security than that scheme based on a single cryptographic assumption. We show that the scheme is resistant to some attacks and the performance of the scheme requires only reasonable number of operations in both encryption and decryption. Keywords: Cryptography, cryptosystem, cryptographic assumptions 1.0
INTRODUCTION
Diffie and Hellman [12] have proposed their brilliant idea in a seminal paper on public key cryptography. They showed how to transmit a private message in an open channel so that it will arrive in the right hand. Such a system is called cryptosystem, the first of which was invented in 1978 [9]. The security of the scheme is solely based on the hardness of factoring problem (FAC). A year later, Rabin [13] designed a cryptosystem based on residuosity problem (RES). His system depends on the difficulty of finding prime divisors of a given large integer. But no concrete relationship between the FAC and RES is found. In 1985, the first discrete logarithm (DL)-based cryptosystem [10] was developed. Since then many cryptosystems have been developed based on these three assumptions or problems. One common feature of these schemes is that they are depending on a number-theoretical problem (except for RES) and thus its implementation heavily depends on modular exponentiation which is known to be time consuming and costly. In the mid-1980s, Koblizt [6] and Miller [11] independently implemented the elliptic curve into cryptography and showed how this curve can be used as a remarkable tool in designing cryptographic schemes. They proposed cryptographic schemes whose security lie on the so-called elliptic curve discrete logarithm problem (ECDL) and proved that ECDLbased scheme provides higher security and greater efficiency than both integer factorization systems and discrete logarithm systems. Their proposal became a turning point of the rigorous development of ECDL-schemes in the literature [8, 3, 4, 5, 6, 11, 1]. In this paper, we propose a new cryptosystem based on hybrid-mode assumptions, ECDL and RES with two contributions. First, the new scheme offers a higher security than that schemes based on ECDL, RES or any other assumptions since it is very unlikely for an enemy to solve the two assumptions simultaneously. The second, our scheme is efficient since it involves no modular exponentiations in each phase or stage. 2.0
BACKGROUND THEORIES
A general elliptic curve has the form π¦π¦ 2 + ππππππ + ππππ = π₯π₯ 3 + πππ₯π₯ 2 + ππππ + ππ, where ππ, ππ, ππ, ππ and ππ are real numbers. On this curve we define a special addition operation with the inclusion of a point at infinity denoted as β. Let a prime ππ be the characteristics and ππ is neither two nor three. Then we obtain an elliptic group over the Galois Field πΈπΈοΏ½πΉπΉππ οΏ½ for π¦π¦ 2 = π₯π₯ 3 + πππ₯π₯ + ππ (mod ππ) where 0 β€ π₯π₯ < ππ.
The numbers ππ, ππ < ππ are non-negative integers satisfying the condition 4ππ 3 + 27ππ2 β 0 (mod ππ).
The rules for addition over the elliptic group πΈπΈοΏ½πΉπΉππ οΏ½ are defined as follows:
(a) If three points are on a line that intersects an elliptic curve, then their sum equals the point at infinity β. (b) Let the points π΄π΄ = (ππ, π π ) and π΅π΅ = (π‘π‘, π’π’) be in the elliptic group πΈπΈοΏ½πΉπΉππ οΏ½. i. π΄π΄ + β = π΄π΄ = β + π΄π΄ and if π΅π΅ = βπ΄π΄ = (ππ, βπ π ) then π΄π΄ + π΅π΅ = β
Β©Informatics '09, UM 2009
RDT6 - 186
Proceeding of the 3rd International Conference on Informatics and Technology, 2009
ii.
iii.
If π΄π΄ β π΅π΅, then π΄π΄ + π΅π΅ = (ππ, ππ) where ππ = ππ2 β ππ β π‘π‘ (mod ππ) and ππ = ππ(ππ β ππ) β π π (mod ππ). The number ππ is calculated using the formula below: π’π’ β π π , ππ β π‘π‘ π‘π‘ β ππ ππ = οΏ½ 2 3ππ + ππ , ππ = π‘π‘, π π β 0 2π π If ππ is a positive integer, we can compute ππππ = πΆπΆ = π΄π΄ + π΄π΄ + β― + π΄π΄ (ππ times) where πΆπΆ is also in πΈπΈοΏ½πΉπΉππ οΏ½.
If π·π· is a point on the elliptic group and ππ is the smallest positive integer satisfying the equation ππππ = β, then we say that π·π· has an order ππ and is called the base point. The important part is ECDL and RES. We define them as follows: ο§ ο§
3.0
ECDL: Assume that we are given two elliptic points π΄π΄ and πΆπΆ. Then it is very difficult to obtain the positive integer ππ such that ππππ = πΆπΆ. RES: Assume that we are given a large integer πΎπΎ = ππ2 (mod ππππ) where ππ and π π are two strong primes and πΎπΎ, ππ β β€βππππ . Then it is very hard to find the number ππ.
THE PROPOSED SCHEME
We present a new cryptosystem design over an elliptic curve by utilizing a residuosity assumption. Three phases are used to establish a secured encryption mechanism between two users (sender and receiver). The scheme process is shown as follows: 3.1
Initialization
The receiver chooses the domain parameters are consists of: β’ β’ β’ β’ β’ β’ β’
The field order ππ. Two coefficients ππ, ππ β πΉπΉππ that define the equation π¦π¦ 2 = π₯π₯ 3 + πππ₯π₯ + ππ (mod ππ) of the elliptic curve πΈπΈ over πΉπΉππ . The number of points in πΈπΈοΏ½πΉπΉππ οΏ½, denoted #πΈπΈοΏ½πΉπΉππ οΏ½. Two field elements π₯π₯1 and π¦π¦1 in πΉπΉππ that define a finite point πΊπΊ = (π₯π₯1 , π¦π¦1 ). π΅π΅ has a large prime order ππ and is called the base point. Publishes a one-way hash function β(β). Parameters (ππ, ππ, π π ) as his private keys, where ππ and π π are two large strong primes. Calculates his public keys ππ = ππππ = (ππ1 , ππ2 ) and ππ = ππππ.
In order to prevent the Pohlig-Hellman attack and Pollardβs rho attack, it is necessary that #πΈπΈοΏ½πΉπΉππ οΏ½ be divisible by a sufficiently large prime number [14] and the maximum resistance to these attacks is by selecting πΈπΈοΏ½πΉπΉππ οΏ½ so that #πΈπΈοΏ½πΉπΉππ οΏ½ is prime or almost prime. 3.2
Encryption
To encrypt a message β(ππ), the sender does the following:
β’ β’ β’ β’
3.3
Selects a secret integer 1 < ππ < ππ. Computes ππ = ππππ = (ππ1 , ππ2 ) and πΎπΎ = ππππ. Calculates π€π€ = οΏ½ππ1 ππ1 + β(ππ)οΏ½ (mod ππ) and πΌπΌ = π€π€ 2 (mod ππ). Send (πΌπΌ, πΎπΎ) to the receiver. Decryption
Upon receiving the encrypted message (πΌπΌ, πΎπΎ), the receiver does the following:
β’ β’ β’
Calculates π π = ππππ = (ππ1 , ππ2 ). Extract the number π€π€ from the received πΌπΌ (refer to [13] for the extraction process for π€π€). Obtains the original message as β(ππ) = (π€π€ β ππ1 ππ1 ) (mod ππ).
Β©Informatics '09, UM 2009
RDT6 - 187
Proceeding of the 3rd International Conference on Informatics and Technology, 2009
4.0
EVALUATION OF THE SCHEME
We evaluate our presented scheme based on the exactness, security analysis and efficiency performance. For exactness we prove the following theorem. Theorem: If the Setup and Encryption processes in the above scheme run smoothly, the decrypting equation in Decryption is correct. Proof: From the received encrypted message (πΌπΌ, πΎπΎ), receiver with the information of ππ and π π can extract π€π€ = ππ1 ππ1 + β(ππ) from πΌπΌ (refer to [13] for the extraction process for π€π€). Since he possesses the private key ππ he can get the number ππ1 via π π = ππππ. Thus he can read the original message by computing π€π€ β ππ1 ππ1 = ππ1 ππ1 + β(ππ) β ππ1 ππ1 = β(ππ) since ππ1 is public.
For security analysis [2, 7] we deliver the scheme to the most common considering attacks; KEY-ONLY attack, RES attack and ECDL attack. We show that for these attacks the adversaries (Adv) would fail.
KEY-ONLY attack: Adv wishes to obtain all secret keys using all information that is available from the system. In this case, Adv needs to solve ECDLP and RES, which is clearly infeasible. RES attack: Assume that Adv can solve the RES assumption. He then knows the prime factorization of ππ and can extract the integer π€π€ from πΌπΌ = π€π€ 2 mod ππ. Obtaining the number ππ, the Adv can obtain the original β(ππ) since β(ππ) = π€π€ β ππ1 ππ1 . But this is impossible due to the hardness of ECDL assumption. Note that in this attack, the integer ππ1 should not be used more than once. If not, the Adv can have π€π€ β π€π€1 β β(ππ) = β(ππ1 ) where β(ππ1 ) = π€π€1 β ππ1 ππ1 . If the message β(ππ1 ) is his then the original β(ππ) can be generated.
ECDL attack: Now let say that Adv can solve the ECDL assumption. He then can figure out the integer ππ1 from the relation of π π = ππππ = (ππ1 , ππ2 ). Unfortunately, to read the message β(ππ) is still hard since no information on π€π€ is available.
Next, we investigate the efficiency performance of our scheme in terms of number of keys, computational complexity and communication costs. We use the following notations to analyze the performance of the scheme. β’ β’ β’ β’ β’ β’ β’ β’ β’ β’ β’ β’
ππππππ ππππππ ππππππππ ππππππππ πππ π π π π π πππ π π π π π ππππππππ ππππππππ ππππππ βππππππ ππππππ βππππππ ππππππππ ππβππππβ
is the number of secret keys, is the number of public keys, is the time complexity for executing the modular multiplication, is the time complexity for executing the modular exponentiation, is the time complexity for executing the modular square, is the time complexity for executing the modular square root, is the time complexity for executing the modular addition, is the time complexity for executing the modular inversion, is the time complexity for executing the multiplication on elliptic curve points, is the time complexity for executing the addition of two elliptic curve points, is the time complexity for selecting a random integer, is the time complexity for performing a one-way hash function, β.
The performance of our new cryptosystem is described as follows: The number of keys of the new scheme is ππππππ = 3 and ππππππ = 2. The computational complexity for encryption is given ππππππππ + 2ππππππ βππππ ππ + ππππππππ + πππ π π π π π + ππβππππβ whereas the time complexity for decryption is ππππππ βππππππ + ππππππππ + πππ π π π π π . Finally the communication costs or size of parameters for encryption and decryption are respectively given by 2|ππ| and |ππ|. 5.0
CONCLUSION
We proposed a new cryptosystem based on hybrid-mode problems; elliptic curve discrete logarithm and residuosity problems. The proposed scheme is shown secure against the three considering attacks for hybrid-mode-based cryptosystem. The adversary has to solve two hard problems in order to break the scheme and this is happen with negligible probability. Our scheme is also efficient since it requires no modular exponentiation in both encryption and decryption. ACKNOWLEDGEMENT We acknowledge the financial support received from Universiti Kebangsaan Malaysia under the Research University Grant UKM-OUP-ICT-36-177/2009 and UKM-GUP-NBT-08-29-120.
Β©Informatics '09, UM 2009
RDT6 - 188
Proceeding of the 3rd International Conference on Informatics and Technology, 2009
REFERENCES
[1]
A. Menezes, Elliptic Curve Public Key Cryptosystem. Kluwer Academic Publishers. Boston, Dordrecht, London. 1993.
[2]
A. Menezes et al., Handbook of Applied Cryptography. CRC Press, USA. 1996.
[3] [4]
C. Lawrence, Elliptic Curves Number Theory and Cryptography. CRC Press. Washington. 2003. C. Popescu, An Identification Scheme Based on the Elliptic Curve Discrete Logarithm Problem, in Proceedings th of The 4 International Conference on High-Performing Computing in the Asia-Region, Vol. 2, pp. 624-625 2000.
[5]
K. Rabah, Elliptic Curve ElGamal Encryption and Signature Schemes. Information Technology Journal 13(3). 2005, pp. 299-306.
[6]
N. Koblitz, Elliptic Curve Cryptosystems. Mathematics of Computation 48(177). 1987, pp. 203-209.
[7]
N. Koblitz and A. Menezes, Another Look at βProvable Securityβ. Journal of Cryptology 20(1). 2007, pp. 3-37.
[8]
N. Koblizt et al., The State of Elliptic Curve Cryptography. Design, Code Cryptography 19(2-3). 2000, pp. 173193.
[9]
R. L. Rivest et al., A Method for Obtaining Digital Signature and Public Key Cryptosystems. Commun. ACM 21(2). 1978, pp. 120-126.
[10]
T. ElGamal, Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithm. IEEE Trans. Inform. Theory, IT-31. 1985, pp. 469-472.
[11]
V. Miller, Uses of Elliptic Curve in Cryptography. Advances in Cryptology-Proceeding of CRYPTOβ85. Lecture Notes in Computer Sciences, 218. Springer-Verlag. 1986, pp. 417-426.
[12]
W. Diffie and M. E. Hellman, New Direction in Cryptography. IEEE Trans. Inform. Theory, 22(6). 1976, pp. 644654.
[13]
M. O. Rabin, Digitalized Signatures and Public Key Functions as Intractable as Factorization. Technical report MIT/LCS/TR-212, MIT Laboratory for Computer Science. 1979.
[14]
S. C. Pohlig and M. E. Hellman, An Improved Algorithm for Computing Logarithms Over GF(p) and Its Cryptographic Significance. IEEE Transactions on Information Theory 24(1). 1978, pp. 106-110.
BIOGRAPHY
Eddie Shahril Ismail is a senior lecturer at School of Mathematical Sciences, Faculty of Science and Technology, Universiti Kebangsaan Malaysia. He obtained his PhD in Cryptography from Universti Sains Malaysia in 2004. His research interests include digital signature, cryptosystem and threshold-like scheme. He has produced a number of articles related to these areas. He is also a member of International Association Cryptographic Research (IACR) since 2008. Mohammad Saleh Nahar Hijazi is a phD student at School of Mathematical Sciences, Faculty of Science and Technology, Universiti Kebangsaan Malaysia. He is currently working on the development of cryptosystem based on hybrid-mode problems.
Β©Informatics '09, UM 2009
RDT6 - 189
