密碼學 - 一次性簽章

Posted on 2024-09-02

在數位時代，資訊安全的重要性與日俱增。隨著量子計算的迅猛發展，傳統的加密方法正面臨著前所未有的挑戰。在這樣的背景下，一次性簽章(
One-Time Signature，OTS)作為一種創新的密碼學技術，正吸引著越來越多研究者和從業者的注意。

本文將深入探討一次性簽章的基本原理，詳細介紹各種主要的一次性簽章方案，包括 Lamport 簽章、Winternitz 簽章、Merkle
簽章方案等。我們還將比較這些方案的優缺點，討論它們在實際應用中的使用情況，並展望這一技術的未來發展方向。

一次性簽章的概念可以追溯到1979年，當時 Leslie Lamport 提出了最早的一次性簽章方案。從那時起，這一領域經歷了顯著的發展，產生了多種不同的實現方式，每種都有其獨特的特點和適用場景。

一次性簽章是一種特殊的數位簽章方案，其核心特點是每個金鑰對只能用於生成一次有效簽章。這種「一次性」的特性使得一次性簽章在面對各種攻擊，尤其是量子計算攻擊時，表現出強大的抗性。

隨著我們逐步邁入後量子時代，理解並掌握一次性簽章這一關鍵技術變得愈發重要。無論您是密碼學專家、IT
從業者，還是對資訊安全感興趣的普通讀者，本文都將為您提供一個全面而深入的一次性簽章技術概覽。

一次性簽章的基本原理

一次性簽章(OTS)是一種獨特的數位簽章系統，其核心理念圍繞著創建一個只能使用一次的簽章機制。這種方法的基礎建立在幾個關鍵概念之上，這些概念共同構成了
OTS 的安全框架和操作原則。

在 OTS
系統中，首先需要生成一對金鑰：私鑰用於簽章，公鑰用於驗證。這對金鑰的特殊之處在於它們被設計為僅使用一次。當用戶需要簽署一條消息時，他們會使用私鑰進行簽章。這個過程通常涉及某種形式的雜湊函數或複雜的數學運算，以確保簽章的唯一性和安全性。

簽章完成後，任何人都可以使用對應的公鑰來驗證簽章的真實性。如果驗證成功，這不僅證明了消息的完整性(即消息未被篡改)
，還確認了消息確實是由擁有私鑰的人簽署的。這個驗證過程是 OTS 系統的關鍵組成部分，它為整個通訊過程提供了必要的信任基礎。

OTS 的一個核心原則是每個私鑰只能使用一次。一旦私鑰被用於簽章，它就必須被廢棄，不能再次使用。這個「一次性」的特性是 OTS
安全性的關鍵。如果同一個私鑰被多次使用，系統的安全性將大幅降低，容易受到各種密碼分析攻擊。

OTS 的安全性主要基於兩個數學概念：雜湊函數的單向性和某些數學問題的難解性。即使攻擊者獲得了已使用過的私鑰，由於這些數學特性，他們也無法推導出未來的簽章或偽造新的有效簽章。此外，許多
OTS 方案還依賴於強隨機數生成器來增強其安全性，進一步提高了系統抵抗各種攻擊的能力。

然而，OTS 系統的設計也帶來了一些挑戰，主要是在金鑰管理方面。由於每對金鑰只能使用一次，系統需要有效的機制來生成、儲存和管理大量的金鑰對。這增加了系統的複雜性，同時也對儲存和計算資源提出了更高的要求。

OTS 的一個重要特性是它們在理論上能夠抵抗量子電腦的攻擊。這使得 OTS
在後量子密碼學中扮演著重要角色，成為未來密碼系統的潛在候選者。然而，這種高度的安全性通常以較大的金鑰和簽章大小為代價，這是在實際應用中需要權衡的因素。

總結來說，一次性簽章的基本原理表現了密碼學中安全性和實用性的平衡。通過巧妙地結合數學原理、金鑰管理策略和一次性使用的概念，OTS
為數位通訊提供了一種獨特而強大的安全機制。隨著量子計算的發展和安全需求的不斷提高，理解和應用這些原理將變得越來越重要，為未來的密碼系統發展奠定基礎。

主要的一次性簽章方案

一次性簽章技術自其誕生以來經歷了顯著的演變，產生了多種不同的方案，每種方案都有其獨特的特點和應用場景。本章節將深入探討幾種主要的一次性簽章方案，揭示它們的工作原理、優勢以及在實際應用中的潛力。

Lamport 簽章

Lamport 簽章是最早提出的一次性簽章方案之一，由 Leslie Lamport 於 1979 年設計。這種方法的核心思想是使用雜湊函數來創建一個安全的簽章系統。
論文可以參考 Lamport 簽章
，相當簡明。

產生金鑰

在 Lamport 簽章中，私鑰是由 512 個 256 bit 隨機數，兩兩一組。
而公鑰則是這些隨機數的雜湊值。

以下是如何產生金鑰的程式碼：

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()

產生簽章

首先，先將要簽章的訊息進行雜湊函數計算，得到一個 256 bit 的雜湊值。
接下來對於雜湊值的每一個位元進行比較，如果當下的 bit 是 0 那就選擇私鑰對應位置的第一個金鑰，如果當下的 bit 是 1
那就選擇第二個金鑰。

如此一來就會產生了一個 256 個 256 bit 的數字序列，這個序列就是簽章。

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}")

在這裏顯而易見的是，雖然 Lamport 簽章提供了強大的安全性，但它的主要缺點是產生較大的金鑰和較大的簽章尺寸。

Merkle 簽章方案

Merkle 簽章是由 Ralph Merkle 在 1979 年提出的一種多次性簽章方案,主要是真對 Lamport 簽章的改進。它通過使用 Merkle
樹結構,大大減少了公鑰的大小,同時保持了高度的安全性。
關於 Merkle 簽章的詳細論述可以參考 Merkle 的原始論文：
SECRECY, AUTHENTICATION, AND PUBLIC KEY SYSTEMS

產生金鑰

產生方法基本上跟 Lamport 簽章一樣，只是在產生金鑰時從一整條路徑變成根到葉節點的路徑。
這就建構了一個 Merkle 樹，而 Merkle 樹的根就是最終的公鑰。

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)

產生簽章

Merkle 簽章的生成過程包括兩個部分:

使用 Lamport 簽章方案對訊息進行簽章
提供 Merkle 樹中從葉節點到根的路徑作為驗證路徑

為簡單示範，我們先用第一個 keypair 來簽章。

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

驗證簽章

驗章原理跟 Lamport 簽章一樣，只是路徑變成是根到葉節點的路徑。

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}")

Winternitz One-Time Signature (Winternitz 簽章)

Winternitz 簽章 (WOTS) 是一種改進的一次性簽章方案,由 Robert Winternitz 在 1980 年代提出。
它的主要優勢是能夠顯著減少簽章和公鑰的大小,同時保持高度的安全性。

而 WOTS 的核心思想是使用可重複應用的單向函數(通常是雜湊函數)來構建簽章。這種方法允許我們用較少的 bit 來表示更多的資訊,從而減小簽章的大小。

簽章

選擇參數 w(Winternitz 參數),通常為 4、8 或 16。
將消息雜湊值分割成 w 位的區塊。
對每個區塊,生成一個隨機私鑰。
公鑰是通過對私鑰重複應用雜湊函數 2^w 次得到的。
簽章過程中,對每個區塊,應用雜湊函數的次數取決於區塊的值。

以下是 WOTS 完整流程的範例。

import hashlib
import secrets


def hash_function(data):
    return hashlib.sha256(data).digest()


def generate_winternitz_keypair(w):
    l = 256 // w  # 假設我們使用 256 位的雜湊函數
    private_key = [secrets.token_bytes(32) for _ in range(l)]
    public_key = [apply_hash(key, 2 ** w - 1) for key in private_key]
    return private_key, public_key


def apply_hash(data, times):
    for _ in range(times):
        data = hash_function(data)
    return data


def winternitz_sign(message, private_key, w):
    l = len(private_key)
    m = int.from_bytes(hash_function(message.encode()), 'big')
    signature = []
    for i in range(l):
        block = (m >> (w * (l - 1 - i))) & ((1 << w) - 1)
        signature.append(apply_hash(private_key[i], block))
    return signature


def winternitz_verify(message, signature, public_key, w):
    l = len(public_key)
    m = int.from_bytes(hash_function(message.encode()), 'big')
    for i in range(l):
        block = (m >> (w * (l - 1 - i))) & ((1 << w) - 1)
        if apply_hash(signature[i], 2 ** w - 1 - block) != public_key[i]:
            return False
    return True


# 使用 Winternitz 簽章
w = 8
private_key, public_key = generate_winternitz_keypair(w)
print(f"Private key: {private_key}")
print(f"Public key: {public_key}")
message = "Hello, Winternitz signature!"
signature = winternitz_sign(message, private_key, w)
print(f"Signature: {signature}")
is_valid = winternitz_verify(message, signature, public_key, w)
print(f"Signature valid: {is_valid}")

你可以試著自己跑跑看。

安全性分析

接下來，我們將介紹一次性簽章方案的安全分析，主要會基於以下幾個方面來判斷:

雜湊函數的抗碰撞性: 所有這些方案都依賴於雜湊函數的安全性。如果雜湊函數被破解,整個系統的安全性就會受到威脅。
一次性使用: 這些方案的安全性嚴重依賴於每個金鑰對只使用一次。多次使用同一金鑰對會大大降低安全性。
抗量子計算: 一次性簽章方案被認為是抗量子的,因為它們不依賴於質因數分解或離散對數等問題。
隨機數生成器: 生成私鑰時使用的隨機數生成器的安全性可能直接影響系統的安全性。

Lamport 簽章

Lamport 簽章的安全性主要基於雜湊函數的單向性。只要雜湊函數保持安全,Lamport 簽章就被認為是安全的。然而,它的主要缺點是大的金鑰和簽章尺寸。

Merkle 簽章

Merkle 簽章結合了 Lamport 簽章的安全性和 Merkle 樹的效率。它的安全性取決於底層一次性簽章方案(如 Lamport)的安全性和雜湊函數的抗碰撞性。

Winternitz 簽章

Winternitz 簽章提供了可調整的安全性參數 w。較大的 w 值會增加安全性,但也會增加計算成本。它的安全性基於反複應用雜湊函數的難度。

效能比較

方案	金鑰大小	簽章大小	生成速度	驗證速度
Lamport 簽章	大	大	快	快
Merkle 簽章	中	中	中	中
Winternitz 簽章	小	小	慢	慢

Lamport 簽章: 最簡單和最快的,但金鑰和簽章大小都很大。
Merkle 簽章: 在金鑰大小和操作速度之間取得了平衡。
Winternitz 簽章: 提供最小的金鑰和簽章大小,但生成和驗證速度較慢。

與傳統簽章方案的比較

特性	一次性簽章	傳統簽章 (如 RSA, ECDSA)
金鑰使用	一次	多次
抗量子能力	強	弱
金鑰大小	通常更大	小
簽章大小	通常更大	小
計算複雜度	低	高
安全性基礎	雜湊函數	RSA, 離散對數

一次性簽章方案的主要優勢在於其抗量子能力和較低的計算複雜度。然而,它們通常需要更大的金鑰和簽章大小,並且金鑰管理更加複雜,因為每個金鑰對只能使用一次。
傳統簽章方案如 RSA 和 ECDSA 則允許多次使用同一金鑰對,金鑰和簽章大小通常較小,但它們在面對量子電腦時可能不安全,並且計算複雜度較高。
選擇使用哪種簽章方案取決於具體的應用場景、安全需求和資源限制。在後量子時代,一次性簽章方案可能會變得越來越重要,尤其是在高安全性要求的場景中。

結論

一次性簽章作為一種創新的密碼學技術，在當前及未來的資訊安全領域中扮演著越來越重要的角色。通過本文的深入探討，我們可以得出以下幾點結論：

安全性優勢：OTS的一次性使用原則和基於雜湊函數的設計，使其在面對各種攻擊，尤其是量子計算攻擊時，表現出強大的抗性。這使得OTS成為後量子密碼學中的重要候選者。
效能權衡：雖然OTS在安全性方面表現出色，但通常需要較大的金鑰和簽章尺寸，這在實際應用中需要進行權衡。不同的OTS方案在金鑰大小
、簽章大小、生成速度和驗證速度等方面各有優劣。
應用前景：隨著量子計算的發展，OTS在高安全性要求的場景中可能會得到更廣泛的應用。特別是在需要長期安全保護的領域，如國家機密、長期金融合約等。
技術挑戰：OTS的主要挑戰在於金鑰管理的複雜性。由於每對金鑰只能使用一次，系統需要有效的機制來生成、儲存和管理大量的金鑰對。
未來發展：未來的研究可能會集中在進一步最佳化OTS的效能，減小金鑰和簽章大小，以及改進金鑰管理機制。同時，OTS與其他密碼學技術的結合也值得探索，以應對更加複雜的安全需求。

總結來說，一次性簽章技術為數位安全提供了一種獨特而強大的機制。隨著資訊技術的發展和安全需求的不斷提高，OTS將繼續發揮其重要作用，為構建更安全的數位世界貢獻力量。然而，在實際應用中，我們需要根據具體場景和需求，權衡OTS的優勢和局限性，選擇最適合的安全解決方案。

一次性簽章的基本原理

主要的一次性簽章方案

Lamport 簽章

產生金鑰

產生簽章

驗證簽章

Merkle 簽章方案

產生金鑰

產生簽章

驗證簽章

Winternitz One-Time Signature (Winternitz 簽章)

簽章

安全性分析

Lamport 簽章

Merkle 簽章

Winternitz 簽章

效能比較

與傳統簽章方案的比較

結論

也許你也會想看看