Patent ID: 8223963

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