Abstract

In 1984, Shamir introduced the concept of an identity-based cryptosystem. In this system, each user needs to visit a Key Authentication Center (KAC) and identify him self before joining a communication network. Once a user is accepted, the KAC will provide him with a secret key. In this way if a user wants to communicate with others he only needs to know the identity of his communication partner and the public key of the KAC. There is no public file required in this system. However, Shamir did not succeed in constructing an identity based cryptosystem but only in constructing an identity-based signature scheme. Meshram and Agrawal have proposed an id-based cryptosystem based on double discrete logarithm problem which uses the public key cryptosystem based on double discrete logarithm problem. In this study, we propose the modification in an id based cryptosystem based on the double discrete logarithm problem and we consider the security against a conspiracy of some entities in the proposed system and show the possibility of establishing a more secure system.

---

INTRODUCTION

In a network environment, secret session key needs to be shared between two users to establish a secret communication. While the number of users in the network is increasing, key distribution will become a serious problem. In Diffie and Hellman (1976) introduced the concept of the Public Key distribution System (PKDS). In the PKDS, each user needs to select a secret key and compute a corresponding public key stored in the public directory. The common secrete session key which will be shared between two users can then be determined by either user, based on his own secret key and the partner’s public key. Although, the PKDS provides an elegant way to solve the key distribution problem, the major concern is the authentication of the public keys used in the cryptographic algorithm.

Many attempts have been made to deal with the public key authentication issue. Kohnfelder (1978) used the RSA digital signature scheme to provide public key certification. His system involves two kinds of public key cryptography: one is in modular p where p is a large prime number; the other is in modular n where n = p q and p and q are large primes. Blorn (1985) proposed a symmetric key generation system (SKGS based on secret sharing schemes. The problems of SKGS however are the difficulty of choosing a suitable threshold value and the requirement of large memory space for storing the secret shadow of each user. In Shamir (1985) introduced the concept of an identity. In this system; each user needs to visit a based cryptosystem. Key Authentication Center (KAC) and identify him self before joining the network. Once a user is accepted, the KAC will provide him with a secret key. In this way, a user needs only to know the identity of his communication partner and the public key of the KAC, together with his secret key, to communicate with others.

There is no public file required in this system. However, Shamir did not succeed in constructing an identity-based cryptosystem but only in constructing an identity-based signature scheme. Since then much research has been devoted especially in Japan to various kinds of ID-based cryptographic schemes. Okarnoto and Tanaka (1989) proposed an identity-based key distribution system in 1988 and later (Ohta, 1988) extended their scheme for user identification. These schemes use the RSA public key cryptosystem (Rivest et al., 1978) for operations in modular n where n is a product of two large primes and the security of these schemes is based on the computational difficulty of factoring this large composite number n.

Tsujii and Itoh (1989) have proposed an ID-based cryptosystem based on the discrete logarithm problem with single discrete exponent which uses the El-Gamal (1985) public key cryptosystem. Meshram and Agrawal (2010a) have proposed an ID-based cryptosystem based on the integer factoring and double discrete logarithm problem which uses the public key cryptosystem based on integer factoring and double discrete logarithm problem. Meshram and Agrawal (2010a, b) have also proposed an ID-based cryptosystem based on double discrete logarithm problem which uses the public key cryptosystem based on double discrete logarithm problem.

Now we modified this cryptosystem for discrete logarithm problem with distinct double discrete exponent because we face the problem of solving double and triple distinct discrete logarithm problem at the same time in the multiplicative group of finite fields as compared to the other public key cryptosystem where we face the difficulty of solving the traditional discrete logarithm problem in the common group.

In this study, we present modification in an ID based cryptosystem based on the double discrete logarithm problem with distinct discrete exponent (the basic idea of the proposed system comes on the public key cryptosystem based on double discrete logarithm problem) here researchers describe further considerations such as the security of the system, the identification for senders etc.

The scheme does not require any interactive preliminary communications in each message transmission and any assumption except the intractability of the discrete logarithm problem (this assumption seems to be quite reasonable) thus the proposed scheme is a concrete example of an ID-based cryptosystem which satisfies (Shamir, 1985) original concept in a strict sence.

MODIFIED ID-BASED PUBLIC KEY CRYPTOSYSTEM

Implementation of the ID-Based cryptosystem
Preparation for the enter and each entity:
Step 1: Each entity generates a k-dimensional binary vector for his ID. We denote entity A’s ID by ID_A as follows:

(1)

Each entity registers his ID with the center and the center stores it in a public file.

Step 2: The center generate two random prime number p and q and compute:

(2)

Then the center chooses an arbitrary random number e, 1≤e≤φ (N) such that gcd (e.φ (N)) = 1 where (φ(N) = (p-1) (q-1) is the Euler function of N. Then center publishes (e, N) as the public key. Any entity can compute the entity A’s extended ID, EID_A by the following:

(3)

Where t = |N| is the numbers of bits of N.

Step 3: Center’s secrete information: The center chooses an arbitrary large prime p and q bit and also generated n-dimensional vector. and m-dimensional vector b over Z^*_p which satisfies:

(4)

(5)

where, I and J are n-dimensional binary vector and stores it as the centers secret information. The condition of Eq. 5 is necessary to avoid the accidental coincidence of some entities secrete key. A simple ways to generate the vectors a and b is to use (Merkle and Hellman, 1978).

Step 4: The center also chooses w which satisfies gcd (w, φ(N)) = 1 and where [x] also denote the floor function which implies the largest integer smaller than compute x.

The center chooses a super increasing sequences corresponding to a and b as a^’_i (1≤i≤n) and b^’_l (1≤l≤m) satisfies:

(6)

(7)

Then the centre computes:

(8)

Where:

(9)

Remark 1: It is clear that the vector and defined by Eq. 9 satisfies Eq. 4 and 5 the above scheme is one method of generating an n and m dimensional vectors a and b satisfies (4) (5). In this study, we adopt the above scheme. However, another method might be possible.

Step 5: The center also choose t arbitrary integers (e₁, e₂, e₃, ... ..., e_t), satisfying gcd (e_i, φ(N)) = 1, (1<i<t) and compute n-dimensional and m-dimensional vectors D^j and D^k, respectively:

(10)

(11)

Since, D^j and D^k are one to one system.

Step 5; Center public information: The center chooses two arbitrary generators a and β of Z^*_pand computes n-dimensional vector h using generator a and m-dimensional vector g using generator β corresponding to the vector a and b.

(12)

(13)

The center informs each entity (N, a, β, h, g) as public information.

Step 6; Each entity secrete key: Entity A’s secrete keys s_a and s_b are given by inner product of a and b (the centre’s secret information) and EID_A (entity A’s extended ID, Eq. 3):

(14)

(15)

System initialization parameters
Center ecrete information: a: n-dimensional vector and b: m-dimensional vector (Eq. 8 and 9).

Center public information: h: n-dimensional vector and g: m-dimensional vector (Eq. 12 and 13), p: a large prime number, e: an integer, two generator α and β of Z^*_p. Entity A's secrete keys s_a and s_b = entity A's public information = ID_A: k-dimensional vector.

Protocol of the proposed cryptosystem: Without loss of generality suppose that entity B wishes to send message M to entity A.

Encryption: Entity B generates EID_A (Entity A's extended ID, (Eq. 3) from ID_A. It then computes γ₁ and γ₂ from corresponding public information h and g and EID_A.

Entity B use γ₁ and γ₂ in Public key cryptosystem based on double discrete logarithm problem. Let M (1≤M≤N) be entity B’s message to be transmitted Entity B select two random integer u and v such that (2≤uv≤φ(N)-1) and computes:

The cipher text is given by C = (C₁, C₂, E).

Decryption: To recover the plaintext M from the cipher text Entity A should do the following:

Compute:

And

Recover the plaintext:

SECURITY ANALYSIS

The security of the proposed I based cryptosystem is based on the intractability of the discrete logarithm problem. It is very difficult to give formal proofs for the security of a cryptosystem in the following; we analyze some possible attacks against the above schemes and show that the security of these attacks is based on the LP assumption.

An intruder should solve a discrete logarithm problem twice to obtain the private key given the public as following: In this encryption the public key is given by (N, e, α, β, γ₁, γ₂) and the corresponding secret key is given by (S_a, s_b). To obtain the private key (s_a) he should solve the DLP:

To obtain the private key (s_b) he should solve the DLP:

This information is equivalent to computing the discrete logarithm problem over multiplicative cyclic group Z^*_p and corresponding secrete key S_a and S_b will never be revealed to the public.

An intruder might try to impersonate user A by developing some relation between w and w’ since γ₁ = Y^wsa(mod N) and γ^’₁ Y^w’sa (mod N). Similarly γ₂ = y^wsb(mod N) and γ^’₂ Y^w’sb(mod N) by knowing γ₁, γ₂, w, w’ the intruder can derive γ^’₁ and γ^’₂ as (mod N) and (mod N) without knowing S_a and S_b however trying to obtain w from α and β is equivalent to compute the discrete logarithm problem.

CONCLUSION

In this study present the modification in an I-based cryptosystem based on double discrete logarithm problem with distinct discrete exponents in the multiplicative group of finite fields. The proposed scheme satisfies Shamir’s original concepts in a strict sense, i.e., it does not require any interactive preliminary communications in each data transmission and has no assumption that tamper free modules are available. This kind of scheme definitely provides a new scheme with a longer and higher level of security than that based on a double discrete logarithm problem with distinct discrete exponents. The proposed scheme also requires minimal operations in encryption and decryption algorithms and thus makes it is very efficient. The present study provides the special result from the security point of view, because we face the problem of solving double and triple distinct discrete logarithm problem at the same time in the multiplicative group of finite fields as compared to the other public key cryptosystem, where we face the difficulty of solving the traditional discrete logarithm problem in the common groups.

How to cite this article:

Chandrashekhar Meshram. Modified ID-Based Public Key Cryptosystem Using Double Discrete Logarithm Problem.
DOI: https://doi.org/10.36478/ajit.2011.32.35
URL: https://www.makhillpublications.co/view-article/1682-3915/ajit.2011.32.35