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