Digital certificates

• US 7,340,606 B2
• Filed: 12/29/2003
• Issued: 03/04/2008
• Est. Priority Date: 06/23/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: NDS Limited (Cisco Systems, Inc.)
• Inventors: Kipnis, Aviad, Shen-Orr, Chaim D., Halperin, Victor, Belenky, Yaacov
• Primary Examiner(s): Sheikh; Ayaz
• Assistant Examiner(s): Chai; Longbit
• Application Number:
  US10/545,737
• Publication Number:
  US 20060107053A1
• Time in Patent Office: 1,527 Days
• Field of Search: 713/175
• US Class Current: 713/175
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823

Abstract

A method for producing a certificate, the certificate including data, the method including choosing a seed s, the seed s including a result of applying a function H to the data, generating a key pair (E,D), such that E=F(s,t), F being a publicly known function, and including s and t in the certificate. Related methods, and certificates produced by the various methods, are also described.

Claims

1. A method for producing a compressed form public key delivery certificate, the compressed form public key delivery certificate comprising data, the method comprising:

choosing a seed s, the seed s comprising a result of applying a function H to the data;

generating a modulus N, wherein;

the modulus N is generated by a scattering method L, a function R and the seed s;

N is generated, in part, by scattering bits of R(s) throughout N using the scattering method L; and

all bits of N other than those scattered by the scattering method L are denoted by t;

generating a key pair (E,D), such that E=F(s,t), D being a private key, E being a public key, F being a publicly known function; and

producing the compressed form public key delivery certificate including the public key E in compressed form, by including the s and the t in the certificate instead of the public key E,

wherein the s and the t together are shorter than E and,

wherein the public key E is generable from the s and the t.

2. The method according to claim 1 and wherein the including the s and the t in the certificate comprises:

including the s concatenated with the t in the certificate.

3. The method according to claim 1 and wherein the function H comprises a hash function.

4. The method according to claim 1 and wherein the function H comprises a checksum function.

5. The method according to claim 1 and wherein the function H comprises adding redundancy to the data.

6. The method according to claim 1 and wherein the R(s) comprises data associated with an owner of the certificate.

7. The method according to claim 1 and wherein N comprises an RSA modulus.

8. The method according to claim 7 and wherein L comprises applying a Lenstra, Lenstra and Lovasz (LLL) method to a lattice.

9. The method according to claim 8 and wherein the lattice is defined, in part, by a generalized pattern G.

10. The method according to claim 9 and wherein the lattice comprises:

V₁=(2^2n+L1 0 . . . 0 0

     0)

V₂=(0 2^2n+L2 . . . 0 0

     0)

. . .

V_k=(0 0 . . . 2^2n+Lk 0

     0)

V_k+1=(2<sup>2n−

S1+L1</sup>p 2<sup>2n−

S2+L2</sup>p . . . 2<sup>2n−

Sk+Lk</sup>p 2<sup>n+x−

z</sup> 0)

V_k+2=(2²ⁿ(r₁+0.5) 2²ⁿ(r₂+0.5) . . . 2²ⁿ(r_k+0.5) 0 2²ⁿ)

and wherein;

n, x, z are integers, and

S1, . . . , Sk are position numbers of contiguous groups of symbols “

*”

in a generalized 2n-bit pattern G, where positions are numbered from the least significant (0) to the most significant (2n−

1), and S1≧

S2≧

. . . ≧

Sk, and

L1, . . . , Lk are lengths of the contiguous groups, numbered correspondingly to the contiguous groups, and

p is a (n−

x)-bit prime, and

R is a function that expands the s to R(s)=r1∥

r2∥

. . . ∥

rk, ∥

denoting concatenation, such that, for each i, ri has a length equal to Li.

12. The method according to claim 6 and wherein the data comprises an owner identifier.

11. A compressed form public key delivery certificate produced by a method comprising:

providing data for inclusion in the compressed form public key certifcate;

choosing a seed s, the seed s comprising a result of applying a function H to the data;

generating a modulus N, wherein;

the modulus N is generated by a scattering method L, a function R and the seed s;

N is generated, in part, by scattering bits of R(s) throughout N using the scattering method L; and

all bits of N other than those scattered by the scattering method L are denoted by t;

generating a key pair (E,D), such that E=F(s,t), D being a private key, E being a public key, F being a publicly known function; and

producing the compressed form public key delivery certificate including the public key E in compressed form, by including the s and the t in the certificate instead of the public key E,

wherein the s and the t together are shorter than E and,

wherein the public key E is generable from the s and the t.