Back to results
US 5,140,634 AGranted
Method and apparatus for authenticating accreditations and for authenticating and signing messages
AssigneeU.S. Philips Corporation
InventorsLouis C. Guillou, Jean-Jacques Quisquater
Life of this patent
Estimating the term…
Abstract
A method and system for authentication of accreditations and of messages with zero-knowledge proof and for the signing of messages, and a station for use in such system, in particular executed as a smart card station. Instead of using multiple accreditations and an iterative process of verification, use is made of a comprehensve accreditation (high exponent p) and a number D is drawn at random, which number is within the range between 0 and p-1. The operations of verifiction proceed by the computation of the D-th power of the inverse accreditation B. Application in particular, to smart cards and, more specifically, to bank cards.
Claims23
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=J.sup.1/p mod N=J), said system comprising
- a memory for storing inverse information modulo N of the accreditation information A, i.e. the inverse accreditation information B (B.sup.P 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.b.sup.D 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. t.sup.P j.sup.D 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 t.sup.P j.sup.D mod N for in a single comparisons step upon a detected equality issuing an authenticated accreditation signal.
10 more elements
A system for the authentication of a message m originating from a presumably accredited principal, by means of a digital word B obtained by a public-key process comprising the following operations:
- an authority issuing the accreditation chooses two prime numbers, forms the product N of these two numbers, chooses an integer p, and publishes N and p,
- for the principal a digital identity is formed and supplemented by redundancy to form a shaded identity word J,
- accreditation information A is formulated by taking the p-th root of the shaped identify J in the ring of integers modulo N, (A=J.sup.1/p mod N), said system comprising
- a memory for storing inverse information modulo N of the accreditation information A, i.e., the inverse accreditation information B (B.sup.p j mod N=1),
- processing means for executing the authentication operation by means of a single-layer interactive and probabilistic process of the zero-knowledge proof type and comprising communication means for communicating between a medium containing the memory called "the verified" and am authentication 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 an element of the ring of integers modulo N,
- power raising means cum first compression means fed by the first random number generating means for raising r to the power p modulo N and computing a result by means of a compression function that has as arguments the message m and r.sup.p mod N, said result constituting a title T,
- first transmission means fed by the first compression means for transmitting at least a predetermined bit portion of the title T to the verifier,
- in the verifier second random generating means for generating a second randon number (D) within the interval between 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 said product as a marker t=r.B.sup.D 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 modulo N, and the D-th power of the shaded identity J, i.e. t.sup.p j.sup.D mod N,
- in the verifier second compression means fed by the second calculating means for computing a result by taking as arguments the message to be authenticated and said product,
- in the verifier comparing means fed by said second compression means and by the first transmission means for in a single comparison step comparing said predetermined bit portion to a corresponding bit portion of said result and upon a detected equality issuing an "authentic message signal".
11 more elements
A system for signing a message m by a presumably accredited entity, this accreditation having been formulated by a public-key process 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 thirty bit positions of publishes N and p,
- for an entity that is a signatory a digital identity I is formed and supplemented by redundancy in order to form a shaded identity word J,
- accreditation in formation A is formulated by the authority by taking the p-th root of the shaded identity J in the ring of integers modulo N (A=j.sup.1/p mod N), said system comprising:
- a memory medium held by the signatory for storing inverse information modulo N of the accreditation information A, i.e. the inverse accreditation information B (i.e., B.sup.p J mod N=1),
- signature generating means for generating a signature according to a probabilistic digital process, and comprising:
- random number generating means for generating a randon integer r that is a member of the ring of integers modulo N,
- power raising means fed by the random number generating means for raising r to the power p modulo N,
- compression means fed by the power raising means for calculating a compression function that has as arguments the message m and r.sup.p mod N to yield a result number D,
- product forming means fed by the random number generator and by the compression means to form the product of r and D-th power of the inverse accreditation information B to yield a sole marker t,
- transmission means fed by the product forming means to transmit a signal message comprising of the message m, the identity I, the result number D, and the sole marker t.
7 more elements
A method for authenticating, comprising the following steps in a verifier element:
- a) receiving, as first comparison data, at least a predetermined multibit field of a title number T calculated according to the equation
- T=r.sup.p mod N;
- b) drawing a second random number D within the closed interval {O,p-1};
- c) providing this second random number;
- d) receiving a marker number t calculated according to the equation:
- t=r.B.sup.D mod N
- e) generating second comparison data equal to
- T.sup.p J.sup.D mod N;
- f) comparing the first comparison data to a corresponding multibit field of the second comparison data, and
- g) upon correspondence directly generating an authentication approbation, where
- p is a first published integer p of at least ten bits;
- N is a second published integer which is a product of two secret prime factors;
- J is a second personalized digital quantity with added redundancy formed from a first personalized digital quantity I;
- B is an accreditation number stored outside the verifier element in the form of an inverse of A, A being equal to J.sup.l/p mod N, so that B.sup.p J mod N=1;
- and
- r is a first random number not available to the verifier element which is a member of the ring of integers modulo N.
13 more elements
A method of authenticating an object element using a verifier element comprising the following steps in the object element:
- a) choosing a first random integer r, as a member of the ring of integers modulo N;
- b) calculating a title number T according to the equation
- T=r.sup.p mod N
- c) providing at least a predetermined multibit field of the title number T as first comparison data to the verifier element;
- d) receiving from the verifier element a second random number D drawn from the closed interval {O,p-1};
- e) calculating a marker number t according to the equation:
- t=r.B.sup.D mod N
- f) providing the marker number t to the verifier element;
- and
- g) receiving an authentication indication from the verifier element based on a comparison therein between the first comparison data and a corresponding multibit field of second comparison data calculated according to t.sup.p J.sup.D mod N, where
- p is a first published integer p of at least ten bits;
- N is a second published integer which is a product of two secret prime factors;
- J is a second personalized digital quantity with added redundancy formed from a first personalized digital quantity I;
- and
- B is an accreditation number, stored in the object element in the form of an inverse of A, A being equal to J.sup.l/p mod N, so that B.sup.p J mod N=1.
12 more elements
Apparatus for authenticating an object element comprising
- a) means for receiving data from and transmitting data to the object element;
- b) means for drawing a random integer D within a closed interval {O,p-1};
- c) means for calculating second comparison data
- t.sup.p J.sup.D mod N;
- d) means for comparing the second comparison data with first comparison data received from the object element which first comparison data is in the form of at least a multibit field of a title number T calculated according to the equation
- T=r.sup.p mod N,
- where
- p is a first published integer p of at least ten bits;
- N is a second published integer which is a product of two secret prime factors;
- J is a second personalized digital quantity with added redundancy formed from a first personalized digital quantity I;
- r is a first random number which is a member of the ring of integers modulo N;
- B is an accreditation number, stored in the object element in the form of an inverse of A, A being equal to J.sup.l/p mod N, so that B.sup.p J mod N=1;
- and
- t is a marker number to be calculated in and received rom the object element and which satisfies the equation:
- t=r.B.sup.D mod N.
12 more elements
An object element susceptible of being verified in a verifier element, the object element comprising:
- a) means for transmitting data to and receiving data from the verifier element;
- b) means for drawing a random integer r from the ring of integers modulo N;
- c) means for calculating a title number T according to the equation
- T=r.sup.p mod N:
- d) means for storing an accreditation number B in the form of an inverse of A, A being equal to J.sup.l/p mod N, so that B.sup.p J mod N=1;
- e) means for calculating a number number t according to the equation:
- t=r.B.sup.d mod N;
- where
- p is a first published integer p of at least ten bits;
- N is a second published integer which is a product of two secret prime factors;
- J is a second personalized digital quantity with added redundancy formed from a first personalized digital quantity I;
- and
- D is a second random number, received from a verifying element, chosen from the interval {O,p-1}.
10 more elements
A method of authenticating a message m, comprising executing the following steps in a verifier element:
- a) receiving, as first comparison data from a communication medium, at least a first multibit field of a title number T, which title number is calculated by using the message m and a first intermediate value, r.sup.p mod N, as arguments to a compression function;
- b) choosing a second random number D within the closed interval {O,p-1};
- c) communicating the second random number to the communication medium;
- d) receiving from the communication medium a marker number t calculated according to the equation:
- t=r.B.sup.D mod N;
- e) calculating a second intermediate value according to t.sup.p J.sup.D mod N;
- f) calculating second comparison data by using message m and the second intermediate value as arguments to the compression function;
- g) comparing the first comparison data to a corresponding second multibit field of the second comparison data;
- h) upon correspondence, generating an authentication signal;
- where
- r is a first random integer which is a member of the ring of integers mod N and which is known at an opposite side of the communication medium;
- p is a first published integer p of at least ten bits;
- N is a second published integer which is a product of two secrete prime factors;
- J is a second personalized digital quantity with added redundancy formed from a first personalized digital quantity I;
- and
- B is an accreditation number stored at an opposite side of the communication medium in the form of an inverse of A, A being equal to J.sup.l/p mod N so that B.sup.p J mod N=1.
13 more elements
A method for authenticating a message m comprising the following steps at an opposite side of a communication medium from a verifier element:
- a) drawing a first random integer r at random from the ring of integers modulo N;
- b) generating, as first comparison data, a title number T which title number is calculated by using the message m and a first intermediate value, r.sup.p mod N, as arguments to a compression function;
- c) transmitting at least a first multibit field of the title number to the verifier element;
- d) receiving from the verifier element a second random number D chosen from the interval {O,p-1};
- e) calculating a marker number t according to the equation:
- t=r.B.sup.D mod N;
- f) transmitting the marker number to the verifier element;
- g) receiving an authentication signal from the verifier element when the first comparison data corresponds to corresponding bits of second comparison data, generated by using the message m and a second intermediate value, t.sup.p J.sup.d mod N, as arguments to the comparison function where
- p is a first published integer p of at least ten bits;
- N is a second published integer which is a product of two secret prime factors;
- J is a second personalized digital quantity with added redundancy formed from a first personalized digital quantity I;
- and
- B is an accreditation number stored at the opposite side in the form of an inverse of A, A being equal to J.sup.l/p mod N, so that B.sup.p J mod N=1.
10 more elements
A method for signing a message m by an accredited entity, said method comprising the following accreditation steps by an accrediting authority;
- a) generating and disclosing a first integer p of at least thirty bits and a product N of two secret prime factors;
- b) generating a first personalized digital quantity I with added redundancy to form a second personalized digital quantity J;
- c) generating and storing into a medium held by the accredited entity an accreditation number B as the inverse of A=J.sup.l/p mod N, so that B.sup.p J mod N=1;
- d) drawing a first random integer r which is a member of the ring of integers modulo N;
- e) calculating a first intermediate value d=r.sup.p mod N;
- f) applying a compression function f to first and second arguments, where the first argument is the message m and the second argument is the intermediate value D;
- g) generating a sole marker t according to the equation
- t=r.B.sup.D mod N;
- h) transmitting the message m, the identity I, the first intermediate value D and the marker t as a signed message.
6 more elements
Dependencies are inferred from the claim text.