×

Method and apparatus for authenticating accreditations and for authenticating and signing messages

DC
  • US 5,140,634 A
  • Filed: 10/09/1991
  • Issued: 08/18/1992
  • Est. Priority Date: 09/07/1987
  • Status: Expired due to Term
First Claim
Patent Images

1. A system for the authentication of an accreditation information A with zero-knowledge proof, this information having been formulated by a process of the public-key type comprising the following operations:

  • an authority issuing the accreditation chooses two prime factors, forms the product N of these two factors, keeps secret these factors, chooses an integer p that comprises at least ten bit positions and publishes N and p,for the holder of the accreditation, a digital identity I is formed, and supplemented by redundancy in order to form a shaded identity word J,accreditation information A is formulated by the authority by taking the p-th root of the shaded identity J in the ring of integers modula N, (A=J1/p mod N=J), said system comprisinga memory for storing inverse information modulo N of the accreditation information A, i.e. the inverse accreditation information B (BP j mod N=1), which is to be authentication,processing means for executing the authentication operation by means of a single-layer interactive and probabilistic digital process of the zero-knowledge proof type and comprising communication means for communicating between a medium containing the memory called "the verified" and an element called "the verifier", said processing means comprising;

    in the verified first random number generating means for generating a first random integer r that is a member of the ring of integers modulo N,power raising means fed by the first random number generating means for raising r to the power p modulo N to produce a title T,first transmission means fed by the power raising means for transmitting at least a predetermined bit portion of the title T to the verifier,in the verifier second random number generating means for generating a second random number (D) within the interval O and (p-1), including the limits thereof,request means cum second transmission means fed by the second random number generating means for generating and transmitting a processing request to the verified,in the verified first calculating means fed by the second transmission means to calculate the product in the ring of integers modulo N of the first random integer r, and the D-th power of the inverse accreditation information B to feed the result thereof as a marker t=r.bD mod N to the first transmission means,in the verifier second calculating means fed by the first transmission means for calculating the product of the marker t, within the ring of integers moduluo N, and the D-th power of the shaded identity J, i.e. tP jD mod N,in the verifier comparing means fed by the second calculating means and by the first transmission means for comparing said predetermined bit portion to a corresponding bit portion of tP jD mod N for in a single comparisons step upon a detected equality issuing an authenticated accreditation signal.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×