基于自动机理论的同时签名算法研究与实现
|
摘要
电子商务是基于Internet的双方或多方之间进行的有形商品或者无形服务的交换,公平交换协议在电子商务中有着广泛的应用。同时签名是一种能够用来解决数字签名公平交换问题的签名方案,由Chen等人在2004年最早提出,其基本思想是签名双方在没有可信第三方TTP(Trusted Third Party)的帮助下进行交互,公平地完成对各自消息的签名和交换。
有限自动机公钥密码体制(FAPKC)是由我国学者陶仁骥和陈世华自主提出的,基于有限自动机可逆性理论的一种公钥密码体制,这是国际上第一个时序型公钥密码体制,由于只涉及到逻辑运算,与其他主流的公钥密码体制相比,该体制具有实现简单,运算速度较快的优势。
本文的工作主要有以下几点:
一、全面总结了近年来同时签名的发展和研究情况,介绍了同时签名方案、完美同时签名方案、多方同时签名方案,并对这些方案的安全性进行了分析。
二、提出了基于有限自动机理论的完美同时签名方案(FAPCS),定义了该方案的算法和协议,引入了完美模糊性和完美公平性的概念,并由此定义了完美同时签名方案的安全性模型,最后给出了FAPCS方案的安全性证明。
三、用C++语言实现了FAPCS方案,定义了基本数据类型,定义并实现了核心算法对应的API,并给出了一个Demo程序,演示了同时签名协议的执行流程及API的调用顺序。
本文最后讨论了目前尚未解决的问题,展望了同时签名方案未来的发展方向以及进一步的工作。
Electronic Commerce is the Internet-Based exchange of tangible merchandize or intangible service between two or more parties, the fair exchange protocol have been widely used in electronic commerce. Concurrent signature is designed to resolve the fair exchange problem of digital signature, which was proposed by Chen et al. in 2004.
Two Chinese cryptographers Tao Renji and Chen Shihua introduced the Finite Automata Public Key Cryptosystem (FAPKC), which is based on the invertibility theory of finite utoma. It is the first time-sequence public key cryptosystem. Compared with other popular public key systems, FAPKC is easy to be implemented and is more efficient because it only uses logical operations.
This paper chiefly refers to the following works:
1. Summarizes the research on Concurrent Signature in recent years. Introduces Concurrent Signature Scheme, Perfect Concurrent Signature Scheme, Multi-Party Concurrent Signature Scheme, and analyzes the security of these schemes.
2. Proposes a concrete Perfect Concurrent Signature scheme based on FAPKC. Defines the security model and introduces the notion of Perfect Ambiguity and Perfect Fairness. Proves that FAPCS scheme satisfies the security model.
3. Implements the FAPCS scheme using C++ language. Defines the basic data structure, the core algorithms, gives out a concrete demo to illustrate the FAPCS protocol and the calling sequence of the core algorithms.
At last, some open questions and future work are discussed.
有限自动机公钥密码体制(FAPKC)是由我国学者陶仁骥和陈世华自主提出的,基于有限自动机可逆性理论的一种公钥密码体制,这是国际上第一个时序型公钥密码体制,由于只涉及到逻辑运算,与其他主流的公钥密码体制相比,该体制具有实现简单,运算速度较快的优势。
本文的工作主要有以下几点:
一、全面总结了近年来同时签名的发展和研究情况,介绍了同时签名方案、完美同时签名方案、多方同时签名方案,并对这些方案的安全性进行了分析。
二、提出了基于有限自动机理论的完美同时签名方案(FAPCS),定义了该方案的算法和协议,引入了完美模糊性和完美公平性的概念,并由此定义了完美同时签名方案的安全性模型,最后给出了FAPCS方案的安全性证明。
三、用C++语言实现了FAPCS方案,定义了基本数据类型,定义并实现了核心算法对应的API,并给出了一个Demo程序,演示了同时签名协议的执行流程及API的调用顺序。
本文最后讨论了目前尚未解决的问题,展望了同时签名方案未来的发展方向以及进一步的工作。
Electronic Commerce is the Internet-Based exchange of tangible merchandize or intangible service between two or more parties, the fair exchange protocol have been widely used in electronic commerce. Concurrent signature is designed to resolve the fair exchange problem of digital signature, which was proposed by Chen et al. in 2004.
Two Chinese cryptographers Tao Renji and Chen Shihua introduced the Finite Automata Public Key Cryptosystem (FAPKC), which is based on the invertibility theory of finite utoma. It is the first time-sequence public key cryptosystem. Compared with other popular public key systems, FAPKC is easy to be implemented and is more efficient because it only uses logical operations.
This paper chiefly refers to the following works:
1. Summarizes the research on Concurrent Signature in recent years. Introduces Concurrent Signature Scheme, Perfect Concurrent Signature Scheme, Multi-Party Concurrent Signature Scheme, and analyzes the security of these schemes.
2. Proposes a concrete Perfect Concurrent Signature scheme based on FAPKC. Defines the security model and introduces the notion of Perfect Ambiguity and Perfect Fairness. Proves that FAPCS scheme satisfies the security model.
3. Implements the FAPCS scheme using C++ language. Defines the basic data structure, the core algorithms, gives out a concrete demo to illustrate the FAPCS protocol and the calling sequence of the core algorithms.
At last, some open questions and future work are discussed.
引文
1.Chen L,Kudla C,Paterson K G.Concurrent signatures[C]//LNCS3027:Advance in Cryptology-Eurocryt2004,2004:287-305.
2.Susilo W,Mu Y,Zhang F.Perfect Concurrent Signature Schemes[C]//ICICS 2004,Lecture Notes in Computer Science,vol 3269.Berlin:Springer-Verlag,2004:14-26.
3.Chow S,Susilo W.Generic construction of(identity-based)perfect concurrent signatures[C]//Information and Communications Security(ICICS 2005),Lecture Notes in Computer Science,vol 3783.Berlin:Springer-Verlag,2005:194-206.
4.Wang Gui-lin,Bao Feng,Zhou Jian-ying.The Fairness of Perfect Concurrent Signatures[C/DL]//ICICS 2006.
5.Huang Zhen-jie,Chen Ke-fei,Wang Yu-min.Analysis and improvements of two identity-based perfect concurrent signature schemes[DB/OL].
6.Chow S M,Yiu S M,Hui L C K.Efficient identity based ring signature[C]//LNCS 3531:ACNS' 05,2005:499-512.
7.Tonien D,Susilo W,Safavi-Naini R.Multi-party concurrent signatures[C]//ISC2006,Lecture Notes in Computer Science,vol 4176.Berlin:Springer-Verlag,2006:131-145.
8.陶仁骥.自动机引论.第一版.北京:科学出版社,1986
9.张焕国,刘玉珍.密码学引论.第1版.武汉:武汉大学出版社,2003
10.杨义先,孙伟,钮心忻.现代密码新理论.第1版.北京:科学出版社,2002.
11.陶仁骥.有限自动机的可逆性.第1版.北京:科学出版社,1979
12.冯登国,裴定一.密码学导引.第1版.北京:科学出版社,1999
13.尤春光.基于自动机理论的公钥密码学研究.南京理工大学硕士论文.2005
14.陶仁骥,陈世华.一种有限自动机公钥密码体制和数字签名.计算机学报.1985(8):401-409
15.陶仁骥,矩阵多项式的几种特殊分解.计算机学报.1999(22):1-10
16.Tao Renji,Chen Shihua.Two varieties of finite automaton public key cryptosystem and digital signatures.J.of Computer Science and Technology.1986(1):10-18
17.陶仁骥,陈世华.基于身份的密码体制和数字签名的有限自动机公钥密码实现.密码学进展-CHINACRYPT'92第二届中国密码学学术会议论文集.1992:87-104
18.Tao Renji,Chen Shihua.Note on finite automaton public key cryptosystems.密码学进展-CHINACRYPT'94,第三届中国密码学学术会议论文集.1994:76-81
19.Tao Renji,Chen Shihua.Chen Xuemei.FAPKC3:a new finite automaton public key cryptosystem.J.of Computer Science and Technology.1997(12):289-305
20.戴宗铎.一类可分非线性有限自动机-兼对FAPKC3加密与签名体制的分析.密码学进展-CHINACRYPT'96,第四届中国密码学学术会议论文集.1996:87-94
21.Tao Renji,Chen Shihua.A variant of the public key cryptosystem FAPKC3.J.of Network and Computer Applications.1997(20):283-303
22.Tao Renji,Chen Shihua.Constructing finite automata with invertibility by transformation method.密码学进展-CHINACRYPT'98,第五届中国密码学学术会议论文集.1998:61-68
23.Tao Renji,Chen Shihua.A note on the public key cryptosystem FAPKC3.密码学进展-CHINACRYPT'98,第五届中国密码学学术会议论文集.1998:69-77
24.Tao Renji,Chen Shihua.The generalization of public key cryptosystem FAPKC4.Chinese Science Bulletin(Kexue Tongbao).1999(44):784-790
25.Tao Renji,Chen Shihua.On finite automaton public key cryptosystem.Theoretical Computer Science.1999(226):143-172
26.覃中平,张焕国.有限自动机公钥密码攻击算法AτM.计算机学报.1995(18):199-204
27.覃中平,张焕国.密码攻击ALT~+算法.计算机学报.1997(6):546-550
28.(德)Michael Welschenbach(著);赵振江等(译).密码编码学:加密方法的C与C++实现.第2版.北京:电子工业出版社,2003
29.李健宝,高翔.有限自动机公钥密码体制和数字签名的软件实现.密码学进展-CHINACRYPT'92第二届中国密码学学术会议论文集.1992:110-113
30.张焕国,戴大为等.FA公开密钥密码体制的软件实现.密码学进展-CHINACRYPT'92第二届中国密码学学术会议论文集.1992:105-109
31.武晓峰,王晓峰等.一个高效的基于身份的同时签名方案.计算机工程与应用.2007.127-128
32.贾仁超,寇卫东等.一种基于可验证环签名的同时生效签名.计算机工程与应用.2006.56-57
33.罗卿.基于FAPKC算法的电子税务的设计与实现.中科院软件研究所硕士论文.2001
34.阎浩.基于有限自动机理论的公钥加密算法研究.南京理工大学硕士论文.2005
35.陈静.有限自动机公钥密码的研究与实现.西南交通大学硕士论文.2007
36.孙燕,耿祥义.一种新的基于FAPKC4的数字签名方法.网络安全技术与应用.2008.92-93
37.刘景伟.电子商务中的公平交换协议研究.西安电子科技大学博士论文.2007
38.马晓静.数字签名在公平交换中的应用研究.西安理工大学硕士论文.2006
39.王鸿吉.可逆有限自动机的结构与分解.中国科学院软件研究所博士论文.2005
40.范伟.电子支付系统的公平性研究.西安电子科技大学硕士论文.2007
41.陈静,李扬渊,何大可.FAPKC3的搜索攻击及非线性算子的新构造.计算机工程.2008(34).111-113
42.韩小西,姚刚.FAPKC签名和加密混合使用的安全性分析.计算机研究与发展.2005(42).1692-1697
2.Susilo W,Mu Y,Zhang F.Perfect Concurrent Signature Schemes[C]//ICICS 2004,Lecture Notes in Computer Science,vol 3269.Berlin:Springer-Verlag,2004:14-26.
3.Chow S,Susilo W.Generic construction of(identity-based)perfect concurrent signatures[C]//Information and Communications Security(ICICS 2005),Lecture Notes in Computer Science,vol 3783.Berlin:Springer-Verlag,2005:194-206.
4.Wang Gui-lin,Bao Feng,Zhou Jian-ying.The Fairness of Perfect Concurrent Signatures[C/DL]//ICICS 2006.
5.Huang Zhen-jie,Chen Ke-fei,Wang Yu-min.Analysis and improvements of two identity-based perfect concurrent signature schemes[DB/OL].
6.Chow S M,Yiu S M,Hui L C K.Efficient identity based ring signature[C]//LNCS 3531:ACNS' 05,2005:499-512.
7.Tonien D,Susilo W,Safavi-Naini R.Multi-party concurrent signatures[C]//ISC2006,Lecture Notes in Computer Science,vol 4176.Berlin:Springer-Verlag,2006:131-145.
8.陶仁骥.自动机引论.第一版.北京:科学出版社,1986
9.张焕国,刘玉珍.密码学引论.第1版.武汉:武汉大学出版社,2003
10.杨义先,孙伟,钮心忻.现代密码新理论.第1版.北京:科学出版社,2002.
11.陶仁骥.有限自动机的可逆性.第1版.北京:科学出版社,1979
12.冯登国,裴定一.密码学导引.第1版.北京:科学出版社,1999
13.尤春光.基于自动机理论的公钥密码学研究.南京理工大学硕士论文.2005
14.陶仁骥,陈世华.一种有限自动机公钥密码体制和数字签名.计算机学报.1985(8):401-409
15.陶仁骥,矩阵多项式的几种特殊分解.计算机学报.1999(22):1-10
16.Tao Renji,Chen Shihua.Two varieties of finite automaton public key cryptosystem and digital signatures.J.of Computer Science and Technology.1986(1):10-18
17.陶仁骥,陈世华.基于身份的密码体制和数字签名的有限自动机公钥密码实现.密码学进展-CHINACRYPT'92第二届中国密码学学术会议论文集.1992:87-104
18.Tao Renji,Chen Shihua.Note on finite automaton public key cryptosystems.密码学进展-CHINACRYPT'94,第三届中国密码学学术会议论文集.1994:76-81
19.Tao Renji,Chen Shihua.Chen Xuemei.FAPKC3:a new finite automaton public key cryptosystem.J.of Computer Science and Technology.1997(12):289-305
20.戴宗铎.一类可分非线性有限自动机-兼对FAPKC3加密与签名体制的分析.密码学进展-CHINACRYPT'96,第四届中国密码学学术会议论文集.1996:87-94
21.Tao Renji,Chen Shihua.A variant of the public key cryptosystem FAPKC3.J.of Network and Computer Applications.1997(20):283-303
22.Tao Renji,Chen Shihua.Constructing finite automata with invertibility by transformation method.密码学进展-CHINACRYPT'98,第五届中国密码学学术会议论文集.1998:61-68
23.Tao Renji,Chen Shihua.A note on the public key cryptosystem FAPKC3.密码学进展-CHINACRYPT'98,第五届中国密码学学术会议论文集.1998:69-77
24.Tao Renji,Chen Shihua.The generalization of public key cryptosystem FAPKC4.Chinese Science Bulletin(Kexue Tongbao).1999(44):784-790
25.Tao Renji,Chen Shihua.On finite automaton public key cryptosystem.Theoretical Computer Science.1999(226):143-172
26.覃中平,张焕国.有限自动机公钥密码攻击算法AτM.计算机学报.1995(18):199-204
27.覃中平,张焕国.密码攻击ALT~+算法.计算机学报.1997(6):546-550
28.(德)Michael Welschenbach(著);赵振江等(译).密码编码学:加密方法的C与C++实现.第2版.北京:电子工业出版社,2003
29.李健宝,高翔.有限自动机公钥密码体制和数字签名的软件实现.密码学进展-CHINACRYPT'92第二届中国密码学学术会议论文集.1992:110-113
30.张焕国,戴大为等.FA公开密钥密码体制的软件实现.密码学进展-CHINACRYPT'92第二届中国密码学学术会议论文集.1992:105-109
31.武晓峰,王晓峰等.一个高效的基于身份的同时签名方案.计算机工程与应用.2007.127-128
32.贾仁超,寇卫东等.一种基于可验证环签名的同时生效签名.计算机工程与应用.2006.56-57
33.罗卿.基于FAPKC算法的电子税务的设计与实现.中科院软件研究所硕士论文.2001
34.阎浩.基于有限自动机理论的公钥加密算法研究.南京理工大学硕士论文.2005
35.陈静.有限自动机公钥密码的研究与实现.西南交通大学硕士论文.2007
36.孙燕,耿祥义.一种新的基于FAPKC4的数字签名方法.网络安全技术与应用.2008.92-93
37.刘景伟.电子商务中的公平交换协议研究.西安电子科技大学博士论文.2007
38.马晓静.数字签名在公平交换中的应用研究.西安理工大学硕士论文.2006
39.王鸿吉.可逆有限自动机的结构与分解.中国科学院软件研究所博士论文.2005
40.范伟.电子支付系统的公平性研究.西安电子科技大学硕士论文.2007
41.陈静,李扬渊,何大可.FAPKC3的搜索攻击及非线性算子的新构造.计算机工程.2008(34).111-113
42.韩小西,姚刚.FAPKC签名和加密混合使用的安全性分析.计算机研究与发展.2005(42).1692-1697