整批驗證密碼系統與雜湊後簽章系統之設計與分析

Design and Cryptanalysis of Batch Verification Schemes and Secure Hash-and-Sign Signatures

許鈺卿(Yu-Ching Hsu)

指導教授 ： 顏嵩銘

國立中央大學/資訊電機學院/資訊工程學系/碩士(2006年)

摘要

隨著電子商務與公文在網路上蓬勃發展，數位簽章被使用來保障資料的確認性及不可否認性，使用者往往需要於短時間內大量地產生或驗證簽章，這對密碼系統的應用而言，無形中增加了不少計算負擔。整批密碼學對此提供了一個解決辦法，讓大量的簽章可以有效率地被同時產生與驗證。

因為電子付費系統常會需要驗證大量的簽章，因此近來的研究都集中在整批簽章驗證上。整批簽章驗證過去的研究包含以離散對數、RSA與橢圓曲線為基礎的簽章系統。然而這些系統也面對各種不相同的攻擊方法。在本論文裡，整批簽章驗證的初步背景、重要系統以及相關的攻擊方法都會被介紹。

在本論文第三章，我們討論RSA簽章整批驗證的安全性與效率改善。以往的RSA簽章整批驗證要求簽章者要使用零知識協定(Zero-knowledge protocol)來保證p與q是兩個安全質數(safe prime)。我們提出新的方法使得驗證者可以避開零知識協定又保障一定程度的安全性。除此之外，RSA簽章利用小指數驗證(Small exponents test)確保整批驗證安全性時，卻必須多做指數運算。本篇論文修改原有的小指數檢驗，提出兩個加快速度的方法，讓有規律的指數取代隨機指數，如此整批驗證時可用簡單的乘法與平方運算來增加效率。為了討論RSA簽章整批驗證的安全性，我們將攻擊的方法分成兩類：湊係數攻擊(Coefficient matching attack)以及湊指數攻擊(Exponent matching attack)。為了抵擋上述兩種攻擊，我們將兩個加速的方法合併使用，再配合簽章重排，提出既安全又有效率的RSA簽章整批驗證系統。

在論文的最後一部分，我們回顧了一個雜湊後簽章系統。為了維護這個系統的安全，雜湊函數的輸出必須要滿足彼此互質的條件。不過這個規定在實際使用上並不適當，因為我們不能就輸出值來選擇輸入的訊息值。為了排除這個限制，本論文修改原來的系統，使其可以利用現有的雜湊函數來完成簽章。除此之外，本論文也提出簡單的說明來證明新雜湊後簽章系統的安全性。

關鍵字

整批驗證

並列摘要

Since digital signatures are largely adopted in many commercial applications, generating or verifying huge amount of them within a period of time is an important challenge for the cryptography researches and applications. Batch cryptography provides a solution for this challenge to let the signatures be generated or
verified efficiently.

Because payment schemes require verifying a large set of signatures, moreover, signature verification is not as efficient as signature generation in some schemes, the recent work focuses on the batch verification.

The previous researches for batch verification include DLP-based, RSA-based and pairing-based signature schemes, and there are several attacks on them. In this thesis, the preliminary background, some important schemes, and related attacks of batch verification are introduced.

The small exponents test for RSA signature verification is reconsidered. We propose a more efficient setup of key generation to avoid executing zero-knowledge protocol. In order to discuss the security of RSA batch verification, two approaches of attacks are classified. Moreover, two efficient tests based on regular
exponents are proposed. Then a new method using those efficient tests as building blocks for secure batch verification is proposed.

In the last part of this thesis, we review a hash-and-sign signature. It requires the outputs of the hash function to co-prime with each other. In order to remove the restriction of this scheme, we modify it and provide a sketch proof to prove that the proposed scheme is secure.

並列關鍵字

batch verification

參考文獻

Verification for Equality of Discrete Logarithms and Threshold

Fail-stop Signature Schemes without Trees,'' emph{Advances in

for Modular Exponentiation and Digital Signarues,'' emph{Advances

M. Bellare and P.Rogaway, ``Random Oracles are Practical: a

Number Is the Product of Two Safe Primes'', emph{Advances in