Method and apparatus for generating a signature for a message and method and apparatus for verifying such a signature

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/emod 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 IE-bit integer, 2) k is an IK-bit integer, and 3) yegkhm≡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.

This application claims the benefit, under 35 U.S.C. §365 of International Application PCT/EP2009/056759, filed Jun. 2, 2009, which was published in accordance with PCT Article 21(2) on Jan. 7, 2010 in English and which claims the benefit of European patent application No. 080305240.7, filed on Jun. 9, 2008.

FIELD OF THE INVENTION

The present invention relates generally to cryptography, and in particular to an online/offline signature scheme that does not rely on random oracles.

BACKGROUND OF THE INVENTION

An online/offline signature scheme allows a two-phase generation of a digital signature. The most costly computations may be performed before the message to sign is known; this is the offline phase. Once the message is known, relatively rapid computations are then performed in the online phase. The skilled person will appreciate that this property is desired for time-constrained applications, such as for example electronic payments or when driving towards automated toll booths, and also for low-cost devices that do not have much in the way of computational resources.

In “On the Fly Authentication and Signature Schemes Based On Groups of Unknown Order” Journal of Cryptology, 19(4):463-487, 2006, M. Girault, G. Poupard, and J. Stern propose an online/offline signature scheme known as the GPS scheme. A drawback of this scheme is that its security proof stands in the random oracle model.

An online/offline signature scheme in the standard model (i.e. not relying on random oracles) is presented by B. Chevallier-Mames and M. Joye in “A Practical and Tightly Secure Signature Scheme Without Hash Function” in M. Abe (editor), Topics in Cryptology—CT-RSA 2007, volume 4377 of Lecture Notes in Computer Science, pages 339-356, Springer-Verlag, 2007. A drawback of this scheme resides in the size of its parameters, the public and private keys, as well as in the size of the resulting signature (both in the off-line and on-line phases). Further, it is noted that an increased size translates into an efficiency loss in computation, storage and transmission.

Another on-line/off-line signature scheme in the standard model is presented by K. Kurosawa and K. Schmidt-Samoa in “New On-line/Off-line Signature Schemes Without Random Oracles” in M. Yung et al. (editors), Public Key Cryptography—PKC 2006, volume 3958 of Lecture Notes in Computer Science, pages 330-346, Springer-Verlag, 2006. A drawback in this scheme is that the on-line phase involves a modular multiplication, which is more costly than an integer multiplication.

Further on-line/off-line signature schemes are presented by Marc Joye and Hung-Mei Lin in “On the TYS Signature Scheme”. These schemes are the Tan-Yi-Siew (TYS) signature scheme in its original and in its modified form.

The original TYS scheme first generates a public key and a private key. Two random primes are chosen p=2p′+1 and q=2q′+1, where p′ and q′ are prime and log2p′q′>2I+1. N=pq. Two quadratic residues g and x in Z*Nare chosen such that the order of g is p′q′. Finally, a random I-bit integer z is chosen and h=g−zmod N is calculated. The public key is pk={g, h, x, N} and the private key is sk={p, q, z}. m denotes the message to be signed. An I-bit integer k and an I-bit prime e are randomly picked and the following values are computed: y=(xg−k)1/emod N, c=H(pk, y, m) and t=k+cz. The signature on message m is then σ=(t, y, e). The authors discovered however that the TYS scheme was totally insecure and therefore provided a modified scheme.

The modified scheme makes use of four security parameters—IN, IH, IEand IK—that satisfy IE≧IH+2 and IK>>IN+IH. The modified scheme first generates a public key and a private key. Two random primes are chosen p=2p′+1 and q=2q′+1, where p′ and q′ are primes of equal length so that N=pq is of length IN. Two quadratic residues g and x in Z*Nare chosen randomly. Finally, h=g−zmod N is calculated for a random integer z mod p′q′. The public key is still pk={g, h, x, N} and the private key is sk={p, q, z}. m denotes the message to be signed. An IK-bit integer t and an IE-bit prime e are randomly picked and the following values are computed: y=(xg−t)1/emod N, c=H(pk, m) and k=t+cz. The signature on message m is then σ=(k, y, e). As will be appreciated, it is mainly the lengths of some parameters that have changed, but this does in fact provide the security that the TYS scheme lacks. However, the modified scheme, which may be seen as a variant of the Camenisch-Lysyanskaya signature scheme, still requires rather much computation and provides a quite lengthy signature. For example, typical parameter lengths—IN=1024, IH=160, IE=162 and IK=1344—give a signature length of 1344+1024+162=2530 bits for the 1024-bit RSA modulus.

It can therefore be appreciated that there is a need for an improved solution that provides online/offline digital signatures. This invention provides such a solution.

SUMMARY OF THE INVENTION

In a first aspect, the invention is directed to a method of generating a signature σ for a message m. Three integers y, e, t, satisfying y=(xg−t)1/emod N are obtained, where c depends on e, and x, g, and N are elements of a public key, x and g being quadratic residues in Z*Nand N being an IN-bit integer; a first part k of a signature σ is calculated, wherein the calculation of k comprises an integer multiplication of m and a IZ-bit integer z and an addition of t; and the signature σ is output, the signature σ comprising at least three values k, y, and e. The lengths of k, e, z, N, and h, h being an integer element of the public key, the lengths respectively being denoted IK, IE, IZ, IN, and IH, satisfy the following relations for a given value b, which denotes the relation between c and e:
IN≧2(IE+2);
b(IE−1)≧IK+1; and
IN−4≧IK>>IZ+IH.

In a first preferred embodiment, e is prime and c equals e to the power of a positive integer b. This use of e raised to the power of b enables shorter signatures.

In a second preferred embodiment, N is a RSA modulus comprising at least two primes p and q. It is advantageous that p=2p′+1 and q=2q′+1, where p′ and q′ are prime.

In a third preferred embodiment, the three values y, e, t, are obtained by generating a prime e and an integer t; and calculating y=(xg−t)1/cmod N.

In a fourth preferred embodiment, the three values y, e, t are obtained from a coupon stored in a memory.

In a fifth preferred embodiment, the message m is received between the obtention of the three values y, e, t, and the calculation step of the first part k of the signature.

In a sixth preferred embodiment, the message m is output with the signature σ.

In a second aspect, the invention is directed to a method of verifying a signature σ for a message m, the signature being generated by a method according to the first aspect of the invention. It is verified that ycgkhm≡x(mod N), wherein c depends on e and h is an element of the public key.

In a seventh preferred embodiment, it is further verified that e is odd.

In a tenth preferred embodiment, it is further verified that e is an IE-bit integer and that k is an IK-bit integer.

In a third aspect, the invention is directed to a device for generating a signature σ for a message m. The signature device comprises a processor adapted to obtain three integers y, e, t, satisfying y=(xg−t)1/cmod 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*Nand N being an IN-bit integer; and calculate a first part k of a signature σ, wherein the calculation of k comprises an integer multiplication of m and an IZ-bit integer z and an addition of t. The signature device further comprises an output unit adapted to output the signature σ, the signature σ comprising at least three values k, y, and e. The lengths of k, e, z, N, and h, h being an integer element of the public key, the lengths respectively being denoted IK, IE, IZ, IN, and IH, satisfy the following relations for a given value b, which denotes the relation between c and e:
IN≧2(IE+2);
b(IE−1)≧IK+1; and
IN−4≧IK>>IZ+IH.

In a fourth aspect, the invention is directed to a device for verifying a signature σ for a message m, the signature being generated by the method of the first aspect of the invention. The verification device comprises a processor adapted to verify that ycgkhm≡x(mod N), wherein c depends on e and h is an element of the public key.

In a fifth aspect, the invention is directed to a computer program support storing instructions that, when executed in a processor, performs the method of signing a message m of the first aspect of the invention.

In a sixth aspect, the invention is directed to a computer program support storing instructions that, when executed in a processor, perform the method of verifying the signature σ for a message m of the second aspect of the invention.

InFIGS. 2 and 3, the represented blocks are purely functional entities, which do not necessarily correspond to physically separate entities. These functional entities may be implemented as hardware, software, or a combination of software and hardware; furthermore, they may be implemented in one or more integrated circuits.

PREFERRED EMBODIMENT OF THE INVENTION

As mentioned, an online/offline signature scheme has an offline phase performed before reception of the message to sign (but which naturally may be performed also after reception) and an online phase that is performed once the message m is known. The skilled person will appreciate that message m may be a digest of a longer message.

A first part of the offline phase is key generation. First, two random primes p and q are generated; preferably p=2p′+1, q=2q′+1, where p′ and q′ are primes of equal length, so that N=pq is of length IN. Then, two random quadratic residues g and x are chosen in Z*N. Finally, for a random IZ-bit integer z, h=g−zmod N is calculated.

The public key pk is then {g, h, x, N} and the private key sk is {p, q, z}.

A second part of the offline phase is the calculation of the offline part y of the signature. A random IK-bit integer t and a random IE-bit prime e are chosen. The offline signature part y may then be calculated as
y=(xg−t)1/ebmodN
where b is an integer bigger than 0, predetermined in the signature scheme.

Now, the scheme is ready for the reception of the message m to sign; mεM, where M denoted the message space—M={0,1}IH, which may also be viewed as the set of integers in the range [0,2IH−1]. The online part k of the signature may then be calculated as
k=t+mz
and the signature on message m is σ=(k, y, e).

It is advantageous to verify, before transmission, that the online part k of the signature is a IK-bit integer; if not, it is preferable to generate another signature based on other values. An advantage of the present scheme is that the online phase may be performed without hashing.

The signature σ is then returned for verification; if necessary, the public key is also provided and in addition, the message m may also be provided. Signature σ=(k, y, e) on message m is accepted if and only if:1. e is an odd IE-bit integer,2. k is an IK-bit integer, and3. yebgkhm≡x(mod N).

In the scheme, the parameters IK, IE, IZ, IN, and IH(the latter denoting the maximal length, in bits, of input message m) should satisfy the following relations for the predetermined value b:
IN≧2(IE+2);
b(IE−1)≧IK+1; and
IN−4≧IK>>IZ+IH

It should be noted that the value b may also be variable, in which case it could be part of the public key pk, or be included in the signature σ.

It will be appreciated that the relations above are not chosen at random, nor are they mere workshop modifications within the reach of the person skilled in the art, as the skilled person would have no reason to come up with these particular relations. After all, as has been shown regarding the TYS scheme, a signature scheme is delicate and modifications thereto are not to be undertaken lightly. These relations enable a proof of the security of the scheme, which may be said to be a significant part of the inventiveness of the present invention.

With exemplary, typical values IH=160, IN=1024, IZ=160, IK=380, IE=128, and b=3, which gives a signature of only 1532 bits for a 1024-bit RSA modulus.

FIG. 1illustrates a method of generating a digital signature for a message m and of verifying the digital signature, according to a preferred embodiment of the invention. The flowchart illustrates the procedure hereinbefore. In step110, the public key pk and the private key sk are generated. Then the offline part y of the digital signature is generated in step120. Once the message m is received in step130, the online part k may be calculated and used to generate the complete digital signature σ in step140. The digital signature σ and the public key are sent in step150and the digital signature σ is verified in step160.

FIG. 2illustrates a unit210for generating at least one digital signature according to a preferred embodiment of the invention. The digital signature unit210comprises an input unit230adapted to receive a message m to sign, and an output unit240adapted to send a digital signature σ. The output unit240may be adapted to send a public key pk used for the signature. The output unit240may also be adapted to send the message m along with, or separately from, the corresponding digital signature σ (and, as the case may be, the public key pk). It will be appreciated that the input unit230and the output unit240may be combined as an input/output unit (not shown).

The digital signing unit210further comprises at least one processor220(hereinafter “processor”) adapted to perform the calculations for generating the digital signature for the received message m. The digital signing unit also comprises a memory250adapted to store data necessary for the calculations.

The person skilled in the art will appreciate that it is possible for the digital signing device210to store a number of so-called coupons, i.e. pre-calculated offline signature parts. It will further be appreciated that such coupons may be provided by a source external to the digital signing unit210, such as for example during manufacture, in which case the input unit230(or another suitable unit; not shown) is adapted to receive such coupons.

The skilled person will appreciate that it is also possible for the digital signature unit210to generate the message m that it signs. In this case, the output unit240is advantageously further adapted to send the message m.

FIG. 2also illustrates a computer program support260, such as an exemplary CD-ROM, that stores instructions that, when executed in the processor220, perform the method of signing a message m as described hereinbefore.

FIG. 3illustrates a unit310for verifying a digital signature of a message m, according to a preferred embodiment of the invention. The verification unit310comprises an input330adapted to receive a digital signature σ and, if necessary, a public key pk used for the signature. It will be appreciated that the verification unit310may possess a number of public keys corresponding to digital signature units. The verification unit310further comprises an output unit340adapted to output information whether or not the received digital signature σ is correct. The verification unit310may also comprise a unit (which may be comprised in the output unit340) for sending the message m to be signed. The input unit330may also be adapted to receive the message m along with, or separately from, the corresponding digital signature σ (and, as the case may be, the public key pk).

The verification unit310further comprises at least one processor320(hereinafter “processor”) adapted to perform the calculations necessary to verify the digital signature σ, and a memory350adapted to store data necessary for verification of message m, in particular the message m itself.

FIG. 3also illustrates a computer program support360, such as an exemplary CD-ROM, that stores instructions that, when executed in the processor320, perform the method of verifying the signature σ for the message m as described hereinbefore.

Each feature disclosed in the description and (where appropriate) the claims and drawings may be provided independently or in any appropriate combination. Features described as being implemented in hardware may also be implemented in software, and vice versa. Connections may, where applicable, be implemented as wireless connections or wired, not necessarily direct or dedicated, connections.

It will be appreciated that in the description and the claims, the expression “random” should be read as “random or pseudo-random”.