# Online/Offline Signatures

Oct 31, 2020 · 3 min read

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 (s1), and the second for a one-time public key (s2) [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=2p′+1

q=2q′+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).

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).

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).

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

The coding is here:

`import randomimport hashlibimport mathfrom Crypto.Util.number import getPrimefrom Crypto.Random import get_random_bytesimport sysimport 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=3n=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=7691779429p'=42131, q'=45641Offline pair:s'=1553375497, X=4399084253X=4399084253, r=544284756g^ mod n=1762454498X^H(m) = 1762454498Signature provenRes3=1Agreement`

Here is a demo:

and the code:

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

[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.

Written by

Written by