Patent US3467765A successfully refreshed from Google Patents.
Patent EP0252499A2 successfully refreshed from Google Patents.
EP0252499A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method, apparatus and article for identification and signature
Assignee: Yeda Research and Development Co Ltd
•
Filing: 1987-07-08
•
Granted: —
•
Expires: 2007-07-08
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
EP
Data Source
google_patents
Last Synchronized
2026-10-27 17:45
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: 34
Claim 1
Independent Claim
129 words
A method of creating a unique identifier for use by an entity which can not be forged by others including those capable of 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 the range [O,n); c) preparing a string I containing information unique to an entity; d) computing v j = f (I,j) for j = small values; e) selecting k distinct values of j so that each v j is a quadratic residue (mod n); f) computing roots s j of v j ⁻¹ (mod n); g) recording on a retrievable medium of an identifier I, k, s j and related indices.
Claim 2
Independent Claim
129 words
A method of creating a unique identifier for use by an entity which can not be forged by others including those capable of 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 the range [O,n); c) preparing a string I containing information unique to an entity; d) computing v j = f (I,j) for j = small values; e) selecting k distinct values of j so that each v j is a quadratic residue (mod n); f) computing roots s j of v j ⁻¹ (mod n); g) recording on a retrievable medium of an identifier I, k, s j and related indices.
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
22 words
The method of claim 1 or 2 wherein the recording is in a ROM and the identifier includes microprocessing and input/output features.
Claim 5
Dependent Claim
139 words
A method of utilizing the identifier of any of claims 1 to 3 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 from the identifier to the verifier; c) generating in the verifier v j = f(I,j) for j = 1...k; d) selecting in the identifier a random r i ε [O,n); e) computing x i =r i ² (mod n) in the identifier and sending x i to the verifier; f) selecting a random binary vector e i ...e ik from a predetermined set of such vectors in the verifier and sending to the identifier; g) computing in the identifier and sending y i to the verifier; h) checking in the verifier i) repeating steps (d) through (h) at least once.
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
16 words
The method of claim 4 or 5 wherein all steps are carried out using binary signals.
Claim 8
Dependent Claim
14 words
The method of claim 6 wherein modulus n is composed of about 512 bits.
Claim 9
Dependent Claim
16 words
The method of claim 6 or 7 wherein only a portion of x i is used.
Claim 10
Independent Claim
19 words
The method of any of claims 6 to 8 wherein steps (d) through (h) are repeated at least twice.
Claim 11
Dependent Claim
144 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 ² (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 for i = 1...t; e) sending to the verifier I, m, the e ij matrix and all the y i values; f) computing in the verifier v j = f(I,j) for j = 1...k; g) computing in the verifier and h) verifying the signature to message m by determining whether the kt bits extracted from f(m,z₁... z t ) are the same as e ij .
Claim 12
Dependent Claim
20 words
The method of claim 10 wherein the first kt bits of f(m,z₁...z t ) are used as e ij matrix.
Claim 13
Dependent Claim
14 words
The method of claim 10 or 11 wherein the exchange is in binary form.
Claim 14
Dependent Claim
16 words
The method of claim 10, 11 or 12 wherein the product kt is at least 72.
Claim 15
Independent Claim
21 words
The method of any of claims 10 to 13 wherein k is at least 18 and t is at least 4.
Claim 16
Dependent Claim
131 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 computing v j = f (I,j) for j = small values where f is a pseudo random function f capable of mapping arbitrary strings to the range [O,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; b) means for selecting k distinct values of j so that each v j is a quadratic residue (mod n); c) means for computing roots s j of v j ⁻¹ (mod n); and d) means for recording on a retrievable medium of an identifier I, s j and related indices.
Claim 17
Dependent Claim
131 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 computing v j = f (I,j) for j = small values where f is a pseudo random function f capable of mapping arbitrary strings to the range [O,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; b) means for selecting k distinct values of j so that each v j is a quadratic residue (mod n); c) means for computing roots s j of v j ⁻¹ (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
22 words
The apparatus of claim 15 or 16 wherein the recording is in a ROM and the identifier includes microprocessing and input/output features.
Claim 20
Dependent Claim
147 words
Apparatus for utilizing the identifier of any of claims 15 to 17 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 from the identifier to the verifier; c) means for generating in the verifier v j = f(I,j) for j = 1...k; d) means for selecting in the identifier a random r i ε [O,n); e) means for computing x i = r i ² (mod n) in the identifier and sending x i to the verifier; f) means for selecting a random vector e il ....e ik in the verifier and sending to the identifier; g) means for computing in the identifier and sending to the verifier; h) means for checking in the verifier 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
16 words
The apparatus of claim 18 or 19 wherein all steps are carried out using binary signals.
Claim 23
Dependent Claim
14 words
The apparatus of claim 20 wherein modulus n is composed of about 512 bits.
Claim 24
Dependent Claim
16 words
The apparatus of claim 20 or 21 wherein only a portion of x i is used.
Claim 25
Independent Claim
19 words
The apparatus of any of claims 20 to 22 wherein steps (d) through (h) are repeated at least twice.
Claim 26
Dependent Claim
160 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₁...r t ε [O,n); b) means for computing in the identifier x i = r i ² (mod n); c) means for computing in the identifier f(m,x₁...x t ) and extracting from it kt bits as e ij values (1 ≦ i ≦ t, 1 ≦ j ≦ k); d) means for computing in the identifier 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 j = 1...k; g) means for computing in the verifier 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₁...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
15 words
The apparatus of claim 24 or 25 wherein the product kt is at least 72.
Claim 29
Dependent Claim
113 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 the range [O,n), values v j which are quadratic residues (mod n), values s j which are roots of v j ⁻¹ (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 ² (mod n) and in responsive to receiving a binary vector e il ...e ik .
Claim 30
Dependent Claim
113 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 the range [O,n), values v j which are quadratic residues (mod n), values s j which are roots of v j ⁻¹ (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 ² (mod n) and in responsive to receiving a binary vector e il ...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
72 words
An identifier according to claim 27 or 28 wherein the microprocessor means includes selection means for selecting random r₁...r t ε [O,n), computing means for computing x i =r i ² (mod n), computing means for computing f(m, x₁...x t ), selection means for extracting from it kt bits as e ij values (1 ≦ i ≦ t, 1 ≦ j ≦ k), and computing means for computing for i = 1.....t.
Claim 33
Dependent Claim
72 words
A verification device for use with the identifier of any of claims 27 to 29, 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 j = 1..., k, selection means for selecting a binary vector e il ...e ik , and checking means for checking that
Claim 34
Dependent Claim
46 words
A verification device according to claim 30 for use with the identifier of claim 31, wherein the microprocessor means includes computing means for computing for i = 1...t and comparing means for comparing that the kt bits extracted from f(m,z₁...z t ) are e ij .
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.