英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料
一种基于离散对数的公钥密码系统和签名方案
摘要：一种基于实现Diffie-Hellman钥匙分布方案的新型签名方案被提出以实现一种公钥密码系统。系统的安全性依赖于在定义域内计算离散对数的难易性。
- 简介
在1976年Diffie和Hellman引入了一种公钥密码学的概念。从那时起，研究人员为了寻找到实用的公钥系统几经尝试，这些公钥系统都依赖于解出问题的难易性。例如，RSA系统依赖于因式分解大型整数的难易性。该文章所提出的系统是依赖于在定义域内计算离散对数的难易性的。
第二部分是介绍一种能够实现由Diffie和Hellman引入的公钥分布方案以译码和解码消息的方式，该系统的安全性等同于分布方案的安全性。第三部分介绍的是一种新型数字签名方案，它取决于在定义域内对离散对数计算的难易性，它还并未能够证明破坏系统与计算离散对数是否相关联。第四部分开发了一些针对签名方案的攻击，但是它们之中似乎并没有能够攻击系统的。第五部分给出了系统的某些部分。第六部分对于整篇文章进行了总结和评价。
- 公钥系统
首先，评估Diffie-Hellman钥匙方案，假设想要共享一个秘密，其中有一个秘密为，有一个秘密为。使成为大质数，为模的素元，两者均已知。计算模，并且发送。相类似的，计算模，并且发送。然后秘密按照如下公式计算：
因此，和都能够计算出。但是对于计算进行干扰是有一定困难的，需要注意的是，目前尚无研究可以证明破坏系统与计算离散对数相关。
在任何基于离散对数的密码学中，必须被选择，至少含有一个大素数元。如果仅仅只有小素数元，那么计算离散对数将会十分简单。
现在我们假设想要将消息发送给，其中。首先，选择了一个在0和之间一致分布的数字，需要注意的是，将会在钥匙分布方案中起到秘密的作用，然后计算“钥匙”：
（1）
其中既是在公共文件中，也是被发送的。加密的消息或者说是密文就是以下的对，其中
（2）
其中的值按照以上的（1）式计算。
需要注意的是，密文的大小是消息大小的两倍，操作（2）中的乘法可以被任意其他的可逆操作如代替。
解密操作被划分为两个部分。第一步为恢复，这对而言是非常简单的，因为，并且仅对可知。第二步为通过划分和恢复消息。
公共文件是由针对每个用户的一个入口组成的，换句话说就是用户（因为和对所有的用户都是可知的）。每一个用户选择他自己的和是有一定可能性的，这从安全性的观点来看更加合理，但是这会使公共文件的大小增至三倍。
使用相同的值译码远比使用消息的一个块更加不明智，因为如果被多次使用，消息中的块的知识会使入侵者按照以下方式计算出其他的块：
使，并且,然后，并且如果已知的话，会很容易地被计算出来。
我们可以容易地得知，攻击系统相当于攻击Diffie-Hellman分布方案。首先，如果可以从和中计算得出，那么也可以从和中计算出来（因为和是未知的，所以这看上去像是随机数）。这等同于攻击分布方案。第二，（即使已知）从和计算或者是等价于计算离散对数，原因在于和都出现在了和的指数上。
- 一种数字签名方案
该部分描述了一种行的签名方案。公共文件包含了针对加密消息的公钥和验证签名。
使成为需要署名的文件，其中。公共文件仍然由每个用户的公钥组成。为了签署文件，用户应该能够使用密钥以一种方式寻找针对的签名，这种方式允许所有用户通过使用公钥（与并用）验证签名的真实性，并且无人可以在不知晓秘密地情况下伪造签名。
的签名是对，，所选择的要满足以下公式：
（3）
-
- 签名步骤
签名程序有以下三个步骤组成：
选择一个随机数，在0到中一致分布，如。
计算
（4） 现在公式（3）可以写作
（5）它可以通过使用公式（6）计算
（6）
如果按照计算得到，那么公式（6）针对有解出的方法。
-
- 验证步骤
根据已给出的和值，通过计算公式（3）的边以及核对它们是否相等可以很容易地验证签名的真实性。
备注：正如第四部分将要展示的，在步骤中被选中的值仅仅只能被使用一次，这个有所保证，例如，通过使用一种“产生器”，一种芯片在计数器模式中作为一个流密码被使用。
- 一些在签名方案中的攻击
该部分介绍一些在签名方案中的可能发生的攻击。这些攻击很容易地被看作是等同于计算在的离散对数。但是攻击签名方案等同于计算离散对数或者攻击分布方案是并没有经过证实的。但是，没有任何的攻击在该部分显示攻击了系统。我们鼓励 读者开发新型攻击或者是寻找快速算法以实现本部分所描述的攻击之一，攻击将会被划分为两组，第一组包括针对恢复密钥的一些攻击，第二组为我们无需恢复而伪造签名的一些攻击。
-
- 旨在恢复的攻击
4.1.1 的文件与相应的签名被给出，侵入者可以尝试解出个（6）形式的方程式，因为有个未知数（每一个签名使用不同的），方程式的系统是欠定的，并且解出方法的数量是巨大的。因为基于对角矩阵系数的线性方程是系统会有结果，所以每一个的数值都会产生一个针对的解出方法。由于被选择为至少有一个大素数元，再生需要一个消息签名对的指数。
备注：如果任意的在签名时被使用两次，那么方程式的系统被特定地决定，可以被再生。所以为了系统的安全性，任意值不能被使用两次。
4.1.2 尝试解出形式为（3）的方程式总是等同于计算在上的离散对数，因为未知的和均出现在指数上。
4.1.3 入侵者可能尝试着在未知的中培养线性依赖关系，这就等同于计算离散对数，因为如果，那么，并且如果可以被计算出来，那么计算离散对数将会十分简单。
-
- 伪造签名的攻击
4.2.1 文件被给出，伪造者可能尝试寻找满足（3）式的。如果针对某些被随机选中的是固定不变的，那么计算等同于解出在上的离散对数问题。
如果伪造者一开始固定了，那么可以按如下的方程式进行计算：
（7）
解出等式（7）中的并没有证明出至少与计算离散对数一样有难度，但是我们不认为在多项式时间中解出（7）是可行的。我们希望读者能够针对（7）寻找到多项式时间算法。
4.2.2 等式（3）看上去似乎能够同时解出和，但是我们并没有寻找到有效的算法能够做到。
4.2.3 签名方案允许以下的攻击，即凭借攻击者了解针对某个消息的一个合法签名能够生成其他的合法签名和消息。这种攻击并不允许入侵者签署任意的消息，因此无法攻破系统。这种性质存在于所有的现存数字签名方案中，它可以被以下的两种方式中的任何一种所避免，即是确定的亦或在签名之前经一种单向函数应用于消息。
对于消息（）给出签名，然后。随意选择整数满足与是互素的。设置
然后断定对消息进行了签名。计算
所有的计算都要
设置作为一种特殊情况，合法的签名可以与相应的消息生成无需看见任何的签名：
可以看出，对消息进行了签名。
- 我们系统的性能与其他签名方案和公钥系统的对比
使成为离散对数问题中的二进制数字或者是整数因式分解问题中的二进制数字，然后对于计算离散对数和因式分解整数都最佳的已知算法（即在某些现存的系统如RSA系统被调用的函数）被给出（可参考[1,5,10]）
（8）
其中，对整数进行因式分解还有上的离散对数的最佳估值为0.89（参考Schnorr和Lenstra[10]）。这些估值意味着我们必须使用在RSA系统中被使用的数字的规模大小以获取相同的安全性级别（这里假设当前的值均针对离散对数问题和整数因式分解问题）。所以，公共文件的规模大小比RSA系统的要大。（对于RSA系统而言，每一个用户在公共文件中都有一个入口作为他与加密密钥一起的公钥）。
-
- 公钥系统的性能
正如以上所显示的，我们的系统与其他的已知系统有着不同之处。首先，由于解密操作中的随机选择，已给出消息的密文没有被重复，即如果我们对相同的消息进行二次解密，我们不会得到相同的密文。这防止了类似可能文本攻击，在可能文本攻击中，如果入侵者就假设文本为，那么他尝试着解密并且发现原本假设的文本的确是。这种攻击以及与它相类似的攻击不会成功，因为初始的发送者选择了随机数字以解密，并且的不同数值会产生的不同值。此外，由于我们系统结构的特点，解密与或者其他与的简单函数是没有明显的联系的。这并不是已知系统如RSA系统所拥有的情况。
假设与RSA系统中所需的有一样的规模大小，那么与相应的RSA系统的密文大小相比。本系统中的密文的大小是它的两倍。
加密操作需要两次求幂，这等价于在中的乘法。对于解密操作仅仅只需要一次求幂（加上一次除法）。
-
- 签名方案的性能
由于签名方案使用了针对我们系统与RSA系统中的数字规模大小的以上参数，所以签名是文档大小的两倍。其次，签名的大小与RSA系统所需的大小是相同的，并且是新型签名方案中签名大小的一半，这里的新型签名方案依赖于Ong,Schnorr和Shamir所出版的二次型（因为系统均是基于整数因式分解问题的）。Ong-Schnorr-Shamir系统已经被Pollard破解，并且新型变体被提出。因此，基于模数方程式的安全系统能否被找到在现在还不是很清楚，因此，涉及这些方案的进一步附注没有被做出。
需要注意的是，因为当文档的数字仅为时，签名的数字为，每一个文档有许多的签名，但是任何签名只签署一个文档。
在签名过程中，需要一次求幂（加上一次除法）。为了核实签名，似乎需要三次求幂，但是这取决于作者A.Shamir，他仅仅使用了1.875次求幂。这在他们的二进制扩展中通过展示三个范例已经实现。在每一步，对数字平方，然后被必要元素除以占据的不同扩展部分。的不同倍数可以在一个由八个入口构成的表格中存储。我们期望仅需要0.875次乘法操作占据所需的1.875次求幂操作。
- 结论与附注
该论文描述了一种基于在定义域内计算离散对数难易度的签名方案和公钥密码系统。该系统仅在被描述、公钥系统可以被轻易地拓展到任何，但是由于在上计算离散对数的近代发展中的较大，所以使用更加明智。但是如果和的规模大小相同，那么对于较大的，在上计算离散对数比在上难度更大。子指数时间算法已经被延伸到并且显示可以被延伸到所有的定义域内。因此，可以看出使用实施任何的密码系统效果会更好。计算离散对数和因式分解整数的运行时间估值是目前为止中已知的最佳的。这些评估值意味着在此方案中的公共文件大小比RSA方案中的要大，但是两种方案最大的区别在于它们的结构不同。此外，加密文本的大小是RSA系统加密文本大小的两倍。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[29535]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
