US5502764A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method, identification device and verification device for identificaiton and/or performing digital signature
Assignee: Vantiva SA
•
Filing: 1992-01-11
•
Granted: 1996-03-26
•
Expires: 2012-01-11
Abstract
Abstract The present invention relates to a method, identification device and verification device for identification and/or performing digital signature which allows zero-knowledge access control. For many applications, e.g. smart cards for Pay-TV purposes, credit cards, passports, dongels or other kind of electronic keys, unforgeable systems for access control or digital signature are required. Such access control and signature systems may include public keys. But in many of such public key systems the key management becomes very complicated when the number of users increases. The invention uses the fact that it is difficult to compute roots mod n when factoring of n is unknown. The invention is based on the identity: x d (x -1 ) d =1 mod n which is computed and verified between an identification device and a verification device. An authority records seed data, the modulus n, a pseudo-random function and a set of numbers derived from roots modulo n on an identifier device. The public key directory is replaced by a unique transmission of seed data from the identifier to a verifier, which will give after a proper processing both, the identity information for the identifier and public keys.
Inventors
- 👤 David Naccache
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 16:14
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/401; G06Q20/4014; G06Q20/40145; H; H04; H04L; H04L9/00; H04L9/32; H04L9/3218; H04L9/3247
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
283 words
Method for identification and/or performing digital signature, wherein data are computed by an authority and recorded on an identification device U, comprising the first steps of: choosing and publishing a modulus X, a power d and a function H, wherein X is a product of at least two big prime numbers, d is a number greater than 1, and H is a one-way pseudo-random function, and comprising the following second steps: computing a set {PK 1 , . . . , PK k } of k small prime numbers PK i such that each PK i has a root modulo X; concatenating said small prime numbers PK i with pattern data PN, especially a part of X, and with specific information data ID which contain information about said identification device U and producing seed data SD such that SD d mod X=(PK 1 & . . . & PK k & PN & ID), wherein in case of (PK 1 & . . . & PK k & PN & ID) having no d-th root either the order of the PK i can be permuted until a root is found or a small arbitrary string J can be appended to (PK 1 & . . . & PK k & PN & ID) in such a way that (J & PK 1 & . . . & PK k & PN & ID) has a d-th root; recording on said identification device U said seed data SD and/or said modulus X and/or said function H and/or a set {SK 1 , . . . , SK k } of numbers SK i which are defined by SK i d PK i mod X=1.
Claim 2
Dependent Claim
283 words
Method for identification and/or performing digital signature, wherein data are computed by an authority and recorded on an identification device U, comprising the first steps of: choosing and publishing a modulus X, a power d and a function H, wherein X is a product of at least two big prime numbers, d is a number greater than 1, and H is a one-way pseudo-random function, and comprising the following second steps: computing a set {PK 1 , . . . , PK k } of k small prime numbers PK i such that each PK i has a root modulo X; concatenating said small prime numbers PK i with pattern data PN, especially a part of X, and with specific information data ID which contain information about said identification device U and producing seed data SD such that SD d mod X=(PK 1 & . . . & PK k & PN & ID), wherein in case of (PK 1 & . . . & PK k & PN & ID) having no d-th root either the order of the PK i can be permuted until a root is found or a small arbitrary string J can be appended to (PK 1 & . . . & PK k & PN & ID) in such a way that (J & PK 1 & . . . & PK k & PN & ID) has a d-th root; recording on said identification device U said seed data SD and/or said modulus X and/or said function H and/or a set {SK 1 , . . . , SK k } of numbers SK i which are defined by SK i d PK i mod X=1.
Claim 3
Dependent Claim
200 words
Method according to claim 1, wherein in case of identification the following third steps are carried out in said identification device U and/or in a verification device V; a) U sends said seed data SD to V; b) U picks h random numbers R i in the range, computes and sends a number Z defined by Z=H (R 1 d mod X & . . . & R h d mod X) to V; c) V computes SD d mod X, checks that said pattern data PN is valid, separates said small prime numbers PK i which are inside SD d mod X, picks a set {c 1 , . . . , c h } of h numbers c i such that each 0≦c i ≦k and sends them to U; d) U computes h values RESP i =(if (c i equal 0) then R i else R i SK ci mod X) and sends the set {RESP 1 , . . . , RESP h } of said h values RESP i to V; e) V checks U's identity by verifying that Z=H(&&(if (c i equal 0) then 1 else PK ci ) RESP i d mod X).
Claim 4
Dependent Claim
202 words
Method according to claim 1, wherein in case of performing digital signature m the following third steps are carried out in said identification device U and/or in a verification device V: a) U sends said seed data SD to V; b) V computes SD d mod X, checks that said pattern data PN is valid and separates said small prime numbers PK i which are inside SD d mod X; c) U picks h random numbers R i in the range, and computes a number Z defined by Z=H (R 1 d mod X & . . . & R h d mod X & m) and reads said number Z as a set {c 1 , . . . , c h } of h numbers c i such that each 0≦c i ≦k; d) U computes h values RESP i =(if (c i equal 0) then R i else R i SK ci mod X) and sends the set {Z, m, RESP 1 , . . . , RESP h }to V; e) V checks U's signature on m by verifying that Z=H(&&(if (c i equal 0) then 1 else PK ci ) RESP i d mod X & m).
Claim 5
Dependent Claim
125 words
Method according to claim 2, wherein said pseudo-random function H is replaced by a pseudo-random hash function H applied on an algebraic function P and that steps b) and e) of said third steps are replaced by: b ) U picks h random numbers R i in the range, computes and sends a number Z defined by Z=H (P(R 1 d & . . . & R h d ) mod X) to V; e) V computes h values {L 1 , . . . , L h }, L i =(if (c i equal 0) then 1 else PK ci ) RESP i d mod X and checks U's identity by verifying that Z=H(P(L 1 , . . . ,L h ) mod X).
Claim 6
Dependent Claim
316 words
Method according to claim 1, wherein in case of identification the following third steps are carried out in said identification device U and/or in a verification device V: a) U sends said seed data SD to V; b) U picks s≧h random numbers R i and/or R j in the range, computes and sends a number Z defined by Z=H((R 1 * . . . * R s ) d mod X) to V; c) V computes SD d mod X, checks that said pattern data PN is valid, separates said small prime numbers PK i which are inside SD d mod X, picks a set {c 1 , . . . , c h } of h numbers c i such that each 0≦c i ≦k and sends them to U; d) V picks and sends to U a set {v 1 , . . . , v h } of h binary vectors v i and/or v j , wherein the length of each v i is s bits and wherein (if ((i not equal j) and (u-th bit of v i equal `1`)) then (u-th bit of v j equal `0`)) and wherein at least one bit in each v i is set to `1`; e) U computes h values {a 1 , . . . , a h } wherein a i =(product for j=1 to s (if (j-th bit of v i equal `1`) then R j else 1)); f) U computes h values RESP i =(if (c i equal 0) then a i else a i SK ci mod X) and sends the set {RESP 1 , . . . ,RESP h } of said h values RESP i to V; e) V checks U's identity by verifying that Z=H(product for i=1 to h (if (c i equal 0) then 1 else PK ci ) RESP i d mod X).
Claim 7
Dependent Claim
132 words
Method according to claim 3, wherein said pseudo-random function H is replaced by a pseudo-random hash function H applied on an algebraic function P and that steps c) and e) of said third steps are replaced by: c) U picks h random numbers R i in the range, computes and sends a number Z defined by Z=H ((P(R 1 d mod X & . . . & R h d ) mod X) & m) to V; e) V computes h values {L 1 , . . . , L h }, L i =(if (c i equal 0) then 1 else PK ci ) RESP i d mod X and checks U's signature on m by verifying that Z=H((P(L 1 , . . . ,L h ) rood X) & m).
Claim 8
Dependent Claim
60 words
Method according to any one of claims 1 to 6, wherein said small prime numbers PK i are a random function of said information data ID, especially by making a table of t small prime numbers in said verifier device V and using the t-th bit of f(ID) to indicate PK t , wherein f is a second pseudo-random function.
Claim 9
Dependent Claim
24 words
Method according to claim 7, wherein said small prime numbers PK i are recorded in a public directory known to said verification device V.
Claim 10
Dependent Claim
39 words
Method according to claim 8 wherein X is about 64 bytes long and/or 3≦h≦10 and/or s=2*h and/or 8≦k≦20 and/or 8≦t≦20 and/or that the length of said numbers SK i is greater equal 1 byte and less equal 8 bytes.
Claim 11
Dependent Claim
13 words
Method according to claim 9 wherein said third steps are repeated e>1 times.
Claim 12
Dependent Claim
83 words
Identification device U which uses a method according to claim 10 and comprising computation means, memory means which are connected to said computation means and data exchange means which are connected to said computation means, wherein said memory means store said seed data SD, said modulus X, said function H and said set {SK i , . . . ,SK k } of numbers SK i and wherein said data exchange means send data to and receive data from a verification device V.
Claim 13
Dependent Claim
77 words
Verification device V which uses a method according to claim 10 and comprising computation means, memory means which are connected to said computation means and data exchange means which are connected to said computation means, wherein said memory means store said modulus X and said function H and wherein said data exchange means send data to and receive data from an identification device U and wherein said computation means verify data received from an identification device U.
Claim 14
Dependent Claim
33 words
Identification device according to claim 11, wherein said identification device U is a smart card or a computer or a terminal or a credit-card or a dongle or a passport or a door-key.
References Cited (Backward Citations)
US5140634A
Cited
US5218637A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-03-26 | 1999-09-25 | 2000-03-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-03-26 | 2003-09-25 | 2004-03-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-03-26 | 2007-09-25 | 2008-03-26 | $7700.00 | Window Closed / Lapsed |