第4讲 公钥密码体制81364

《第4讲 公钥密码体制81364》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4讲　公钥密码体制主讲：谢昕课程主要内容公钥密码体制概述背包公钥密码RSA公钥密码椭圆曲线密码概率加密等§1　公钥密码体制概述对称密钥密码体制问题：如何在网络上安全地传送和保管密钥？无法实现抗抵赖的需求等…1976年，美国学者Diffie和Hellman发表了著名论文《密码学的新方向》，提出了建立“公开密钥密码体制”：若用户A有加密密钥PK(公开)，不同于解秘密钥SK(保密)，要求PK的公开不影响SK的安全。若B要向A保密送去明文m，可查A的公开密钥PKA，若用PKA加密得密文c，A收到密文c后，用只有A自己才掌握的解密密钥SKA对x进行解密得到明文m。

2、公开密钥密码体制是现代密码学最重要的发明离散数学尽人皆知的密钥叫做公开密钥(publickey)；只有密钥拥有者才知道的密钥：私有密钥(privatekey)这两种密钥合在一起称为密钥对；公开密钥可以解决安全分配密钥问题（不需要与保密密钥通信，所传输的只有公开密钥，它不需要保密），但对保证其真实性和完整性却非常重要。如果某一信息用公开密钥加密，则必须用私有密钥解密，这就是实现保密的方法。如果某一信息用私有密钥加密，它必须用公开密钥解密，这就是实现验证的方法。§1　公钥密码体制概述离散数学算法特点：使用一个加密算法E和一个解密算法D，它们彼此完全不同，根据已

3、选定的E和D，即使已知E的完整描述，也不可能推导出D。§1　公钥密码体制概述离散数学§1　公钥密码体制概述数字签名必须保证做到以下3点：（1）接收者能够核实发送者对报文的签名；（2）发送者事后不能抵赖对报文的签名；（3）接收者不能伪造对报文的签名。离散数学RSA是一种基于公钥密码体制的优秀加密算法，1978年由美国(MIT)的李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提的。RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数其因子分解是困难的（基于大数分解的难度）。公钥和私钥是一对大素数的函数，从一个公

4、钥和密文中恢复出明文的难度等价于分解两个大素数之积。RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。§2RSA公钥密码体制离散数学整数n的　　　　　　因子分解的　　　所需计算十进制位数　　　　　运算次数　　　　时间501.4x10103.9小时759.0x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0x1015年5001.3x10394.2x1025年（每微秒一次）§2RSA公钥密码体制离散数学RSA密钥体制的特点：（1）密钥配发十

5、分方便，用户的公开密钥可以像电话本那样公开，使用方便，每个用户只需持有一对密钥即可实现与网络中任何一个用户的保密通信。（2）RSA加密原理基于单向函数，非法接收者利用公开密钥不可能在有限时间内推算出秘密密钥。RSA在用户确认和实现数字签名方面优于现有的其他加密机制。§2RSA公钥密码体制离散数学单向函数：给定一个函数f，若对任意给定的x，计算y，使得y=f(x)是容易的；但对任意给定的y，计算x，使得f(x)=y是难解的，即计算f-1(y)是困难的。则称f为单向函数。例：f(x)=ax（x、aGF(q)）为单向函数。§2RSA公钥密码体制陷门单向函数：给

6、定一个函数f，t为f相关的参数，任意给定的x，计算y=f(x)是容易的；当t未知时，计算逆函数f-1(y)难解，而当t已知时，计算f-1(y)容易。则称为f陷门单向函数。离散数学用于构造双钥密码的单向函数：（1）多项式求根（2）离散对数（3）大整数分解（4）背包问题（5）Diffie-Hellman问题（6）二次剩余问题（7）模n的平方根问题§2RSA公钥密码体制离散数学§2.1　RSA公钥密码算法描述（1）设计密钥A、在离线方式下，先产生两个足够大的强质数p、q；B、令n=p＊q。计算欧拉函数(n)=(p-1)×(q-1)；C、选取一个与(n)互素的

7、奇数e，称e为公开指数；D、根据e×d=1mod((n))，找出d；E、舍弃p和q（但绝不能泄露），公开(n，e)，公钥；F、保密(n，d)私钥。离散数学（2）加密对于明文M，用公钥(n，e)加密可得到密文C。C=Memod(n)§2.1　RSA公钥密码算法描述（3）解密对于密文C，用私钥(n，d)解密可得到明文M。M=Cdmod(n)当定义用私钥(n，d)先进行解密后，然后用公钥(n，e)进行加密，就是数字签名。离散数学举例1：选取p=3,q=5，则n=p＊q=15，(n)=(p-1)(q-1)=8选取e=11（大于p和q的质数）；由d×11=1mo

8、d8，计算出d=3，得到公开密钥：（n，e）=（15，11）私有密