基于椭圆曲线的事务数字签名算法的研究
|
摘要
电子政务提供的平台上有相当多的重要公文在流转，因此，保证其中的信息安全非常重要。政务机关内部具有严格的办事流程和程序规定，一旦违反了业务程序和流程，会造成严重后果。通常的数字签名提供了信息发送者的身份验证，但却无法保证事务处理流程的正确。
本文介绍了一种事务数字签名算法，该算法能够验证整个事务处理流程的正确性。事务数字签名算法的安全性建立在椭圆曲线离散对数问题的难解性之上。作者以椭圆曲线密码体制为基础，完成了该事务数字签名算法的实现。事务数字签名协议包括生成事务签名，和对接收到的签名进行验证两部分。
目前，对定义在特征值为2或者大素数的有限域上的椭圆曲线计算已经有了比较深入的研究，因此本文讨论了定义在特征3的有限域上的椭圆曲线运算，采用多项式基表示法实现。作者对定义在有限域F_(3~2)，F_(3~3)，F_(3~4)上的椭圆曲线，详细分析了曲线上的点构成的循环群结构。椭圆曲线点群中元素之间的运算构成了事务数字签名算法的基本运算。
本文考虑两种基本的事务类型：一种是各个部门按顺序依次处理某事务，简称“串联”；另一种是除处理事务的起始部门和最终部门之外，其余各个部门并行处理某事务，简称“并联”。不同类型的事务有不同的处理流程，对某一类型的事务，作者根据其规定的处理流程，完成了事务数字签名的生成。
椭圆曲线上的Tate配对具有双线性性质，本文利用这一性质对收到的事务数字签名进行验证。计算Tate配对采用Miller算法，在特征3的有限域上实现。Miller算法的基本思想是将椭圆曲线点乘中的加法和倍点运算与点加过程中的直线函数估计联系起来。
本文将上述事务数字签名协议应用到电子政务中，用来检验政务系统里事务处理流程的正确性，提山了一个分布式安全事务平台的构建方案。根据事务活动的特征及存在的安全问题，为分布式电子事务活动提供一个安全、可靠的运行环境。该平台遵循分布式组件标准CORBA进行设计，本文给出了平台的IDL组件接口定义和系统类结构的定义。
There are a lot of significant documents flowing in the platform offered by the electronic government, so it is essential to keep the information confidential. In the government, the strict regulation of affairs is called for. In case of acting against the regulation, the serious effect would be made. As we know, usual digital signature just offers sender authentication, however it cannot guarantee the correctness of the transaction processing.
In this paper, we have discussed an algorithm of transaction signature. This algorithm can verify the correctness of the whole procedure. The security of the algorithm is based on the complexity of solving elliptic curve discrete logarithm problem. We implement the algorithm of transaction signature, base on Elliptic Curve Cryptography. Producing a digital signature and verifying this signature constitute the transaction signature protocol.
About the computations of the elliptic curves on finite fields of characteristic 2 or a large prime number p, there are a lot profound studies already. In this paper, we concentrate on computations on the finite field of characteristic 3, and implement it on polynomial base. To illustrate this algorithm, we have
discussed several concrete examples, the elliptic curves on finite fields F32, F33 , F34. In those examples,
we first analyze the structure of cyclic groups and the basic calculation:; in details, which consist of the points of elliptic curves, and then establish the construction of the digital signature.
There are two basic types of managing one transaction. One is called "series connection", in which each department completely deal with the transaction in sequence. The other is called "parallel connection", in which every department except the starting department and the ending department synchronously transact it.
Since the Tate pairing on the elliptic curve is doubly linear, we utilize the property to verify the digital signature. About the calculations of Tate pairing, we adopt Miller algorithm, and implement it on the finite field of characteristic 3. Miller's algorithm is basically the usual 'double and add' algorithm for elliptic curve point multiplication combined with an evaluation of certain intermediate functions which are the straight lines used in the addition process.
To apply the transaction signature protocol to check the transaction processing in the electronic government, we propose a design of distributed transaction security platform. According to the
characteristic of transaction and existed problem related with safety, the platform will provide a secure and credible environment for the distributed electronic transaction. The designed platform conform with the distributed component standard, The Common Object Request Broker Architecture. The IDL definition and system structure is given on the following paper.
本文介绍了一种事务数字签名算法，该算法能够验证整个事务处理流程的正确性。事务数字签名算法的安全性建立在椭圆曲线离散对数问题的难解性之上。作者以椭圆曲线密码体制为基础，完成了该事务数字签名算法的实现。事务数字签名协议包括生成事务签名，和对接收到的签名进行验证两部分。
目前，对定义在特征值为2或者大素数的有限域上的椭圆曲线计算已经有了比较深入的研究，因此本文讨论了定义在特征3的有限域上的椭圆曲线运算，采用多项式基表示法实现。作者对定义在有限域F_(3~2)，F_(3~3)，F_(3~4)上的椭圆曲线，详细分析了曲线上的点构成的循环群结构。椭圆曲线点群中元素之间的运算构成了事务数字签名算法的基本运算。
本文考虑两种基本的事务类型：一种是各个部门按顺序依次处理某事务，简称“串联”；另一种是除处理事务的起始部门和最终部门之外，其余各个部门并行处理某事务，简称“并联”。不同类型的事务有不同的处理流程，对某一类型的事务，作者根据其规定的处理流程，完成了事务数字签名的生成。
椭圆曲线上的Tate配对具有双线性性质，本文利用这一性质对收到的事务数字签名进行验证。计算Tate配对采用Miller算法，在特征3的有限域上实现。Miller算法的基本思想是将椭圆曲线点乘中的加法和倍点运算与点加过程中的直线函数估计联系起来。
本文将上述事务数字签名协议应用到电子政务中，用来检验政务系统里事务处理流程的正确性，提山了一个分布式安全事务平台的构建方案。根据事务活动的特征及存在的安全问题，为分布式电子事务活动提供一个安全、可靠的运行环境。该平台遵循分布式组件标准CORBA进行设计，本文给出了平台的IDL组件接口定义和系统类结构的定义。
There are a lot of significant documents flowing in the platform offered by the electronic government, so it is essential to keep the information confidential. In the government, the strict regulation of affairs is called for. In case of acting against the regulation, the serious effect would be made. As we know, usual digital signature just offers sender authentication, however it cannot guarantee the correctness of the transaction processing.
In this paper, we have discussed an algorithm of transaction signature. This algorithm can verify the correctness of the whole procedure. The security of the algorithm is based on the complexity of solving elliptic curve discrete logarithm problem. We implement the algorithm of transaction signature, base on Elliptic Curve Cryptography. Producing a digital signature and verifying this signature constitute the transaction signature protocol.
About the computations of the elliptic curves on finite fields of characteristic 2 or a large prime number p, there are a lot profound studies already. In this paper, we concentrate on computations on the finite field of characteristic 3, and implement it on polynomial base. To illustrate this algorithm, we have
discussed several concrete examples, the elliptic curves on finite fields F32, F33 , F34. In those examples,
we first analyze the structure of cyclic groups and the basic calculation:; in details, which consist of the points of elliptic curves, and then establish the construction of the digital signature.
There are two basic types of managing one transaction. One is called "series connection", in which each department completely deal with the transaction in sequence. The other is called "parallel connection", in which every department except the starting department and the ending department synchronously transact it.
Since the Tate pairing on the elliptic curve is doubly linear, we utilize the property to verify the digital signature. About the calculations of Tate pairing, we adopt Miller algorithm, and implement it on the finite field of characteristic 3. Miller's algorithm is basically the usual 'double and add' algorithm for elliptic curve point multiplication combined with an evaluation of certain intermediate functions which are the straight lines used in the addition process.
To apply the transaction signature protocol to check the transaction processing in the electronic government, we propose a design of distributed transaction security platform. According to the
characteristic of transaction and existed problem related with safety, the platform will provide a secure and credible environment for the distributed electronic transaction. The designed platform conform with the distributed component standard, The Common Object Request Broker Architecture. The IDL definition and system structure is given on the following paper.
引文
[1] C.E.Shannon, Communication theory of security systems, Bell System Technical Journal, Vol. IT-28, 1949, pp. 656-715.
[2] W.Diffie, M.Hellman, New directions in cryptography, IEEE Trans Inform Theory, Vol. IT-22, 1976,pp. 644-654.
[3] R.L.Rivest, A.Shamir, L.Adleman, A method for obtaining digital signatures and public-key cryptosystems. Communications of the AC M, Vol.21, 1978, pp. 120-126.
[4] G.J.Simmons, Symmetric and asymmetric encryption, ACM Computing Surveys, Vol. 11, No.4, Dec 1979, pp. 305-330.
[5] 冯登国，斐定一，密码学导引，科学出版社，1999，142-177页．
[6] 冯登国，密码分析学．清华大学出版社，2000，93-110页．
[7] L.EIGamal, A public key cryptosystem and a signature scheme base on discrete logarithms, IEEE Transactions on Information Theory, Vol.31, 1985, pp.469-472.
[8] D.R.Stinson, Cryptography-theory and practice, CRC Press, 1995.
[9] A.J.Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993.
[10] S.D.Galbraith. Supersingular curves in cryptography, available at http://www.isg.rhul.ac.uk/～sdg.
[11] D.Chaum and H.E.Van, Group signatures, Advances in Cryptology-Eutocrypt'91, Springer-Verlag,1991, pp. 257-265.
[12] Y.Desmedt, Threshold cryptosystems, Advances in Cryptology-Auscrypt'92, Springer-Verlag, 1993,pp.3-14.
[13] C.Boyd, Digital multisignatures in cryptography and coding, Clarendon Press, 1989, pp.241-246.
[14] M.Stadler, J.M.Piveteau and J.Camenisch, Fair blind signatures, Advances in Cryptology-Eurocrypt'95, Springer-Verlag, pp.209-219.
[15] N.Kobliz, Elliptic curve crysystems, Math.of Comp, Vol.48, 1987, pp. 203-209.
[16] V.Miller, Use of elliptic curves in cryptography, CRYPTO'85, LNCS 218, Springer-Verlag, 1986, pp. 417-426.
[17] J.H.Sliverman. The arithmetic of elliptic curves, Springer GTM 106, 1986.
[18] I.F.Blake, G.Seroussi, and N.P.Smart. Elliptic curves in cryptography, London Mathematical Society
Lecture Note Series, Cambridge University Press, Vol.265, 1999.
[19] S.C.Pohlig, M.E.Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans Inform Theory, Vol.24, 1978, pp. 106-110.
[20] M. Joye. Efficient GF(p^m) arithmetic architectures for cryptographic, Computer Science, Springer-Verlag, July 2003, pp. 158-175.
[21] A.J.Menezes, T.Okamoto and S.A.Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans Inform Theory, Vol.39 No.5, 1993, pp.1639-1646.
[22] G.Frey and H.G.Ruck, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Math of Comp, Vol.62 No.206, 1994, pp.865-874.
[23] G.Frey, V.Miller, H.G.Ruck, The rate pairing and the discrete logarithm applied to elliptic curve cryptosystems, IEEE Trans Inform Theory, Vol.45 No.5, 1999, pp. 1717-1719.
[24] V.Miller, Short programs for functions on curves, unpublished manuscript 1986.
[25] S.D.Galbraith, K.Harrison and D.soldera, Implementing the tare pairing, Algorithm Number Theory Symposium-ANTS V, Lecture Notes in Computer Science, Vol.2369, Springer-Verlag, 2002, pp. 324-337.
[26] J.H.Cheon, D.H.Lee, Diffie-Hellman. Problems and bilinear maps, Cryptology ePrint Archive, Report 2002, available at http://eprint.iacr.org/2002/.
[27] H．Michi．徐金梧，徐科，吕志民．基于c++的CORBA高级编程，清华大学出版社，2000．
[28] P.Barreto, H. Kim, B. Lynn and M. Scott, Efficient algorithms for pairing-based cryptosystems, Cryptology ePrint Archive, Report 2002, available at http://eprint.iacr.org/2002/008/.
[2] W.Diffie, M.Hellman, New directions in cryptography, IEEE Trans Inform Theory, Vol. IT-22, 1976,pp. 644-654.
[3] R.L.Rivest, A.Shamir, L.Adleman, A method for obtaining digital signatures and public-key cryptosystems. Communications of the AC M, Vol.21, 1978, pp. 120-126.
[4] G.J.Simmons, Symmetric and asymmetric encryption, ACM Computing Surveys, Vol. 11, No.4, Dec 1979, pp. 305-330.
[5] 冯登国，斐定一，密码学导引，科学出版社，1999，142-177页．
[6] 冯登国，密码分析学．清华大学出版社，2000，93-110页．
[7] L.EIGamal, A public key cryptosystem and a signature scheme base on discrete logarithms, IEEE Transactions on Information Theory, Vol.31, 1985, pp.469-472.
[8] D.R.Stinson, Cryptography-theory and practice, CRC Press, 1995.
[9] A.J.Menezes, Elliptic curve public key cryptosystems, Kluwer Academic Publishers, 1993.
[10] S.D.Galbraith. Supersingular curves in cryptography, available at http://www.isg.rhul.ac.uk/～sdg.
[11] D.Chaum and H.E.Van, Group signatures, Advances in Cryptology-Eutocrypt'91, Springer-Verlag,1991, pp. 257-265.
[12] Y.Desmedt, Threshold cryptosystems, Advances in Cryptology-Auscrypt'92, Springer-Verlag, 1993,pp.3-14.
[13] C.Boyd, Digital multisignatures in cryptography and coding, Clarendon Press, 1989, pp.241-246.
[14] M.Stadler, J.M.Piveteau and J.Camenisch, Fair blind signatures, Advances in Cryptology-Eurocrypt'95, Springer-Verlag, pp.209-219.
[15] N.Kobliz, Elliptic curve crysystems, Math.of Comp, Vol.48, 1987, pp. 203-209.
[16] V.Miller, Use of elliptic curves in cryptography, CRYPTO'85, LNCS 218, Springer-Verlag, 1986, pp. 417-426.
[17] J.H.Sliverman. The arithmetic of elliptic curves, Springer GTM 106, 1986.
[18] I.F.Blake, G.Seroussi, and N.P.Smart. Elliptic curves in cryptography, London Mathematical Society
Lecture Note Series, Cambridge University Press, Vol.265, 1999.
[19] S.C.Pohlig, M.E.Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans Inform Theory, Vol.24, 1978, pp. 106-110.
[20] M. Joye. Efficient GF(p^m) arithmetic architectures for cryptographic, Computer Science, Springer-Verlag, July 2003, pp. 158-175.
[21] A.J.Menezes, T.Okamoto and S.A.Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans Inform Theory, Vol.39 No.5, 1993, pp.1639-1646.
[22] G.Frey and H.G.Ruck, A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Math of Comp, Vol.62 No.206, 1994, pp.865-874.
[23] G.Frey, V.Miller, H.G.Ruck, The rate pairing and the discrete logarithm applied to elliptic curve cryptosystems, IEEE Trans Inform Theory, Vol.45 No.5, 1999, pp. 1717-1719.
[24] V.Miller, Short programs for functions on curves, unpublished manuscript 1986.
[25] S.D.Galbraith, K.Harrison and D.soldera, Implementing the tare pairing, Algorithm Number Theory Symposium-ANTS V, Lecture Notes in Computer Science, Vol.2369, Springer-Verlag, 2002, pp. 324-337.
[26] J.H.Cheon, D.H.Lee, Diffie-Hellman. Problems and bilinear maps, Cryptology ePrint Archive, Report 2002, available at http://eprint.iacr.org/2002/.
[27] H．Michi．徐金梧，徐科，吕志民．基于c++的CORBA高级编程，清华大学出版社，2000．
[28] P.Barreto, H. Kim, B. Lynn and M. Scott, Efficient algorithms for pairing-based cryptosystems, Cryptology ePrint Archive, Report 2002, available at http://eprint.iacr.org/2002/008/.