# Online/Offline Signatures

In Nov 1988, Silvio Micali, Oded Goldreich and Shimon Even submitted a patent that allowed for a pre-computation element so that a message could be signed without the requirement to be on-line. It involved two main stages. The first was a precomputed value that was independent on the message (*s*1), and the second for a one-time public key (*s*2) [here]:

Let’s implement an offline/online signature scheme, based on the paper: “An online/offline signature scheme based on the strong rsa assumption” [1]. In this method, we generate two prime numbers *p* and *q *and which are:

*p*=2*p*′+1

*q*=2*q*′+1

and where *p*′ and *q*′ are also prime. We then create a random generator (*g*), and select a hash function (H). This hash function has *k *bits. Alice’s public key is:

(*n*,*g*,*H*)

and her private key is (p,q).

## Offline phase

Alice selects a number of random values (*s_i*) between 0 and (*p*′×*q*′), and then calculates:

The offline pairs will be (*s_i*,*X_i*).

## Online phase

Alice takes a message (*M*), and computes *H*(*m*), and then uses the next unused (*s_i*,*X_i*) pair to compute:

The signature is then (*Xi*,*r*).

## Check signature

Bob takes the signature of (*X*,*r*) will check the signature with:

The coding is here:

import random

import hashlib

import mathfrom Crypto.Util.number import getPrime

from Crypto.Random import get_random_bytesimport sys

import sympyprimebits=32msg="hello"

if (len(sys.argv)>1):

primebits=int(sys.argv[1])

if (len(sys.argv)>2):

msg=(sys.argv[2])if primebits>48: primebits=48while (True):

p_1 = getPrime(primebits, randfunc=get_random_bytes)

q_1= getPrime(primebits,

randfunc=get_random_bytes)

p=2*p_1+1

q=2*q_1+1

if (sympy.isprime(p) and sympy.isprime(q)): break;g=3

n=p*qs=random.randint(0,2**32)X1 = pow(g,s,n)

print (f"Message: {msg}")

print (f"\np={p}, q={q}, n={n}")

print (f"p'={p_1}, q'={q_1}")print ("Offline pair:")

print (f"s'={s}, X={X_1}")

a = hashlib.md5(msg.encode())

b = a.hexdigest()

H=int(b, 16)r = (s*H) % (p_1*q_1)

print (f"X={X1}, r={r}")

res1= pow(g,r,n)

res2 = pow(X1,H,n)print (f"\ng^ mod n={res1}\nX^H(m) = {res2}")if (res1==res2): print("Signature proven")res3=sympy.gcd(H,r)print (f"\n\nRes3={res3}")if (res3<pow(2,int(2*math.sqrt(128)),n)): print ("Agreement")

A sample run is:

Message: Hellop=84263, q=91283, n=7691779429

p'=42131, q'=45641

Offline pair:

s'=1553375497, X=4399084253

X=4399084253, r=544284756g^ mod n=1762454498

X^H(m) = 1762454498

Signature proven

Res3=1

Agreement

Here is a demo:

and the code:

## Conclusions

And there you go. Alice can be offline and still produce signatures.

## Reference

[1] Yu, P., & Tate, S. R. (2007, May). An online/offline signature scheme based on the strong rsa assumption. In 21st International Conference on Advanced Information Networking and Applications Workshops (AINAW’07) (Vol. 1, pp. 601–606). IEEE.