密碼學 - 一次性簽章

import hashlib
import secrets

private_key = [[None for _ in range(256)] for _ in range(2)]
public_key = [[None for _ in range(256)] for _ in range(2)]
for i in range(256):
    private_key[0][i] = secrets.token_bytes(32)  # 256 bit
    private_key[1][i] = secrets.token_bytes(32)
    public_key[0][i] = hashlib.sha256(private_key[0][i]).digest()
    public_key[1][i] = hashlib.sha256(private_key[1][i]).digest()

import hashlib


def generate_signature(message, secret_keys):
    # Convert the message to bytes if it's not already
    if isinstance(message, str):
        message = message.encode('utf-8')

    # Hash the message
    hashed_message = hashlib.sha256(message).digest()

    # Convert hash to an integer (little endian)
    msg_int = int.from_bytes(hashed_message, 'little')

    # Generate the signature
    signature = []
    for i in range(256):
        bit = (msg_int >> i) & 1
        signature.append(secret_keys[bit][i])

    return signature


# Example usage
raw_message = 'Hello, World! I am the message.'
signature = generate_signature(raw_message, private_key)  # Assuming 'sk' is defined as before

print(f"Message: {raw_message}")
print(f"Signature length: {len(signature)}")
print(f"First few bytes of signature: {signature[:5]}")

def verify_signature(message, signature, public_keys):
    """
    Verify the digital signature of a given message.

    :param message: The original message (bytes or string)
    :param signature: The signature to verify (list of 256 byte strings)
    :param public_keys: The public key set (2x256 list of byte strings)
    :return: Boolean indicating if the signature is valid
    """
    # Convert the message to bytes if it's not already
    if isinstance(message, str):
        message = message.encode('utf-8')

    # Hash the message
    hashed_message = hashlib.sha256(message).digest()

    # Convert hash to an integer (little endian)
    msg_int = int.from_bytes(hashed_message, 'little')

    try:
        for i in range(256):
            bit = (msg_int >> i) & 1
            if hashlib.sha256(signature[i]).digest() != public_keys[bit][i]:
                return False
        return True
    except Exception as e:
        print(f"Error during signature verification: {e}")
        return False


# Assuming 'signature' and 'pk' (public keys) are already defined
is_valid = verify_signature(raw_message, signature, public_key)

print(f"Message: {raw_message}")
print(f"Signature is valid: {is_valid}")

import hashlib
import secrets


def generate_lamport_keypair():
    private_key = [[secrets.token_bytes(32) for _ in range(256)] for _ in range(2)]
    public_key = [[hashlib.sha256(private_key[i][j]).digest() for j in range(256)] for i in range(2)]
    return private_key, public_key


def hash_public_key(public_key):
    # 直接返回公鑰的串聯，不進行額外的雜湊
    return b''.join(b''.join(row) for row in public_key)


class MerkleTree:
    def __init__(self, leaves):
        self.leaves = leaves
        self.layers = [leaves]
        self.build_tree()

    def build_tree(self):
        layer = self.leaves
        while len(layer) > 1:
            next_layer = []
            for i in range(0, len(layer), 2):
                if i + 1 < len(layer):
                    next_layer.append(hashlib.sha256(layer[i] + layer[i + 1]).digest())
                else:
                    next_layer.append(layer[i])
            self.layers.append(next_layer)
            layer = next_layer
        self.root = layer[0]

    def get_proof(self, index):
        proof = []
        for layer in self.layers:
            if index % 2 == 0:
                if index + 1 < len(layer):
                    proof.append(('R', layer[index + 1]))
            else:
                proof.append(('L', layer[index - 1]))
            index //= 2
        return proof


# Generate Merkle tree
num_keypairs = 8
lamport_keypairs = [generate_lamport_keypair() for _ in range(num_keypairs)]
public_key_hashes = [hash_public_key(pk) for _, pk in lamport_keypairs]
merkle_tree = MerkleTree(public_key_hashes)

# Sign a message
message = "Hello, Merkle signature!"
keypair_index = 0  # Use the first keypair
private_key, public_key = lamport_keypairs[keypair_index]

merkle_proof = merkle_tree.get_proof(keypair_index)

import hashlib
import secrets


def hash_public_key(public_key):
    # 直接返回公鑰的串聯，不進行額外的雜湊
    return b''.join(b''.join(row) for row in public_key)


class MerkleTree:
    def __init__(self, leaves):
        self.leaves = leaves
        self.layers = [leaves]
        self.build_tree()

    def build_tree(self):
        layer = self.leaves
        while len(layer) > 1:
            next_layer = []
            for i in range(0, len(layer), 2):
                if i + 1 < len(layer):
                    next_layer.append(hashlib.sha256(layer[i] + layer[i + 1]).digest())
                else:
                    next_layer.append(layer[i])
            self.layers.append(next_layer)
            layer = next_layer
        self.root = layer[0]

    def get_proof(self, index):
        proof = []
        for layer in self.layers:
            if index % 2 == 0:
                if index + 1 < len(layer):
                    proof.append(('R', layer[index + 1]))
            else:
                proof.append(('L', layer[index - 1]))
            index //= 2
        return proof


def verify_proof(leaf, proof, root):
    current = leaf
    for direction, sibling in proof:
        if direction == 'L':
            current = hashlib.sha256(sibling + current).digest()
        else:
            current = hashlib.sha256(current + sibling).digest()
    return current == root


# Verify the signature
leaf_hash = hash_public_key(public_key)
is_merkle_valid = verify_proof(leaf_hash, merkle_proof, merkle_tree.root)

print(f"Message: {message}")
print(f"Merkle proof valid: {is_merkle_valid}")

import hashlib
import math
import secrets


def hash_function(data):
    """SHA-256 雜湊函數。"""
    return hashlib.sha256(data).digest()


def int_to_bytes(value, length):
    """將整數轉換為指定長度的位元組串。"""
    return value.to_bytes(length, byteorder='big')


def bytes_to_int(b):
    """將位元組串轉換為整數。"""
    return int.from_bytes(b, byteorder='big')


def base_w(X, w, l):
    """
    將整數 X 轉換為以 w 為基數、長度為 l 的數字列表。
    """
    digits = []
    for _ in range(l):
        digits.append(X % w)
        X //= w
    digits += [0] * (l - len(digits))  # 填充至長度 l
    return digits[::-1]  # 反轉列表以保持正確順序


def checksum(base_w_message, w, l2):
    """
    計算訊息的校驗和。
    """
    csum = sum(w - 1 - x for x in base_w_message)
    csum_len = l2
    csum_digits = base_w(csum, w, csum_len)
    return csum_digits


def generate_wots_parameters(n, w):
    """
    根據安全參數 n 和 Winternitz 參數 w 計算 WOTS 參數 l1、l2 和 l。
    """
    l1 = math.ceil(n / math.log2(w))
    l2 = math.ceil(math.log2(l1 * (w - 1)) / math.log2(w))
    l = l1 + l2
    return l1, l2, l


def generate_wots_keypair(n=256, w=16):
    """
    生成 WOTS 金鑰對。
    """
    l1, l2, l = generate_wots_parameters(n, w)
    # 生成 l 個隨機的 n 位私鑰元素
    sk = [secrets.token_bytes(n // 8) for _ in range(l)]
    # 計算公鑰
    pk = []
    for i in range(l):
        key = sk[i]
        for _ in range(w - 1):
            key = hash_function(key)
        pk.append(key)
    return sk, pk


def wots_sign(message, sk, n=256, w=16):
    """
    使用 WOTS 對訊息進行簽章。
    """
    l1, l2, l = generate_wots_parameters(n, w)
    # 將訊息進行雜湊
    msg_hash = hash_function(message.encode())
    # 將雜湊值轉換為以 w 為基數的數字列表
    msg_int = bytes_to_int(msg_hash)
    base_w_msg = base_w(msg_int, w, l1)
    # 計算校驗和
    csum_digits = checksum(base_w_msg, w, l2)
    # 合併訊息和校驗和數字列表
    digits = base_w_msg + csum_digits
    # 生成簽章
    signature = []
    for i in range(l):
        key = sk[i]
        for _ in range(digits[i]):
            key = hash_function(key)
        signature.append(key)
    return signature


def wots_verify(message, signature, pk, n=256, w=16):
    """
    驗證 WOTS 簽章。
    """
    l1, l2, l = generate_wots_parameters(n, w)
    # 將訊息進行雜湊
    msg_hash = hash_function(message.encode())
    # 將雜湊值轉換為以 w 為基數的數字列表
    msg_int = bytes_to_int(msg_hash)
    base_w_msg = base_w(msg_int, w, l1)
    # 計算校驗和
    csum_digits = checksum(base_w_msg, w, l2)
    # 合併訊息和校驗和數字列表
    digits = base_w_msg + csum_digits
    # 計算簽章對應的公鑰
    computed_pk = []
    for i in range(l):
        key = signature[i]
        for _ in range(w - 1 - digits[i]):
            key = hash_function(key)
        computed_pk.append(key)
    # 比較計算得到的公鑰和原始公鑰
    return computed_pk == pk


# 範例使用
if __name__ == "__main__":
    n = 256  # 安全參數，雜湊函數輸出位數
    w = 16  # Winternitz 參數，可調整
    sk, pk = generate_wots_keypair(n, w)
    message = "Hello, Winternitz signature!"
    signature = wots_sign(message, sk, n, w)
    is_valid = wots_verify(message, signature, pk, n, w)
    print(f"訊息: {message}")
    print(f"簽章有效性驗證結果: {is_valid}")