Method and apparatus for generating a signature for a message and method and apparatus for verifying such a signature
View Patent ↗A method of generating a signature σ for a message m, the method enabling online/offline signatures. Two random primes p and q are generated, with N=pq; two random quadratic residues g and x are chosen in Z* N , and, for an integer z, h=g −z mod N is calculated. This gives the public key {g, h, x, N} and the private key {p, q, z}. Then, an integer t and a prime e are chosen. The offline signature part y may then be calculated as y=(xg −t ) 1/e b mod N where b is an integer bigger than 0, predetermined in the signature scheme. The online part k of the signature on message m is then calculated as k=t+mz and the signature σ on message m is generated as σ=(k, y, e) and returned. To verify the signature, it is checked that 1) e is an odd I E -bit integer, 2) k is an I K -bit integer, and 3) y e b g k h m ≡x(mod N). An advantage of the method is that it may be performed without hashing. Also provided are a signing device, a verification device, and computer program supports.
1. A method of generating a signature σ for a message m, the method comprising the steps, in a device, of:
obtaining three integers y, e, t, satisfying y=(xg −t ) 1/c mod N, where c=e b , b being a positive integer, and x, g, and N are elements of a public key, x and g being quadratic residues in Z* N and N being an I N -bit integer;
calculating a first part k of a signature σ, wherein the calculation of k comprises an integer multiplication of m and an I Z -bit integer z and an addition of t; and
outputting the signature σ, the signature σ comprising at least three values k, y, and e,
wherein the lengths of k, e, z, N, and h, h being an integer element of the public key, the lengths respectively being denoted I K , I E , I Z , I N , and I H , satisfy the following relations for a given value b, which denotes the relation between c and e:
I N ≧2( I E +2);
b ( I E −1)≧ I K +1; and
I N −4 ≧I K .
2. The method of claim 1 , wherein N is a RSA modulus comprising at least two primes p and q.
3. The method of claim 2 , wherein p=2p′+1 and q=2q′+1, where p′ and q′ are prime.
4. The method of claim 1 , wherein the step of obtaining three values y, e, t, comprises the steps of:
generating a prime e and an integer t and
calculating y=(xg −t ) 1/c mod N.
5. The method of claim 1 , wherein the three values y, e, t are obtained from a coupon stored in a memory.
6. The method of claim 1 , further comprising the step, between the obtention step and the calculation step, of receiving the message m.
7. The method of claim 1 , wherein the outputting step further comprises outputting the message m.
8. A method of verifying a signature σ for a message m, the signature being generated by a method according to claim 1 , the verification method comprising the step, in a device, of:
verifying that y c g k h m ≡x(mod N), wherein c depends on e and h is an element of the public key.
9. The method of claim 8 , further comprising the step of verifying that e is odd.
10. The method of claim 8 , further comprising the step of verifying that e is a I E -bit integer and that k is a I K -bit integer.
11. A device for generating a signature σ for a message m, the signature device comprising:
a processor adapted to:
obtain three integers y, e, t, satisfying y=(xg −t ) 1/c mod N,
where c depends on e, and x, g, and N are elements of a public key, x and g being quadratic residues in Z* N and N being an I N -bit integer; and
calculate a first part k of a signature σ wherein the calculation of k comprises an integer multiplication of m and an I Z -bit integer z and an addition of t; and
an output unit adapted to output the signature σ, the signature σ comprising at least three values k, y, and e,
wherein the lengths of k, e, z, N, and h, h being an integer element of the public key, the lengths respectively being denoted I K , I E , I Z , I N , and I H , satisfy the following relations for a given value b, which denotes the relation between c and e:
I N ≧2( I E +2);
b ( I E −1)≧ I K +1; and
I N −4≧ I K .
12. A device for verifying a signature σ for a message m, the signature being generated by a method according to claim 1 , the verification device comprising a processor adapted to:
verify that y c g k h m ≡x (mod N), wherein c depends on e and h is an element of the public key.
13. A computer program support storing instructions that, when executed in a processor, perform the method of signing a message m of claim 1 .
14. A computer program support storing instructions that, when executed in a processor, perform the method of verifying the signature σ for a message m of claim 8 .
15. The method of claim 1 , wherein I K is much greater than I Z +I H .
16. The device of claim 11 , wherein I K is much greater than I z +I H .