Implicit certificate scheme

Details Implicit certificate scheme Implicit certificate scheme

2000-09-22

2004-09-14

Barrón, Gilberto (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Central trusted authority provides computer authentication

C380S028000, C380S030000, C380S279000

Reexamination Certificate

active

06792530

ABSTRACT:

This invention relates to key distribution schemes for transfer and authentication of encryption keys.
BACKGROUND OF THE INVENTION
Diffie-Hellman key agreement provided the first practical solution to the key distribution problem, in cryptographic systems. The key agreement protocol allowed two parties never having met in advance or shared key material to establish a shared secret by exchanging messages over an open (unsecured) channel. The security rests on the intractability of the Diffie-Hellman problem and the related problem of computing discrete logarithms.
With the advent of the Internet and such like the requirement for large-scale distribution of public keys and public key certificates are becoming increasingly important. Public-key certificates are a vehicle by which public keys may be stored, distributed or forwarded over unsecured media without danger of undetectable manipulation. The objective is to make one parties' public key available to others such that its authenticity and validity are verifiable.
A public-key certificate is a data structure consisting of a data part and a signature part. The data part contains cleartext data including as a minimum, public key and a string identifying the party to be associated therewith. The signature part consists of the digital signature of a certification authority (CA) over the data part, thereby binding the entities identity to the specified public key. The CA is a trusted third party whose signature on the certificate vouches for the authenticity of the public key bound to the subject entity.
Identity-based systems (ID-based system) resemble ordinary public-key systems, involving a private transformation and a public transformation, but parties do not have explicit public keys as before. Instead, the public key is effectively replaced by a party's publicly available identity information (e.g. name or network address). Any publicly available information, which uniquely identifies the party and can be undeniably associated with the party, may serve as identity information.
An alternate approach to distributing public keys involves implicitly certified public keys. Here explicit user public keys exist, but they must be reconstructed rather than transported by public-key certificates as in certificate based systems. Thus implicitly certified public keys may be used as an alternative means for distributing public keys (e.g. Diffie-Hellman keys).
An example of an implicitly certified public key mechanism is known as Gunther's implicitly-certified (ID-based) public key method. In this method:
1. A trusted server T selects an appropriate fixed public prime p and generator &agr; of Z
p
*. T selects a random integer t, with 1≦t≦p−2 and gcd(t, p−1)=1, as its private key, and publishes its public key u=&agr;
t
mod p, along with &agr;, p.
2. T assigns to each party A a unique name or identifying string I
A
and a random integer k
A
with gcd(k
A
, p−1)=1. T then computes P
A
=&agr;
k
A
mod p. P
A
is A's KEY reconstruction public data, allowing other parties to compute (P
A
)
a
below.
3. Using a suitable hash function h, T solves the following equation for a:
H
(
I
A
)≡
t.P
A
+k
A
a
(mod
p
−1)
4. T securely transmits to A the pair (r,s)=(P
A
, a), which is T's ElGamal signature on I
A
. (a is A's private key for Diffie-Hellman key-agreement)
5. Any other party can then reconstruct A's Diffie-Hellman public key P
A
a
entirely from publicly available information (&agr;, I
A
, u, P
A
, p) by computing:
P
A
a
≡&agr;
h(I
A
)
u
−P
A
mod
p
Thus for discrete logarithm problems, signing a certificate needs one exponentiation operation, but reconstructing the ID-based implicitly-verifiable public key needs two exponentiations. It is known that exponentiation in the group Z
p
* and its analog scalar multiplication of a point in E(F
q
) is computationally intensive. For example an RSA scheme is extremely slow compared to elliptic curve systems. However despite the resounding efficiency of EC systems over RSA type systems this is still a problem particularly for computing devices having limited computing power such as “smart cards”, pagers and such like.
SUMMARY OF THE INVENTION
The present invention seeks to provide an efficient ID-based implicit certificate scheme, which provides improved computational speeds over existing schemes. For convenience, we describe the schemes over Z
p
, however these schemes are equally implementable in elliptic curve cryptosystems.
In accordance with this invention there is provided a method of generating an identity-based public key in a secure digital communication system, having at least one trusted entity CA and subscriber entities A, the method comprising the steps of:
(a) for each entity A, the CA selecting a unique identity I
A
distinguishing the entity A;
(b) generating a public key reconstruction public data &ggr;
A
of entity A by mathematically combining a generator of the trusted party CA with a private value of the entity A, such that the pair (I
A
, &ggr;
A
) serves as A's implicit certificate;
(c) combining the implicit certificate information (I
A
, &ggr;
A
) in accordance with a mathematical function F(&ggr;
A
, I
A
) to derive an entity information f;
(d) generating a private key a of the entity A by signing the entity information f and
transmitting the private key a to the entity A, whereby the entity A's public key may be reconstructed from the public information, the generator &ggr;
A
and the identity I
A
relatively efficiently.
In accordance with a further embodiment of the invention there is provided a public key certificate comprising a plurality of public keys having different bit strengths and wherein one of the public keys is an implicitly certified public key.


REFERENCES:
patent: 678134 (1991-07-01), None
patent: 0807911 (1997-11-01), None
H. Danisch, “RFC 1824”, 1995, pp. 5.*
M. Girault, “Self-certified public keys”, LNCS 547, Advances in Cryptology—Eurocrypt '91, Springer, pp. 490-497.*
C. Gunther, “An Identity-Based Key-Exchange Protocol”, LNCS 434, Advances in Crytology—Eurocrypt '89, Springer, pp. 29-37.*
A. Shamir, Identity-Based Cryptosystems And Signature Schemes, LNCS 196, Advances in Cryptology—Crypto '84, Springer, pp. 47-53.*
Alfred J. Menezes and Scott A. Vanstone, “Elliptic Curve Cryptosystems and Their Implementation”, Journal of Cryptology, International Associattion for Cryptologic Research, 1993, pp. 209-224.
Holger Petersen and Patrick Horster, “Self-certified keys—Concepts and Applications”, Ecole Normale Superieure in Paris and The University of Klagenfurt in Austria, 1997, pp. 1-15.

Affiliated with

Also associated with

Rating

Implicit certificate scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Implicit certificate scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implicit certificate scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3242182