资源描述：
《第8章 公钥密码学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、公钥密码学张原西北工业大学电子信息学院内容提要公开密钥密码算法的基本思想公开密钥密码算法的数学基础一些经典算法对称算法的不足密钥管理的困难：传统密钥管理：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500密钥发布的困难：密钥必须通过某一信道协商，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高数字签名的问题传统加密算法无法实现抗抵赖的需求。对称算法的优点：速度快公钥
2、密码的起源公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见CommunitionsoftheACM.Vol.21.No.2.Feb.197
3、8,PP.120-126公开密钥密码的重要特性基于公开密钥的加密过程用公钥密码实现保密用户拥有自己的密钥对(KU,KR)公钥KU公开,私钥KR保密A?B:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X基于公开密钥的鉴别过程用公钥密码实现鉴别条件：两个密钥中任何一个都可以用作加密而另一个用作解密鉴别（不提供保密）：A?ALL:Y=DKRa(X)ALL：EKUa(Y)=EKUa(DKRa(X))=X鉴别+保密：A?B：Z=EKUb(DKRa(X))B：EKUa(DKRb(Z))=X公钥密钥的应用范围加密/解密数字签
4、名(身份鉴别)密钥交换：交换会话密钥基本要求和思想涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换思想：陷门单向函数单向陷门函数是满足下列条件的函数f：给定x，计算y=fk(x)是容易的；给定y，计算x使x=fk-1(y)是不可行的。存在k，已知k时，对给定的任何y，若相应的x存在，则计算x使
5、x=fk-1(y)是容易的。公钥密码基于的数学难题背包问题大整数分解问题（TheIntegerFactorizationProblem,RSA体制）离散对数问题有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem,ElGamal体制）定义在有限域的椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,类比的ElGamal体制）内容提要公开密钥密码算法的基本思想公开密钥密码算法的数学基础一些经典算法数的整除性设Z为全体整数的集合，若b≠0且a,b,
6、m∈Z使得a=mb,此时称b整除a。记为b
7、a,还称b为a的因数(因子)，a叫作b的倍数。如果不存在整数m,使得a=mb,则称b不能整除a或a不能被b整除，记为b
8、a。模运算给定任意一个正整数n和任意整数a，如果将n除a，则得到整数商q和整数余数r，且它们之间满足以下关系：其中是小于或等于x的最大整数。r记为：r＝amodn如果amodn=bmodn，称整数a和b模n同余，记为：a≡bmodn模运算的性质如果n
9、(a-b)，那么a≡bmodna≡bmodn隐含b≡amodna≡bmodn和b≡cmodn隐含a≡cmodn模算术运算(
10、modn)运算将所有的整数映射到{0,1,…,n-1}组成的集合，可以在该集合上进行算术运算，称为模算术，模算术有如下性质：[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)x(bmodn)]modn=(axb)modn定义：比n小的非负整数集合Zn：Zn={0,1,…,n-1}，称该集合为模n的剩余类。如果a和n互素，那么a乘以Zn中的所有元素再模n，将得到和Zn相同的集合。素数(PrimeNumbers)一个大于1的整数，如果它的正因数只有
11、1和它本身，就叫做质数（素数），否则就叫做合数。eg.2,3,5,7素数，4,6,8,9,10不是素数在数论中具有重要的地位小于200的素数有:235711131719232931374143475359616771737983899
