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