《第4章非对称密码体制网络1》由会员分享，可在线阅读，更多相关《第4章非对称密码体制网络1（35页珍藏版）》请在金锄头文库上搜索。
1、第四章公开密钥密码体制v一一. 基本要求与基本知识点基本要求与基本知识点（1）掌握公钥密码体制的基本概念；）掌握公钥密码体制的基本概念；（2）掌握）掌握RSA的密钥产生、加密及解密的密钥产生、加密及解密过程；过程；（3）理解）理解ELGamal体制的密钥产生、加体制的密钥产生、加密及解密过程；密及解密过程；（4）理解背包体制的密钥产生、加密及）理解背包体制的密钥产生、加密及解密过程。解密过程。v二二. 教学重点与难点教学重点与难点（1）公钥密码体制的基本概念；）公钥密码体制的基本概念；（2）RSA体制；体制；（3）ELGamal体制；体制；（4）背包体制。）背包体制。14.1 公钥密码体制的基
2、本概念公钥密码体制的基本概念v公钥密码体制是为了解决对称密码体制中最难解公钥密码体制是为了解决对称密码体制中最难解决的两个问题而提出的。决的两个问题而提出的。一是对称密码技术的一是对称密码技术的密钥分配密钥分配问题。问题。在对称密码体制中，加密密钥和解密密钥是相在对称密码体制中，加密密钥和解密密钥是相同的，任何人只要获得加密密钥，才能对密文同的，任何人只要获得加密密钥，才能对密文进行解密，获得明文。利用对称密码体制进行进行解密，获得明文。利用对称密码体制进行保密通信时，密钥不能公开，要通过安全信道保密通信时，密钥不能公开，要通过安全信道传送给合法的接收者。若网络中有传送给合法的接收者。若网络中
3、有n个人要互个人要互相进行保密通信的话，每一个人就须保存另外相进行保密通信的话，每一个人就须保存另外n-1的密钥，因而网络中就会有的密钥，因而网络中就会有n(n-1)2个密个密钥，且为安全起见，密钥需要经常更换。因此钥，且为安全起见，密钥需要经常更换。因此当当n较大时，大量密码的产生、分发和更换十较大时，大量密码的产生、分发和更换十分困难，即密钥管理变得十分复杂。分困难，即密钥管理变得十分复杂。二是对称密码不能实现二是对称密码不能实现数字签名数字签名，无法证实信，无法证实信息的真实性。息的真实性。2vDiffie和和Hellmna于于1976年在密码学的新方向年在密码学的新方向中首次提出了公钥
4、密码的观点，即为每个用户分配中首次提出了公钥密码的观点，即为每个用户分配两个相互两个相互匹配匹配又相互又相互独立独立的密钥，其中：的密钥，其中：一个密钥被公开，称为公开密钥（一个密钥被公开，称为公开密钥（公钥公钥），用），用于于加密加密。另一个密钥被保密，称为私有密钥（另一个密钥被保密，称为私有密钥（私钥私钥），），用于用于解密解密。v所有用户的公钥均登记在类似电话号码簿的密钥本所有用户的公钥均登记在类似电话号码簿的密钥本上。上。当要给用户当要给用户A发送加密信息时，需要在密码本上发送加密信息时，需要在密码本上查找查找A用户的公钥，然后加密信息，并发给用户用户的公钥，然后加密信息，并发给用户A
5、。用户用户A接收到密文之后，用自己的私钥进行解密接收到密文之后，用自己的私钥进行解密即可得到明文。即可得到明文。3v1977年由年由Rivest（李维斯特）、（李维斯特）、Shamir（沙米尔）（沙米尔）和和Adleman（埃德曼）共同提出了第一个公钥密码（埃德曼）共同提出了第一个公钥密码算法（即算法（即RSA密码体制密码体制），是公钥密码中最优秀的），是公钥密码中最优秀的加密算法，被誉为密码学发展史上的加密算法，被誉为密码学发展史上的里程碑里程碑之一。之一。此后，人们基于不同的计算问题提出了大量的公钥此后，人们基于不同的计算问题提出了大量的公钥密码算法。密码算法。v在公钥密码体制（在公钥密码
6、体制（Public-Key Cryptosystem）中，）中，加密和解密使用两把不同的密钥，加密和解密使用两把不同的密钥，即公钥（即公钥（Public Key）和私钥（）和私钥（Private Key）。）。公钥可以被任何人知道，用于公钥可以被任何人知道，用于加密消息加密消息以及以及验证验证签名签名；私钥仅仅自己知道，用于私钥仅仅自己知道，用于解密消息解密消息和和签名签名。因此又称其为因此又称其为非对称密码体制非对称密码体制(Asymmetric Cryptosystem)。v如果能从公开的加密密钥推出解密密钥，那么这种如果能从公开的加密密钥推出解密密钥，那么这种密码体制就是不安全的。密码体
7、制就是不安全的。4v与对称密码体制所采取的技术不同，公钥密码算法与对称密码体制所采取的技术不同，公钥密码算法是基于是基于数学函数数学函数，而不是基于，而不是基于代换和置换代换和置换。因此要。因此要构造一个公钥密码体制时，必须寻找符合下列条件构造一个公钥密码体制时，必须寻找符合下列条件的函数的函数f(x)：（1）对于）对于f(x)定义域中的每个定义域中的每个x，使，使f(x)=y，均存，均存在函数在函数f -1 (y)，使，使f-1 (f(x)=x； -相当于加密和解密变换均存在相当于加密和解密变换均存在（2）f(x)和和f -1 (y)都容易计算；都容易计算； -相当于加密和解密过程都容易进行
8、相当于加密和解密过程都容易进行（3）已知）已知f(x)，求出，求出f -1 (y)非常困难。非常困难。 -相当于由密文推出明文困难。相当于由密文推出明文困难。5加密模型和认证模型加密模型和认证模型v一个公钥密码体制由一个公钥密码体制由6个部分构成：明文，加密算个部分构成：明文，加密算法，公钥和私钥，密文，解密算法。可以构成两种法，公钥和私钥，密文，解密算法。可以构成两种基本的模型：加密模型和认证模型。基本的模型：加密模型和认证模型。1、加密模型、加密模型-保密性保密性v在加密模型中，发送方用接收方的在加密模型中，发送方用接收方的公钥公钥作为作为加密加密密密钥，接收方用自己的钥，接收方用自己的私
9、钥私钥作作解密解密密钥。由于该私钥密钥。由于该私钥只有接收方拥有，因此只有接收者才能解密密文，只有接收方拥有，因此只有接收者才能解密密文，得到明文。得到明文。6v如图如图4-1所示，假设用户所示，假设用户A向用户向用户B发送消息发送消息M。在发送方，用户在发送方，用户A首先用用户首先用用户B的公钥的公钥PUB加密加密消息消息M，得到密文：，得到密文： ；在接收方，用户在接收方，用户B用自己的私钥用自己的私钥PRB解密密文解密密文C，得到明文：，得到明文：由于只有由于只有B知道知道PRB，所以其他人不能解密，所以其他人不能解密C。7图图4-1 公钥加密模型公钥加密模型 8加密模型和认证模型加密模
10、型和认证模型2、认证模型、认证模型-认证性（完整性、真实性）认证性（完整性、真实性）v在认证模型中，发送方用自己的在认证模型中，发送方用自己的私钥私钥对消息进行变对消息进行变换，产生换，产生数字签名数字签名。接收者用发送者的。接收者用发送者的公钥公钥对数字对数字签名进行签名进行验证验证以确定签名是否有效。以确定签名是否有效。只有拥有私钥的发送者才能对消息产生有效的只有拥有私钥的发送者才能对消息产生有效的数字签名，所以其他人数字签名，所以其他人不能伪造不能伪造其签名。其签名。任何人都任何人都可以得到发送方的公钥，因此可以用可以得到发送方的公钥，因此可以用签名人的公钥，来签名人的公钥，来验证验证其
11、数字签名的有效性。其数字签名的有效性。9v如图如图4-2所示，所示，用户用户A首先用自己的首先用自己的私钥私钥PRA对消息对消息M做做解密解密变换，变换，即数字签名：即数字签名： ；在接收方，用户在接收方，用户B用用A的的公钥公钥PUA对对C做加密变换，做加密变换，即即验证验证A的数字签名：的数字签名： 。10图图4-2 公钥认证模型公钥认证模型 114.2 RSA密码体制密码体制vRSA密码体制是密码体制是1977年由年由Rivest、Shamir、Adleman提出的非常著名的公钥密码算法。提出的非常著名的公钥密码算法。vRSA算法的安全性基于：求两个大素数的乘积是算法的安全性基于：求两个
12、大素数的乘积是容易的，但分解两个大素数的乘积，求出其素因容易的，但分解两个大素数的乘积，求出其素因子则是困难的，它属于子则是困难的，它属于NP完全类问题，至今没完全类问题，至今没有有效的算法。有有效的算法。vRSA算法是一种分组密码，明文和密文是算法是一种分组密码，明文和密文是0到到n-1之间的整数，通常之间的整数，通常n的大小为的大小为1024位二进制数或位二进制数或309位十进制数。位十进制数。121、密钥的产生、密钥的产生v（1）随机选择两个大素数（如）随机选择两个大素数（如100位十进制数）位十进制数）p和和q，令，令n=pq；v（2）计算欧拉函数（见定理）计算欧拉函数（见定理） (n
13、)=n(1-1/p)( 1-1/q)=(p -1)(q -1) ；v（3）选择）选择 e使得使得1e (n)，且，且gcd(e, (n)=1；v（4）计算）计算d ed1 mod (n)， 且且 0dnv（5）公开公钥：）公开公钥：PU=e, n；v（6）保存私钥：）保存私钥：PR=d, p, q。132、加密过程、加密过程v（1）在公钥库中查得用户）在公钥库中查得用户U的公钥：的公钥：PU=e, n；v（2）将明文分组）将明文分组m=m1m2mr，使得，使得0min，i=1，2， ，r；v（3）对明文分组）对明文分组mi作加密变换：作加密变换： ci=E(mi) mie mod n， i=1
14、，2， ，rv（4）将密文）将密文c1 c2cr传送给用户传送给用户U。3、解密过程、解密过程v（1）先对每组密文做解密变换：）先对每组密文做解密变换： mi=D(ci) cid mod n v（2）合并分组得到明文）合并分组得到明文m=m1m2mr。14图图4-3 RSA算法算法15【例例4-1】选择素数：选择素数： p=47 和和 q=71，并选取，并选取e=79，求出，求出RSA算法的公钥和私钥。算法的公钥和私钥。【解解】：v（1）计算：）计算：n= pq =4771=3337， (n)=(p-1)(q-1)=4670=3220。v（2）选择）选择e：使：使gcd(e, 3220)=1，
15、选取，选取e=79；v（3）求解）求解d：de1 mod 3220， 即即 79d1 mod 3220辗转除法：辗转除法： 3220=4079+6079=160+1960=319+319=63+116回代：回代：1 =19-63 =19-6（60-319）=1919-660 =19(79-160)-660=1979-2560 =1979-25(3220-4079) =101979-253220两边同时对模两边同时对模3220进行求余运算得进行求余运算得1019791 mod 3220于是于是d =1019v（4）公开公钥）公开公钥PU =e, n = 79，3337 保存私钥保存私钥PR =d
16、, p, q = 1019，47，71；17v（5）假设消息为）假设消息为 m = 6882326879666683，进行，进行分组，分组的位数比分组，分组的位数比N要小，我们选取要小，我们选取m1 = 688，m2 = 232，m3 = 687，m4 = 966，m5 =668，m6 =003。加密变换加密变换：ci=E(mi) mie mod N，即，即m1的密文的密文为为c1 68879 mod 3337 1570 mod 3337 ， c1 = 1570，依次进行类似计算。可得到最终密文为：，依次进行类似计算。可得到最终密文为： c =1570 2756 2091 2276 158解密
17、变换解密变换：mi=D(ci) cid mod N，即，即c1 的明文的明文m1 15701019 mod 3337 688 mod 3337 ， m1 = 688，依次可以求出其他明文。最后恢复明文，依次可以求出其他明文。最后恢复明文为：为：m = 688 232 687 966 668 318vRSA密码体制的特点密码体制的特点（1）运算速度慢）运算速度慢由于进行的都是大数计算，使得由于进行的都是大数计算，使得RSA最快的最快的情况也比情况也比DES慢上慢上100倍，一般来说适用于倍，一般来说适用于少量数据的加密。少量数据的加密。（2）产生密钥烦琐）产生密钥烦琐产生密钥很麻烦，受到素数产生
18、技术的限制。产生密钥很麻烦，受到素数产生技术的限制。194.2.2 RSA算法的安全性算法的安全性 vRSA体制的安全性是基于大数的因子分解问题，体制的安全性是基于大数的因子分解问题，大数的因子分解在数学上是一个难解问题，即无大数的因子分解在数学上是一个难解问题，即无法从公钥参数法从公钥参数n中计算出素数因子（大于中计算出素数因子（大于100个十个十进制位）进制位）p和和q，于是无法计算出，于是无法计算出 (n) =(p-1)(q-1)，也就无法计算出私钥，也就无法计算出私钥d，从而保证非法者不能，从而保证非法者不能对密文进行解密。对密文进行解密。20vRSA的安全性依赖于大数分解困难，即从一
19、个密钥的安全性依赖于大数分解困难，即从一个密钥和密文推断出明文的难度等同于分解两个大素数的和密文推断出明文的难度等同于分解两个大素数的积。显然，分解积。显然，分解n是最常遇到的攻击方法。在算法中是最常遇到的攻击方法。在算法中要求要求p和和q均大于均大于100位十进制数，这样的话位十进制数，这样的话n至少至少200位十进制数，目前人们已能分解位十进制数，目前人们已能分解140多位的十进多位的十进制数的大素数。制数的大素数。 v最新记录是最新记录是129位十进制数的因数分解，在网络通过位十进制数的因数分解，在网络通过分布计算被成功分解。估计对分布计算被成功分解。估计对200位十进制数的因数位十进制
20、数的因数分解，在亿次计算机上也要进行分解，在亿次计算机上也要进行55万年。万年。214.3 EIGamal密码体制密码体制v该体制是该体制是1985年由年由EIGamal提出的一个著名的公提出的一个著名的公钥密码算法。该算法既能用于数据加密也能用于钥密码算法。该算法既能用于数据加密也能用于数字签名，其安全性依赖于离散对数这一难题。数字签名，其安全性依赖于离散对数这一难题。【离散对数问题：设【离散对数问题：设g，x，p是正整数。已知是正整数。已知g，x和和p，可以容易地求出，可以容易地求出y，使得：，使得：ygx(mod p)反之，如果已知反之，如果已知y，g和和p，求，求x，这就是离散对数，这
21、就是离散对数问题，属问题，属NP完全类问题，是难解的。】完全类问题，是难解的。】22 1. 密钥产生密钥产生v（1）任选一个大素数）任选一个大素数p（300位十进制数），使位十进制数），使得得p-1有大素因子，有大素因子，g是模是模p的一个本原根（即的一个本原根（即g是是0，1，2，p-1中与中与p互素的数），公开互素的数），公开p与与g；v（2）任选一私钥）任选一私钥x，x0, p-1；v（3）计算）计算y g x (mod p)；v（4）公开公钥：）公开公钥：y；v（5）保密私钥：）保密私钥：x；23 2. 加密过程加密过程v（1）在公钥库中查得用户）在公钥库中查得用户U的公开密钥：的公开
22、密钥：y；v（2）对于明文）对于明文m，随机选取一个整数，随机选取一个整数r，r0, p-1v（3）计算）计算 c1 gr (mod p) c2 myr (mod p)v（4）将（）将（c1，c2）作为密文发给用户）作为密文发给用户U.。 3. 解密过程解密过程（1）先计算）先计算 w (c1x)-1 (mod p)（2）再计算出明文）再计算出明文 m c2w(mod p)【因为【因为w (c1x)-1 (mod p) - wc1x 1(mod p)-w (gr)x 1(mod p)- w (gx) r 1(mod p) - wyr1(mod p) - wmyrm(mod p) -wc2 m
23、(mod p) - m c2w(mod p)】24v与与RSA方法比较，方法比较，ElGamal方法具有以下优点：方法具有以下优点：（1）系统不需要保存秘密参数，所有的系统参）系统不需要保存秘密参数，所有的系统参数均可公开；数均可公开；（2）密文依赖于加密过程所选择的随机数）密文依赖于加密过程所选择的随机数r，加，加密相同的明文可能会产生不同的密文；密相同的明文可能会产生不同的密文；（3）ElGamal方法的计算复杂度比方法的计算复杂度比RSA方法要方法要大。大。25【例【例4-2】假设假设Alice想要加密消息想要加密消息m=1299后传送给后传送给Bob。（1）密钥产生）密钥产生vAlic
24、e任选一个大素数任选一个大素数p为为2579，g是模是模p的一个本原的一个本原根，取根，取g为为2，公开参数，公开参数p，g。v任选私钥任选私钥x为为765，计算公钥计算公钥y g x (mod p) 2765(mod 2579) 949 (mod 2579)，v公开：公开：PU=949，保密：，保密：PR=765。26（2）加密）加密vAlice在在0, p-1= 0, 2578内任选内任选r为为853，v计算：计算：c1 gr (mod p) 2853 (mod 2579) 435(mod 2579)c2 myr (mod p) 1299*949853 (mod 2579) 2396(mo
25、d 2579)vAlice将（将（c1，c2）=（435，2396）作为密文发给）作为密文发给Bob。（3）解密）解密vBob计算：计算：m c2w(mod p)c2*(c1x)-1 (mod p)(c2*c1p-1-x ) (mod p) (2396*4352579-1-765) (mod 2579) (2396*4351813) (mod 2579) 1299 (mod 2579)274.4 背包密码体制背包密码体制v背包密码体制是背包密码体制是1978年由年由Merkle（默克尔）和（默克尔）和Hellman（赫尔曼）基于求解背包问题的困难性提（赫尔曼）基于求解背包问题的困难性提出的一个
26、公开密钥体制。出的一个公开密钥体制。v我们第二章曾经讲过背包问题是一个我们第二章曾经讲过背包问题是一个NP完全类问题。完全类问题。但不是所有的背包问题都是难解的，超递增背包序但不是所有的背包问题都是难解的，超递增背包序列就很容易求解。列就很容易求解。v定义定义4.3.1 正整数序列正整数序列a1，a2，an称为超递增的，称为超递增的，若对于任意（若对于任意（1 n-1），有），有 例如（例如（1，2，4，8，16）就是一个超递增序列。）就是一个超递增序列。28v定理定理4.3.1 由超递增序列由超递增序列a1，a2，an及及k确定确定的超递增背包问题是容易求解的。（即对于背包的超递增背包问题是
27、容易求解的。（即对于背包问题：问题：其中已知超递增序列其中已知超递增序列a1，a2，an及及k，容易求，容易求出出X=(x1,x2,xn)）29 1. 密钥产生密钥产生v（1）随机选取一个超递增序列（）随机选取一个超递增序列（e1，e2，en），），作为用户的私钥加以保存，记为作为用户的私钥加以保存，记为PR；v（2）选取一对大的互素的数）选取一对大的互素的数w和和N，把序列（，把序列（e1，e2，en）变换为：）变换为： T(ei) wei (mod N) 即做即做MH变换，将一个超递增序列转换为一个普通变换，将一个超递增序列转换为一个普通序列后作为公钥，记为序列后作为公钥，记为PU；v（3
28、）将公钥）将公钥PU =（T(e1)，T(e2)，T(en)）加）加以公布。以公布。30 2. 加密过程加密过程v（1）在公钥库中查出用户）在公钥库中查出用户U的公钥：的公钥：PU=（T(e1)，T(e2)，T(en)）v（2）将明文表示成）将明文表示成n位长的位长的0/1字符序列，即字符序列，即 m=m1m2mn，mi=0/1；v（3）对明文做加密变换：）对明文做加密变换： c=E(m)=m1T(e1)+ m2T(e2)+ mnT(en) = v（4）将密文）将密文c发给用户发给用户U。31 3. 解密过程解密过程v（1）计算）计算c w-1c (mod N)；v（2）按超递增序列（）按超递
29、增序列（e1，e2，en）从）从c中还原中还原mi（相当于求解特殊的背包问题）；（相当于求解特殊的背包问题）；v（3）得到明文）得到明文m=m1m2mn。32【以下说明如何按超递增序列（【以下说明如何按超递增序列（e1，e2，en）从）从c中还原中还原mi？因为因为c=E(m)=m1T(e1)+ m2T(e2)+ nT(en)= ,而而T(ei) wei (mod N)所以所以c , cw-1 于是于是 c 由已知由已知w和和N互素，则有互素，则有ww-11 (mod N)，因此因此 c 其中，已知其中，已知c和和ei，求，求mi，即按超递增序列（，即按超递增序列（e1，e2，en）从）从c中
30、还原中还原mi，就变成求解特殊的背包问题，是容易求，就变成求解特殊的背包问题，是容易求解的，因此解密是容易进行的。】解的，因此解密是容易进行的。】33关于背包密码体制的安全问题说明如下。关于背包密码体制的安全问题说明如下。v由于，由于，c= 是个是个普通背包问题普通背包问题，由公开信息，由公开信息c和和T(ei)求出明文求出明文是难解问题，所以是难解问题，所以破译是困难的破译是困难的。v而解密时，是按超递增序列（而解密时，是按超递增序列（e1，e2，en）从）从c中还原中还原mi，即由私钥，即由私钥ei和和c求解超递增背包问题求解超递增背包问题c ，这是个，这是个易解问题易解问题，因此，因此解
31、解密容易进行密容易进行。vMerkle和和Hellman的背包密码体制提出后，悬赏以的背包密码体制提出后，悬赏以求破译者，两年后被求破译者，两年后被RSA的发明者之一沙米尔攻破。的发明者之一沙米尔攻破。尽管二人又做了改进，但最终出现了一种新的破译尽管二人又做了改进，但最终出现了一种新的破译方法，彻底结束了背包公钥密码体制的历史使命。方法，彻底结束了背包公钥密码体制的历史使命。344.5 本章总结本章总结（1）公开密钥密码体制的基本概念；）公开密钥密码体制的基本概念；（2）RSA的密钥产生、加密及解密过程；的密钥产生、加密及解密过程；（3）背包体制的密钥产生、加密及解密）背包体制的密钥产生、加密及解密过程；过程；（4）ELGamal体制的密钥产生、加密及体制的密钥产生、加密及解密过程；解密过程；v课堂练习：课堂练习：如果如果选择素数选择素数 p=101 和和 q=113，选取，选取e=3533，计算，计算RSA的公钥和私钥。的公钥和私钥。35
