US4933970A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Variants of the fiat-shamir identification and signature scheme
Assignee: Yeda Research and Development Co Ltd
•
Filing: 1988-01-19
•
Granted: 1990-06-12
•
Expires: 2008-01-19
Abstract
Abstract A method and apparatus are disclosed and claimed which enable an entity to generate proofs of identity and signatures of messages that everyone can verify but no one can forge. Compared to other schemes of this type (such as the RSA), the Fiat-Shamir scheme is faster by one to two orders of magnitude. In the present invention disclosed and claimed in this patent application, two improved variants of the Fiat-Shamir scheme are described which are even faster. One variant uses small public values to optimize the vertification procedure, and the other variant uses particular secret values to optimize the generation procedure.
Inventors
- 👤 Adi Shamir
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:31
CPC Classifications
G; G07; G07F; G07F7/00; G07F7/08; G07F7/10; G07F7/1016; H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302; H04L9/32; H04L9/3218; H04L9/3247
Claims Analysis
Total Claims: 68
Claim 1
Independent Claim
168 words
A method of proving the identity of an entity comprising the steps of (a) establishing a public key for the entity consisting of a modulus n which is the product of at least two prime numbers, and a sequence of k numbers v 1 , . . . , v k ; (b) computing a private key for the entity consisting of k numbers s 1 , . . . , s k satisfying s j d v j =1 (mod n) for all 1≦j≦k, where d is a universally known constant larger than 1; (c) transmitting from the entity to a verifier x=r d (mod n) where r is a random number in the range 0<r<n; (d) transmitting from the verifier to the entity a sequence of k random numbers e 1 , . . . , e k in the range 0<e j <d; (e) transmitting from the entity to the verifier the value ##EQU7## (f) verifying the identity of the entity by checking that ##EQU8##
Claim 2
Independent Claim
168 words
A method of proving the identity of an entity comprising the steps of (a) establishing a public key for the entity consisting of a modulus n which is the product of at least two prime numbers, and a sequence of k numbers v 1 , . . . , v k ; (b) computing a private key for the entity consisting of k numbers s 1 , . . . , s k satisfying s j d v j =1 (mod n) for all 1≦j≦k, where d is a universally known constant larger than 1; (c) transmitting from the entity to a verifier x=r d (mod n) where r is a random number in the range 0<r<n; (d) transmitting from the verifier to the entity a sequence of k random numbers e 1 , . . . , e k in the range 0<e j <d; (e) transmitting from the entity to the verifier the value ##EQU7## (f) verifying the identity of the entity by checking that ##EQU8##
Claim 3
Dependent Claim
20 words
A method as claimed in claim 1 wherein steps c, d, e and f are repeated t times where t≧1.
Claim 4
Dependent Claim
19 words
A method as claimed in claim 1 wherein the v j 's are the same for all the entities.
Claim 5
Dependent Claim
18 words
A method as claimed in claim 1 wherein the v j 's are the first k prime numbers.
Claim 6
Dependent Claim
34 words
A method as claimed in claim 1 including the further step of storing the modulus n and the k numbers v 1 , . . . , v k in a public key directory.
Claim 7
Dependent Claim
45 words
A method as claimed in claim 1 including the further step of transmitting the modulus n and the k numbers v 1 , . . . , v k from the entity to the verifier along with a trusted center's signature on this public key.
Claim 8
Dependent Claim
21 words
A method as claimed in claim 3 including the further step of storing the modulus n in a public key directory.
Claim 9
Dependent Claim
32 words
A method as claimed in claim 3 including the further step of transmitting the modulus n from the entity to the verifier along with a trusted center's signature on this public key.
Claim 10
Dependent Claim
13 words
A method as claimed in claim 1 wherein d k ≧2 20 .
Claim 11
Dependent Claim
14 words
A method as claimed in claim 1 wherein d is either 2 or 3.
Claim 12
Dependent Claim
13 words
A method as claimed in claim 1 wherein k is at least 20.
Claim 13
Dependent Claim
15 words
A method as claimed in claim 1 wherein n is at least 512 bits long.
Claim 14
Dependent Claim
32 words
A method as claimed in claim 1 wherein the secret key s 1 , . . . , s k is chosen first and each v j is then computed as ##EQU9##
Claim 15
Dependent Claim
28 words
A method as claimed in claim 13 wherein all the entities use the same modulus n which is chosen by a trusted center that keeps its factorization secret.
Claim 16
Dependent Claim
19 words
A method as claimed in claim 13 wherein the s j are chosen as random numbers for all 1≦j≦k.
Claim 17
Independent Claim
166 words
A method of generating a signature for a message m comprising the steps of (a) establishing a public key for the entity consisting of a modulus n which is the product of at least two prime numbers, and a sequence of k numbers v 1 , . . . , v k ; (b) computing a private key for the entity consisting of k numbers s 1 , . . . , s k satisfying s j d r j =1 (mod n) for all 1≦j≦k, where d is a universally known constant larger than 1; (c) agreeing on a common cryptographically strong pseudo random function f which maps its inputs into a sequence of k numbers e=e 1 , . . . , e k in the range 0≦e j <d; (d) choosing a random number r in the range 0<r<n and computing e=f (r d (mod n), m); (e) computing ##EQU10## (f) transmitting or storing e and y as the entity's signature on m.
Claim 18
Independent Claim
166 words
A method of generating a signature for a message m comprising the steps of (a) establishing a public key for the entity consisting of a modulus n which is the product of at least two prime numbers, and a sequence of k numbers v 1 , . . . , v k ; (b) computing a private key for the entity consisting of k numbers s 1 , . . . , s k satisfying s j d r j =1 (mod n) for all 1≦j≦k, where d is a universally known constant larger than 1; (c) agreeing on a common cryptographically strong pseudo random function f which maps its inputs into a sequence of k numbers e=e 1 , . . . , e k in the range 0≦e j <d; (d) choosing a random number r in the range 0<r<n and computing e=f (r d (mod n), m); (e) computing ##EQU10## (f) transmitting or storing e and y as the entity's signature on m.
Claim 19
Dependent Claim
22 words
A method according to claim 16 comprising the further steps of (a) computing ##EQU11## and (b) comparing the computed values to e.
Claim 20
Dependent Claim
102 words
A method as claimed in claim 16 wherein t≧1 random numbers r 1 , . . . , r t are chosen in the range 0<r i <n, e=e 1 1 , . . . , e k t numbers in the range 0≦e j i <d are computed as e=f (r 1 d (mod n), . . . , r t d (mod n), m), t values y 1 , . . . , y t are computed as ##EQU12## and e, y 1 , . . . , y t are transmitted or stored as the entity's signature on m.
Claim 21
Dependent Claim
21 words
A method as claimed in claim 18 comprising the further steps of computing ##EQU13## and comparing the computed values to e.
Claim 22
Dependent Claim
19 words
A method as claimed in claim 18 wherein the v j 's are the same for all the entities.
Claim 23
Dependent Claim
18 words
A method as claimed in claim 18 wherein the v j 's are the first k prime numbers.
Claim 24
Dependent Claim
34 words
A method as claimed in claim 18 including the further step of storing the modulus n and the k numbers v 1 , . . . , v k in a public key directory.
Claim 25
Dependent Claim
46 words
A method as claimed in claim 18 including the further step of incorporating the modulus n, the k numbers v 1 , . . . , v k , and a trusted center's signature on these values as part of the signature of the message m.
Claim 26
Dependent Claim
21 words
A method as claimed in claim 20 including the further step of storing the modulus n in a public key directory.
Claim 27
Dependent Claim
32 words
A method as claimed in claim 20 including the further step of incorporating the modulus n and a trusted center's signature on it as part of the signature of the message m.
Claim 28
Dependent Claim
13 words
A method as claimed in claim 18 wherein d k ≧2 64 .
Claim 29
Dependent Claim
14 words
A method as claimed in claim 18 wherein d is either 2 or 3.
Claim 30
Dependent Claim
13 words
A method as claimed in claim 18 wherein k is at least 64.
Claim 31
Dependent Claim
15 words
A method as claimed in claim 18 wherein n is at least 512 bits long.
Claim 32
Dependent Claim
32 words
A method as claimed in claim 18 wherein the secret key s 1 , . . . , s k is chosen first and each v j is then computed as ##EQU14##
Claim 33
Dependent Claim
28 words
A method as claimed in claim 30 wherein all the entities use the same modulus n which is chosen by a trusted center that keeps its factorization secret.
Claim 34
Dependent Claim
19 words
A method as claimed in claim 30 wherein the s j are chosen as random numbers for all 1≦j≦k.
Claim 35
Dependent Claim
176 words
Apparatus for proving the identity of an entity comprising (a) means for establishing a public key for the entity consisting of a modulus n which is the product of at least two prime numbers, and a sequence of k numbers v 1 , . . . , v k ; (b) means for computing a private key for the entity consisting of k numbers s 1 , . . . , s k satisfying s j d v j =1 (mod n) for all 1≦j≦k, where d is a universally known constant larger than 1; (c) means for transmitting from the entity to a verifier x=r d (mod n) where r is a random number in the range 0<r<n; (d) means for transmitting from the verifier to the entity a sequence of k random numbers e 1 , . . . , e k in the range 0≦e j <d; (e) means for transmitting from the entity to the verifier the value ##EQU15## (f) means for verifying the identity of the entity by checking that ##EQU16##
Claim 36
Dependent Claim
176 words
Apparatus for proving the identity of an entity comprising (a) means for establishing a public key for the entity consisting of a modulus n which is the product of at least two prime numbers, and a sequence of k numbers v 1 , . . . , v k ; (b) means for computing a private key for the entity consisting of k numbers s 1 , . . . , s k satisfying s j d v j =1 (mod n) for all 1≦j≦k, where d is a universally known constant larger than 1; (c) means for transmitting from the entity to a verifier x=r d (mod n) where r is a random number in the range 0<r<n; (d) means for transmitting from the verifier to the entity a sequence of k random numbers e 1 , . . . , e k in the range 0≦e j <d; (e) means for transmitting from the entity to the verifier the value ##EQU15## (f) means for verifying the identity of the entity by checking that ##EQU16##
Claim 37
Dependent Claim
57 words
Apparatus as claimed in claim 33 including means for repeating t times where t≧1, the transmitting from the entity to a verifier x=r d (mod n) where r is a random number in the range 0<r<n, the transmitting from the verifier, the transmitting from the entity to the verifier the value ##EQU17## and the verifying the identity.
Claim 38
Dependent Claim
18 words
Apparatus as claimed in claim 33 wherein the v j 's are the same for all the entities.
Claim 39
Dependent Claim
17 words
Apparatus as claimed in claim 33 wherein the v j 's are the first k prime numbers.
Claim 40
Dependent Claim
31 words
Apparatus as claimed in claim 33 including means for storing the modulus n and the k numbers v 1 , . . . , v k in a public key directory.
Claim 41
Dependent Claim
42 words
Apparatus as claimed in claim 33 including means for transmitting the modulus n and the k numbers v 1 , . . . , v k from the entity to the verifier along with a trusted center's signature on this public key.
Claim 42
Dependent Claim
18 words
Apparatus as claimed in claim 35 including means for storing the modulus n in a public key directory.
Claim 43
Dependent Claim
29 words
Apparatus as claimed in claim 35 including means for transmitting the modulus n from the entity to the verifier along with a trusted center's signature on this public key.
Claim 44
Dependent Claim
12 words
Apparatus as claimed in claim 33 wherein d k ≧2 20 .
Claim 45
Dependent Claim
13 words
Apparatus as claimed in claim 33 wherein d is either 2 or 3.
Claim 46
Dependent Claim
12 words
Apparatus as claimed in claim 33 wherein k is at least 20.
Claim 47
Dependent Claim
14 words
Apparatus as claimed in claim 33 wherein n is at least 512 bits long.
Claim 48
Dependent Claim
31 words
Apparatus as claimed in claim 33 wherein the secret key s 1 , . . . , s k is chosen first and each v j is then computed as ##EQU18##
Claim 49
Dependent Claim
27 words
Apparatus as claimed in claim 45 wherein all the entities use the same modulus n which is chosen by a trusted center that keeps its factorization secret.
Claim 50
Dependent Claim
18 words
Apparatus as claimed in claim 45 wherein the s j are chosen as random numbers for all 1≦j≦k.
Claim 51
Dependent Claim
174 words
Apparatus for generating a signature for a message m comprising (a) means for establishing a public key for the entity consisting of a modulus n which is the product of at least two prime numbers, and a sequence of k numbers v 1 , . . . , v k ; (b) means for computing a private key for the entity consisting of k numbers s 1 , . . . , s k satisfying s j d v j =1 (mod n) for all 1≦j≦k, where d is a universally known constant larger than 1; (c) means for agreeing on a common cryptographically strong pseudo random function f which maps its inputs into a sequence of k numbers e=e 1 , . . . , e k in the range 0≦e j <d; (d) means for choosing a random number r in the range 0<r<n and computing e=f (r d (mod n), m); (e) means for computing ##EQU19## (f) means for transmitting or storing e and y as the entity's signature on m.
Claim 52
Dependent Claim
174 words
Apparatus for generating a signature for a message m comprising (a) means for establishing a public key for the entity consisting of a modulus n which is the product of at least two prime numbers, and a sequence of k numbers v 1 , . . . , v k ; (b) means for computing a private key for the entity consisting of k numbers s 1 , . . . , s k satisfying s j d v j =1 (mod n) for all 1≦j≦k, where d is a universally known constant larger than 1; (c) means for agreeing on a common cryptographically strong pseudo random function f which maps its inputs into a sequence of k numbers e=e 1 , . . . , e k in the range 0≦e j <d; (d) means for choosing a random number r in the range 0<r<n and computing e=f (r d (mod n), m); (e) means for computing ##EQU19## (f) means for transmitting or storing e and y as the entity's signature on m.
Claim 53
Dependent Claim
23 words
Apparatus according to claim 48 comprising (a) computing means for computing ##EQU20## and (b) comparing means for comparing these computed values to e.
Claim 54
Dependent Claim
111 words
Apparatus as claimed in claim 48 wherein t≧1 random numbers r 1 , . . . , r t are chosen in the range 0<r i <n, e=e 1 1 , . . . , e k t numbers in the range 0≦e j i <d are computed as e=f (r 1 d (mod n), . . . , r t d (mod n), m), t values y 1 , . . . , y t are computed as y i =r i .πs j e u i (mod n), and e, y 1 , . . . , y t are transmitted or stored as the entity's signature on m.
Claim 55
Dependent Claim
22 words
Apparatus as claimed in claim 50 comprising computing means for computing ##EQU21## and comparing means for comparing the computed values to e.
Claim 56
Dependent Claim
18 words
Apparatus as claimed in claim 50 wherein the v j 's are the same for all the entities.
Claim 57
Dependent Claim
17 words
Apparatus as claimed in claim 50 wherein the v j 's are the first k prime numbers.
Claim 58
Dependent Claim
31 words
Apparatus as claimed in claim 50 including means for storing the modulus n and the k numbers v 1 , . . . , v k in a public key directory.
Claim 59
Dependent Claim
43 words
Apparatus as claimed in claim 50 including means for incorporating the modulus n, the k numbers v 1 , . . . , v k , and a trusted center's signature on these values as part of the signature of the message m.
Claim 60
Dependent Claim
18 words
Apparatus as claimed in claim 52 including means for storing the modulus n in a public key directory.
Claim 61
Dependent Claim
29 words
Apparatus as claimed in claim 52 including means for incorporating the modulus n and a trusted center's signature on it as part of the signature of the message m.
Claim 62
Dependent Claim
12 words
Apparatus as claimed in claim 50 wherein d k ≧2 64 .
Claim 63
Dependent Claim
13 words
Apparatus as claimed in claim 50 wherein d is either 2 or 3.
Claim 64
Dependent Claim
12 words
Apparatus as claimed in claim 50 wherein k is at least 64.
Claim 65
Dependent Claim
14 words
Apparatus as claimed in claim 50 wherein n is at least 512 bits long.
Claim 66
Dependent Claim
31 words
Apparatus as claimed in claim 50 wherein the secret key s 1 , . . . , s k is chosen first and each v j is then computed as ##EQU22##
Claim 67
Dependent Claim
27 words
Apparatus as claimed in claim 62 wherein all the entities use the same modulus n which is chosen by a trusted center that keeps its factorization secret.
Claim 68
Dependent Claim
18 words
Apparatus as claimed in claim 62 wherein the s j are chosen as random numbers for all 1≦j≦k.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-06-11 | 1993-12-11 | 1994-06-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-06-11 | 1997-12-11 | 1998-06-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-06-11 | 2001-12-11 | 2002-06-12 | $7700.00 | Window Closed / Lapsed |