Method, apparatus and article for identification and signature
AssigneeYeda Research and Development Co. Ltd.
InventorsAdi Shamir, Amos Fiat
Life of this patent
Estimating the term…
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.
Claims42
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.sub.j =f(I,j) is a residue (mod n) having a root s.sub.j ;
- (e) computing roots s.sub.j of v.sub.j.sup.-1 (mod n);
- (f) recording on a retrievable medium of an identifier I, k, s.sub.j and related indices j.
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.sub.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.sub.j of v.sub.j.sup.- 1 (mod n);
- and
- (d) means for recording on a retrievable medium of an identifier I, s.sub.j and related indices.
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.sub.j which are quadratic residues (mod n), values s.sub.j which are roots of v.sub.j.sup.-1 (mod n), said microprocessor means including selection means for selecting a number r.sub.i .epsilon. (O,n), and computing means for computing x.sub.i =r.sub.i.sup.2 (mod n) and ##EQU13## in responsive to receiving a binary vector e.sub.i1...e.sub.ik.
Dependencies are inferred from the claim text.