第二章 可验证秘密分享的基础理论

1、第二章 可验证秘密分享的基础理论本章将介绍一些必要的秘密分享基础知识，并对几个典型的分享方案进行了描述和分析2.1 公钥密码密码系统根据密钥的特点，可分为两类，即私钥密码系统和公钥密码系统在私钥密码系统中，解密密钥与加密密钥相同或容易从加密密钥导出因此，加密密钥的暴露会使系统变得不安全；私钥密码系统的一个严重缺陷是通信双方必须使用一个安全信道预先约定密钥，但现实中这一点是很难实现的在公钥密码系统中，解密密钥和加密密钥不同，从一个难以推出另一个，解密和加密是可分离的；从而，通信双方无需事先交换密钥就可以建立起保密通信公钥密码的思想是由Diffie和Hellman在1976年首次提出的，给密码学的

2、发展带来了划时代的变革自从那时起，人们基于不同的计算问题，提出了大量的公钥密码系统当然最重要的有RSA体制、ElGamal体制、Williams体制、Merkle-Hellman背包体制和基于身份的公钥密码系统等；其中RSA体制是1977年由Rivest，Shamir和Adleman提出的第一个比较完善的公钥密码系统 公钥密码的研究中经常涉及到一个很重要的概念陷门单向函数一个函数，如果对它的定义域上的任意都易于计算，而对于的值域中的几乎所有的，即使当已知时要计算也是不可行的，就称是单向函数若当给定某些辅助信息下易于计算单向函数的逆，就称是一个陷门单向函数这一辅助信息就是解密密钥这就是设计公钥密

3、码体制的基本原理这类密码的强度取决于求的计算复杂性 主要的基本概念这里，介绍公钥密码学中的一些重要的基本概念u 公钥密码体制由上面的叙述可知，使用传统的密码体制进行秘密通信，显然要求不同用户间应约定不同的密钥这样，如果个用户都能够秘密地交换信息，则每个用户将需要个密钥；这样巨大的密钥量给密钥的分配与管理带来极大的困难由Diffie和Hellman提出的公钥密码体制解决了这个问题，他们提出：加密密钥与解密密钥分开，并将加密密钥公开、解密密钥保密这样，每个用户拥有两个密钥：公开钥（公钥）和秘密钥（私钥）,并且所有公钥均被记录在类似电话号码薄的密钥本中这种密码体制的安全性是从已知的公钥、加密算法与在

4、信道上截获的秘文不能求出明文或私钥若用、分别表示加、解密变换，则它们应满足如下三个条件：（1）是的逆变换，即（明文空间），均有（2）在已知的公钥与私钥的条件下，与均是多项式时间的确定性算法（3），找到算法，使得是非常困难的这里所谓的非常困难是指在现有的资源与算法下，找到是不现实的 满足上述三条的定义在正整数集上的数论函数称为陷门单向函数于是设计公钥密码体制就变成寻找陷门单向函数通常选择NP问题或NPC问题作为构造公钥密码体制的数学基础u 门限方案不论哪种密码体制，解密密钥都是需要严格保密的；所以，研究密钥的管理就成为一个重要课题以往，通常是将要管理的密钥放在特殊警卫的保险柜内，或按照某种方式记

5、在某个人的头脑里；但这些都是不安全的为了可靠起见，人们想到将密钥复制成多个副本，存放在不同的保险柜内或计算机中，或者增加掌握密钥的人数，但这样做显然又增加了泄密的可能性为了解决这一问题，Shamir和Blakley在1979年分别给出了门限密钥分散管理方案（简称门限方案）；简单地说，设密钥通过分配算法被分发给个成员保管，如果满足：（1）任何不少于个的合格成员通过所持有的正确的信息都可以重构；（2）任何个以下的成员集都无法重构；称这种方案为门限方案，其中为方案的门限值u 数字签名在进行秘密通信中，怎样才能鉴别收方收到的信息确定是发方所发的，且发方可以确认内容没有被收方窜改？这是一个十分重要的问题

6、；而解决这个问题的办法就是实施数字签名在公钥密码体制中，如果加、解密变换、是可交换的互逆变换，即对，有；则可以用这样的PKC来实现数字签名这时的公钥密码体制就可用于数字签名设用户发送一个签了名的明文给用户，则操作过程如下：（1）先用自己的私钥变换得到；（2）再用用户的公钥对进行变换得到，并将发送给用户；（3） 收到后，用他的私钥进行变换得 ；（4）再用用户的公钥对进行变换得到这样，用户就收到了由用户签了名的明文因为除外，任何人均无法由明文产生，所以这样做的结果是：用户确信收到的明文是用户所发送的，而用户也无法否认发送过明文 重要的公钥密码体制这里，主要描述几个最重要的公钥密码体制u RSA密码

7、体制RSA体制的安全性是基于分解大整数的困难性 设其中和为素数设，且定义对于，定义加密变换为 ，；解密变换为，；值是公钥，是私钥使用RSA体制时必须注意几点：（1）不能泄露解密指数，否则必须重新选择模数；（2）为了使分解算法（分解算法是一种分解大整数的方法）失败，选择和时应使和含有大的素因子一般的方法是选择两个大素数和，使得和也是素数（形如的素数通常称为安全素数）；（3）不同用户不可以共用模数这是因为，假定用户与共用模数，他们的加密指数分别为和，且如果用户想加密同一明文送给与，那么用户计算，；然后将发送给 假定截取到了和，那么就可以按照欧几里德算法求出和,使得，则这表明，无论密码系统多么“安全

8、”，解密发送的明文都是可能的； （4）不同用户选用的素数不能相重不然的话，若与共用素数，设与分别是他们的模数，那么任何人可用欧几里德算法求出，从而得到与的分解式u ElGamal密码体制ElGamal体制是在密码协议中有着大量应用的一类公钥密码体制，它的安全性是基于离散对数问题的困难性在一个有限域（为素数）上的离散对数问题可叙述为：给定一个素数和的一个本原元，对，找唯一的一个整数，使得通常用来表示一般地，如果仔细选择，那么认为该问题是困难的特别地，目前还没有找到计算离散对数的多项式时间算法为了抵抗已知的攻击，应该至少为150位十进制整数，并且至少有一个大的素因子ElGamal密码体制是非确定性

9、的，同一明文的秘文取决于每次加密者选择的随机值上的ElGamal公钥密码体制描述如下：设是一个素数，使得在上的离散对数问题是难处理的，令是一个本原元令，,定义 ，是公钥，是私钥对于，以及一个秘密的随机数，定义 ，其中 ，对、，定义u Williams密码体制密钥的产生：与RSA系统相同，接收者任选两个大素数，并求出；公开密钥：加 密：若欲传送明文给，则首先取得的公钥，并求出密文；将密文传送给解 密：收到密文后，将求出密文在模数下的四个平方根、及其，则必为此四个根之一若明文满足某种格式（如后面加时间或许多0），则由此格式可以判定此四个根何者为真正的明文Williams体制由于在解密时有四个平方根，由此此系统并非如RSA般一明文对应一密文的一对一系统利用格式法会造成传输效率较低（明文长度减少）为了使Williams体制为一对一的系统，有些学者提出利用额外两个位使接收者能唯一确定四个平方根中何者为明文Harn及Kiesler提出一种消除此额外二位的方法，他们的方法基于下列定理：定理 若，是大素数且同余3模4，则对于任一整数，若不知道，那么的四个平方根可依下面的情况加以分辨：(1) ；(2) ；(3) ；(4) u Merkle-Hellman背包体制Merkle-Hellman背包体制