离散对数难题

第２７卷第１０期　

２００７年１０月　计算机应用　

Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖｏ１．２７　Ｎｏ．１０　

Ｏｃｔ．２００７　

文覃编号：１００１—９０８１（２００７）１０—２４５９—０２　

基于离散对数和因子分解具有消息恢复的签名方案　

袁喜凤，孙艳蕊，孙金青，杨迎辉　

（东北大学理学院，沈阳１１０００４）　

（ｙａｎｒｕｉｓｕｎ＠１　２６．ｃｏｍ）　

摘要：基于双难题具有消息恢复的签名方案研究甚少，仅有的一些方案都存在计算效率和传输　

效率过低的问题。由此提出了一个新的同时基于离散对数和大整数分解两种困难问题的具有消息恢　

复的签名方案，并对其进行安全性分析及效率分析。其安全性要比基于一个难题的数字签名方案好，　

并且该方案比已有的基于双难题的具有消息恢复签名方案效率要高。　

关键词：数字签名；消息恢复；离散对数；因子分解　

中图分类号：ＴＰ３０９　文献标志码：Ａ　

Ｓｉｇｎａｔｕｒｅ　ｓｃｈｅｍｅ　ｗｉｔｈ　ｍｅｓｓａｇｅ　ｒｅｃｏｖｅｒｙ　ｂａｓｅｄ　ｏｎ　

ｄｉｓｃｒｅｔｅ　ｌｏｇａｒｉｔｈｍｓ　ａｎｄ　ｆａｃｔｏｒｉｎｇ　

ＹＵＡＮ　Ｘｉ—ｆｅｎｇ，ＳＵＮ　Ｙａｎ—ｒｕｉ，ＳＵＮ　Ｊｉｎ—ｑｉｎｇ，ＹＡＮＧ　Ｙｉｎｇ—ｈｕｉ　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｓｃｉｅｎｃｅ，Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ　Ｌｉａｏｎｉｎｇ　１　１０００４，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｒｅｃｅｎｔｌｙ，ｔｈｅｒｅ　ｉｓ　ｌｉｔｔｌｅ　ｒｅｓｅａｒｃｈ　ａｂｏｕｔ　ｄｉｇｉｔａｌ　ｓｃｈｅｍｅｓ　ｗｉｔｈ　ｍｅｓｓａｇｅ　ｒｅｃｏｖｅｒｙ　ｂａｓｅｄ　ｏｎ　ｄｏｕｂｌｅ　ｈａｒｄ　ｐｒｏｂｌｅｍｓ．　Ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｔｒａｎｓｍｉｓｓｉｏｎ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｓｃｈｅｍｅｓ　ｉｓ　ｔｏｏ　ｌｏｗ．Ｈｅｎｃｅ，ｉｎ　ｔｈｅ　ｐａｐｅｒ，ａ　ｎｅｗ　ｄｉｇｉｔａｌ　ｓｉｇｎａｔｕｒｅ　ｓｃｈｅｍｅ　ｗｉｔｈ　ｍｅｓｓａｇｅ　ｒｅｃｏｖｅｒｙ　Ｗａｓ　ｇｉｖｅｎ，ｉｎ　ｗｈｉｃｈ　ｔｈｅ　ｓｅｃｕｒｉｔｙ　ｗａｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｄｉｆｉｃｕｌｔｉｅｓ　ｏｆ　ｃｏｍｐｕｔｉｎｇ　ｄｉｓｃｒｅｔｅ　

椭圆曲线离散对数问题是基于椭圆曲线上的离散对数难题，通常用于椭圆曲线密码学中的一种加密算法，比如椭圆曲线数字签名算法（ECDSA）和椭圆曲线Diffie-Hellman密钥交换（ECDH）等。

下面我将详细解释椭圆曲线离散对数问题的背景和基本概念：

1. 椭圆曲线基础

椭圆曲线是一个由满足特定方程的点组成的集合。通常，椭圆曲线的方程可以表示为：

𝑦2=𝑥3+𝑎𝑥+𝑏

其中，𝑎和𝑏是定义曲线的参数。在有限域上，我们通常选择一个素数域（有限域）作为底域，比如GF(p)，其中p是一个素数。曲线上的点和加法运算定义了一个群结构。

2. 离散对数问题

离散对数问题是在一个有限群中找到给定元素的幂等于另一个给定元素的指数。对于椭圆曲线离散对数问题，我们考虑椭圆曲线上的点和它们的倍数。

具体而言，对于椭圆曲线上的点 𝑃 和整数 𝑘，问题是找到整数 𝑛，使得 𝑛𝑃=𝑄，其中 𝑄 是已知的椭圆曲线上的点。这里，𝑛 就是离散对数。

3. 安全性

椭圆曲线离散对数问题是一种困难的数学问题，目前尚未找到高效的经典算法来解决。这使得椭圆曲线密码学方案变得相对安全。然而，随着量子计算技术的发展，部分经典加密算法（如RSA、DSA）和椭圆曲线密码学也面临潜在的风险。

因此，未来的密码学研究重点之一是发展抵抗量子计算攻击的密码学算法，以确保信息安全。

总体来说，椭圆曲线离散对数问题在密码学中扮演着重要的角色，它为很多加密算法提供了安全性基础。

椭圆曲线上的离散对数难题

椭圆曲线离散对数难题是现代密码学的基础，它是一种被用来加密传输信息的技术，它包含了两个可以解密信息的私有密钥。椭圆曲线离散对数难题是一个很大的计算难题，通过分解一个位数很大的数字来解决这个问题。

椭圆曲线离散对数难题基于椭圆曲线定理，即在上椭圆曲线定义的点P上，函数x^2+y^2=n的值极大。它的原理是：对任何把一个点P乘以自身，结果是确定的。问题可以用简单的破解数学证明：如果一个P点乘上自己n次后，可以表示成Q，也就是Q=n P，叫做加法和椭圆曲线离散对数，用另外一个数Q来表示n。

要解决椭圆曲线离散对数难题，必须找出那些不变的点P，它们对于上述加法共有特点。如果能找到一个椭圆曲线上的点P，并且它的两个坐标大致相同，那么就可以根据该点的性质来推导出p的椭圆曲线离散之参数n值。

椭圆曲线离散对数难题也被称为“离散对数问题”或“正多支椭圆曲线模糊问题”。它是一个非常重要和有用的大型计算难题，用于许多密码编码系统。由于它可以提供足够的安全性，因此可以被广泛应用于金融交易、数据传输和信息存储等多种场景。

基于离散对数问题(一)

基于离散对数问题

在密码学中，离散对数问题是一种重要的数学难题，基于这个问题的算法在密码学中得到广泛应用。本文将介绍相关问题，并对其进行解释说明。

离散对数问题简介

离散对数问题是指在一个有限域中，找到一个数的指数是另一个给定数的问题。具体而言，对于素数p和整数a，找到一个整数x，使得a^x ≡ b (mod p)。

相关问题

离散对数问题相关的一些问题包括：

• 离散对数问题的求解：给定p、a和b，找到一个满足a^x ≡ b

(mod p)的整数x。

• 离散对数问题的困难性：证明离散对数问题在计算上是困难的，即没有已知的有效算法可以在多项式时间内解决该问题。

• 离散对数问题的应用：探讨离散对数问题在密码学中的应用，如基于离散对数问题的公钥密码算法，例如Diffie-Hellman密钥交换算法和ElGamal加密算法。 • 离散对数问题的安全性：研究离散对数问题的安全性，即它是否可以被破解。目前，离散对数问题被认为是一个强大的密码学基础，并且在合适的参数选择下，具有很高的安全性。

• 离散对数问题的优化算法：探索提高离散对数问题求解效率的优化算法。例如，Pohlig-Hellman算法是一种用于解决离散对数问题的优化算法。

解释说明

离散对数问题是一个在密码学中经常使用的问题，它基于一个简单的数学难题，即找到一个指数使得指数函数的结果与给定值同余。离散对数问题的困难性保证了基于该问题的密码体系的安全性。

离散对数问题的应用非常广泛。其中，Diffie-Hellman密钥交换算法允许两个通信方通过公开的通道协商出一个共享密钥，而该密钥对于外部攻击者是困难的。ElGamal加密算法则基于离散对数问题提供了对称密钥加密的安全性。

尽管离散对数问题被广泛应用于密码学中，但目前没有已知的有效算法可以在多项式时间内解决这个问题。因此，离散对数问题被认为是一个困难的数学难题，并被广泛接受为安全的密码学基础。