公钥加密体制

公钥加密体制私钥加密体制（对称加密体制、单钥加密体制）公钥加密体制（非对称加密体制、双钥加密体制）私钥加密体制的优缺点：1 运算速度快，密钥产生容易。2 当用户很多、分布很广时，密钥的分配的存储就成了大问题；3 不能实现数字签名。一、DiffieHellman加密体制二、 RSA加密体制RSA体制是由R.L.Rivest, A.Shamir和L.Adlemansh在1978年提出的。它既可用于加密、也可用于数字签名，标准化组织ISO，ITU及SWIFT等均已接受RSA体制作为标准。RSA密码体制的提出是密码学史上的一个里程碑，RSA的基础是数论中的欧拉定理，安全性依赖于大数的因数分解的困难性(即哥德巴赫猜想这一难题)。由于其算法简单，在实际应用中容易实现，因此在理论上是最为成功的密码体制，它是目前应用最为广泛的公钥密码体制之一。基于此，第4章中我们采用该密码体制来加密传送会话密钥。下面给出几个定理及推论，它们是RSA体制的数学理论背景。定理2.1（欧拉定理）若整数a和n互素，则其中是比n小但与n互素的整数的个数。 特别地，当n为素数时，由欧拉定理可得下面的推论：推论2.1（费马小定理）若p为素数，则： 根据欧拉定理，可以证明下面的定理，它直接给出关于RSA密码体制中的解密变换是加密变换的逆的证明。定理2.2 设p和q是两个不同的素数，对任意的整数x()，及任意的非负整数k，有：定理2.3（中国剩余定理）设是两两互素的正整数，则同余式组有唯一解其中 由于篇幅关系，以上定理及推论的证明略。 RSA加密算法的过程是1. 取两个素数p和q(保密)。2. 计算(公开)，(保密)。3. 随机选取整数e，满足(公开)。4. 计算d，满足(保密)。 加密算法：将明文分组，各组在下可唯一表示，密文为： 解密算法：下面作几点说明：1因为在该体制中是公开的，因此为了防止敌人用穷搜索发现p、 q，这两个素数应该是在一个足够大的整数集合中选取的大数（建议采用100位的十进制的大素数）。2为了保证RSA公钥密码体制的安全性，除了要求素数p、q足够大外，我们还要对其作如下要求：(1) ；其中，a、b均为奇素数；(2) p和q的长度相差不大；(3) 和有大素数因子；(4) 很小。满足条件(1)的p、q称之为强素数，满足条件(2), (3), (4)的称之为安全素数。3加密密钥e的适当选择能极大地加快RSA的加密速度。最经常使用的三个e的值是3，17和65537（它们的二进制表示中都只有两个1，分别只需进行2次、5次和17次乘法运算）。考虑到安全性，e的值一般选取65537。4为了提高RSA的解密速度，可在解密运算中运用中国剩余定理。三、 ElGamal密码体制ElGamal密码体制是一种基于离散对数问题的公钥密码体制，既可用于加密，又可用于数字签名，其安全性依赖于计算有限域上离散对数的难度。其加密算法如下所述。令是一个有p个元素的有限域，p是一个素数，令g是(中除去0元素)中的一个本原元或其生成元。明文集为，密文集为。要产生一对密钥，首先选定一素数p，两个随机数g和x，g和x都小于p，然后计算。公开密钥是y，g和p； 私钥是x。加密： 要加密消息M，首先选择随机数k，且，然后计算： （随机数k被加密） （明文被随机数k和公钥y加密）密文由a和b两个部分构成，其大小是明文的两倍。明文是由密文和所选择的随机数k来确定，因而是非确定性加密，一般称为随机化加密。解密： 收到密文对a和b后，计算：四、背包加密体制背包加密体制的加、解密过程：1 密钥生成(1) 随机选取一超递增序列，用它作为用户的秘密密钥，记为； （2）选取一对大的且互素的数W，N，并把背包序列变为困难的背包序列：（3）将公开作为E，记为2 加密过程（1） 在公开密钥数据库中查得用户U的公开密钥 （2） 将明文表示成二元序