Cryptography – Particular algorithmic function encoding – Nbs/des algorithm
Patent
1994-01-24
1996-03-26
Cain, David C.
Cryptography
Particular algorithmic function encoding
Nbs/des algorithm
380 25, 380 28, 380 30, H04K 100
Patent
active
055027644
DESCRIPTION:
BRIEF SUMMARY
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.
BACKGROUND
In access control systems roots modulo X are used where X is a composite number having at least two large prime factors. There are such access control systems where the factoring of X is known to some users. One example is the algorithm due to Rabin which is disclosed in "Probabilistic Algorithms", in S. Traub Ed., "Algorithms and Complexity, New Directions and Recent Results", Academic press, New York, 1976, 21-24.
INVENTION
It is one object of the invention to disclose a method for preparing identification and/or digital signature which allows zero-knowledge access control. This object is reached by the inventive method disclosed in claim 1.
It is a further object of the invention to disclose a method for performing identification and/or digital signature. This object is reached by and advantageous additional embodiments of the inventive method are resulting from the respective dependent claims.
In principle the inventive method consists in computing data by an authority and recording on an identification device U, comprising the following first steps:
choosing and publishing a modulus X, a power d and a function H, whereby X is a product of at least two big prime numbers and H is a one-way pseudo-random function;
computing a set {PK.sub.1, . . . , PK.sub.k } of k small prime numbers PK.sub.i such that each PK.sub.1 has a root modulo X;
concatenating said small prime numbers PK.sub.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.sup.d mod X=(PK.sub.1 & . . . & PK.sub.k & PN & ID), whereby in case of (PK.sub.1 & . . . & PK.sub.k & PN & ID) having no d-th root either the order of the PK.sub.i can be permuted until a root is found or a small arbitrary string J can be appended to (PK.sub.1 & . . . & PK.sub.k & PN & ID) in such a way that (J & PK.sub.1 & . . . & PK.sub.k & PN & ID) has a d-th root;
recording on said identification device U (18) said seed data SD and/or said modulus X and/or said function H and/or a set {SK.sub.1, . . . ,SK.sub.k } of numbers SK.sub.i which are defined by SK.sub.i.sup.d PK.sub.i mod X=1.
Thereafter in case of identification the following second steps (FIG. 2) are carried out in said identification device U (18) and/or in a verification device V (17): computes and sends a number Z defined by Z=H(R.sub.1.sup.d mod X & . . . & R.sub.h.sup.d mod X) to V; separates said small prime numbers PK.sub.i which are inside SD.sup.d mod X, picks a set {c.sub.1, . . . ,c.sub.h } of h numbers c.sub.i such that each O.ltoreq.c.sub.i .ltoreq.k and sends them to U; R.sub.i SK.sub.ci mod X) and sends the set {RESP.sub.1, . . . ,RESP.sub.h } of said h values RESP.sub.i to V; 1 else PK.sub.ci)RESP.sub.i.sup.d mod X); and in case of performing digital signature of a message m the following second steps are carried out in said identification device U (18) and/or in a verification device V (17): separates said small prime numbers PK.sub.i which are inside SD.sup.d mod X; and computes a number Z defined by Z=H(R.sub.1.sup.d mod X & . . . & R.sub.h.sup.d mod X & m) and reads said number Z as a set {c.sub.1, . . . ,c.sub.h } of h numbers c.sub.i such that each 0.ltoreq.c.sub.i .ltoreq.k; R.sub.i SK.sub.ci mod X) and sends the set {Z, m, RESP.sub.1, . . . ,RESP.sub.h } to V; 0) then 1 else PK.sub.ci)RESP.sub.i.sup.d mod X & m).
It is a further object of the invention to disclose an identification device and a verification device, respectively, for the inventive method. This object is reached by the inventive identification device and verification device disclosed in claims 11 and 12, respectively.
In principle the inventive identification device contains first computation means (15), first memory means (16) which are connected to said first computation means and first
REFERENCES:
patent: 5140634 (1992-08-01), Guillou et al.
patent: 5218637 (1993-06-01), Angebaud et al.
Cain David C.
Emanuel Peter M.
Shedd Robert D.
Thomson Consumer Electronics S.A.
Tripoli Joseph S.
LandOfFree
Method, identification device and verification device for identi does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, identification device and verification device for identi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, identification device and verification device for identi will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-922033