Granted Patent B2

US 7,340,606 · App. 10/545,737 · Granted Mar 4, 2008

Abstract

Claims (44)

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 1 =(2 2n+L1 0 . . . 0 0 0)

V 2 =(0 2 2n+L2 . . . 0 0 0)

. . .

V k =(0 0 . . . 2 2n+Lk 0 0)

V k+1 =(2 2n−S1+L1 p 2 2n−S2+L2 p . . . 2 2n−Sk+Lk p 2 n+x−z 0)

V k+2 =(2 2n ( r 1 +0.5) 2 2n ( r 2 +0.5) . . . 2 2n ( r k +0.5) 0 2 2n )

and wherein:

n, x, z are integers, and

S 1 , . . . , 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 S 1 ≧S 2 ≧ . . . ≧Sk, and

L 1 , . . . , 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)=r 1 ∥r 2 ∥ . . . ∥rk, ∥ denoting concatenation, such that, for each i, ri has a length equal to Li.

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.

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

Assignments (8)