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

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=J 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 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 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 P j 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 P j D mod N for in a single comparisons step upon a detected equality issuing an authenticated accreditation signal.

Claim 2

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 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 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 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 P j 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 P j D mod N for in a single comparisons step upon a detected equality issuing an authenticated accreditation signal.

Claim 7

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 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 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 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 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 p j 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".

Claim 8

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 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 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 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 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 p j 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".

Claim 11

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

Claim 12

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

Claim 15

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 l/p mod N, so that B 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.

Claim 16

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 l/p mod N, so that B 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.

Claim 20

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 p J 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 l/p mod N, so that B p J mod N=1.

Claim 21

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 p J 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 l/p mod N, so that B p J mod N=1.

Claim 26

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 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 p J 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 l/p mod N so that B p J mod N=1.

Claim 27

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 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 p J 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 l/p mod N so that B p J mod N=1.

Claim 30

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 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 p J 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 l/p mod N, so that B p J mod N=1.

Claim 31

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 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 p J 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 l/p mod N, so that B p J mod N=1.

Claim 32

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 l/p mod N, so that B 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 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.

Claim 33

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 l/p mod N, so that B 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 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.