SharedW-OTS.sagewsOpen in CoCalc
######################
# PoC implementation of
# Winternitz one-time signature scheme (W-OTS)
######################
#### some results (trade-off time vs. space)
# n = 256
#
# w = 2
# sizeof(S) = 1256 bytes
# 0.0134010314941  execution time in seconds
#
# w = 16
# sizeof(S) = 272 bytes
# 2.50523591042  execution time in seconds

import hashlib
import sys
import time

# "hash" function
def H(input, power):
    for i in range(power):
        m = hashlib.md5(str(input))
        input = m.digest()
    return input
#        input = (input + 1)
#   return R(input)

start = time.time()

# security parameter n
n = 256

# Winternitz paramter w
w = 16

# calculate t1, t2, and t
t1 = ceil(n/w)
t2 = ceil((floor(log(t1, 2))+1+w)/w)
t = t1 + t2
print ("n = {}, w = {}, t1 = {}, t2 = {}, and t = {}".format(n, w, t1, t2, t))

#  0 ... 2^n - 1
R = IntegerModRing(2**n)

# random message
m = R.random_element()
print ("random message m = {}".format(m))

# message in base 2
d = (Integer(m).digits(2))
print ("random message m base 2 = {}".format(d))

# padding d
d_ = [ d.insert(0,0) for i in range(len(d),t1*w) ]
print ("padded message d = {}".format(d))

# create secret key
# .... create 2*n random in ModRing(2**n)
X = [ R.random_element() for i in range(t) ]
print ("secret key X = {}, sizeof(X) = {} bytes".format(X, sys.getsizeof(X)))

# create public key
# H : x -> x + 1 modulo (2^n - 1)
Y = [ H(X[i], (2**w - 1)) for i in range(len(X))]
print ("public key Y = {}, sizeof(Y) = {} bytes".format(Y, sys.getsizeof(Y)))

# calculate the checksum
c = sum([ (2**w)-(int(str(str(d[i*w]) + str(d[i*w+1])), base=2)) for i in range(t1) ])
print ("checksum = {}".format(c))
c_b = Integer(c).digits(2)
c_b_ = [ c_b.insert(0,0) for i in range(len(c_b),t2*w) ]
print ("padded checksum c_b = {}".format(c_b))

# concatenate "d" padded message (base 2) and "c_b" padded checksum (base 2)
for i in range(len(c_b)):
    d.append(c_b[i])

print ("d and c_b = {}".format(d))

# calculate signature
S = [ H(X[i], (int(str(str(d[i*w]) + str(d[i*w+1])), base=2))) for i in range(t) ]
print ("signature S = {}, sizeof(S) = {} bytes".format(S, sys.getsizeof(S)))

# verify the signature
Y_S = [ H(S[i], (2**w)-1-(int(str(str(d[i*w]) + str(d[i*w+1])), base=2))) for i in range(t) ]
#print ("Y_S = {}".format(Y_S))
print ("verfication = {}".format(Y == Y_S))

end = time.time()
print ("{} execution time in seconds".format(end - start))

# flip the first bit in the message
d[0] = (d[0] + 1) % 2
print ("manipulated d and c_b = = {}".format(d))

# verify the signature
Y_S = [ H(S[i], (2**w)-1-(int(str(str(d[i*w]) + str(d[i*w+1])), base=2))) for i in range(t) ]
#print ("Y_S = {}".format(Y_S))
print ("verfication = {}".format(Y == Y_S))

n = 256, w = 16, t1 = 16, t2 = 2, and t = 18 random message m = 77604501905584796122332430185362543747211110907312320097787155862631486859018 random message m base 2 = [0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1] padded message d = [0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1] secret key X = [85302381627046238855072260009322222959953812180317304648180846358115724817742, 106729843719415632393612793679727209611382570220042232908207118431557534918346, 61871119706188128136670428378777263221009673231680604726484396758028643847146, 115245473174618494264499954724066178180993932390207644781321130718865452265851, 52736175388007211640975850159064878306531227208126518503984687476956798038308, 83445900348045818371914607226141819557305324512562223151871079475067996904014, 87735179159225578406645771479435003542619931774614206251189855501522298363242, 109907652924599064387562168075803483910593749556454406909096832733208125782395, 34890631093947075147814882116187874722311939540150967569365331819498914573805, 69608698242339687123549892214517366783786765734679572437114255052307853907609, 83707997943021335733547038538426740047090606418494384188570377124867623090814, 37805051718151504017041951895436681418873594624575957845265650188798621629345, 61716250035562586495310430733813520336058487570091505287380157965012129950186, 4547373223832338584895476035286797840520669658104863667371869409090803478251, 79550016827947083213974319675216384933554221591311658703898498630876566923367, 99706621704453355201825663754867053884407454616518108257069297036381111286604, 112050530080434158596691718271222875711960550546587765864666646980691206830580, 60097013302728934044372780815725735757636679762853342422536141564852268756215], sizeof(X) = 272 bytes public key Y = ['\x98*\xab\xa3\xd9\x9dOi\x98\x81\x93\x87\x1b3]>', 'QZ\xf70\xe4B\x14U\xb8\xe5^\xaf\xd8\x10\xad_', '\x887\x02\xbbP\x00\xcdV\x94\x1f\xa2\x99\xce\xff \xe1', 'r\xf2\x9f,\xee/Y\xe9|ss\x145\x0b\xe5k', '\x97\x8d\x15/9oGb\xf2\xb1=\xca\xb6\xee[\x04', '\x13\x8a\xa6\x194\xfb\'Y\xc1\x91\xf9\xea\xcc"\xa8\xa3', '\x8f\xefZ\x92\x1fz\xb3\x94%\xcf\xd5\x18\xeb\xc0\x9aT', '\x0eo\xd1\xbd\xfe\x1cz5\x10\xb3\xf1\xc8&-dK', 'A\x16\xf1f\x05u\xffzC\xfc\xc75J\xb5z\xcc', '\xde\xd73/\xc59i\[email protected]\xba\xe3M\xe5t|O', '\x1b\xa8\xf8\xd3\xdb\x01\xac\x00\xe5\xc9\xcb\xae%r\xeb\x07', '\xdd\x8c8z\x7fz\x1cUK\xc1G\xbe\xeb\[email protected]\x8b', '\xc6zk\xfb\xb8\x8c\x15\x9a\xe8\xfe\xd4h{\x1f:Y', '\x10G\xb9\x02q\xf3\xbf\x8f%\x04\x99-\xd2\xd9\x01\xa5', '\xf5\xd4\xfa\xbcB+3\x1d\x9d\xd7\xaf\x8f\xf4\x11i\xa7', '|@\xc8\x91"\xaa\xd7\xce\x91\xf3\x86\xe4\xf3P\xf4Q', '\x11l\x94\x17)\ti\x9c\xe4\x80[F\xf7\xdb\xff\n', '\x16\x87\xaa\x1e\x90n\xff\x08\xdd\x9f]\xe7 |\x17\xbd'], sizeof(Y) = 272 bytes checksum = 1048548 padded checksum c_b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] d and c_b = [0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] signature S = ['z\x9e\x98&\x98&\x03\xb9\x03\xb9x\x03+\xa2\xfcs', 106729843719415632393612793679727209611382570220042232908207118431557534918346, '\xa4\xb9\xdb)\x12\xf5\x8e\xd1\xe02\xc9\n\x9d!\x94\xfb', 115245473174618494264499954724066178180993932390207644781321130718865452265851, '\xf5\xb0z\x84\x88\xdaJ\x19\x90T\xb0\xea\x0eO\x80\xe5', 'dx\x90\xb1\xb5oIK\xd2OHg#\x96\xc0\x8d', '\x89\x08\xac\xa66i\xdc[Z\x99\\\x92\x18\xf7\x9b+', 109907652924599064387562168075803483910593749556454406909096832733208125782395, "\xd6\xcel\xf1\x97'\xac\xfe\xc0Yx\xf6\x93\xd92<", '\x89\xf4\x92o\xeb\x81\x95\x15\xef\xf6\x92"Q\xff\xd9\xf2', '\x88*\x88J\[email protected]\xd4\x10\x83\x85\x85\x1f\xef\xcd\x85\xb5', 'b\x8b \xabL\xa8M\xdb\x0f|T{\x0e\x1a\xe0\xf3', '\nOg(4]\xee\xfb\x1a\xba\xabJ\x8e|\x8a\x1e', '\x93\xad\x0c\xfce\x17{\x08\xa2\xb5]\x82\x03Sm\xbf', '\xce\xb1\x8d\xa6\xbb|\x9ao\x05\xa3\xfc\xef\x0cr\xc5\x17', '\xa1\xe0a\xf5\x01a\x17\xa6\x9f\xe0\x15h\xcd\x83\x7f3', 112050530080434158596691718271222875711960550546587765864666646980691206830580, '\x10\x86/>y\xe2\x9c\x9a\xe0Z\xc6\xaa\xb1g(\x83'], sizeof(S) = 272 bytes verfication = True 2.70785093307 execution time in seconds manipulated d and c_b = = [1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] verfication = False