Online/Offline Signatures

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

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 math

from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes

import sys
import sympy

primebits=32

msg="hello"

if (len(sys.argv)>1):
  primebits=int(sys.argv[1])
if (len(sys.argv)>2):
  msg=(sys.argv[2])

if primebits>48: primebits=48

while (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*q

s=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: Hello

p=84263, q=91283, n=7691779429
p'=42131, q'=45641
Offline pair:
s'=1553375497, X=4399084253
X=4399084253, r=544284756

g^ 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.