《信息安全技术五讲公钥密码体制》由会员分享，可在线阅读，更多相关《信息安全技术五讲公钥密码体制（40页珍藏版）》请在金锄头文库上搜索。
1、信 息 安 全 技 术 万 涛 华东交通大学信息工程学院 E-mail:wantao217 Tel:13807097997 QQ:471387802 第5讲 公钥密码体制 5.1 概述 5.2 RSA公钥密码 5.3 其他公钥密码体制 5.4 相关补充 对称密钥密码体制问题：如何在网络上安全地传送和保管密对称密钥密码体制问题：如何在网络上安全地传送和保管密 钥？无法实现抗抵赖的需求等钥？无法实现抗抵赖的需求等 1976 1976年，美国学者年，美国学者DiffieDiffie和和HellmanHellman发表了著名论文发表了著名论文密码密码 学的新方向学的新方向，提出了建立，提出了建立“ “
2、公开密钥密码体制公开密钥密码体制” ”：若用户：若用户A A有有 加密密钥加密密钥PKPK（公开），不同于解秘密钥公开），不同于解秘密钥SKSK（保密），要求保密），要求PKPK 的公开不影响的公开不影响SKSK的安全。若的安全。若B B要向要向A A保密送去明文保密送去明文m m ，可查可查A A 的公开密钥的公开密钥PKPK A A ，若用若用PKPK A A 加密得密文加密得密文c c，A A收到密文收到密文c c后，用后，用 只有只有A A自己才掌握的解密密钥自己才掌握的解密密钥SKSK A A 对对x x进行解密得到明文进行解密得到明文mm。 公开密钥密码体制是现代密码学最重要的发明
3、公开密钥密码体制是现代密码学最重要的发明 5.1 5.1 概述概述 2019/11/14离散数学3 尽人皆知的密钥叫做尽人皆知的密钥叫做公开密钥公开密钥(public key)(public key)； 只有密钥拥有者才知道的密钥： 只有密钥拥有者才知道的密钥：私有密钥私有密钥(private key) (private key) ； 这两种密钥合在一起称为 这两种密钥合在一起称为密钥对密钥对； 公开密钥可以解决安全分配密钥问题（不需要与保密密钥通 公开密钥可以解决安全分配密钥问题（不需要与保密密钥通 信，所传输的只有公开密钥，它不需要保密），但对保证其信，所传输的只有公开密钥，它不需要保密）
4、，但对保证其真真 实性实性和和完整性完整性却非常重要。却非常重要。 如果某一信息用如果某一信息用公开密钥公开密钥加密，则必须用私有密钥解密，这加密，则必须用私有密钥解密，这 就是就是实现保密实现保密的方法。的方法。 如果某一信息用如果某一信息用私有密钥私有密钥加密，它必须用公开密钥解密，这加密，它必须用公开密钥解密，这 就是就是实现验证实现验证的方法。的方法。 5.1 5.1 概述概述 2019/11/14离散数学4 公开密钥密码体制算法的特点：使用一个加密算法公开密钥密码体制算法的特点：使用一个加密算法E E和一个和一个 解密算法解密算法D D，它们彼此完全不同，根据已选定的它们彼此完全不同
5、，根据已选定的E E和和D D，即使已即使已 知知E E的完整描述，也不可能推导出的完整描述，也不可能推导出D D。 公开密钥密码体制如图公开密钥密码体制如图 5.1 5.1 概述概述 加密加密解密解密 发送者发送者A A接收者接收者B B 密文密文C C明文明文P P明文明文P P B B的公钥的公钥B B的私钥的私钥 2019/11/14离散数学5 使用公开密钥加密算法进行数字签名：书信或文件是根据亲使用公开密钥加密算法进行数字签名：书信或文件是根据亲 笔签名或印章来证明其真实性的。但在计算机网络中传送的文笔签名或印章来证明其真实性的。但在计算机网络中传送的文 件又如何盖章呢？这就是数字签
6、名所要解决的问题。件又如何盖章呢？这就是数字签名所要解决的问题。 数字签名必须保证做到以下数字签名必须保证做到以下3 3点：点： （1 1）接收者能够核实发送者对报文的签名；）接收者能够核实发送者对报文的签名； （2 2）发送者事后不能抵赖对报文的签名；）发送者事后不能抵赖对报文的签名； （3 3）接收者不能伪造对报文的签名。）接收者不能伪造对报文的签名。 5.1 5.1 概述概述 2019/11/14离散数学6 数字签名的实现如图数字签名的实现如图 5.1 5.1 概述概述 签名签名验证签名验证签名 发送者发送者A A接收者接收者B B 密文密文C C明文明文P P明文明文P P A A的私
7、钥的私钥A A的公钥的公钥 2019/11/14离散数学7 RSARSA是一种基于公钥密码体制的优秀加密算法，是一种基于公钥密码体制的优秀加密算法，19781978年由美年由美 国麻省理工学院国麻省理工学院(MIT)(MIT)的研究小组成员：李维斯特的研究小组成员：李维斯特( (R Rivestivest) )、沙、沙 米尔米尔( (S Shamirhamir) )、艾德曼、艾德曼( (A Adlemandleman) )提出的。提出的。 RSARSA算法是一种分组密码体制算法，它的保密强度是建立在算法是一种分组密码体制算法，它的保密强度是建立在 具有大素数因子的合数，其因子分解是困难的（基于
8、大数分解具有大素数因子的合数，其因子分解是困难的（基于大数分解 的难度）。的难度）。 公钥和私钥是一对大素数的函数，从一个公钥和密文中恢复 公钥和私钥是一对大素数的函数，从一个公钥和密文中恢复 出明文的难度等价于分解两个大素数之积。出明文的难度等价于分解两个大素数之积。 RSARSA得到了世界上的最广泛的应用，得到了世界上的最广泛的应用，ISOISO在在19921992年颁布的国年颁布的国 际标准际标准X.509X.509中，将中，将RSARSA算法正式纳入国际标准。算法正式纳入国际标准。 5.2 RSA5.2 RSA公钥密码体制公钥密码体制 2019/11/14离散数学8 整数整数n n的十
9、进制位数的十进制位数 因子分解的运算次数因子分解的运算次数 所需计算时间所需计算时间 （每微秒一次）（每微秒一次） 50 50 1.4 1.4x10x1010 10 3.9 3.9小时小时 75 75 9.0 9.0x10x1012 12 104 104天天 100 100 2.3 2.3x10x1015 15 74 74年年 200 200 1.2 1.2x10x1023 23 3.8x10 3.8x10 9 9 年年 300 300 1.5 1.5x10x1029 29 4.0x10 4.0x1015 15年 年 500 500 1.3 1.3x10x1039 39 4.2x10 4.2x
10、1025 25年 年 5.2 RSA5.2 RSA公钥密码体制公钥密码体制 2019/11/14离散数学9 RSARSA密钥体制的特点：密钥体制的特点： （1 1）密钥配发十分方便密钥配发十分方便，用户的公开密钥可以像电话本那样，用户的公开密钥可以像电话本那样 公开，使用方便，每个用户只需持有一对密钥即可实现与网络公开，使用方便，每个用户只需持有一对密钥即可实现与网络 中任何一个用户的保密通信。中任何一个用户的保密通信。 （2 2）RSARSA加密原理基于单向函数加密原理基于单向函数，非法接收者利用公开密钥，非法接收者利用公开密钥 不可能在有限时间内推算出秘密密钥。不可能在有限时间内推算出秘密
11、密钥。 RSA RSA在在用户确认用户确认和和实现数字签名实现数字签名方面优于现有的其他加密方面优于现有的其他加密 机制。机制。 5.2 RSA5.2 RSA公钥密码体制公钥密码体制 2019/11/14离散数学10 单向函数：单向函数： 给定一个函数给定一个函数f f，若对任意给定的若对任意给定的x x，计算计算y y，使得使得y y = = f f( (x x) )是是 容易的；但对任意给定的容易的；但对任意给定的y y，计算计算x x，使得使得 f f( (x x) = ) = y y是难解的，是难解的， 即计算即计算f f - -1 1 ( (y y) )是困难的。则称是困难的。则称f
12、 f为单向函数。为单向函数。 例：例：f f( (x x) )=a=a x x （x x、a a GFGF( (q q) )）为单向函数。为单向函数。 陷门单向函数：陷门单向函数： 给定一个函数给定一个函数f f，t t为为f f 相关的参数相关的参数，任意给定的任意给定的x x，计算计算y y， 使得使得y y = = f f( (x x) )是容易的；当是容易的；当t t未知时，计算逆函数未知时，计算逆函数f f - -1 1 ( (y y) )难解，而难解，而 当当t t已知时，计算已知时，计算f f - -1 1 ( (y y) )容易。则称为容易。则称为f f 陷门单向函数。陷门单向
13、函数。 5.2 RSA5.2 RSA公钥密码体制公钥密码体制 2019/11/14离散数学11 用于构造双钥密码的单向函数：用于构造双钥密码的单向函数： （1 1）多项式求根）多项式求根 （2 2）离散对数）离散对数 （3 3）大整数分解）大整数分解 （4 4）背包问题）背包问题 （5 5）Diffie-HellmanDiffie-Hellman问题问题 （6 6）二次剩余问题）二次剩余问题 （7 7）模）模n n的平方根问题的平方根问题 5.2 RSA5.2 RSA公钥密码体制公钥密码体制 2019/11/14离散数学12 一、一、RSARSA公钥密码算法描述公钥密码算法描述 （1 1）设计
14、密钥：）设计密钥： (a) (a) 在离线方式下，先产生两个足够大的强质数在离线方式下，先产生两个足够大的强质数p p、q q； (b) (b) 令令n=pn=pq q。计算欧拉函数。计算欧拉函数 ( (n n) )=(p-1)(q-1)=(p-1)(q-1)； (c) (c) 选取一个与选取一个与 ( (n n) )互素的奇数互素的奇数e e，称，称e e为公开指数；为公开指数； (d) (d) 根据根据eded=1 =1 mod(mod( ( (n n) ) )，找出，找出d d； (e) (e) 舍弃舍弃p p和和q q （但绝不能泄露）（但绝不能泄露） ，公开，公开(n(n，e)e)，
15、公钥；，公钥； (f) (f) 保密保密(n(n，d) d) ，私钥。，私钥。 5.2 RSA5.2 RSA公钥密码体制公钥密码体制 2019/11/14离散数学13 （2 2）加密：）加密： 对于明文对于明文MM，用公钥用公钥 ( (n n，e) e) 加密可得到密文加密可得到密文C C。 。 C = M C = M e e mod (n) mod (n) （3 3）解密：解密： 对于密文对于密文C C，用私钥用私钥( (n n，d)d)解密可得到明文解密可得到明文MM。 M = M = C C d d mod (n) mod (n) 当定义用私钥当定义用私钥( (n n，d)d)先进行解密后，然后用公钥先进行解密后，然后用公钥( (n n，e)e)进行进行 加密，就是加密，就是数字签名数字签名。 5.2 RSA5.2 RSA公钥密码体制公钥密码体制 2019/11/14离散数学14 举例举例1 1：选取选取p=3, q=5p=3, q=5，则则n=n=pqpq =15 =15， ( (n n) )=(p-1)(q-1)=8=(p-1)(q-1)=8 选取选取e=11e=11（大于大于p p和和q q的质数）；的质数）； 由由d11=1 mod 8d11=1 mod 8，计算出计算出d =3d =3， 得到公开密钥：（得到公开密钥：（n n，e e）
