Method for providing information security by exchanging authentication and signing an electronic signature and apparatus therefor

Claim 3

A method in accordance with claim 1, wherein q used as a modulus is replace by p-1.

Claim 4

An authentication method for authenticating a prover electronic data processing entity to a verifier electronic data processing entity within an electronic data processing system and authenticating data transferring between the prover entity and the verifier entity, comprising steps of: (a) sending a first signal representative of a value x from the prover entity to the verifier entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g r1 mod p), where p and q are prime numbers, g is an integer between 1 and p, and r 1 is a random number between 1 and q; (b) sending a second signal representative of a random number e from the verifier entity to a prover entity, the second signal being produced, by the verifier entity, by generating a random number e; (c) sending a third and fourth signal representative of a value y 1 and y 2 , respectively, from the prover entity to the verifier entity after receiving the second signal, the third and fourth signal being produced, by the prover entity, by calculating the value y 1 (y 1 ≡r+er 4 mod q) and the value y 2 (y 2 ≡r 2 +er 3 mod q), where r 2 and r 3 are random numbers, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the prover entity; and (d) determining whether the prover entity is authentic by comparing the first signal with a fifth signal representative of a value x' after receiving the first, third and fourth signals, the fifth signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v2 are public keys of the prover entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p).

Claim 5

An authentication method for authenticating a prover electronic data processing entity to a verifier electronic data processing entity within an electronic data processing system and authenticating data transferring between the prover entity and the verifier entity, comprising steps of: (a) sending a first signal representative of a value x from the prover entity to the verifier entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g r1 mod p), where p and q are prime numbers, g is an integer between 1 and p, and r 1 is a random number between 1 and q; (b) sending a second signal representative of a random number e from the verifier entity to a prover entity, the second signal being produced, by the verifier entity, by generating a random number e; (c) sending a third and fourth signal representative of a value y 1 and y 2 , respectively, from the prover entity to the verifier entity after receiving the second signal, the third and fourth signal being produced, by the prover entity, by calculating the value y 1 (y 1 ≡r+er 4 mod q) and the value y 2 (y 2 ≡r 2 +er 3 mod q), where r 2 and r 3 are random numbers, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the prover entity; and (d) determining whether the prover entity is authentic by comparing the first signal with a fifth signal representative of a value x' after receiving the first, third and fourth signals, the fifth signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v2 are public keys of the prover entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p).

Claim 6

A method in accordance with claim 3, wherein q used as a modulus is replace by p-1.

Claim 7

A signing method for a verifier electronic data processing entity to verify authenticity of an electronic signature produced by signer electronic data processing entity within an electronic data processing system, comprising steps of: (a) sending a first signal representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m from the signer entity to the verifier entity, the second signal being produced, by the signer entity, by calculating a value e by hashing a value x with m (e=h(x, m)), a value y 1 (y 1 ≡r+er 4 mod q), and a value y 2 (y 2 r 2 +er 3 mod q), where the value x is calculated according to a function (x≡g r1 mod p), p and q are prime numbers, g is an integer between 1 and p, r 1 , r 2 and r 3 are random numbers, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the signer entity; and (b) determining whether the document m from signer entity is authentic by hashing the first signal representative of m with a third signal representative of a value x' to generate a hash value h(x', m) and comparing the hash value h(x', m) with a portion of the second signal representative of the value e after receiving the first and second signals, the third signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v 2 are public keys of the signer entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p).

Claim 8

A signing method for a verifier electronic data processing entity to verify authenticity of an electronic signature produced by signer electronic data processing entity within an electronic data processing system, comprising steps of: (a) sending a first signal representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m from the signer entity to the verifier entity, the second signal being produced, by the signer entity, by calculating a value e by hashing a value x with m (e=h(x, m)), a value y 1 (y 1 ≡r+er 4 mod q), and a value y 2 (y 2 r 2 +er 3 mod q), where the value x is calculated according to a function (x≡g r1 mod p), p and q are prime numbers, g is an integer between 1 and p, r 1 , r 2 and r 3 are random numbers, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the signer entity; and (b) determining whether the document m from signer entity is authentic by hashing the first signal representative of m with a third signal representative of a value x' to generate a hash value h(x', m) and comparing the hash value h(x', m) with a portion of the second signal representative of the value e after receiving the first and second signals, the third signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v 2 are public keys of the signer entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p).

Claim 9

A method in accordance with claim 5, wherein q used as a modulus is replace by p-1.

Claim 10

An authentication method for authenticating a prover electronic data processing entity to a verifier electronic data processing entity within an electronic data processing system, comprising steps of: (a) sending a second signal representative of a random number e from the verifier entity to a prover entity, the second signal being produced by the verifier entity, by generating a random number e, the second signal being sent responsive to a first signal representative of a value x being sent from the prover entity to the verifier entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g r mod p), where p and q are prime numbers, g is an integer between 1 and p, and r is a random number; and (b) determining whether the prover entity is authentic by comparing the first signal with a fourth signal representative of a value x' after receiving the first signals, the fourth signal being produced, by the verifier, entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where y is substituted for y 1 , 1 is substituted for v 1 , 0 is substituted for y 2 , and v is substituted for v 2 , v is a public key of the prover entity calculated according to a function (V≡g -s mod p), and s is a secret key of the prover entity, the fourth signal being generated responsive to a third signal representative of a value y being sent from the prover entity to the verifier entity, the third signal being produced, by the prover entity, by calculating a value y (y≡r+es mod q).

Claim 11

An authentication method for authenticating a prover electronic data processing entity to a verifier electronic data processing entity within an electronic data processing system, comprising steps of: (a) sending a second signal representative of a random number e from the verifier entity to a prover entity, the second signal being produced by the verifier entity, by generating a random number e, the second signal being sent responsive to a first signal representative of a value x being sent from the prover entity to the verifier entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g r mod p), where p and q are prime numbers, g is an integer between 1 and p, and r is a random number; and (b) determining whether the prover entity is authentic by comparing the first signal with a fourth signal representative of a value x' after receiving the first signals, the fourth signal being produced, by the verifier, entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where y is substituted for y 1 , 1 is substituted for v 1 , 0 is substituted for y 2 , and v is substituted for v 2 , v is a public key of the prover entity calculated according to a function (V≡g -s mod p), and s is a secret key of the prover entity, the fourth signal being generated responsive to a third signal representative of a value y being sent from the prover entity to the verifier entity, the third signal being produced, by the prover entity, by calculating a value y (y≡r+es mod q).

Claim 12

An authentication method for authenticating a prover electronic data processing entity to a verifier electronic data processing entity within an electronic data processing system, comprising steps of: (a) sending a second signal representative of a random number e from the verifier entity to a prover entity, the second signal being produced by the verifier entity, by generating a random number e, the second signal being sent responsive to a first signal representative of a value x being sent from the prover entity to the verifier entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g 1 r1 g 2 r2 mod p), where p and q are prime numbers, g 1 and g 2 are integers between 1 and p, and r 1 and r 2 are random numbers; and (b) determining whether the prover entity is authentic by comparing the first signal with a fifth signal representative of a value x' after receiving the first signals, the fifth signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where g 2 is substituted for v 1 , v is substituted for v 2 , g 1 is substituted for g, v is a public key of the prover entity calculated according to a function (V≡g 1 -s1 g 2 -s2 mod p), and s 1 and s 2 are secret keys of the prover entity, the fifth signal being generated responsive to a third and a fourth signal representative of a value y 1 and y 2 , respectively, being sent from the prover entity to the verifier entity, the third and the fourth signal being produced, by the prover entity, by calculating a value y 1 (y 1 ≡r 1 +es 1 mod q) and a value y 2 (y 2 ≡r 2 +es s mod q).

Claim 13

An authentication method for authenticating a prover electronic data processing entity to a verifier electronic data processing entity within an electronic data processing system, comprising steps of: (a) sending a second signal representative of a random number e from the verifier entity to a prover entity, the second signal being produced by the verifier entity, by generating a random number e, the second signal being sent responsive to a first signal representative of a value x being sent from the prover entity to the verifier entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g 1 r1 g 2 r2 mod p), where p and q are prime numbers, g 1 and g 2 are integers between 1 and p, and r 1 and r 2 are random numbers; and (b) determining whether the prover entity is authentic by comparing the first signal with a fifth signal representative of a value x' after receiving the first signals, the fifth signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where g 2 is substituted for v 1 , v is substituted for v 2 , g 1 is substituted for g, v is a public key of the prover entity calculated according to a function (V≡g 1 -s1 g 2 -s2 mod p), and s 1 and s 2 are secret keys of the prover entity, the fifth signal being generated responsive to a third and a fourth signal representative of a value y 1 and y 2 , respectively, being sent from the prover entity to the verifier entity, the third and the fourth signal being produced, by the prover entity, by calculating a value y 1 (y 1 ≡r 1 +es 1 mod q) and a value y 2 (y 2 ≡r 2 +es s mod q).

Claim 14

An electronic signing method for a verifier electronic data processing entity to verify authenticity of an electronic signature produced by signer electronic data processing entity within an electronic data processing system, comprising steps of: (a) producing a third signal representative of a value x', by the verifier entity, by calculating the value x'(x'=g y1 v 1 y2 v 2 e mod p), where y is substituted for y 1 , 1 is substituted for v 1 , 0 is substituted for y 2 , and v is substituted for v 2 , v is a public key of the prover entity calculated according to a function (V≡g -s mod p), and s is a secret key of the prover entity, the third signal being produced responsive to a first signal representative of electronic date m and a second signal representative of an electronic signature (e, y) for m being sent from the signer entity to the verifier entity, the second signal being produced, by the signer entity, by calculating a value y (y≡r+es mod q) and by calculating a value e by hashing a value x with m (e=h(x, m)) where the value x is calculated according to a function (x≡g r mod p), p and q are prime numbers, g is an integer between 1 and p, r is a random number, and s is a secret key of the signer entity; (b) hashing the first signal representative of m with the third signal representative of the value x' to generate a hash value h(x', m); and (c) determining whether the document m from signer entity is authentic by comparing the hash value h(x', m) with a portion of the second signal representative of the value.

Claim 15

An electronic signing method for a verifier electronic data processing entity to verify authenticity of an electronic signature produced by signer electronic data processing entity within an electronic data processing system, comprising steps of: (a) producing a third signal representative of a value x', by the verifier entity, by calculating the value x'(x'=g y1 v 1 y2 v 2 e mod p), where y is substituted for y 1 , 1 is substituted for v 1 , 0 is substituted for y 2 , and v is substituted for v 2 , v is a public key of the prover entity calculated according to a function (V≡g -s mod p), and s is a secret key of the prover entity, the third signal being produced responsive to a first signal representative of electronic date m and a second signal representative of an electronic signature (e, y) for m being sent from the signer entity to the verifier entity, the second signal being produced, by the signer entity, by calculating a value y (y≡r+es mod q) and by calculating a value e by hashing a value x with m (e=h(x, m)) where the value x is calculated according to a function (x≡g r mod p), p and q are prime numbers, g is an integer between 1 and p, r is a random number, and s is a secret key of the signer entity; (b) hashing the first signal representative of m with the third signal representative of the value x' to generate a hash value h(x', m); and (c) determining whether the document m from signer entity is authentic by comparing the hash value h(x', m) with a portion of the second signal representative of the value.

Claim 16

An electronic signing method for a verifier electronic data processing entity to verify authenticity of an electronic signature produced by signer electronic data processing entity within an electronic data processing system, comprising steps of: (a) producing a third signal representative of a value x', by the verifier entity, by calculating the value x'(x'=g y1 v 1 y2 v 2 e mod p), where g 2 is substituted for v, v is substituted for v 2 , g 1 is substituted for g, v is a public key of the prover entity calculated according to the function (V≡g 1 -s1 g 2 -s2 mod p), p and q are prime numbers, g 1 and g 2 are integers between 1 and p, and s 1 and s 2 are secret keys of the signer entity, the third signal being produced responsive to a first signal representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m being sent from the signer entity to the verifier entity, the second signal being produced, by the signer entity, by calculating the value y 1 (y 1 ≡r 1 +es 1 mod q) and a value y 2 (y 2 ≡r 2 +es 2 mod q) and by calculating a value e by hashing a value x with m (e=h(x, m)) where the value x is calculated according to a function (x≡g 1 r1 g 2 r2 mod p), e, r 1 and r 2 are random numbers; (b) hashing the first signal representative of m with the third signal representative of the value x' to generate a hash value h(x', m); and (c) determining whether the document m from signer entity is authentic by comparing the hash value h(x', m) with a portion of the second signal representative of the value.

Claim 17

An electronic signing method for a verifier electronic data processing entity to verify authenticity of an electronic signature produced by signer electronic data processing entity within an electronic data processing system, comprising steps of: (a) producing a third signal representative of a value x', by the verifier entity, by calculating the value x'(x'=g y1 v 1 y2 v 2 e mod p), where g 2 is substituted for v, v is substituted for v 2 , g 1 is substituted for g, v is a public key of the prover entity calculated according to the function (V≡g 1 -s1 g 2 -s2 mod p), p and q are prime numbers, g 1 and g 2 are integers between 1 and p, and s 1 and s 2 are secret keys of the signer entity, the third signal being produced responsive to a first signal representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m being sent from the signer entity to the verifier entity, the second signal being produced, by the signer entity, by calculating the value y 1 (y 1 ≡r 1 +es 1 mod q) and a value y 2 (y 2 ≡r 2 +es 2 mod q) and by calculating a value e by hashing a value x with m (e=h(x, m)) where the value x is calculated according to a function (x≡g 1 r1 g 2 r2 mod p), e, r 1 and r 2 are random numbers; (b) hashing the first signal representative of m with the third signal representative of the value x' to generate a hash value h(x', m); and (c) determining whether the document m from signer entity is authentic by comparing the hash value h(x', m) with a portion of the second signal representative of the value.

Claim 18

An authentication method for authenticating a prover electronic data processing entity to a verifier electronic data processing entity within an electronic data processing system and authenticating data transferring between the prover entity and the verifier entity, comprising steps of: (a) sending a first signal representative of the value x from the prover entity to the verifier entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g r1 mod p), where p and q are prime numbers, g is an integer between 1 and p, and r 1 is a random number between 1 and q; (b) sending a second signal representative of a random number e from the verifier entity to a prover entity, the second signal being produced, by the verifier entity, by generating a random number e; (c) sending a third and fourth signal representative of a value y 1 and y 2 , respectively, from the prover entity to the verifier entity after receiving the second signal, the third and the fourth signal being produced, by the prover entity, by setting the value y 2 equal to a random number r 2 and by calculating the value y 1 (y 1 ≡r 1 +es 2 +s 1 y 2 mod q), where s 1 and s 2 are secret keys of the prover entity; and (d) determining whether the prover entity is authentic by comparing the first signal with a fifth signal representative of a value x' after receiving the first, third and fourth signals, the fifth signal being produced, by the verifier entity, by calculating a valuex'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v 2 are public keys of the prover entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p).

Claim 19

An authentication method for authenticating a prover electronic data processing entity to a verifier electronic data processing entity within an electronic data processing system and authenticating data transferring between the prover entity and the verifier entity, comprising steps of: (a) sending a first signal representative of the value x from the prover entity to the verifier entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g r1 mod p), where p and q are prime numbers, g is an integer between 1 and p, and r 1 is a random number between 1 and q; (b) sending a second signal representative of a random number e from the verifier entity to a prover entity, the second signal being produced, by the verifier entity, by generating a random number e; (c) sending a third and fourth signal representative of a value y 1 and y 2 , respectively, from the prover entity to the verifier entity after receiving the second signal, the third and the fourth signal being produced, by the prover entity, by setting the value y 2 equal to a random number r 2 and by calculating the value y 1 (y 1 ≡r 1 +es 2 +s 1 y 2 mod q), where s 1 and s 2 are secret keys of the prover entity; and (d) determining whether the prover entity is authentic by comparing the first signal with a fifth signal representative of a value x' after receiving the first, third and fourth signals, the fifth signal being produced, by the verifier entity, by calculating a valuex'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v 2 are public keys of the prover entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p).

Claim 20

A signing method for a verifier electronic data processing entity to verify authenticity of an electronic signature produced by signer electronic data processing entity within an electronic data processing system, comprising steps of: (a) sending a first signal representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m from the signer entity to the verifier entity, the second signal being produced by the signer entity, by calculating a value e by hashing a value x with m (e=h(x, m)), a value y 1 (y 1 ≡r 1 +es 2 s 1 y 2 mod q), and setting a value y 2 equal to a random number r 2 , where the value x is calculated according to a function (x≡g r1 mod p), p and q are prime numbers, g is an integer between 1 and p, r 1 and r 2 are random numbers, and s 1 and s 2 are secret keys of the signer entity; and (b) determining whether the document m from signer entity is authentic by hashing the first signal representative of m with a third signal representative of a value x' to generate a hash value h(x', m) and comparing the hash value h(x', m) with a portion of the second signal representative of the value e after receiving the first and second signals, the third signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p , where v 1 and v 2 are public keys of the signer entity.

Claim 21

A signing method for a verifier electronic data processing entity to verify authenticity of an electronic signature produced by signer electronic data processing entity within an electronic data processing system, comprising steps of: (a) sending a first signal representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m from the signer entity to the verifier entity, the second signal being produced by the signer entity, by calculating a value e by hashing a value x with m (e=h(x, m)), a value y 1 (y 1 ≡r 1 +es 2 s 1 y 2 mod q), and setting a value y 2 equal to a random number r 2 , where the value x is calculated according to a function (x≡g r1 mod p), p and q are prime numbers, g is an integer between 1 and p, r 1 and r 2 are random numbers, and s 1 and s 2 are secret keys of the signer entity; and (b) determining whether the document m from signer entity is authentic by hashing the first signal representative of m with a third signal representative of a value x' to generate a hash value h(x', m) and comparing the hash value h(x', m) with a portion of the second signal representative of the value e after receiving the first and second signals, the third signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p , where v 1 and v 2 are public keys of the signer entity.

Claim 22

A prover electronic data processing entity for enabling authentication of the prover entity to a verifier electronic data processing entity and authentication of data transferring between the prover entity and the verifier entity, the prover entity comprising: (a) signal generation means for (i) producing a first signal representative of a value x by calculating the value x (x≡g 1 r1 g 2 r2 mod p, (ii) producing a third signal representative of a value y 1 by calculating the value y 1 (y 1 ≡r+er 4 mod q), and (iii) producing a fourth signal representative of a value y 2 by calculating the value y 2 (y 2 ≡r 2 +er 3 mod q), where p and q are prime numbers, g 1 and g 2 are integers between 1 and p, r 1 , r 2 and r 3 are random numbers between 1 and q, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the prover entity; and (b) communication means, operatively coupled to the signal generation means, for (i) sending the first signal from the prover entity to the verifier entity and (ii) sending a third and fourth signal representative of a value y 1 and y 2 , respectively, from the prover entity to the verifier entity in response to receiving a second signal representative of a random number e generated by the verifier entity.

Claim 23

A prover electronic data processing entity for enabling authentication of the prover entity to a verifier electronic data processing entity and authentication of data transferring between the prover entity and the verifier entity, the prover entity comprising: (a) signal generation means for (i) producing a first signal representative of a value x by calculating the value x (x≡g 1 r1 g 2 r2 mod p, (ii) producing a third signal representative of a value y 1 by calculating the value y 1 (y 1 ≡r+er 4 mod q), and (iii) producing a fourth signal representative of a value y 2 by calculating the value y 2 (y 2 ≡r 2 +er 3 mod q), where p and q are prime numbers, g 1 and g 2 are integers between 1 and p, r 1 , r 2 and r 3 are random numbers between 1 and q, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the prover entity; and (b) communication means, operatively coupled to the signal generation means, for (i) sending the first signal from the prover entity to the verifier entity and (ii) sending a third and fourth signal representative of a value y 1 and y 2 , respectively, from the prover entity to the verifier entity in response to receiving a second signal representative of a random number e generated by the verifier entity.

Claim 24

The prover entity of claim 13 wherein g is substituted for g 1 , 1 is substituted for g 2 , and 0 is substituted for r 1 .

Claim 25

The prover entity of claim 13 wherein 1 is substituted for g 2 , r 1 is substituted for r, 0 is substituted for y 2 , and s 1 is substituted for r 4 .

Claim 26

The prover entity of claim 13 wherein r 1 is substituted for r, s 1 is substituted for r 4 , and s 2 is substituted for r 3 .

Claim 27

The prover entity of claim 13 wherein g is substituted for g 1 , 1 is substituted for g 2 , 0 is substituted for r 1 , y is substituted for y 1 , and r 2 is substituted for y 2 , where y is calculated according to a function y 1 (y 1 ≡r 1 +es 2 +s 1 y 2 mod q).

Claim 28

A verifier electronic data processing entity for enabling authentication of a prover entity to the verifier electronic data processing entity and authentication of data transferring between the prover entity and the verifier entity, the verifier entity comprising: (a) signal generation means for producing a second signal representative of a random number e; (b) communication means, operatively coupled to the signal generation means, for (i) sending the second signal from the verifier entity to the prover entity in response to receiving a first signal representative of a value x produced by the prover entity and (ii) receiving the first signal, a third representative of a value y 1 , and a fourth signal representative of a value y 2 , from the prover entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g 1 r1 g 2 r2 mod p), the third signal being produced, by the prover entity, by calculating the value y 1 (y 1 ≡r+er 4 mod q), and the fourth signal being produced, by the prover entity, by calculating the value y 2 (y 2 ≡r 2 +er 3 mod q), where p and q are prime numbers, g, g 1 and g 2 are integers between 1 and p, r 1 , r 2 and r 3 are random numbers between 1 and q, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the prover entity; and (c) comparison means, operatively coupled to the signal generation means and the communication means, for determining whether the prover entity is authentic by comparing the first signal with a fifth signal representative of a value x' after receiving the first, third and fourth signals , the fifth signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v 2 are public keys of the prover entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p).

Claim 29

A verifier electronic data processing entity for enabling authentication of a prover entity to the verifier electronic data processing entity and authentication of data transferring between the prover entity and the verifier entity, the verifier entity comprising: (a) signal generation means for producing a second signal representative of a random number e; (b) communication means, operatively coupled to the signal generation means, for (i) sending the second signal from the verifier entity to the prover entity in response to receiving a first signal representative of a value x produced by the prover entity and (ii) receiving the first signal, a third representative of a value y 1 , and a fourth signal representative of a value y 2 , from the prover entity, the first signal being produced, by the prover entity, by calculating the value x (x≡g 1 r1 g 2 r2 mod p), the third signal being produced, by the prover entity, by calculating the value y 1 (y 1 ≡r+er 4 mod q), and the fourth signal being produced, by the prover entity, by calculating the value y 2 (y 2 ≡r 2 +er 3 mod q), where p and q are prime numbers, g, g 1 and g 2 are integers between 1 and p, r 1 , r 2 and r 3 are random numbers between 1 and q, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the prover entity; and (c) comparison means, operatively coupled to the signal generation means and the communication means, for determining whether the prover entity is authentic by comparing the first signal with a fifth signal representative of a value x' after receiving the first, third and fourth signals , the fifth signal being produced, by the verifier entity, by calculating a value x'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v 2 are public keys of the prover entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p).

Claim 30

The verifier entity of claim 18 wherein g is substituted for g 1 , 1 is substituted for g 2 , and 0 is substituted for r 1 .

Claim 31

The verifier entity of claim 18 wherein 1 is substituted for g 2 , r 1 is substituted for r, 0 is substituted for y 2 , 1 is substituted for v 1 , and s 1 is substituted for r 4 .

Claim 32

The verifier entity of claim 18 wherein r 1 is substituted for r, s 1 is substituted for r 4 , g 2 is substituted for v 1 , v is substituted for v 2 , and s 2 is substituted for r 3 , where v is a public key of the prover entity calculated according to a function (V≡g 1 -21 g 2 -s2 mod p).

Claim 33

The verifier entity of claim 18 wherein g is substituted for g 1 , 1 is substituted for g 2 , 0 is substituted for r 1 , y is substituted for y 1 , and r 2 is substituted for y 2 , where y is calculated according to a function y 1 (y 1 ≡r 1 +es 2 +s 1 y 2 mod q).

Claim 34

A signer electronic data processing entity for enabling verification of authenticity of an electronic signature produced by the signer entity by a verifier electronic data processing entity, the signer entity comprising: (a) signal generation means for generating a first signal representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m, the second signal being produced, by the signer entity, by calculating a value e by hashing a value x with m (e=h(x, m)), a value y 1 (y 1 ≡r+er 4 mod q), and a value Y 2 (y 2 ≡r 2 +er 3 mod q), where the value x is calculated according to a function x (x≡g 1 r1 g 2 r2 mod p), p and q are prime numbers, g, g 1 and g 2 are integers between 1 and p, r 1 , r 2 and r 3 are random numbers between 1 and q, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the signer entity; and (b) communication means, operatively coupled to the signal generation means, for sending the first and the second signal from the signer entity to the verifier entity.

Claim 35

A signer electronic data processing entity for enabling verification of authenticity of an electronic signature produced by the signer entity by a verifier electronic data processing entity, the signer entity comprising: (a) signal generation means for generating a first signal representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m, the second signal being produced, by the signer entity, by calculating a value e by hashing a value x with m (e=h(x, m)), a value y 1 (y 1 ≡r+er 4 mod q), and a value Y 2 (y 2 ≡r 2 +er 3 mod q), where the value x is calculated according to a function x (x≡g 1 r1 g 2 r2 mod p), p and q are prime numbers, g, g 1 and g 2 are integers between 1 and p, r 1 , r 2 and r 3 are random numbers between 1 and q, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the signer entity; and (b) communication means, operatively coupled to the signal generation means, for sending the first and the second signal from the signer entity to the verifier entity.

Claim 36

The signer entity of claim 23 wherein g is substituted for g 1 , 1 is substituted for g 2 , and 0 is substituted for r 1 .

Claim 37

The signer entity of claim 23 wherein 1 is substituted for g 2 , r 1 is substituted for r, 0 is substituted for y 2 , and s 1 is substituted for r 4 .

Claim 38

The signer entity of claim 23 wherein r 1 is substituted for r, s 1 is substituted for r 4 , and s 2 is substituted for r 3 .

Claim 39

The signer entity of claim 23 wherein g is substituted for g 1 , 1 is substituted for g 2 , 0 is substituted for r 1 , y is substituted for y 1 , and r 2 is substituted for y 2 , where y is calculated according to a function y 1 (y 1 ≡r 1 +es 2 +s 1 y 2 mod q).

Claim 40

A verifier electronic data processing entity for enabling verification of authenticity of an electronic signature produced by a signer electronic data processing entity by the verifier entity, the verifier entity comprising: (a) communication means for receiving a first representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m from the signer entity to the verifier entity, the second signal being produced, by the signer entity, by calculating a value e by hashing a value x with m (e=h(x, m)), a value y 1 (y 1 ≡r+er 4 mod q), and a value y 2 (y 2 ≡r 2+er 3 mod q), where the value x is calculated according to a function x (x≡g 1 r1 g 2 r2 mod p), p and q are prime numbers, g, g 1 and g 2 are integers between 1 and p, r 1 , r 2 and r 3 are random numbers between 1 and q, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the, value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the signer entity; and (b) signal generation means, operatively coupled to the communication means, for producing a third signal representative of a value x' by calculating the value x'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v 2 are public keys of the signer entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p); (c) comparison means, operatively coupled to the communication means, for determining whether the document m from signer entity is authentic by hashing the first signal representative of m with the third signal representative of a value x' to generate a hash value h(x', m) and comparing the hash value h(x', m) with a portion of the second signal representative of the value e after receiving the first and second signals.

Claim 41

A verifier electronic data processing entity for enabling verification of authenticity of an electronic signature produced by a signer electronic data processing entity by the verifier entity, the verifier entity comprising: (a) communication means for receiving a first representative of electronic data m and a second signal representative of an electronic signature (e, y 1 , y 2 ) for m from the signer entity to the verifier entity, the second signal being produced, by the signer entity, by calculating a value e by hashing a value x with m (e=h(x, m)), a value y 1 (y 1 ≡r+er 4 mod q), and a value y 2 (y 2 ≡r 2+er 3 mod q), where the value x is calculated according to a function x (x≡g 1 r1 g 2 r2 mod p), p and q are prime numbers, g, g 1 and g 2 are integers between 1 and p, r 1 , r 2 and r 3 are random numbers between 1 and q, the value r is calculated according to a function (r≡r 1 +s 1 r 2 mod q), the, value r 4 is calculated according to a function (r 4 ≡s 1 r 3 +s 2 mod q), and s 1 and s 2 are secret keys of the signer entity; and (b) signal generation means, operatively coupled to the communication means, for producing a third signal representative of a value x' by calculating the value x'(x'=g y1 v 1 y2 v 2 e mod p), where v 1 and v 2 are public keys of the signer entity calculated according to functions (V 1 ≡g -s1 mod p) and (V 2 ≡g -s2 mod p); (c) comparison means, operatively coupled to the communication means, for determining whether the document m from signer entity is authentic by hashing the first signal representative of m with the third signal representative of a value x' to generate a hash value h(x', m) and comparing the hash value h(x', m) with a portion of the second signal representative of the value e after receiving the first and second signals.

Claim 42

The verifier entity of claim 28 wherein g is substituted for g 1 , 1 is substituted for g 2 , and 0 is substituted for r 1 .

Claim 43

The verifier entity of claim 28 wherein 1 is substituted for g 2 , r 2 is substituted for r, 0 is substituted for y 2 , 1 is substituted for v 1 , and s 1 is substituted for r 4 .

Claim 44

The verifier entity of claim 28 wherein r 1 is substituted for r, s 1 is substituted for r 4 , g 2 is substituted for v 1 , v is substituted for v 2 , and s 2 is substituted for r 3 , where v is a public key of the prover entity calculated according to a function (V≡g 1 -s1 g 2 -s2 mod p).

Claim 45

The verifier entity of claim 28 wherein g is substituted for g 1 , 1 is substituted for g 2 , 0 is substituted for r 1 , y is substituted for y 1 , and r 2 is substituted for y 2 , where y is calculated according to a function y 1 (y 1 ≡r 1 +es 2 +s 1 y 2 mod q).