Method and apparatus for authenticating accreditations and for authenticating and signing messages
DCFirst Claim
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.
2 Assignments
Litigations
0 Petitions
Accused Products
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.
252 Citations
23 Claims
-
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 comprising a 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 Dependent Claims (2, 3, 4, 5)
-
-
6. 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=J1/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 (Bp 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 rp 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.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 modulo N, and the D-th power of the shaded identity J, i.e. tp jD 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". - View Dependent Claims (7, 8)
-
-
9. 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=j1/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., Bp 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 rp 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. - View Dependent Claims (10, 11)
-
-
12. 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
space="preserve" listing-type="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;
space="preserve" listing-type="equation">t=r.B.sup.D mod Ne) generating second comparison data equal to
space="preserve" listing-type="equation">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 Jl/p mod N, so that Bp 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. - View Dependent Claims (13, 14, 15)
-
-
16. 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
space="preserve" listing-type="equation">T=r.sup.p mod Nc) 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;
space="preserve" listing-type="equation">t=r.B.sup.D mod Nf) 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 tp JD 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 Jl/p mod N, so that Bp J mod N=1.
-
-
17. 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
space="preserve" listing-type="equation">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
space="preserve" listing-type="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 Jl/p mod N, so that Bp 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;
space="preserve" listing-type="equation">t=r.B.sup.D mod N.
-
-
18. 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
space="preserve" listing-type="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 Jl/p mod N, so that Bp J mod N=1; e) means for calculating a number number t according to the equation;
space="preserve" listing-type="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}.
-
-
19. 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, rp 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;
space="preserve" listing-type="equation">t=r.B.sup.D mod N;e) calculating a second intermediate value according to tp JD 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;
wherer 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 Jl/p mod N so that Bp J mod N=1. - View Dependent Claims (20, 21)
-
-
22. 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, rp 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;
space="preserve" listing-type="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, tp Jd 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 Jl/p mod N, so that Bp J mod N=1.
-
-
23. 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=Jl/p mod N, so that Bp 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=rp 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
space="preserve" listing-type="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.
-
Specification