In Nov 1988, Micali, Goldreich and Even submitted a patent that allows 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\)) This page uses an offline/online signature scheme, based on the paper: "An online/offline signature scheme based on the strong rsa assumption" [1]. Within this method, Alice has a public and a private key. Whilst she is offline, she can create a number of offline key pairs, and which she can use to sign a message which she is online.
Offline/Online Signatures |
Theory
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' \times q')\), and then calculates:
\(X_i = g^{s_i} \pmod n\)
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:
\(r = s_i \times H(M) \pmod {p'q'}\)
The signature is then \((X_i,r)\).
Check signature
Bob takes the signature of \((X,r)\) will check the signature with:
\(X^{H(M)} \equiv g^r \pmod n\)
This works because:
\(X^{H(M)} \equiv {(g^{s_i})}^{H(M)} \equiv g^{s_i H(M)} \equiv g^{s_i H(M) \pmod {p'q'}} \equiv g^r \pmod n\)
Coding
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) p=2*p_1+1 if (sympy.isprime(p)): break; while (True): q_1= getPrime(primebits, randfunc=get_random_bytes) q=2*q_1+1 if (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 ("\nOffline pair:") print (f"s'={s}, X={X1}") 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^r 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=22005907214787629663, q=28302012508433361623, n=622811461252343452952085601595080623049 p'=11002953607393814831, q'=14151006254216680811 Offline pair: s'=2479550251, X=477042813831727728995906390188334982865 X=477042813831727728995906390188334982865, r=110311308473964283357072898432008088810 g^r mod n=549994792011473692396468826533301533213 X^H(m) = 549994792011473692396468826533301533213 Signature proven Res3=1 Agreement
References
[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 [here].