Patent US4748668A successfully refreshed from Google Patents.
US4748668A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method, apparatus and article for identification and signature
Assignee: Yeda Research and Development Co Ltd
•
Filing: 1986-07-09
•
Granted: 1988-05-31
•
Expires: 2006-07-09
Abstract
Abstract A method and apparatus for simple identification and signature which enable any user to prove his identity and the authenticity of his messages to any other user. The method and apparatus are provably secure against any known or chosen message attack if factoring is difficult, and require only 1% to 4% of the number of modular multiplications previously required. The simplicity, security and speed of the method and apparatus derive from microprocessor-based devices which may be incorporated into smart cards, personal computers, passports, and remote control systems.
Inventors
- 👤 Adi Shamir
- 👤 Amos Fiat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 15:26
CPC Classifications
G; G07; G07F; G07F7/00; G07F7/08; G07F7/10; G07F7/1008; G06; G06Q; G06Q20/00; G06Q20/30; G06Q20/34; G06Q20/341; G06Q20/38; G06Q20/40; G06Q20/409; G06Q20/4097; G06Q20/40975; G07F7/1016; H; H04; H04L; H04L9/00; H04L9/30; H04L9/3066; H04L9/3073; H04L9/32; H04L9/3218; H04L9/3221; H04L2209/00; H04L2209/56
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
121 words
A method of creating a unique identifier for use by an entity which cannot be forged by others including those capable or verifying the entity, comprising the steps of: (a) selecting a modulus n which is the product of at least two secret primes; (b) selecting a pseudo random function f capable of mapping arbitrary strings to numbers; (c) preparing a string I containing information unique to an entity; (d) selecting k distinct values of j so that each v j =f(I,j) is a residue (mod n) having a root s j ; (e) computing roots s j of v j -1 (mod n); (f) recording on a retrievable medium of an identifier I, k, s j and related indices j.
Claim 2
Independent Claim
121 words
A method of creating a unique identifier for use by an entity which cannot be forged by others including those capable or verifying the entity, comprising the steps of: (a) selecting a modulus n which is the product of at least two secret primes; (b) selecting a pseudo random function f capable of mapping arbitrary strings to numbers; (c) preparing a string I containing information unique to an entity; (d) selecting k distinct values of j so that each v j =f(I,j) is a residue (mod n) having a root s j ; (e) computing roots s j of v j -1 (mod n); (f) recording on a retrievable medium of an identifier I, k, s j and related indices j.
Claim 3
Dependent Claim
15 words
The method of claim 1 wherein the recording on the identifier is in binary form.
Claim 4
Dependent Claim
20 words
The method of claim 1 wherein the recording is in a ROM and the identifier includes microprocessing and input/output features.
Claim 5
Dependent Claim
144 words
A method of utilizing the identifier of claim 1 comprising: (a) placing the identifier of claim 1 in communication with a verifier having recorded therein modulus n and pseudo random function f; (b) transmitting I and the indices j from the identifier to the verifier; (c) generating in the verifier v j =f(I,j) for the indices j; (d) selecting in the identifier a random r i ε (O,n); (e) computing x i =r i 2 (mod n) in the identifier and sending x i to the verifier; (f) selecting a random binary vector e i1 . . . e ik from a predetermined set of such vectors in the verifier and sending to the identifier; (g) computing in the identifier ##EQU5## and sending y i to the verifier; (h) checking in the verifier ##EQU6## (i) repeating steps (d) through (h) t times, where t≧1.
Claim 6
Dependent Claim
19 words
The method of claim 4 wherein the transmissions between the identifier and verifier are carried out in binary form.
Claim 7
Dependent Claim
14 words
The method of claim 4 wherein all steps are carried out using binary signals.
Claim 8
Dependent Claim
15 words
The method of claim 6 wherein modulus n is composed of at least 512 bits.
Claim 9
Dependent Claim
15 words
The method of claim 6 wherein only a lashed version of x i is used.
Claim 10
Dependent Claim
16 words
The method of claim 6 wherein steps (d) through (h) are repeated at least two times.
Claim 11
Dependent Claim
151 words
A method of signing a message m exchanged between an identifier created according to claim 1 and verifier comprising: (a) selecting in the identifier random r i . . . r t ε (O,n); (b) computing in the identifier x i =r i 2 (mod n); (c) computing in the identifier f(m, x 1 . . . x t ) and extracting from it kt bits as e ij values; (d) computing in the identifier ##EQU7## for i=1 . . . t; (e) sending to the verifier I, the indices j, m, the e ij matrix and all the y i values; (f) computing in the verifier v j =f(I,j) for the indices j; (g) computing in the verifier ##EQU8## and (h) verifying the signature to message m by determining whether the kt bits extracted from f(m,z 1 . . . z t ) are the same as e ij .
Claim 12
Dependent Claim
26 words
The method of claim 10 wherein the first kt bits of f(m, z 1 . . . z t ) are used as e ij matrix.
Claim 13
Dependent Claim
12 words
The method of claim 10 wherein the exchange is in binary form.
Claim 14
Dependent Claim
13 words
The method of claim 10 wherein the product kt is at least 72.
Claim 15
Dependent Claim
17 words
The method of claim 10 wherein k is at least 18 and t is at least 4.
Claim 16
Dependent Claim
122 words
Apparatus for creating a unique identifier for use by an entity and unforgeable by others including those capable of verifying the entity, comprising: (a) means for selecting k distinct indices of j so that each v j =f(I,j) is a quadratic residue (mod n); (b) where f is a pseudo random function f capable of mapping arbitrary strings to numbers in the range (0,n) and n is a modulus which is the product of at least two secret primes and I is a string containing information unique to an entity; (c) means for computing roots s j of v j - 1 (mod n); and (d) means for recording on a retrievable medium of an identifier I, s j and related indices.
Claim 17
Dependent Claim
122 words
Apparatus for creating a unique identifier for use by an entity and unforgeable by others including those capable of verifying the entity, comprising: (a) means for selecting k distinct indices of j so that each v j =f(I,j) is a quadratic residue (mod n); (b) where f is a pseudo random function f capable of mapping arbitrary strings to numbers in the range (0,n) and n is a modulus which is the product of at least two secret primes and I is a string containing information unique to an entity; (c) means for computing roots s j of v j - 1 (mod n); and (d) means for recording on a retrievable medium of an identifier I, s j and related indices.
Claim 18
Dependent Claim
15 words
The apparatus of claim 15 wherein the recording on the identifier is in binary form.
Claim 19
Dependent Claim
20 words
The apparatus of claim 15 wherein the recording is in a ROM and the identifier includes microprocessing and input/output features.
Claim 20
Dependent Claim
151 words
Apparatus for utilizing the identifier of claim 15 comprising: (a) means for placing the identifier of claim 1 in communication with a verifier having recorded therein modulus n and pseudo random function f; (b) means for transmitting I and the indices j from the identifier to the verifier; (c) means for generating in the verifier v j =f(I,j) for the selected indices j; (d) means for selecting in the identifier a random r i "(0,n); (e) means for computing x i =r i 2 (mod n) in the identifier and sending x i to the verifier; (f) means for selecting a random vector e i1 . . . e ik in the verifier and sending to the identifier; (g) means for computing in the identifier ##EQU9## and sending to the verifier; (h) means for checking in the verifier ##EQU10## and (i) means for repeating steps (d) through (h) at least once.
Claim 21
Dependent Claim
19 words
The apparatus of claim 18 wherein the transmissions between the identifier and verifier are carried out in binary form.
Claim 22
Dependent Claim
14 words
The apparatus of claim 18 wherein all steps are carried out using binary signals.
Claim 23
Dependent Claim
15 words
The apparatus of claim 20 wherein modulus n is composed of at least 512 bits.
Claim 24
Dependent Claim
15 words
The apparatus of claim 20 wherein only a hased version of x i is used.
Claim 25
Dependent Claim
16 words
The apparatus of claim 20 wherein steps (d) through (h) are repeated at least two times.
Claim 26
Dependent Claim
170 words
Appratus for signing a message m exchanged between an identifier created according to claim 1 and a verifier comprising: (a) means for selecting in the identifier random r i . . . r t ε(0,n); (b) means for computing in the identifier x i =r i 2 (mod n); (c) means for computing in the identifier f(m, x i . . . x t ) and extracting from it kt bits as e ij values; (d) means for computing in the identifier ##EQU11## for i=1 . . . t; (e) means for sending to the verifier I, m, the e ij matrix and all the y i values; (f) means for computing in the verifier v j =f(I,j) for the indices j; (g) means for computing in the verifier ##EQU12## for i=1 . . . t; and (h) means for verifying the signature to message m by determining whether the kt bits extracted from f(m, z 1 . . . z t ) are the same as e ij .
Claim 27
Dependent Claim
12 words
The apparatus of claim 24 wherein the exchange is in binary form.
Claim 28
Dependent Claim
13 words
The apparatus of claim 24 wherein the product kt is at least 72.
Claim 29
Dependent Claim
114 words
An identifier comprising microprocessor means, memory means and I/O means and having recorded in said memory means a string I containing information unique to an entity, a modulus n which is the product of at least two secret primes, a pseudo random function f capable of mapping arbitrary strings to numbers, indices; and values v j which are quadratic residues (mod n), values s j which are roots of v j -1 (mod n), said microprocessor means including selection means for selecting a number r i ε (O,n), and computing means for computing x i =r i 2 (mod n) and ##EQU13## in responsive to receiving a binary vector e i1 ...e ik .
Claim 30
Dependent Claim
114 words
An identifier comprising microprocessor means, memory means and I/O means and having recorded in said memory means a string I containing information unique to an entity, a modulus n which is the product of at least two secret primes, a pseudo random function f capable of mapping arbitrary strings to numbers, indices; and values v j which are quadratic residues (mod n), values s j which are roots of v j -1 (mod n), said microprocessor means including selection means for selecting a number r i ε (O,n), and computing means for computing x i =r i 2 (mod n) and ##EQU13## in responsive to receiving a binary vector e i1 ...e ik .
Claim 31
Dependent Claim
29 words
An identifier according to claim 27, wherein the microprocessor means includes loop means for repeating the selection of r i and computing of x i and y i .
Claim 32
Dependent Claim
73 words
An identifier according to claim 27 wherein the microprocessor means includes selection means for selecting random r i . . . r t ε (O,n), computing means for computing x i =r i 2 (mod n), computing means for computing f(m, x i . . . x t ), selection means for extracting from it kt bits as e ij values, and computing means for computing ##EQU14## for i=1 . . . t.
Claim 33
Dependent Claim
70 words
A verification device for use with the identifier of claim 27, comprising microprocessor means, memory means and I/O means and having recorded in said memory means modulus n and function f, said microprocessor means including generating means for generating values of v j =f(I,j) for the indices j; selection means for selecting a binary vector e i1 . . . e ik , and checking means for checking that ##EQU15##
Claim 34
Dependent Claim
55 words
A verification device according to claim 30 for use with the identifier of claim 27, wherein the microprocessor means includes computing means for computing ##EQU16## for i=1 . . . t and comparing means for comparing that the kt bits extracted from f(m, z 1 . . . z t ) are e ij .
Claim 35
Dependent Claim
19 words
The method of claim 1 including the step of placing the numbers v j in a public key directory.
Claim 36
Dependent Claim
30 words
The method of claim 4 including the steps of placing the numbers v j in a public key directory, and retrieving the numbers v j from the public key directory.
Claim 37
Dependent Claim
139 words
A method of utilizing the identifier of claim 1 comprising: (a) placing the identifier of claim 1 in communication with a verifier having recorded therein modulus n and pseudo random function f; (b) transmitting the numbers v j along with a signature of a trusted center from the identifier to the verifier; (c) selecting in the identifier a random r i ε (O,n); (d) computing x i =r i 2 (mod n) in the identifier and sending x i to the verifier; (e) selecting a random binary vector e i . . . e ik from a predetermined set of such vectors in the verifier and sending to the identifier; (f) computing in the identifier ##EQU17## and sending y i to the verifier; (g) checking in the verifier ##EQU18## and (h) repeating steps (d) through (h) at least once.
Claim 38
Dependent Claim
18 words
The method of claim 4 wherein the repetition of steps (d) through (h) are carried out in parallel.
Claim 39
Dependent Claim
98 words
A method of signing a message m by an identifier created according to claim 1 comprising: (a) selecting in the identifier random r i . . . r t ε (O,n); (b) computing in the identifier x i =r i 2 (mod n); (c) computing in the identifier f(m, x i . . . x t ) and extracting from it kt bits as e ij values (1≦i≦t, 1≦j≦k); (d) computing in the identifier ##EQU19## for i=1 . . . t; and (e) storing I, indices j, m, and e ij matrix and all the y i values.
Claim 40
Dependent Claim
90 words
A method of verifying the stored signature of a stored message m as defined in claim 36 including the steps of: (a) retrieving I, the indices j, m, and e ij matrix and all the y i values from storage; (b) computing in the verifier v j =f(I,j) for the indices j; (c) computing in the verifier ##EQU20## and (d) verifying the signature to message m by determining whether the kt bits extracted from f(m, z 1 . . . z t ) are the same as e ij .
Claim 41
Dependent Claim
31 words
Apparatus as defined in claim 15 further including means for establishing a public key directory and means for recording the I, v j and related indices in said public key directory.
Claim 42
Dependent Claim
23 words
Apparatus as defined in claim 38 further including means for retrieving the I, v j and related indices from said public key directory.
Claim 43
Dependent Claim
142 words
Apparatus for utilizing the identifier of claim 15 comprising: (a) means for placing the identifier of claim 1 in communication with a verifier having recorded therein modulus n and pseudo random function f; (b) means for transmitting the numbers v j along with a signature of a trusted signature from the identifier to the verifier; (c) means for selecting in the identifier a random r i ε(0,n); (d) means for computing x i =r i 2 (mod n) in the identifier and sending x i to the verifier; (e) means for selecting a random vector e i1 . . . e ik in the verifier and sending to the identifier; (f) means for computing in the identifier ##EQU21## and sending to the verifier; (g) means for checking in the verifier ##EQU22## (h) means for repeating steps (d) through (h) at least once.
Claim 44
Dependent Claim
112 words
Apparatus for signing a message m exchanged between an identifier created according to claim 1 and a verifier comprising: (a) means for selecting in the identifier random r i . . . r t ε (O,n); (b) means for computing in the identifier x i =r i 2 (mod n); (c) means for computing in the identifier f(m, x i . . . x t ) and extracting from it kt bits as e ij values; (d) means for computing in the identifier ##EQU23## for i=1 . . . t; and (e) means for storing the verifier I, the indices j, m, the e ij matrix and all the y i values.
Claim 45
Dependent Claim
92 words
The apparatus according to claim 41 including (a) means for retrieving the verifier I, the indices j, m, the e ij matrix and all the y i values from storage; (b) means for computing in the verifier v j =f(I,j) for the indices j; (c) means for computing in the verifier ##EQU24## for i=1 . . . t; and (d) means for verifying the signature to message m by determining whether the kt bits extracted from f(m, z 1 . . . z t ) are the same as e ij .
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-05-31 | 1991-11-30 | 1992-05-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-05-31 | 1995-11-30 | 1996-05-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-05-31 | 1999-11-30 | 2000-05-31 | $7700.00 | Window Closed / Lapsed |