CA2232936C - Implicit certificate scheme - Google Patents
Implicit certificate scheme Download PDFInfo
- Publication number
- CA2232936C CA2232936C CA 2232936 CA2232936A CA2232936C CA 2232936 C CA2232936 C CA 2232936C CA 2232936 CA2232936 CA 2232936 CA 2232936 A CA2232936 A CA 2232936A CA 2232936 C CA2232936 C CA 2232936C
- Authority
- CA
- Canada
- Prior art keywords
- entity
- public
- key
- gamma
- public key
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/3263—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3066—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
- H04L9/3073—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy involving algebraic varieties, e.g. elliptic or hyper-elliptic curves involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
- H04L9/321—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving a third party or a trusted authority
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Signal Processing (AREA)
- Computer Networks & Wireless Communication (AREA)
- Theoretical Computer Science (AREA)
- Mathematical Physics (AREA)
- Physics & Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Optimization (AREA)
- Computing Systems (AREA)
- Mathematical Analysis (AREA)
- General Physics & Mathematics (AREA)
- Algebra (AREA)
- Storage Device Security (AREA)
- Mobile Radio Communication Systems (AREA)
Abstract
A method of generating a 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: for each entity A, the CA selecting a unique identity I A distinguishing the entity A; generating a public key reconstruction public data .gamma.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, .gamma.A ) serves as A's implicit certificate; combining the implicit certificate information (I A, .gamma.A ) in accordance with a mathematical function F(.gamma.A , I A) to derive an entity information f; 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 .gamma.A and the identity I A relatively efficiently.
Description
IMPLICIT CERTIFICATE SCHEME
'fhis 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 problern, in cryptographic systems. The key agreement protocol allowed two parties never having inet 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, involvir-g 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:
I. A trusted server T selects an appropriate fixed public prime p and generator a of Zp .
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 = a' mod p, along with a, p.
'fhis 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 problern, in cryptographic systems. The key agreement protocol allowed two parties never having inet 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, involvir-g 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:
I. A trusted server T selects an appropriate fixed public prime p and generator a of Zp .
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 = a' mod p, along with a, p.
2. T assigns to each party A a unique name or identifying string IA and a random integer kA with gcd(kA, p-1) =1. T then computes PA = a"a mod p. PA is A's KEY
reconstruction public data, allowing other parties to compute (PA)a below.
reconstruction public data, allowing other parties to compute (PA)a below.
3. Using a suitable hash function h, T solves the following equation for a:
H(IA) = t.PA + kA a (mod p-1) 4. T securely transmits to A the pair (r,s) = (PA, a), which is T's ElGamal signature on IA. (a is A's private key for Diffie-Hellman key-agreement) 5. Any other party can then reconstruct A's Diffie-Hellman public key PA
entirely from publicly available information ((x, IA, u, PA, p) by computing:
PA = a"("'u-P" 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 ZP and its analog scalar multiplication of a point in E(Fq) 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 ZP, however these schemes are equally implementable in elliptic curve cryptosystems.
][n 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 IA distinguishing the entity A;
(b) generating a public key reconstruction public data yA 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 (IA, yA ) serves as A's implicit certificate;
(c) combining the implicit certificate information (IA, yA ) in accordance with a imathematical function F( yA , IA) to derive an entity information f;
(d) generating a private key a of the entity A by signing the entity informationf and transmitting the private key a to the entity A, whereby the entity A's public key may be reconstlucted from the public information, the generator yA and the identity IA relatively efficiently.
BRIEF DESCRIPTION OF THE DRAWINGS
Embodiments of the present invention will now be described by way of example only with reference to the accompanying drawings in which:-Figure 11 is a schematic representation of a first system configuration according to an embodiment of the present invention; and Figure 2 is a schematic representation of a second system configuration according to an embodijment in the present invention.
DETAI]LED DESCRIPTION OF A PREFERRED EMBODIMENT
Referring to Figure 1, a system with implicitly-certified public keys is shown generally by 10. "This system 10 includes a trusted third party CA and at least a pair of first and second correspondents A and B respectively. The correspondents A and B exchange information over a communication channel and each includes a cryptographic unit for performing visual finding/verification and encryption/decryption.
Referring back to Figure 1, the trusted party CA selects an appropriate prime p with p=tq+1 where q is a large prime and a generator a of order q. The CA selects a random integer c, with 1:5c<_ q-1 as its private key, then computes the public key P=ac mod p and publishes ((3,a, p, q).
Scheme 1:
1. For each party A, the CA choose a unique distinguished name or identity IA
(e.g., name, address, phone number), and a random integer CA with 1:5 cA <_ q-1. Then the CA computes yA=aC" mod p. (YA is the party A's public key reconstruction public data. The pair (IA, YA) serves as A's implicit certificate) 2. The CA selects a function f=F(IA, YA). For example, F(yA, IA )= yA+h(IA), or F(YA, IA )= h(YA+IA) where h is a secure hash function and solves the following equation for a, which is party A's private key. If a=0, then the CA chooses another CA
and re-solves the equation.
1 = ef + cAa(mod q) :3. The CA securely sends the triple (yA, a,IA) to A, which is CA's signature on IA.
Then a is A's private key;
YA is A's generator; and Y A(_acAa) is A's public key.
A publishes (a, IA, (3, yA, p, q) in the public domain.
4. Anyone can obtain party A's (ID-based) implicitly verifiable public key from the public domain by computing, Y n = a(3-f (mod p), thus deriving the public key from the above equation, which requires only one exponentiation operation.
Although everyone can reconstruct party A's public key from public data, this does not mean that the reconstructed public key y A has been certified. This scheme is more effective when it is combined with an application protocol that shows that party A has complete knowlecige of the corresponding private key. For example, with the MQV key-agreement scheme or with any signature scheme and particularly with an KCDSA (Korean Certificate based Digital Signature Algorithm). In general, this implicit certificate scheme can be used with any scheme, which is required to verify the certificate. This may be demonstrated by referring to the Digital Signature Algorithm (DSA) signature scheme.
13uppose Alice has a private key a, generator yA and publishes ((x, IA, (3, yA, p, q) in public domain. Now Alice wants to sign a message M using DSA.
Alice does the following:
1. randomly chooses k, computes r=y A(mod p);
2. computes e=sha-1(M);
3. computes s=k-1(e + ar) (mod p);
4. The signature on M is (r,s).
'Verifier does the following:
1. gets Alice's public data (a, IA, (3, YA, p, q) and reconstructs the public key dA=Y a =aR-r (mod p);
2. computes e=sha-1(M);
3. computes ul = es-1 (mod q) and U2 = rs-1 (mod q);
4. computes r' = yA 8A' modp;
5. if r=r', the signature is verified. At the same time Alice's (ID-based) public key is implicitly verified.
'The pair (IA, YA) serves as certificate of Alice. Reconstructing the public key serves as implicit verification when the application protocol results in a valid verification. Recall that obtainirig the public key needs only one exponentiation operation.
In an alternate embodiment, the scheme can be generalized to most ElGamal signature schemes by modifying the signing equation appropriately. In the following section, we give some examples.
Scheme 2:
'The CA uses the signing equation 1=ca+c,kf (mod q). The CA securely sends the triple (YA, a, I,k) to A, then a is A's private key, 0 is A's generator and (3a is A's public key. A publishes (a, IA, P~, yA, p, q) in public domain. Anyone can obtain A's (ID-based) implicitly certified public key frorn the public domain by computing (3a =ay AJ (mod p) For this scheme, each user has the same generator (3 which is the CA's public key.
Scheme 3:
'fhe CA uses the signing equation a = cf + CA (mod q). The CA securely sends the triple (y,4, a, IA) to A, then a is A's private key, a is A's generator and aa is A's public key. A
publishes (a, IA, (3, YA, p, q) in the public domain. Anyone can obtain A's (ID-based) implicitly certified public key from the public domain by computing aa = RfYA(mod p) For this scheme, each user including the CA has the same generator a.
Scheme 4:
The CA uses the signing equation a- CAf + c (mod q). The CA securely sends the triple (Y,A, a, IA) to A, then a is A's private key, a is A's generator and aa is A's public key. A
publishes (a, IA, (3, YA, p, q) in the public domain. Anyone can obtain A's (ID-based) implicitly certified public key from the public domain by computing aa = Y a R (mod p) For this scheme, each user including CA has same generator a.
l[n the above schemes the user or party A does not have freedom to choose its own private key. The following schemes as illustrated in figure 2 both the CA and the user control the user's private key but only the user knows its private key.
Scheme 1':
A first randomly chooses an integer k and computes ak, then sends it to the CA. The CA
computes yA = ak( -' mod p, and solves the following signing equation for kA
1 = cf + cAkA (mod q).
Then the CA computes yA = aC, mod p and sends the triple (Y A, kA, IA) to A. A
computes a=kAk-1 (mod q) and YA =(Y A)k(mod p). Then a is A's private key, YA
is A's generator and y A is A's public key. A publishes (a, IA, 0, yA, p, q) in the public domain. Anyone can obtain A's (ID-based) implicitly certified public key from the public domain by computing Y A = a(3-f(mod p) Scheme 3':
H(IA) = t.PA + kA a (mod p-1) 4. T securely transmits to A the pair (r,s) = (PA, a), which is T's ElGamal signature on IA. (a is A's private key for Diffie-Hellman key-agreement) 5. Any other party can then reconstruct A's Diffie-Hellman public key PA
entirely from publicly available information ((x, IA, u, PA, p) by computing:
PA = a"("'u-P" 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 ZP and its analog scalar multiplication of a point in E(Fq) 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 ZP, however these schemes are equally implementable in elliptic curve cryptosystems.
][n 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 IA distinguishing the entity A;
(b) generating a public key reconstruction public data yA 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 (IA, yA ) serves as A's implicit certificate;
(c) combining the implicit certificate information (IA, yA ) in accordance with a imathematical function F( yA , IA) to derive an entity information f;
(d) generating a private key a of the entity A by signing the entity informationf and transmitting the private key a to the entity A, whereby the entity A's public key may be reconstlucted from the public information, the generator yA and the identity IA relatively efficiently.
BRIEF DESCRIPTION OF THE DRAWINGS
Embodiments of the present invention will now be described by way of example only with reference to the accompanying drawings in which:-Figure 11 is a schematic representation of a first system configuration according to an embodiment of the present invention; and Figure 2 is a schematic representation of a second system configuration according to an embodijment in the present invention.
DETAI]LED DESCRIPTION OF A PREFERRED EMBODIMENT
Referring to Figure 1, a system with implicitly-certified public keys is shown generally by 10. "This system 10 includes a trusted third party CA and at least a pair of first and second correspondents A and B respectively. The correspondents A and B exchange information over a communication channel and each includes a cryptographic unit for performing visual finding/verification and encryption/decryption.
Referring back to Figure 1, the trusted party CA selects an appropriate prime p with p=tq+1 where q is a large prime and a generator a of order q. The CA selects a random integer c, with 1:5c<_ q-1 as its private key, then computes the public key P=ac mod p and publishes ((3,a, p, q).
Scheme 1:
1. For each party A, the CA choose a unique distinguished name or identity IA
(e.g., name, address, phone number), and a random integer CA with 1:5 cA <_ q-1. Then the CA computes yA=aC" mod p. (YA is the party A's public key reconstruction public data. The pair (IA, YA) serves as A's implicit certificate) 2. The CA selects a function f=F(IA, YA). For example, F(yA, IA )= yA+h(IA), or F(YA, IA )= h(YA+IA) where h is a secure hash function and solves the following equation for a, which is party A's private key. If a=0, then the CA chooses another CA
and re-solves the equation.
1 = ef + cAa(mod q) :3. The CA securely sends the triple (yA, a,IA) to A, which is CA's signature on IA.
Then a is A's private key;
YA is A's generator; and Y A(_acAa) is A's public key.
A publishes (a, IA, (3, yA, p, q) in the public domain.
4. Anyone can obtain party A's (ID-based) implicitly verifiable public key from the public domain by computing, Y n = a(3-f (mod p), thus deriving the public key from the above equation, which requires only one exponentiation operation.
Although everyone can reconstruct party A's public key from public data, this does not mean that the reconstructed public key y A has been certified. This scheme is more effective when it is combined with an application protocol that shows that party A has complete knowlecige of the corresponding private key. For example, with the MQV key-agreement scheme or with any signature scheme and particularly with an KCDSA (Korean Certificate based Digital Signature Algorithm). In general, this implicit certificate scheme can be used with any scheme, which is required to verify the certificate. This may be demonstrated by referring to the Digital Signature Algorithm (DSA) signature scheme.
13uppose Alice has a private key a, generator yA and publishes ((x, IA, (3, yA, p, q) in public domain. Now Alice wants to sign a message M using DSA.
Alice does the following:
1. randomly chooses k, computes r=y A(mod p);
2. computes e=sha-1(M);
3. computes s=k-1(e + ar) (mod p);
4. The signature on M is (r,s).
'Verifier does the following:
1. gets Alice's public data (a, IA, (3, YA, p, q) and reconstructs the public key dA=Y a =aR-r (mod p);
2. computes e=sha-1(M);
3. computes ul = es-1 (mod q) and U2 = rs-1 (mod q);
4. computes r' = yA 8A' modp;
5. if r=r', the signature is verified. At the same time Alice's (ID-based) public key is implicitly verified.
'The pair (IA, YA) serves as certificate of Alice. Reconstructing the public key serves as implicit verification when the application protocol results in a valid verification. Recall that obtainirig the public key needs only one exponentiation operation.
In an alternate embodiment, the scheme can be generalized to most ElGamal signature schemes by modifying the signing equation appropriately. In the following section, we give some examples.
Scheme 2:
'The CA uses the signing equation 1=ca+c,kf (mod q). The CA securely sends the triple (YA, a, I,k) to A, then a is A's private key, 0 is A's generator and (3a is A's public key. A publishes (a, IA, P~, yA, p, q) in public domain. Anyone can obtain A's (ID-based) implicitly certified public key frorn the public domain by computing (3a =ay AJ (mod p) For this scheme, each user has the same generator (3 which is the CA's public key.
Scheme 3:
'fhe CA uses the signing equation a = cf + CA (mod q). The CA securely sends the triple (y,4, a, IA) to A, then a is A's private key, a is A's generator and aa is A's public key. A
publishes (a, IA, (3, YA, p, q) in the public domain. Anyone can obtain A's (ID-based) implicitly certified public key from the public domain by computing aa = RfYA(mod p) For this scheme, each user including the CA has the same generator a.
Scheme 4:
The CA uses the signing equation a- CAf + c (mod q). The CA securely sends the triple (Y,A, a, IA) to A, then a is A's private key, a is A's generator and aa is A's public key. A
publishes (a, IA, (3, YA, p, q) in the public domain. Anyone can obtain A's (ID-based) implicitly certified public key from the public domain by computing aa = Y a R (mod p) For this scheme, each user including CA has same generator a.
l[n the above schemes the user or party A does not have freedom to choose its own private key. The following schemes as illustrated in figure 2 both the CA and the user control the user's private key but only the user knows its private key.
Scheme 1':
A first randomly chooses an integer k and computes ak, then sends it to the CA. The CA
computes yA = ak( -' mod p, and solves the following signing equation for kA
1 = cf + cAkA (mod q).
Then the CA computes yA = aC, mod p and sends the triple (Y A, kA, IA) to A. A
computes a=kAk-1 (mod q) and YA =(Y A)k(mod p). Then a is A's private key, YA
is A's generator and y A is A's public key. A publishes (a, IA, 0, yA, p, q) in the public domain. Anyone can obtain A's (ID-based) implicitly certified public key from the public domain by computing Y A = a(3-f(mod p) Scheme 3':
A first randomly chooses an integer k and computes ak, then sends it to the CA. Now CA computes YA = akaCA (mod p), solves the signing equation for kA
kA = cf + cA(mod q) '.Chen the CA computes y (ak)CA (mod p) and sends the triple (Y A, kA, IA) to A. A
computes YA =(Y A)k-1 ak (mod p). Then a = kA+k (mod q) is A's private key, a is A's generator and aa is A's public key. A publishes (a, IA, (3, YA, p, q) in public domain.
Anyone can obtain A's (ID.-based) implicitly certified public key from the public domain by computing aa = PYA(mod p) The security of the new scheme depends on the signing equations. For example, in scheme 1, the signing equation is 1 = cf+ cAa (mod q). (1) We are going to show that for some choose of the one way function F(YA, IA), the new scheme 1 is equivalent to DSA.
Let's consider CA using DSA signing equation to sign A's identity IA. First CA
randomly choose a cA and compute YA= acA mod p, then CA uses a secure hash function h to computer h(IA), finally CA solves following equation for s.
h(IA) = cYA+ cAs (mod q). (2) Now (YA, s) is CA's signature on IA.
Multiply equation (2) by h(IA)-l we got 1 CYA h(I,4)-1 + cAsh(IA)-1 (mod q) Let F(YA, IA) = YA h(IA)-1 and replace sh(IA)-l by a in above equation we got the equation (1).
Obviously, equation (2) is equivalent to equation (1) if F(YA, IA) = YA h(IA)-1. That means, if anyone can break the scheme using the signing equation (1), then he/she can break the scheme using the signing equation (2) which is DSA scheme.
Heuristic arguments suggest our new schemes are secure for suitable choice of F(YA, IA), where F(YA, IA) = YA h(IA) or F(YA, IA) = h(YA, IA). Note F(YA, IA) can be some other format, for example when IA is small, say 20 bits, but q is more than 180 bits, then we can use F(yA, IA)=YA +
IA. A disadvantage of the new schemes is all users and CA use the same field size. However this is the way that all ID-based implicitly certified public key schemes work, for example, Girault's RSA based Diffie-Hellman public key agreement scheme.
Applications The following examples are illustrated with respect to scheme 3 (or Scheme 3') as CA's signing equation since everyone shares the same generator in this scheme.
Setup:
Alice has a private key a, generator a and publishes (a, IA, (3, yA, p, q) in the public domain.
Bob has a private key b, a generator a and publishes (a, IA, (3, yA, p, q) in the public domain.
A key agreement scheme (MTI/C0).
We use MTI/C0 key agreement protocol to demonstrate how to use our new scheme.
Assume Alice and Bob want to perform a key exchange.
The MT'I/CO protocol 1. Alice reconstructs Bob's public key a" =8F('"B'IB)yB , and randomly chooses an integer x and computes (ab)", then sends it to Bob.
2. Bob reconstructs Alice's public key a =flF(r"''A)yA and randomly chooses an integer y and computes (aa)Y, then sends it to Alice.
3. Alice computes the shared key KA =(a'ry' )" , = ax'' 4. l3ob computes the shared key KR =(anx ) yn-' = aXy This is a two-pass protocol. With the implicit certificate scheme of the present invention, each party only does three exponentiation operations to get the shared key while at the same time performing an authentication key agreement and implicit public key verification.
Signcryption Assume Bob wants to send a signed and encrypted message M to Alice:
Bob does following:
1. reconstructs Alice's public key a =/j''(Ya''A'y,, mod p 2. randomly chooses an integer x and computes a key r=(aa)" (mod p) 3. computes C=DESr(M) 4. computes e=hash(C 11 IA) 5. computes s=be+x(mod q) 6. sends the pair (C,s) to Alice, thus C is the encrypted message and s is the signature.
To recover the message Alice does following:
1. computes e=hash(C 11 IA) 2. reconstructs Bob's public key ab ='8F(YB''B) yB mod p 3. computes aas(ab)-ac (mod p) which is r 4. decrypts the message M=DESr(C) 5. check for redundancy Thus, Bob only does two exponentiation operations and Alice does three exponentiation operations. But Alice and Bob are both confident of each others authentication. Note that for this scheme, the message M must have some redundancy or pattern.
In conclusion it may be seen that the present scheme, when combined with an application protocol for which the user's private key must be used directly in computation, provides an implicitly certified ID-based public key of the user. These schemes can also be used for a Key Authentication Center (KAC) to distribute implicitly certified public keys to users.
While the invention has been described in connection with specific embodiments thereof and in specific uses, various modifications thereof will occur to those skilled in the art without departing from the spirit of the invention as set forth in the appended claims. For example in the above description of preferred embodiments, use is made of multiplicative notation, however the method of the subject invention may be equally well described utilizing additive notation. It is well known for example that elliptic curve algorithm embodied in the ECDSA is equivalent of the DSA and that the elliptic curve analog of a discrete log logorithm algorithm that is usually described in a setting of, Fp the multiplicative group of the integers modulo a prime. There is a correspondence between the elements and operations of the group Fn and the elliptic curve group E(Fq). Furthermore, this signature technique is equally well applicable to functions performed in a field defined over FP and F2- It is also to be noted that the DSA signature scheme described above is a specific instance of the ElGamal generalized signature scheme which is known in the art and thus the present techniques are applicable thereto.
kA = cf + cA(mod q) '.Chen the CA computes y (ak)CA (mod p) and sends the triple (Y A, kA, IA) to A. A
computes YA =(Y A)k-1 ak (mod p). Then a = kA+k (mod q) is A's private key, a is A's generator and aa is A's public key. A publishes (a, IA, (3, YA, p, q) in public domain.
Anyone can obtain A's (ID.-based) implicitly certified public key from the public domain by computing aa = PYA(mod p) The security of the new scheme depends on the signing equations. For example, in scheme 1, the signing equation is 1 = cf+ cAa (mod q). (1) We are going to show that for some choose of the one way function F(YA, IA), the new scheme 1 is equivalent to DSA.
Let's consider CA using DSA signing equation to sign A's identity IA. First CA
randomly choose a cA and compute YA= acA mod p, then CA uses a secure hash function h to computer h(IA), finally CA solves following equation for s.
h(IA) = cYA+ cAs (mod q). (2) Now (YA, s) is CA's signature on IA.
Multiply equation (2) by h(IA)-l we got 1 CYA h(I,4)-1 + cAsh(IA)-1 (mod q) Let F(YA, IA) = YA h(IA)-1 and replace sh(IA)-l by a in above equation we got the equation (1).
Obviously, equation (2) is equivalent to equation (1) if F(YA, IA) = YA h(IA)-1. That means, if anyone can break the scheme using the signing equation (1), then he/she can break the scheme using the signing equation (2) which is DSA scheme.
Heuristic arguments suggest our new schemes are secure for suitable choice of F(YA, IA), where F(YA, IA) = YA h(IA) or F(YA, IA) = h(YA, IA). Note F(YA, IA) can be some other format, for example when IA is small, say 20 bits, but q is more than 180 bits, then we can use F(yA, IA)=YA +
IA. A disadvantage of the new schemes is all users and CA use the same field size. However this is the way that all ID-based implicitly certified public key schemes work, for example, Girault's RSA based Diffie-Hellman public key agreement scheme.
Applications The following examples are illustrated with respect to scheme 3 (or Scheme 3') as CA's signing equation since everyone shares the same generator in this scheme.
Setup:
Alice has a private key a, generator a and publishes (a, IA, (3, yA, p, q) in the public domain.
Bob has a private key b, a generator a and publishes (a, IA, (3, yA, p, q) in the public domain.
A key agreement scheme (MTI/C0).
We use MTI/C0 key agreement protocol to demonstrate how to use our new scheme.
Assume Alice and Bob want to perform a key exchange.
The MT'I/CO protocol 1. Alice reconstructs Bob's public key a" =8F('"B'IB)yB , and randomly chooses an integer x and computes (ab)", then sends it to Bob.
2. Bob reconstructs Alice's public key a =flF(r"''A)yA and randomly chooses an integer y and computes (aa)Y, then sends it to Alice.
3. Alice computes the shared key KA =(a'ry' )" , = ax'' 4. l3ob computes the shared key KR =(anx ) yn-' = aXy This is a two-pass protocol. With the implicit certificate scheme of the present invention, each party only does three exponentiation operations to get the shared key while at the same time performing an authentication key agreement and implicit public key verification.
Signcryption Assume Bob wants to send a signed and encrypted message M to Alice:
Bob does following:
1. reconstructs Alice's public key a =/j''(Ya''A'y,, mod p 2. randomly chooses an integer x and computes a key r=(aa)" (mod p) 3. computes C=DESr(M) 4. computes e=hash(C 11 IA) 5. computes s=be+x(mod q) 6. sends the pair (C,s) to Alice, thus C is the encrypted message and s is the signature.
To recover the message Alice does following:
1. computes e=hash(C 11 IA) 2. reconstructs Bob's public key ab ='8F(YB''B) yB mod p 3. computes aas(ab)-ac (mod p) which is r 4. decrypts the message M=DESr(C) 5. check for redundancy Thus, Bob only does two exponentiation operations and Alice does three exponentiation operations. But Alice and Bob are both confident of each others authentication. Note that for this scheme, the message M must have some redundancy or pattern.
In conclusion it may be seen that the present scheme, when combined with an application protocol for which the user's private key must be used directly in computation, provides an implicitly certified ID-based public key of the user. These schemes can also be used for a Key Authentication Center (KAC) to distribute implicitly certified public keys to users.
While the invention has been described in connection with specific embodiments thereof and in specific uses, various modifications thereof will occur to those skilled in the art without departing from the spirit of the invention as set forth in the appended claims. For example in the above description of preferred embodiments, use is made of multiplicative notation, however the method of the subject invention may be equally well described utilizing additive notation. It is well known for example that elliptic curve algorithm embodied in the ECDSA is equivalent of the DSA and that the elliptic curve analog of a discrete log logorithm algorithm that is usually described in a setting of, Fp the multiplicative group of the integers modulo a prime. There is a correspondence between the elements and operations of the group Fn and the elliptic curve group E(Fq). Furthermore, this signature technique is equally well applicable to functions performed in a field defined over FP and F2- It is also to be noted that the DSA signature scheme described above is a specific instance of the ElGamal generalized signature scheme which is known in the art and thus the present techniques are applicable thereto.
Claims
PRIVILEGE IS CLAIMED ARE DEFINED AS FOLLOWS:
1. A method of generating a public key in a secure digital communication system, having at least one trusted entity CA and subscriber entities A, said method comprising the steps of:
(a) for each entity A, said CA selecting a unique identity I A distinguishing said entity A;
(b) generating a public key reconstruction public data .gamma.A of entity A by mathematically combining a generator of said trusted party CA with a private value of said entity A, such that said pair (I A, .gamma.A ) serves as A's implicit certificate;
(c) combining said implicit certificate information (I A, .gamma.A ) in accordance with a mathematical function F(.gamma.A , I A) to derive an entity information f;
(d) generating a private key a of said entity A by signing said entity information f and transmitting said private key a to said entity A, whereby said entity A's public key may be reconstructed from said public information, said generator .gamma.A and said identity I A
relatively efficiently.
(a) for each entity A, said CA selecting a unique identity I A distinguishing said entity A;
(b) generating a public key reconstruction public data .gamma.A of entity A by mathematically combining a generator of said trusted party CA with a private value of said entity A, such that said pair (I A, .gamma.A ) serves as A's implicit certificate;
(c) combining said implicit certificate information (I A, .gamma.A ) in accordance with a mathematical function F(.gamma.A , I A) to derive an entity information f;
(d) generating a private key a of said entity A by signing said entity information f and transmitting said private key a to said entity A, whereby said entity A's public key may be reconstructed from said public information, said generator .gamma.A and said identity I A
relatively efficiently.
Priority Applications (17)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA 2232936 CA2232936C (en) | 1998-03-23 | 1998-03-23 | Implicit certificate scheme |
| CA2235359A CA2235359C (en) | 1998-03-23 | 1998-04-20 | Implicit certificate scheme with ca chaining |
| DE69918818T DE69918818T2 (en) | 1998-03-23 | 1999-03-23 | A method for generating a public key in a secure digital communication system and implicit certificate |
| PCT/CA1999/000244 WO1999049612A1 (en) | 1998-03-23 | 1999-03-23 | Implicit certificate scheme |
| EP99908723A EP1066699B1 (en) | 1998-03-23 | 1999-03-23 | Method of generating a public key in a secure digital communication system and implicit certificate |
| AU28235/99A AU758044B2 (en) | 1998-03-23 | 1999-03-23 | Implicit certificate scheme |
| IL13866099A IL138660A0 (en) | 1998-03-23 | 1999-03-23 | Implicit certificate scheme |
| JP2000538463A JP4588874B2 (en) | 1998-03-23 | 1999-03-23 | Inherent certificate method |
| US09/667,819 US6792530B1 (en) | 1998-03-23 | 2000-09-22 | Implicit certificate scheme |
| US10/921,870 US7391868B2 (en) | 1998-03-23 | 2004-08-20 | Implicit certificate scheme |
| US12/137,276 US7653201B2 (en) | 1998-03-23 | 2008-06-11 | Implicit certificate scheme |
| US12/627,906 US8270601B2 (en) | 1998-03-23 | 2009-11-30 | Implicit certificate scheme |
| JP2010023602A JP5247740B2 (en) | 1998-03-23 | 2010-02-04 | Inherent certificate method |
| US13/527,060 US8705735B2 (en) | 1998-03-23 | 2012-06-19 | Implicit certificate scheme |
| US13/527,007 US8712042B2 (en) | 1998-03-23 | 2012-06-19 | Implicit certificate scheme |
| JP2013038451A JP5702813B2 (en) | 1998-03-23 | 2013-02-28 | Inherent certificate method |
| US14/257,781 US20140229730A1 (en) | 1998-03-23 | 2014-04-21 | Implicit certificate scheme |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA 2232936 CA2232936C (en) | 1998-03-23 | 1998-03-23 | Implicit certificate scheme |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CA2232936A1 CA2232936A1 (en) | 1999-09-23 |
| CA2232936C true CA2232936C (en) | 2008-10-21 |
Family
ID=29409501
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CA 2232936 Expired - Lifetime CA2232936C (en) | 1998-03-23 | 1998-03-23 | Implicit certificate scheme |
Country Status (1)
| Country | Link |
|---|---|
| CA (1) | CA2232936C (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8457307B2 (en) | 2007-07-17 | 2013-06-04 | Certicom Corp. | Method and system for generating implicit certificates and applications to identity-based encryption (IBE) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP2276196B1 (en) | 2000-06-09 | 2014-09-03 | Certicom Corp. | Method for the Application of Implicit Signature Schemes |
-
1998
- 1998-03-23 CA CA 2232936 patent/CA2232936C/en not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8457307B2 (en) | 2007-07-17 | 2013-06-04 | Certicom Corp. | Method and system for generating implicit certificates and applications to identity-based encryption (IBE) |
Also Published As
| Publication number | Publication date |
|---|---|
| CA2232936A1 (en) | 1999-09-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CA2235359C (en) | Implicit certificate scheme with ca chaining | |
| US10530585B2 (en) | Digital signing by utilizing multiple distinct signing keys, distributed between two parties | |
| US8522012B2 (en) | Method for the application of implicit signature schemes | |
| US7036015B2 (en) | Verification protocol | |
| JP4307589B2 (en) | Authentication protocol | |
| CA2232936C (en) | Implicit certificate scheme |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EEER | Examination request | ||
| MKEX | Expiry |
Effective date: 20180323 |