Research Article
Efficient Scheme for Obtaining Public Key Cryptosystem Using Shared Secrets
Department of Computer Science, Faculty of IT, University for Graduate Studies, Amman-Jordan
Secret sharing schemes is a method of sharing a message m among a set of n participants such that any subset consisting of t participants can reconstruct the message m, but no subset of smaller size can reconstruct. Secret sharing methods have numerous practical uses. For example, they can be employed to control the access to protect so only an authorized subgroup of bank workers can open it by grouping their shares together and rebuilding the secret combination which unlocks the protection. The key investigation regarding the understanding of a secret sharing scheme was considered by many researchers (Simmons, 1994; Jackson et al., 1995; Charnes et al., 1997) suggested various solutions for building such systems.
Threshold schemes are originally invented by (Shamir, 1979). Shamir secret sharing method suggests a method of distributing a secret number between numerous users. Simply after some minimum number of users cooperates can the secret number be rebuild. The (Diffie and Hellman, 1976), public key distribution method presents a technique for two users to agree on a secret number among them, while all their exchanges are transmitted over a public way.
In this research we propose a new scheme for obtaining public key cryptosystem using the combination of both Shamir secret sharing scheme and the trap door characteristics of discrete logarithm as employed in the Diffie-Hellman (1976) secret number exchange scheme. The object of this proposed scheme is to protect the secrecy of the numbers held by the users of the shared secret, whilst at the same time permitting them to send information in the clear which, when issued by sufficiency of the individuals enables mutually authenticated base key exchange, between the users.
THE PROPOSED SCHEME
The polynomial of degree n in one parameter is entirely defined when n + 1 points in which it sends are specified. This is factual if the coefficients related to any field and in particular to GF (p) the field of integer. If these points are (xi, zi), for i = 1, , n + 1, the value of z according to any number of x is specified by the Lagrange interpolation theorem:
(1) |
Such that:
(2) |
In this suggested method the ordinates x are public number and since wi base only on them, these are also public. It must be noticed that wi, x and z, the wi results from numerical operations, p and x are also members of the field GF (p), i.e., are both integers. The divisions needed in their derivation are achieved by employing the Euclidean method Trappe and Washington (2006). The ordinates z on the other hand, remain secret by the users and by no means directly sent by them. Instead they are employed as key exponents to raise certain public base value h to various powers to give a new set of values s. This exponentiation is performed by mod operation with another prime number q, the base value h and the out comings ss are consequently members of the field GF (q). So
si = hzi mod q | (3) |
According to Menezenes et al. (1997). The exponentiations can be accomplished efficiently employing the repeated square and multiply algorithm, which is commonly employed in public key encryption and illustrated for instance by RSA (Rivest, 1978). While in the Diffie-Hellman public key distributed algorithm given q is a well selected prime knowledge of h, q and the ss does not disclose the matching zs because logarithm mod a well selected prime is a computationally difficult to solve. The prime numbers p and q are selected so that both are related to each other by the following formula:
q = g* p + 1 | (4) |
When p is selected as a prime number, g is handily chosen from the sorting order of even numbers 2, 4, 6, is the least positive integer which produces q prime. This relationship has two aims:
• | To ensure that q-1 has large prime factor which is an essential condition for guaranteeing that logarithm mod q is computationally difficult to solve. According to Menezenes Vanstone (1997). The well-known method is shanks method which needs operations to achieve the logarithm. |
• | To offer a technique of efficiency achieving the operations among the exponents z needed by formula 1 via performing on the matching s numbers. Additions among z values are substituted by multiplications among s values. Multiplications of z values by known key multipliers wi are substituted by raising the s values to the power of these public multipliers. To achieve this properly, it is essential to limit the selection of base integer h as follows: |
(5) |
By Fermats Theorem:
(6) |
Hence
(7) |
(8) |
The exponents of h act as integer mod p It can be noted that this constraint still allows selection of p−1 which is another possibility working numbers for h. If h is raised correspondingly to the power of every part of formula 1, the following relationship is computed.
(9) |
(10) |
Formula 10 is a relationship among n + 2 different ss every of which is resulting from one of the n + 2 matching zs which demonstrate the relationship given in formula 1. Every user provided with a sum of n + 2 numbers of s can test if formula 10 is achieved. When it is achieved, then the n + 2 numbers of s and therefore their providers are real.
MUTUAL AUTHENTICATION
This application is more general knowing an exponent key distribution system with mutual authentication of all users. So in this application all users have equal situation.
Assume the total number of users is n, for i = 1 to n user i is published with two (x, z) pairs a transmission pair (xi1, zi1) and an authentication pair (xi2, zi2). From these the user can compute two (x, s) pairs, a transmission pair (xi1, si1) and an authentication pair (xi2, si2) .
The minimum number of operative users in a polynomial of degree n, is n + 1, if every of n + 1 operative users passes his transmission (x, s) pair, then every operative user will know n + 2 (x, s) pairs, by the n + 1 transmission pairs together with his own authentication pair. So every user individually can verify for satisfaction with formula 10 to authenticate the other users.
Having generated the authenticity of all the other users i, j can connect as in the Diffie-Hellman method employing the base number:
(11) |
In which i, j computes:
Note: that sj1 is publicly sent by j and zi1 is is private key.
(12) |
And j computes:
(13) |
Note: that si1 is publicly sent by i and zs is a private key.
By the security of the Diffie-Hellman method, it is computationally hard for any user other than i, j to solve gij. Once base numbers have been generated communicate among users, these connects can be employed if required to generate a net-wide base number. Once n + 1,s numbers are publicly known and any other s value can be computed from them, so that the same base key should not be reemployed later. To avoid this it is recommended that the base key must combine in certain way a time stamp with date.
Example: An example of the method explained in section above is given below. It employs small prime numbers to illustrate the rule of algorithm. According to Stinson (2006) a number of 150 or more decimal digits can be employed. Assume that the number of operative users is 3 out of a total of 5. Choose a prime number p = 29. Next q = g* p + 1 = 59 compute prime with g = 2. A program is employed to choose a private polynomial of degree 2 with coefficients in GF (29). Assume it chooses:
(14) |
Then, it chooses 10 ordinates x two for every of the 5 users. It computes privately from formula 14. The equivalent ordinates z employing the multiplicative inverse (Aboud, 2005) which is computed as follows:
The program then provides all users with records of each ones transmission pair x numbers (xi1s) and every user separately with his authentication pair x number (xi2) and his private z keys (zi1, zi2). The program then deletes its memory to erase the details of the polynomial coefficients it has selected.
Assume that users 1, 3, 5 determine to generate base numbers for communication among them. They choose a number a = 11 and from it compute the base key:
(15) |
Then every computes his own transmission pair xi1, si1, such that:
(16) |
And the authentication pair xi2, si2, such that:
(17) |
User 1 computes the authentication verification as follows. He computes wi numbers according to his own authentication ordinates, i.e., xi2 = 14. Thus
(18) |
(19) |
(20) |
Then user 1 computes employing formula 10 the value of his authentication s must take to calculate with the 3 transmitted ss as follows:
(21) |
Since this matches with his authentication, user 1 can be certain that user 3 and user 5 are definitely the other users. User 3 and user 5 every one carries out similar computations to check the individualities of the other two. Then for instance user 1 and user 3 can communicate employing the base number.
(22) |
Which user 1 computes as follows:
(23) |
Note that is publicly transmitted by user 3 and the key = 19 is the user 1 private key.
And user 3 computes as follows:
(24) |
Note that S11 is publicly transmitted by user 1 and the key = 23 is the user 3 private key.
Similarity the base numbers can be generated among user 1 and user 5 and among user 3 and user 5. Once this specific base key is employed its future utilize is no longer private. The z numbers however, hold their secrecy and can be reemployed with another base key.
In this method we assumed that the private z values are physically kept in the contributing stations. This makes the scheme vulnerable to detained stations, thus it maybe suitable to have certain mnemonic system to allow users to remember their private keys. For the base number exchange method, it is preferable that users remember two private keys. Though, a lesser degree of security is obtainable if just one is considered.
It is possible for one user to masquerade another in the authentication operation. However, there is no benefit to him acting this, since the intruder can not figure out the base number for communication. So it is essential that all authorizing stations trust one another, if not one authorizing station could obtain a benefit by creation it appears that a new authorized a transaction rather than itself. Alternatives of the Shamir secret sharing method are studied by (Kaliaperumal, 2003) which have their similarities in the scheme examined. These give better authority to certain parties than others. It is potential to change the scheme to employ polynomials in many variables. This can give benefits of overview in practical completion and of expanding the possible uses of the system.
It is easy to enhance the base number exchange method if the minimum number of operative users is 2. Corresponding to the suggested method f (x) is a polynomial with 2 private coefficients, so we can write:
(25) |
Each user has two pairs and can therefore, figure out w and h and therefore the private number of all other users. To prevent this, a polynomial of the following structure can be employed:
(26) |
We mean that one have 4 private coefficients. Every user is published with 3 (x, z) pairs, two for transmission and one for authentication. Prior to transmission every user has 3 (x, z) points on a polynomial with 4 private coefficients and thus can not be working out the coefficients or other users private keys. After transmission every user has 5 (x, s) pairs and can carry out the authentication verification by employ the formula 10.
It is possible to modify the scheme to employ polynomials in more than one parameter. This can give benefits of simplification in practical implementations and of expanding the possible users of the system.
This research is described the Shamir secret sharing scheme combined with the trap door characteristics of discrete logarithm as employed in the Diffie-Hellman secret exchange scheme. This combination permits the users components of a shared secret key to be broadcasted over a public means in a concealed type, so that the privacy of the components and the total shared number are protected. This denotes that the same private key can be employed repeatedly, on future times. This scheme can be employed in many statuses needing the co-operation of t users out of n. The example, given illustrating that the scheme can be employed to achieve mutually authenticated base number exchange between users.