Digital certificates
View Patent ↗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.
1. A method for producing a certificate, the certificate comprising data, the method comprising:
generating a modulus N by a computer programmed to generate the modulus N by a scattering method L, a function R and a seed s, where
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 R(s) are denoted by t;
generating a key pair (E,D) by the computer, which is programmed to generate the 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 certificate, including the public key E in compressed form by the computer, which is programmed to include the s and the t in the certificate instead of the public key E,
wherein the s and the t together are shorter than the 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 s concatenated with t in the certificate.
3. The method according to claim 1 and wherein the R(s) comprises data associated with an owner of the certificate.
4. The method according to claim 3 and wherein the data comprises an owner identifier.
5. The method according to claim 1 and wherein N comprises an RSA modulus.
6. The method according to claim 5 and wherein the generating of the modulus N includes applying a Lenstra, Lenstra and Lovasz (LLL) method to a lattice.
7. The method according to claim 6 and wherein the applying the Lenstra, Lenstra and Lovasz (LLL) method to the lattice scatters the bits of R(s) throughout N and generates t.
8. The method according to claim 6 and wherein the lattice is defined, in part, by a generalized pattern G.
9. The method according to claim 8 and wherein the lattice comprises:
V
1
=
(
2
2
n
+
L
1
0
…
0
0
0
)
V
2
=
(
0
2
2
n
+
L
2
…
0
0
0
)
…
…
…
…
…
V
k
=
(
0
0
…
2
2
n
+
Lk
0
0
)
V
k
+
1
=
(
2
2
n
-
S
1
+
L
1
p
2
2
n
-
S
2
+
L
2
p
…
2
2
n
-
Sk
+
Lk
p
2
n
+
x
-
z
0
)
V
k
+
2
=
(
2
2
n
(
r
1
+
.5
)
2
2
n
(
r
2
+
.5
)
…
2
2
n
(
r
k
+
.5
)
0
2
2
n
)
and wherein:
n, x, z are integers, and
S 1 ,. . ., S k 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 ≧. . . ≧S k , 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.
10. A compressed form public key delivery digital certificate for being parsed in hardware, the certificate being produced by a method comprising:
generating a modulus N by a computer programmed to generate the modulus N by a scattering method L, a function R and a seed s, where
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 R(s) are denoted by t;
generating a key pair (E,D) by the computer, which is programmed to generate the 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 certificate, including the public key E in compressed form by the computer, which is programmed to include the s and the t in the certificate instead of the public key E,
wherein the s and the t together are shorter than the E and,
wherein the public key E is generable from the s and the t.