In this paper, we present two explicit invalid-curve attacks on the genus 2 hyperelliptic curve over a finite field. First, we propose two explicit attack models by injecting a one-bit fault in a given divisor. Then, ...In this paper, we present two explicit invalid-curve attacks on the genus 2 hyperelliptic curve over a finite field. First, we propose two explicit attack models by injecting a one-bit fault in a given divisor. Then, we discuss the construction of an invalid curve based on the faulted divisor. Our attacks are based on the fact that the Hyperelliptic Curve Scalar Multiplication (HECSM) algorithm does not utilize the curve parameters and We consider three hyperelliptic curves as the attack targets. For curve with security level 186 (in bits), our attack method can get the weakest invalid curve with security level 42 (in bits); there are 93 invalid curves with security level less than 50. We also estimate the theoretical probability of getting a weak hyperelliptic curve whose cardinality is a smooth integer. Finally, we show that the complexity of the fault attack is subexponential if the attacker can freely inject a fault in the input divisor. Cryptosystems based on the genus 2 hyperelliptic curves cannot work against our attack algorithm in practice.展开更多
Discrete logarithm based cryptosysterns have subtle problems that make the schemes vulnerable. This paper gives a comprehensive listing of security issues in the systems and analyzes three classes of attacks which are...Discrete logarithm based cryptosysterns have subtle problems that make the schemes vulnerable. This paper gives a comprehensive listing of security issues in the systems and analyzes three classes of attacks which are based on mathematical structure of the group which is used in the schemes, the disclosed information of the subgroup and implementation details respectively. The analysis will, in turn, allow us to motivate protocol design and implementation decisions.展开更多
Digital signature scheme is a very important research field in computer security and modern cryptography. A (k, n) threshold digital signature scheme is proposed by integrating digital signature scheme with Shamir sec...Digital signature scheme is a very important research field in computer security and modern cryptography. A (k, n) threshold digital signature scheme is proposed by integrating digital signature scheme with Shamir secret sharing scheme. It can realize group-oriented digital signature, and its security is based on the difficulty in computing discrete logarithm and quadratic residue on some special conditions. In this scheme, effective digital signature can not be generated by anyk?1 or fewer legal users, or only by signature executive. In addition, this scheme can identify any legal user who presents incorrect partial digital signature to disrupt correct signature, or any illegal user who forges digital signature. A method of extending this scheme to an Abelian group such as elliptical curve group is also discussed. The extended scheme can provide rapider computing speed and stronger security in the case of using shorter key. Key words threshold scheme - digital signature - discrete logarithm - quadratic residuc - threshold digital signature CLC number TP 309. 7 Foundation item: Supported the National Nature Science Foundation of China, Hubei Province (90104005, 2002 AB0039)Biography: FEI Ru-chun (1964-), male, Ph. D candidate, Associated professor, research direction: information security and cryptography.展开更多
This paper provides a framework that reduces the computational complexity of the discrete logarithm problem. The paper describes how to decompose the initial DLP onto several DLPs of smaller dimensions. Decomposabilit...This paper provides a framework that reduces the computational complexity of the discrete logarithm problem. The paper describes how to decompose the initial DLP onto several DLPs of smaller dimensions. Decomposability of the DLP is an indicator of potential vulnerability of encrypted messages transmitted via open channels of the Internet or within corporate networks. Several numerical examples illustrate the frame- work and show its computational efficiency.展开更多
The discrete logarithm problem(DLP)is to find a solution n such that g^n=h in a finite cyclic group G=,where h∈G.The DLP is the security foundation of many cryptosystems,such as RSA.We propose a method to improve Pol...The discrete logarithm problem(DLP)is to find a solution n such that g^n=h in a finite cyclic group G=,where h∈G.The DLP is the security foundation of many cryptosystems,such as RSA.We propose a method to improve Pollard’s kangaroo algorithm,which is the classic algorithm for solving the DLP.In the proposed algorithm,the large integer multiplications are reduced by controlling whether to perform large integer multiplication.To control the process,the tools of expanding factor and jumping distance are introduced.The expanding factor is an indicator used to measure the probability of collision.Large integer multiplication is performed if the value of the expanding factor is greater than the given bound.The improved algorithm requires an average of(1.633+o(1))q(1/2)times of the large integer multiplications.In experiments,the average large integer multiplication times is approximately(1.5+o(1))q(1/2).展开更多
共识机制是区块链系统的核心技术,但是目前的共识机制存在3个问题,即共识效率低、可靠性和安全性低、计算复杂度高。针对这些问题,提出了一种新的子分组多重Schnorr签名方案,该方案既拥有Schnorr数字签名密码体制的计算复杂度低优势,又...共识机制是区块链系统的核心技术,但是目前的共识机制存在3个问题,即共识效率低、可靠性和安全性低、计算复杂度高。针对这些问题,提出了一种新的子分组多重Schnorr签名方案,该方案既拥有Schnorr数字签名密码体制的计算复杂度低优势,又拥有子分组多重签名的优势(它可以从集合的全体成员中选择不定数量的成员组成子分组,以代替群组产生多重签名,由于子分组是不可预知的,因此可以有效避免出现Byzantine叛徒,提高了方案的安全性,解决了共识机制存在的可靠性和安全性低、计算复杂度高的问题)。该方案引入了公共第三方(PTP,public third party),PTP由可自动公开执行的智能合约充当,完全公开透明,不仅可以抵御流氓密钥攻击,还减少了签名过程的总通信轮次和时间开销,解决了共识机制存在的共识效率低问题。同时,详细证明了该方案具有鲁棒性,可以提高共识机制的安全性;基于离散对数假设,该方案在随机预言模型下具有不可伪造性。理论分析和实验结果证明,该方案拥有更小的公钥长度、私钥长度、单签名长度和多重签名长度,拥有更少的通信轮次,签名生成算法和验证签名算法的时间开销更小,应用在共识机制上具有更优越的性能。展开更多
The representative collective digital signature,which was suggested by us,is built based on combining the advantages of group digital signature and collective digital signature.This collective digital signature schema...The representative collective digital signature,which was suggested by us,is built based on combining the advantages of group digital signature and collective digital signature.This collective digital signature schema helps to create a unique digital signature that deputizes a collective of people representing different groups of signers and may also include personal signers.The advantage of the proposed collective signature is that it can be built based on most of the well-known difficult problems such as the factor analysis,the discrete logarithm and finding modulo roots of large prime numbers and the current digital signature standards of the United States and Russian Federation.In this paper,we use the discrete logarithmic problem on prime finite fields,which has been implemented in the GOST R34.10-1994 digital signature standard,to build the proposed collective signature protocols.These protocols help to create collective signatures:Guaranteed internal integrity and fixed size,independent of the number of members involved in forming the signature.The signature built in this study,consisting of 3 components(U,R,S),stores the information of all relevant signers in the U components,thus tracking the signer and against the“disclaim of liability”of the signer later is possible.The idea of hiding the signer’s public key is also applied in the proposed protocols.This makes it easy for the signing group representative to specify which members are authorized to participate in the signature creation process.展开更多
The discrete logarithm method is the foundation of many public key algorithms. However, one type of key, defined as a weak-key, reduces the security of public key cryptosystems based on the discrete logarithm method. ...The discrete logarithm method is the foundation of many public key algorithms. However, one type of key, defined as a weak-key, reduces the security of public key cryptosystems based on the discrete logarithm method. The weak-key occurs if the public key is a factor or multiple of the primitive element, in which case the user＇s private key is not needed but can be obtained based on the character of the public key. An algorithm is presented that can easily test whether there is a weak-key in the cryptosystem. An example is given to show that an attack can be completed for the Elgamal digital signature if a weak-key exists, therefore validating the danger of weak-keys. Methods are given to prevent the generation of these weak-keys.展开更多
基金supported by the National Basic Research Program （973 Program）under Grant No.2013CB834205 the National Natural Science Foundation of China under Grant No.61272035 the Independent Innovation Foundation of Shandong University under Grant No.2012JC020
文摘In this paper, we present two explicit invalid-curve attacks on the genus 2 hyperelliptic curve over a finite field. First, we propose two explicit attack models by injecting a one-bit fault in a given divisor. Then, we discuss the construction of an invalid curve based on the faulted divisor. Our attacks are based on the fact that the Hyperelliptic Curve Scalar Multiplication (HECSM) algorithm does not utilize the curve parameters and We consider three hyperelliptic curves as the attack targets. For curve with security level 186 (in bits), our attack method can get the weakest invalid curve with security level 42 (in bits); there are 93 invalid curves with security level less than 50. We also estimate the theoretical probability of getting a weak hyperelliptic curve whose cardinality is a smooth integer. Finally, we show that the complexity of the fault attack is subexponential if the attacker can freely inject a fault in the input divisor. Cryptosystems based on the genus 2 hyperelliptic curves cannot work against our attack algorithm in practice.
基金Supported by the National Natural Science Foun-dation of China (60573047)
文摘Discrete logarithm based cryptosysterns have subtle problems that make the schemes vulnerable. This paper gives a comprehensive listing of security issues in the systems and analyzes three classes of attacks which are based on mathematical structure of the group which is used in the schemes, the disclosed information of the subgroup and implementation details respectively. The analysis will, in turn, allow us to motivate protocol design and implementation decisions.
文摘Digital signature scheme is a very important research field in computer security and modern cryptography. A (k, n) threshold digital signature scheme is proposed by integrating digital signature scheme with Shamir secret sharing scheme. It can realize group-oriented digital signature, and its security is based on the difficulty in computing discrete logarithm and quadratic residue on some special conditions. In this scheme, effective digital signature can not be generated by anyk?1 or fewer legal users, or only by signature executive. In addition, this scheme can identify any legal user who presents incorrect partial digital signature to disrupt correct signature, or any illegal user who forges digital signature. A method of extending this scheme to an Abelian group such as elliptical curve group is also discussed. The extended scheme can provide rapider computing speed and stronger security in the case of using shorter key. Key words threshold scheme - digital signature - discrete logarithm - quadratic residuc - threshold digital signature CLC number TP 309. 7 Foundation item: Supported the National Nature Science Foundation of China, Hubei Province (90104005, 2002 AB0039)Biography: FEI Ru-chun (1964-), male, Ph. D candidate, Associated professor, research direction: information security and cryptography.
文摘This paper provides a framework that reduces the computational complexity of the discrete logarithm problem. The paper describes how to decompose the initial DLP onto several DLPs of smaller dimensions. Decomposability of the DLP is an indicator of potential vulnerability of encrypted messages transmitted via open channels of the Internet or within corporate networks. Several numerical examples illustrate the frame- work and show its computational efficiency.
基金partially supported by National Key R&D Program of China(no.2017YFB0802500)The 13th Five-Year National Cryptographic Development Foundation(no.MMJJ20180208)+1 种基金Beijing Science and Technology Commission(no.2181100002718001)NSF(no.61272039).
文摘The discrete logarithm problem(DLP)is to find a solution n such that g^n=h in a finite cyclic group G=,where h∈G.The DLP is the security foundation of many cryptosystems,such as RSA.We propose a method to improve Pollard’s kangaroo algorithm,which is the classic algorithm for solving the DLP.In the proposed algorithm,the large integer multiplications are reduced by controlling whether to perform large integer multiplication.To control the process,the tools of expanding factor and jumping distance are introduced.The expanding factor is an indicator used to measure the probability of collision.Large integer multiplication is performed if the value of the expanding factor is greater than the given bound.The improved algorithm requires an average of(1.633+o(1))q(1/2)times of the large integer multiplications.In experiments,the average large integer multiplication times is approximately(1.5+o(1))q(1/2).
文摘共识机制是区块链系统的核心技术,但是目前的共识机制存在3个问题,即共识效率低、可靠性和安全性低、计算复杂度高。针对这些问题,提出了一种新的子分组多重Schnorr签名方案,该方案既拥有Schnorr数字签名密码体制的计算复杂度低优势,又拥有子分组多重签名的优势(它可以从集合的全体成员中选择不定数量的成员组成子分组,以代替群组产生多重签名,由于子分组是不可预知的,因此可以有效避免出现Byzantine叛徒,提高了方案的安全性,解决了共识机制存在的可靠性和安全性低、计算复杂度高的问题)。该方案引入了公共第三方(PTP,public third party),PTP由可自动公开执行的智能合约充当,完全公开透明,不仅可以抵御流氓密钥攻击,还减少了签名过程的总通信轮次和时间开销,解决了共识机制存在的共识效率低问题。同时,详细证明了该方案具有鲁棒性,可以提高共识机制的安全性;基于离散对数假设,该方案在随机预言模型下具有不可伪造性。理论分析和实验结果证明,该方案拥有更小的公钥长度、私钥长度、单签名长度和多重签名长度,拥有更少的通信轮次,签名生成算法和验证签名算法的时间开销更小,应用在共识机制上具有更优越的性能。
基金supported by Duy Tan University,Da Nang,Vietnam.
文摘The representative collective digital signature,which was suggested by us,is built based on combining the advantages of group digital signature and collective digital signature.This collective digital signature schema helps to create a unique digital signature that deputizes a collective of people representing different groups of signers and may also include personal signers.The advantage of the proposed collective signature is that it can be built based on most of the well-known difficult problems such as the factor analysis,the discrete logarithm and finding modulo roots of large prime numbers and the current digital signature standards of the United States and Russian Federation.In this paper,we use the discrete logarithmic problem on prime finite fields,which has been implemented in the GOST R34.10-1994 digital signature standard,to build the proposed collective signature protocols.These protocols help to create collective signatures:Guaranteed internal integrity and fixed size,independent of the number of members involved in forming the signature.The signature built in this study,consisting of 3 components(U,R,S),stores the information of all relevant signers in the U components,thus tracking the signer and against the“disclaim of liability”of the signer later is possible.The idea of hiding the signer’s public key is also applied in the proposed protocols.This makes it easy for the signing group representative to specify which members are authorized to participate in the signature creation process.
基金Supported by the National Key Basic Research and Development (973) Program (No. 2003CB314805) and the National Natural Science Foundation of China (No. 90304014)
文摘The discrete logarithm method is the foundation of many public key algorithms. However, one type of key, defined as a weak-key, reduces the security of public key cryptosystems based on the discrete logarithm method. The weak-key occurs if the public key is a factor or multiple of the primitive element, in which case the user＇s private key is not needed but can be obtained based on the character of the public key. An algorithm is presented that can easily test whether there is a weak-key in the cryptosystem. An example is given to show that an attack can be completed for the Elgamal digital signature if a weak-key exists, therefore validating the danger of weak-keys. Methods are given to prevent the generation of these weak-keys.
