SharedMSS.sagewsOpen in CoCalc
######################
# PoC implementation of
# Merkle's signature scheme using W-OTS
######################
#
# n = 256, w = 16, h = 4, t1 = 16, t2 = 2, and t = 18
# number of leafs = 16 : 2^4 * 32 = 512 bytes
# 19.1253180504 execution time in seconds for generating keys
# 0.00327515602112 execution time in seconds for signing (!!!hash tree available!!!)
# 1.14603590965 execution time in seconds for verifying
#
###
#
# n = 256, w = 16, h = 10, t1 = 16, t2 = 2, and t = 18
# number of leafs = 1024 : 2^10 * 32 = 32768
# 1270.08455801 execution time in seconds for generating keys
# 0.0460112094879 execution time in seconds for signing (!!!hash tree available!!!)
# 1.33836889267 execution time in seconds for verifying

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


# calculate root note = public key
def calcRoot(pk, height):
    #print ("pk = {}, height = {}".format(pk, height))
    if height == 0:
        return pk
    else:
        treeLayers[height -1] = pk
        return calcRoot([ H(((pk[i]) + (pk[i+1])),1) for i in range(0, len(pk)-1, 2)], height - 1)

# calculate authentication path
def getAuthPath(index, tree):
    resultTree = [ ]
    for height in range(h-1, -1, -1):
        if(index% 2 == 0):
            resultTree.append(tree[height][index+1])
        else:
            resultTree.append(tree[height][index-1])
        index = index >> 1
    return resultTree

# calculate root node corresponding to the given authentication path
def calcRootAP(authPath, index):
    #print ("authentication path = {}".format(authPath))
    if (len(authPath) > 1):
        if(index% 2 == 0):
        #print ("length of authentication path = {}".format(len(authPath)))
            newNode = H((authPath[0] + authPath[1]),1)
        else:
            newNode = H((authPath[1] + authPath[0]),1)
        index = index >> 1
        authPath.pop(1)
        authPath[0] = newNode
        #print ("authPath = {}".format(authPath))
        return calcRootAP(authPath, index)
    else:
        #print ("authPath = {}".format(authPath))
        return authPath




start = time.time()

# security parameter n
n = 256

# Winternitz paramter w
w = 16

# height of the merkle tree
h = 3

# leaf index
leafIndex = 0

treeLayers = [ i for i in range(h) ]

# calculate t1, t2, and t
t1 = ceil(n/w)
t2 = ceil((floor(log(t1, 2))+1+w)/w)
t = t1 + t2
print ("n = {}, w = {}, h = {}, t1 = {}, t2 = {}, and t = {}".format(n, w, h, 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 j in range(t)] for i in range(2**h) ]
#print ("X = {}, sizeof(secret key) = {} bytes".format(X, sys.getsizeof(X)))

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

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

start = time.time()

# calculate H(Y[i][0]) for i in range(2**h) using only the first value instead of the whole Y[i][j]
HashedY = [ H(Y[i], 1) for i in range(2**h)]
#print ("HashedY = {}, sizeof(HashedY) = {} bytes".format(HashedY, sys.getsizeof(HashedY)))

# 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])

# calculate public key (root of merkle's tree)
PK = calcRoot(HashedY, h)
print ("number of leafs = {}".format(len(HashedY)))
print ("public key / root = {}".format(PK))
#print ("hash tree = {}".format(treeLayers))

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

# calculate authentication path for index = 0
AP = getAuthPath(leafIndex, treeLayers)
AP.insert(0, HashedY[leafIndex])
print ("sizeof(authentication path) = {} bytes".format(sys.getsizeof(AP)))

end = time.time()
print ("{} execution time in seconds for signing (!!!hash tree available!!!)".format(end - start))

start = time.time()

# verify W-OTS 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 of W-OTS signature = {}".format(Y[leafIndex] == Y_S))

# verify public key
resultAP = calcRootAP(AP, leafIndex)
print ("resultAP = {}".format(resultAP))
print ("verification of public key = {}".format(resultAP == PK))

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