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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：75

、訪客IP：3.21.106.240

姓名

許鈺卿(Yu-Ching Hsu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

整批驗證密碼系統與雜湊後簽章系統之設計與分析
(Design and Cryptanalysis of Batch Verification Schemes and Secure Hash-and-Sign Signatures)

相關論文

★ 多種數位代理簽章之設計	★ 小額電子支付系統之研究
★ 實體密碼攻擊法之研究	★ 商業性金鑰恢復與金鑰託管機制之研究
★ AES資料加密標準之實體密碼分析研究	★ 電子競標系統之研究
★ 針對堆疊滿溢攻擊之動態程式區段保護機制	★ 通用型數域篩選因數分解法之參數探討
★ 於8051單晶片上實作可防禦DPA攻擊之AES加密器	★ 以非確定式軟體與遮罩分割對策防禦能量攻擊之研究
★ 遮罩保護機制防禦差分能量攻擊之研究	★ AES資料加密標準之能量密碼分析研究
★ 小額電子付費系統之設計與密碼分析	★ 公平電子現金系統之研究
★ RSA公開金鑰系統之實體密碼分析研究	★ 保護行動代理人所收集資料之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

隨著電子商務與公文在網路上蓬勃發展，數位簽章被使用來保障資料的確認性及不可否認性，使用者往往需要於短時間內大量地產生或驗證簽章，這對密碼系統的應用而言，無形中增加了不少計算負擔。整批密碼學對此提供了一個解決辦法，讓大量的簽章可以有效率地被同時產生與驗證。
因為電子付費系統常會需要驗證大量的簽章，因此近來的研究都集中在整批簽章驗證上。整批簽章驗證過去的研究包含以離散對數、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

論文目次

1 Introduction 1
1.1 Background and Motivation.......................................1
1.2 Outline of the Thesis...........................................3
2 Review of Batch Verification 5
2.1 Definition of Batch Verification................................5
2.2 Batch Verification for Modular Exponentiation...................7
2.2.1 Random subset test........................................7
2.2.2 Small exponent test.......................................8
2.3 The Preliminary Schemes with Batch Verification.................8
2.3.1 Batch verification for Schnorr signature..................8
2.3.2 Batch verification for RSA signature......................9
2.3.3 Batch verification for YCK pairing-based signature........10
2.3.4 Batch verification for theshold decryptions...............11
2.4 Attacks on Bathc Verification...................................13
2.4.1 Attack on RSA screening...................................13
2.4.2 Attacks on Yen and Laih's RSA batch verification..........14
2.5 Remarks and Discussions.........................................15
3 The Proposed Batch Verification Methods 18
3.1 The Requirement of Key Generation...............................19
3.2 Two Speeding Up Methods.........................................20
3.2.1 Regular small exponents tests.............................20
3.2.2 Matching attacks on RSA batch verification................22
3.3 Dual Checking...................................................27
3.3.1 Dual checking with random permutation.....................27
3.3.2 Dual checking with deliberate permutation.................29
3.3.3 Further improvement.......................................30
3.4 Performance and Security Analysis...............................31
4 The Improvement of GHR Hash-and-Sign Signature 35
4.1 Review of GHR Hash-and-Sign Signature...........................35
4.1.1 The construction..........................................35
4.1.2 The security under random oracle model....................36
4.1.3 Eliminating the random oracle.............................37
4.2 The Modified Scheme.............................................38
4.2.1 The modified construction.................................38
4.2.2 The security of the modified scheme.......................38
4.2.3 Further improvement.......................................39
4.2.4 Performance of the modified scheme........................40
5 Conclusions 42
5.1 Brief Review of Main Contributions..............................42
5.2 Further Works...................................................42
6 Bibliography 44
A Fiat's batch RSA 48

參考文獻

R. Aditya, K. Peng, C. Boyd, E. Dawson, and B. Lee, ``Batch
Verification for Equality of Discrete Logarithms and Threshold
Decryptions,' emph{ACNS 04}, LNCS, Vol. 3089, pp. 494-508,
Springer-Verlag, 2004.
N. Baric and B. Pfitzmann, ``Collision-free Accumulators and
Fail-stop Signature Schemes without Trees,' emph{Advances in
Cryptology -- Eurocrypt'97}, LNCS, Vol. 1233, pp. 480--494,
Springer-Verlag, 1997.
M. Bellare, J.A. Garay, and T. Rabin, ``Fast Batch Verification
for Modular Exponentiation and Digital Signarues,' emph{Advances
in Cryptology -- Eurocrypt'98}, LNCS, Vol. 1403, pp. 236--250,
Springer-Verlag, 1998.
M. Bellare, J.A. Garay, and T. Rabin, ``Fast Batch Verification
for Modular Exponentiation and Digital Signarues,' available
online at http://www-cse.ucsd.edu/users/mihir.
M. Bellare and P.Rogaway, ``Random Oracles are Practical: a
Paradigm for Designing Efficient Protocols,' emph{In 1st Conf.
on Computer and Communications Security, ACM}, pp. 62--73, 1993.
C. Boyd, E. Foo, and C. Pavlovski, ``Efficient Electronic Cash
Using Batch Signatures,' emph{Information Security and Privacy
-- ACISP'99}, LNCS, Vol. 1587, pp. 244--257, Springer-Verlag,
1999.
C. Boyd and C. Pavlovski, ``Attacking and Repairing Batch
Verification Schemes,' emph{Advances in Cryptology -- Asiacrypt
2000}, LNCS, Vol. 1976, pp. 58--71, Springer-Verlag, 2000.
J. Camenisch and M. Michels, ``Proving in Zero-Knowledge that a
Number Is the Product of Two Safe Primes', emph{Advances in
Cryptology -- Eurocrypt'99}, LNCS, Vol. 1592, pp. 107--122, 1999.
T. Cao, D. Lin, and R. Xue, ``Security Analysis of Some Batch
Verifying Signatures from Pairings', emph{International Journal
of Network Security}, Vol. 3, No. 1, pp. 58--63, 2005.
D. Chaum, A. Fiat, and M. Naor, ``Untraceable Electronic Cash,'
emph{Advances in Cryptology -- Crypto'88}, pp. 319--227, 1988.
J.S. Coron and D. Naccache, ``On The Security of RSA Screening,'
emph{PKC 99}, LNCS, Vol. 1560, pp. 197--203, Springer-Verlag,
1999.
G. Davida, ``Chosen Signature Cryptanalysis of the RSA (MIT)
Public-key Cryptosystem', Technical report TR-CS-82-2, Department
of EECS, University of Wisconsin, 1982.
Y. Desmedtg and Y. Frankel, ``Threshold Cryptosystems,'
emph{Advances in Cryptology -- Crypt'89 }, LNCS, Vol. 435,
pp.307--315, Springer-Verlag, 1990.
Y. Desmedtg and Y. Frankel, ``Shared Generation of Authenticators
and Signatures,' emph{Advances in Cryptology -- Crypto'91},
LNCS, Vol. 576, pp.457--569, Springer-Verlag, 1992.
Y. Desmedt and Y. Frankel, ``Parallel Reliable Threshold
Multisignature,' Technical report TR-92-04-02, Department of
EECS, University of Wisconsin-Milwaukee, 1992.
A. Fiat, ``Batch RSA,' emph{Advances in Cryptology --
Crypto'89}, LNCS, Vol. 435, pp. 175--185, Springer-Verlag, 1990.
A. Fiat, ``Batch RSA,' emph{Journal of Cryptology}, Vol.10,
Springer-Verlag, pp.75-88, 1997.
P. Fouque, G. Poupard, and J. Stern, ``Sharing Decryption in the
Context of Voting or Lotteries,' emph{Financial Cryptology -- FC
2000}, LNCS, Vol. 1962, pp.90--104, Spring-Verlag, 2001.
R. Gennaro, S. Halevi, and T. Rabin, ``Secure Hash-and-Sign
Signatures without The Random Oracle,' emph{Advances in
Cryptology -- Eurocrypt'99}, LNCS, Vol. 1592, pp.123--139,
Springer-Verlag, 1999.
R. Gennaro, H. Krawczyk, and T. Rabin, ``RSA-Based Undeniable
Signatures,' emph{Advances in Cryptology -- Crypto'97}, pp.
132--149, Spring-Verlag, 1997.
L. Harn, ``Batch Verifying Multiple DSA-type Digital Signatures,'
emph{Electronics Letterrs}, Vol. 34, No. 9, pp. 870--871, 30th
April 1998.
L. Harn, ``Batch Verifying Multiple RSA Digital Signatures,'
emph{Electronics Letterrs}, Vol. 34, No. 12, pp. 1219--1220, 30th
April 1998.
M.S. Hwang, C.C. Lee, and Y.L. Tang, ``Two Simple Batch Verifying
Multiple Digital Signatures,' emph{Proceeding of ICICS 2001},
LNCS, Vol. 2229, pp. 233--237, Springer-Verlag, 2001.
G. Miller, ``Riemann's Hypothesis and Tests for Primality',
emph{7th ACM Symposium on the Theory of Computing}, May 1975.
R.C. Merkle, ``A Certified Digital Signature,' emph{Advances in
Cryptology -- Crypto'89}, LNCS, Vol. 435, pp.218--238,
Springer-Verlag, 1990.
D. M'Ra"{i}hi and D. Naccache, ``Batch Exponentiation - A Fast
DLP-Based Signature Generation Strategy,' emph{3rd ACM
Conference on Computer and Communications Security}, pp. 58--61,
1996.
D. Naccache, D. M'Ra"{i}hi, D. Raphaeli, and S. Vaudenay, ``Can
DSA be Improved: Complexity Trade-Off with the Digital Signature
Standard,' emph{Advances in Cryptology -- Eurocrypt'94}, LNCS,
Vol. 950, pp. 85--94, Springer-Verlag, 1994.
C.J. Pavlovski and C. Boyd, ``Efficient Batch Signature Generation
Using Tree Structures,' emph{CrypTEC'99}, pp. 70--77, 1999.
M. Rabin, ``Probabilistic Algorithms for Primality Testing',
emph{Journal of Number Theory}, December 1980.
R.L. Rivest, A. Shamir, and L. Adleman, ``A Method for Obtaining
Digital Signatures and Public-key Cryptosystem,' {em Commun. of
ACM}, Vol.21, No.2, pp.120-126, 1978.
A. Shamir, ``How to Share a Secret,' emph{Commun. of ACM},
22:612--613, 1979.
C.P. Schnorr, ``Efficient Identification and Signatures for Smart
Cards,' emph{Advances in Cryptology --- Crypto'89}, LNCS, vol.
435, pp. 239--252, Springer-Verlag, 1990.
V. Shoup, ``Practical Threshold Signatures', technical report,
IBM, 1999, IBM Research Report RZ 3121.
S.M. Yen, C.S. Laih, and A.K. Lenstra, ``Multi-exponentiation,'
emph{IEE Proceedings, Part E: Computers and Digital Techniques},
Vol. 141, No. 6, pp. 325--326, 1994.
S.M. Yen and C.S. Lain, ``Improved Digital Signature Suitable for
Batch Verification,' emph{IEEE Transcations on Computers}, Vol.
44, No. 7, pp. 957--959, July 1995.
H. Yoon, J.H. Cheon, and Y.Kim, ``Batch Verifications with
ID-based Signatures,' emph{Information Security and Cryptology
-- ICISC'04}, LNCS, Vol. 3506, pp. 233--248, Springer-Verlag,
2005.
F. Zhang and K. Kim, ``Efficient ID-based Blind Signature and
Proxy Signature from Bilinear Pairings,' emph{Information
Security and Privacy -- ACISP'03}, LNCS, Vol. 2727, pp. 312--323,
Springer-Verlag, 2003.

指導教授

顏嵩銘(Sung-Ming Yen)

審核日期

2006-7-24

推文