论文标题
离散对数密码学的可移动弱键
Removable Weak Keys for Discrete Logarithm Based Cryptography
论文作者
论文摘要
我们描述了一种新型的弱加密私钥类型,该钥匙可以在任何基于离散对数的公共密钥密码系统中都存在于一组Prime Order $ p $中,其中$ p-1 $具有很小的除数。与基于\ textIt {数字大小}的弱私钥(例如,较小的私钥或位于间隔的私钥)不同,它将在任何DLP加密系统中都存在\ textit {始终},我们的弱私钥类型纯粹是由于$ p $的参数选择,因此可以删除$ p $的参数,因此可以将其删除。使用隐式组表示理论,我们提出可以确定键是否弱的算法,如果是,则从相应的公共密钥中恢复了私钥。我们分析了文献和各种标准中提出的几条椭圆曲线,从而给出了可以通过相对较少的计算而破坏的键数。我们的结果表明,其中许多曲线,包括标准的一些曲线,都有相当多的私密钥匙。我们还使用我们的方法表明,从我们的意义上讲,14个出色的认证挑战问题实例都没有弱,直到某种弱点。
We describe a novel type of weak cryptographic private key that can exist in any discrete logarithm based public-key cryptosystem set in a group of prime order $p$ where $p-1$ has small divisors. Unlike the weak private keys based on \textit{numerical size} (such as smaller private keys, or private keys lying in an interval) that will \textit{always} exist in any DLP cryptosystems, our type of weak private keys occurs purely due to parameter choice of $p$, and hence, can be removed with appropriate value of $p$. Using the theory of implicit group representations, we present algorithms that can determine whether a key is weak, and if so, recover the private key from the corresponding public key. We analyze several elliptic curves proposed in the literature and in various standards, giving counts of the number of keys that can be broken with relatively small amounts of computation. Our results show that many of these curves, including some from standards, have a considerable number of such weak private keys. We also use our methods to show that none of the 14 outstanding Certicom Challenge problem instances are weak in our sense, up to a certain weakness bound.