Method, apparatus and article for identification and signature

• US 4,748,668 A
• Filed: 07/09/1986
• Issued: 05/31/1988
• Est. Priority Date: 07/09/1986
• Status: Expired due to Term

• Current Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Original Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Inventors: Fiat, Amos, Shamir, Adi
• Primary Examiner(s): Cangialosi, Salvatore
• Assistant Examiner(s): Lewis, Aaron J.
• Application Number:
  US06/883,247
• Time in Patent Office: 692 Days
• Field of Search: 380/30, 380/28
• US Class Current: 380/30
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: G07F 7/1016 Devices or methods for securing the PIN and other transaction-data, e.g. by encryption arrangements for secret communication, see H04L9/00
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs

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.

Claims

1. 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.

2. The method of claim 1 wherein the recording on the identifier is in binary form.

3. The method of claim 1 wherein the recording is in a ROM and the identifier includes microprocessing and input/output features.

4. 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² (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.

5. The method of claim 4 wherein the transmissions between the identifier and verifier are carried out in binary form.

6. The method of claim 4 wherein all steps are carried out using binary signals.

7. The method of claim 6 wherein modulus n is composed of at least 512 bits.

8. The method of claim 6 wherein only a lashed version of x_i is used.

9. The method of claim 6 wherein steps (d) through (h) are repeated at least two times.

10. 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₁ . . . 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₁ . . . z_t) are the same as e_ij.

11. The method of claim 10 wherein the first kt bits of f(m, z₁ . . . z_t) are used as e_ij matrix.

12. The method of claim 10 wherein the exchange is in binary form.

13. The method of claim 10 wherein the product kt is at least 72.

14. The method of claim 10 wherein k is at least 18 and t is at least 4.

18. 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² (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.

19. The apparatus of claim 18 wherein the transmissions between the identifier and verifier are carried out in binary form.

20. The apparatus of claim 18 wherein all steps are carried out using binary signals.

21. The apparatus of claim 20 wherein modulus n is composed of at least 512 bits.

22. The apparatus of claim 20 wherein only a hased version of x_i is used.

23. The apparatus of claim 20 wherein steps (d) through (h) are repeated at least two times.

24. 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² (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₁ . . . z_t) are the same as e_ij.

25. The apparatus of claim 24 wherein the exchange is in binary form.

26. The apparatus of claim 24 wherein the product kt is at least 72.

32. The method of claim 1 including the step of placing the numbers v_j in a public key directory.

33. 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.

34. 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² (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.

35. The method of claim 4 wherein the repetition of steps (d) through (h) are carried out in parallel.

36. 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² (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.

37. 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₁ . . . z_t) are the same as e_ij.

40. 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² (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.

41. 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² (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.

42. 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₁ . . . z_t) are the same as e_ij.

15. 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.

16. The apparatus of claim 15 wherein the recording on the identifier is in binary form.

17. The apparatus of claim 15 wherein the recording is in a ROM and the identifier includes microprocessing and input/output features.

38. 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.

39. Apparatus as defined in claim 38 further including means for retrieving the I, v_j and related indices from said public key directory.

27. 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² (mod n) and ##EQU13## in responsive to receiving a binary vector e_i1...e_ik.

28. 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.

29. 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² (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.

30. 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##

31. 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₁ . . . z_t) are e_ij.