《现代密码学 学习心得》由会员分享，可在线阅读，更多相关《现代密码学 学习心得（8页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 8 页混合离散对数及安全认证摘要：近二十年来，电子认证成为一个重要的研究领域。其第一个应用就是对数字文档进行数字签名，其后 Chaum 希望利用银行认证和用户的匿名性这一性质产生电子货币，于是他提出盲签名的概念。对于所有的这些问题以及其他的在线认证，零知识证明理论成为一个非常强有力的工具。虽然其具有很高的安全性，却导致高负荷运算。最近发现信息不可分辨性是一个可以兼顾安全和效率的性质。本文研究混合系数的离散对数问题，也即信息不可识别性。我们提供一种新的认证，这种认证比因式分解有更好的安全性，而且从证明者角度看来有更高的效率。我们也降低了对 Schnorr 方案变形的实际安全参数的
2、 Girault 的证明的花销。最后，基于信息不可识别性，我们得到一个安全性与因式分解相同的盲签名。1概述在密码学中，可证明为安全的方案是一直以来都在追求的一个重要目标。然而，效率一直就是一个难以实现的属性。即使在现在对于认证已经进行了广泛的研究，还是很少有方案能兼顾效率和安全性。其原因就是零知识协议的广泛应用。身份识别： 关于识别方案的第一篇理论性的论文就是关于零知识的，零知识理论使得不用泄漏关于消息的任何信息，就可以证明自己知道这个消息。然而这样一种能够抵抗主动攻击的属性，通常需要许多次迭代来得到较高的安全性，从而使得协议或者在计算方面，或者在通信量方面或者在两个方面效率都十分低下。最近，
3、poupard 和 stern 提出了一个比较高效的方案，其安全性等价于离散对数问题。然而，其约减的代价太高，使得其不适用于现实中的问题。几年以前，fiege 和 shamir 就定义了比零知识更弱的属性，即“信息隐藏”和“信息不可分辨”属性，它们对于安全的识别协议来说已经够用了。说它们比零知识更弱是指它们可能会泄漏秘密消息的某些信息，但是还不足以找到消息。具体一点来说，对于“信息隐藏”属性，如果一个攻击者能够通过一个一次主动攻击发现秘密消息，她不是通过与证明者的交互来发现它的。而对于“信息不可分辨”属性，则意味着在攻击者方面看来，证据所用的私钥是不受约束的。也就是说有许多的私钥对应于一个公钥
4、，证据仅仅传递了有这样一个私钥被使用了这样一个信息，但是用的是哪个私钥，并没有在证据传递的信息中出现。下面，我们集中考虑后一种属性，它能够提供一种三次传递识别方案并且对抗主动攻击。Okamoto 描述了一些 schnorr 和 guillou-quisquater 识别方案的变种，是基于 RSA 假设和离散对数子群中的素数阶的。随机 oracle 模型 ：最近几年，随机 oracle 模型极大的推动了研究的发展，它能够用来证明高效方案的安全性，为设计者提供了一个有价值的工具。这个模型中理想化了一些具体的密码学模型，例如哈希函数被假设为真正的随机函数，有助于给某些加密方案和数字签名等提供安全性的
5、证据。尽管在最近的报告中对于随机 oracle 模型采取了谨慎的态度，但是它仍然被普遍认为非常的有效被广泛的应用着。例如，在这个模型中被证明安全的第 2 页 共 8 页OAPE 加密方案就被集成进 VISA 和 Master 信用卡系统的模块中。有许多其他的方案在这个模型中的安全性也是有效的。11 相关的工作：前几年，Schnorr 提出了一个高效的基于素数阶子群离散对数问题的识别方案和签名方案的变种，这个著名的方案我们就不再介绍了。这个以零知识闻名的方案为了抵抗主动攻击获得较高的安全性，使用了许多次固定长度的挑战应答交互。这样，高的安全性就需要很大的通信量和很大的存储空间存储预计算量。虽然没
6、有提出安全的预处理方案，还是有许多应用中假定如果使用较大规模的挑战应答它的安全性与基本的三次通过协议相当。其安全性依赖于未经证明的假设，即假设这个方案是“信息隐藏”的。在定义了信息隐藏和信息不可分辨属性以后，brickell 和 mccuely 提出了使用信息隐藏属性的 schnorr 方案的一个变种。接着， okamoto 提出了一个基于信息不可分辨属性的三次通过协议，可以证明其安全性可以抵挡主动攻击。这些协议中有些是基于素数阶子群的离散对数问题，有的是基于 RSA 假设。但是所以这些方案都并不比原来的 schnorr 方案更加有效。在 1991 年，Grault 利用合数作为模代替素数，提
7、出了 schnorr 的一个变种，从证明者的角度来说提高了效率。Poupard 和 stern 给出了这个方案的统计意义上的零知识属性的证明，证实了这个方案的安全性等价于合数的离散对数问题。然而，这个方案，对于高的安全性要求也需要许多次交互，而大的简化只能适用于大的不实用的数据。最近他们改进了他们的简化，使其安全性仅仅等价于因数分解。这是仍在进行的一项工作。至于签名方案，由于在 pointcheval-stern 和 ohta-ocamoto 的论文中已经能够有效的将任何三次通过协议转化成签名方案，这样，对于识别协议的有效解决，对于签名协议也同样有效。盲签名：在 1982 年，chau 就想要
8、产生一种电子货币的属性，也就是具有匿名性。他指出一种方法就是将电子货币的概念和盲签名结合起来。盲签名需要涉及到银行和用户两个参与者。用户想要得到一个经过银行签名的货币，但是在签名以后，银行无法追踪这个货币和签名。后来就提出了基于 RSA 和离散对数问题的签名方案。但是这些方案都无法证明是安全的，而可以证明为安全的方案只有理论上的应用，没有什么实践价值。一直到 1996 年盲签名才可以证明为安全的。它们是基于 okamoto 的信息不可分辨协议，可以证明碰撞是很难被计算出来的。代表系问题离散对数： 。一个碰撞泄漏了 h 在基 g 中的phgsrfsrhgpmod),(,离散对数，即： fsrf
9、srhgphgp),(),( )/(, RSA 问题 /因式分解： NasrereaNod,选取适当参数，一个碰撞泄漏了 a 模 N 的 e 阶根，即：sfsrf reaeaN m)/(),(),( , 对足够大的质数 e，则根据 Bezout 等式可以解得 a 模 N 的 e 阶根，否则，如果 e 是一个合数而 N 是一个 Blum 整数，则我们可以得到 N 的因式分解。后来，另一个有名的信息不可识别性问题被用到模二次方根： 对于任Nxfmod)(2意的 满足2/0x第 3 页 共 8 页),gcd()(的 因 子NyxyfxfN在这些论文中，盲签名方案被认为是可证明安全性的，可以抵御比较攻
10、击。这就意味着银行保证 10 美元给用户后，用户得到的不能多于 10 美元。然而这些方案的主要缺点是计算量大。至今，盲签名所面对的一个重要挑战是：从签名者角度看来，他们需要高效并且可证明是安全的签名，因为他们可能同时会签成千上万的签名。12 论文要点本文中，我们首次研究通过混合系数的离散对数所提供的信息不可识别性。我们首先回顾 Girault 的方案，不幸的是相对 Schnorr 的方案，这个方案仅仅使用固定长度的挑战证明零知识，需要很多次的迭代才产生高安全性。这里，我们使用信息不可识别性证明这个方案的安全性，即使它仅仅通过一次迭代。对于先前的结果，在实用性方面有了很大提高。更进一步，即使我们
11、使用很小的密钥，我们也可以对一个有效的方案证明其安全性。其后我们认为基于该问题的盲签名的安全证明和因式分解相同。除了可证明安全性，新方案的主要特性是有效性，从银行角度看来，它仅仅需要一次乘法（不是模乘） 。2离散对数问题feige 和 shamir 已经证明，信息不可分辨属性对于识别协议来说已经足够提供用于抵抗主动攻击的安全性了。Pointcheval 和 stern 进一步证明了盲签名的这一属性还提供了抵抗并行攻击下的多次伪装攻击的安全性。这是利用了函数 fN,g(x)=gx mod N,其中 N,g 是选择好的。下面我们定义一些有用的概念。定义一（强素数） 如果一个素数 p=2r+1,其中
12、 r 是一个大整数，其素数因子都大于 ，则称 p 是 强素数。定义二（强 RSA 模数） 如果 Npq，并且 p 和 q 都是 强素数，N 就被称为 强 RSA 模数。定义三（不对称基） Npq 是一个 RSA 模数，在 ZN*中的基 g 如果在 Zp*和在 Zq*中的 Ord（ g）的奇偶性不一样，就说它是不对称基。也就是说，不对称基就是仅仅在 Zp*和Zq*的两个子群其中之一的一个二次剩余。定理四 如果 Npq 是一个任意的 强 RSA 模数，对于某些 2,g 是一个阶大于 的在 ZN*中的任意不对称基，那么定义为 xg x mod N 的一个 fN,g()的碰撞，可以将 N分解。证明：
13、我们用 2l 标记在 ZN*中 g 的阶。可以认为这一阶就是偶数，因为它至少，并且恰在子群中的一个，例如 Zp*中是偶数。而且，l 是奇数，并且大于 ，因为 l 大于/21，(p-1)/2 和(q-1)/2 的任何素数因子都是奇数，并且大于 。因此，g2l=1mod p, g2l=1modq,但是 gl=-1mod p,gl=1mod q.让我们假设我们有一个 x-e0,.2 k-1y=r+es -x=gyvemod N 我们有两个安全参数 k 和 k,其中 k 代表了挑战的长度，k 代表了泄漏的信息。还有私钥的一个范围。接着，我们定义 R2k kS。我们使用 RSA 模 N=pq 以及属于
14、ZN*的一个高阶元素。证明者随机的选择一个属于0,:,S-1 的私钥 s，公布 vg s mod N。证明者选择一个随机数 r 属于0, 。 。 。 。 。 。 ，R 1 ，发送数值 xg r mod N；验证者随机的选择一个挑战 e 属于0,.2 k-1,送给证明者；最后，证明者计算并且发送 y=r+es;验证者检验是否 x=gyvemod N.不能说这是知道基 g 模 N 中关于 v 的离散对数的证据，但是在特殊情况下，N 是一个2k强 RSA 模数时（包括实际应用中典型的强 RSA 模数）可以应用下面的定理：定理 5 假设 N 是一个 2k强 RSA 模数，如果存在一个攻击者 A，其运行
15、时间界定为T，对于 不可忽略的小量 v，能够以大于 22k 的概率 被接受，那么基 g 模 N 的离散对数可以在界定为 4T/S/Ord （g）的时间内被计算出来。证明 用古典的开方技术，我们能够得到两个对于同一个声明 x 的有效证明，一对(,)使得 v =b mod N,其中 0=2Ord(g),这一协议抵抗主动攻击的安全性是等价于分解 N 的。证明 为了证明这个识别方案的安全性能够抵抗主动攻击，我们选择一个随机的私钥s-e0,.2 k-1y=r+es -h=H（g yvemod N）? 备注 9 需要注意的是我们仅仅证明了在伪装的主动攻击下比因式分解更为困难，这个交互协议的安全性实际上已经用零知识属性证明了是等价于合数离散对数问题的。尽管如此，当我们有了 N 的因式分解，剩下的安全性就完全等价于 schnorr 识别方案，可以预见，素数阶子群的离散对数问题仍然难以解决。而且，即使为了高的安全性级别而提高挑战程度，安全性仍然保持。而基于零知识属性的协议就不具备这种特点。让我们比较一下从伪装者那获得两个应答的简化的花费。利用 Poupard 和 stern 的证明，这将导致计算 v 的离散对数的更多的
