Image for post
Image for post
Photo by Romain Dancre on Unsplash

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]:

Image for post
Image for post

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:

Image for post
Image for post

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:

Image for post
Image for post

The signature is then (Xi,r).

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

Image for post
Image for post

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=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*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: Hellop=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:

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.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store