lecture03-公钥加密与hash函数

1、1公钥加密与公钥加密与Hash函数函数王丽苹王丽苹华东师范大学软件学院华东师范大学软件学院2022年年7月月4日日2outlinen公钥密码体制的基本原理（公钥密码体制的基本原理（Chapter6）nRSA算法的简介（算法的简介（Chapter6）n消息认证和消息认证和hash函数（函数（Chapter8）3公钥密码体制的基本原理公钥密码体制的基本原理n对称密钥算法的不足对称密钥算法的不足（1）密钥管理量的困难：传统密钥管理：两两分别用一密钥管理量的困难：传统密钥管理：两两分别用一个密钥，则个密钥，则n个用户需要个用户需要c（n,2) =n(n-1)/2个密钥，个密钥，当用户量增大时，密钥空间

2、急剧增大。如：当用户量增大时，密钥空间急剧增大。如： n = 100 时，时， c（100，2）= 4.995 n = 5000时，时，c（5000，2）=12，497，500（2）密钥必须通过某一信道协商，对这个信道的安全性密钥必须通过某一信道协商，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高的要求比正常的传送消息的信道的安全性要高（3）数字签名的问题：传统加密算法无法实现抗抵赖的数字签名的问题：传统加密算法无法实现抗抵赖的要求。要求。4公钥密码体制的基本原理公钥密码体制的基本原理n起源：起源：n公钥密码又称为双钥密码和非对称密码，是公钥密码又称为双钥密码和非对称密码，是197

3、6年由Diffie和Hellman在其“密码学新方向”文中提出的，见划时代的文献：nW.Diffie and M.E.Hellman, New Directrions inCryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654nRSA公钥算法公钥算法是由Rivest,Shamir和Adleman在1978年提出来的，见n1978 Communitions of the ACM. Vol.21.No.2.5公钥密码体制的基本原理公钥密码体制的基本原理n公钥密码体制的重要特性：

4、公钥密码体制的重要特性：n加密与解密由不同的密钥完成加密与解密由不同的密钥完成:n加密加密: X-Y:Y=EKU(X) /KU为公钥，为公钥，KR为私钥为私钥n解密解密: Y-X:X=DKR(Y)=DKR(EKU(X) n知道加密算法知道加密算法,从加密密钥得到解密密钥在计算从加密密钥得到解密密钥在计算上是不可行的上是不可行的n两个密钥中任何一个都可以用作加密而另一个两个密钥中任何一个都可以用作加密而另一个用作解密用作解密nX=DKR(EKU(X)=EKU(DKR(X)6公钥密码体制的加密过程公钥密码体制的加密过程7公钥密码体制的加密过程公钥密码体制的加密过程n用公钥密码实现保密用公钥密码实现

5、保密n用户拥有自己的密钥对用户拥有自己的密钥对(KU,KR)n公钥公钥KU公开公开,私钥私钥KR保密保密.nA-B:Y=E KUb(X).nB: DKRb(Y)=DKRb(EKUb(X)=X8公钥密码体制的认证过程公钥密码体制的认证过程9公钥密码体制的认证过程公钥密码体制的认证过程n用公钥密码实现鉴别用公钥密码实现鉴别n条件条件:两个密钥中任何一个都可以用作加密而另两个密钥中任何一个都可以用作加密而另一个用作解密一个用作解密n鉴别鉴别:nA-ALL:Y=D KRa(X)nALL: EKUa(Y) = EKUa(DKRa(X) = X.n鉴别鉴别+保密保密:nA-B: Z = EKUb(DKRa

6、(X)nB: EKUa(DKRb(Z) = X10思考思考n如何通过互联网进行可靠的邮件传输？如何通过互联网进行可靠的邮件传输？n假设甲要寄信给乙，他们互相知道对方的公钥。假设甲要寄信给乙，他们互相知道对方的公钥。n甲就用乙的公钥加密邮件寄出，乙收到后就可以用自己的私钥甲就用乙的公钥加密邮件寄出，乙收到后就可以用自己的私钥解密出甲的原文。由于别人不知道乙的私钥，所以即使是甲本解密出甲的原文。由于别人不知道乙的私钥，所以即使是甲本人也无法解密那封信，这就解决了信件保密的问题。人也无法解密那封信，这就解决了信件保密的问题。 n由于每个人都知道乙的公钥，他们都可以给乙发信，那由于每个人都知道乙的公钥

7、，他们都可以给乙发信，那么乙怎么确信是不是甲的来信呢？么乙怎么确信是不是甲的来信呢？n需要用到基于加密技术的数字签名。需要用到基于加密技术的数字签名。过程：过程：甲用自己的私钥将签名内容加密，附加在邮件后，再用甲用自己的私钥将签名内容加密，附加在邮件后，再用乙的公钥将整个邮件加密（注意这里的次序，如果先加密再签乙的公钥将整个邮件加密（注意这里的次序，如果先加密再签名的话，别人可以将签名去掉后签上自己的签名，从而篡改了名的话，别人可以将签名去掉后签上自己的签名，从而篡改了签名）。这样这份密文被乙收到以后，乙用自己的私钥将邮件签名）。这样这份密文被乙收到以后，乙用自己的私钥将邮件解密，得到甲的原文

8、和数字签名，然后用甲的公钥解密签名，解密，得到甲的原文和数字签名，然后用甲的公钥解密签名，这样一来就可以确保两方面的安全了。这样一来就可以确保两方面的安全了。11公钥密钥的应用范围公钥密钥的应用范围n加密加密/解密解密n数字签名（身份鉴别）数字签名（身份鉴别）n密钥交换密钥交换12outlinen公钥密码体制的基本原理（公钥密码体制的基本原理（Chapter9）nRSA算法的简介（算法的简介（Chapter9）n消息认证和消息认证和hash函数（函数（Chapter11）13RSA算法简介算法简介nRAS算法是由算法是由Rivest, Shamir和和Adleman在在1978年提出来的。年提

9、出来的。n是一种分组加密算法：是一种分组加密算法：n分组的大小可以变，但是不能够超过密钥的长度。分组的大小可以变，但是不能够超过密钥的长度。n应用最广泛的公钥算法应用最广泛的公钥算法n在美国申请专利，且已于在美国申请专利，且已于2000年年9月到期。月到期。14RSA算法描述算法描述Key GenerationSelect p, q p and q both prime, p !=qCalculate n = p * qCalculate (n) = (p 1)(q 1)Select integer e gcd(n), e) = 1; 1 e (n) Calculate d d = e-1 m

10、od (n) 等价于等价于 de = 1 mod (n)Public key KU = e, nPrivate key KR = d, nEncryptionPlaintext: M nCiphertext: C = Me (mod n)DecryptionCiphertext: CPlaintext: M = Cd (mod n)15RSA算法描述算法描述nRSA体制是一种分组密码，明文需要按照体制是一种分组密码，明文需要按照分组来加密。分组来加密。n其明文和密文都是其明文和密文都是0至至n-1之间的整数。之间的整数。n通常通常n的大小为的大小为1029位的二进制位或者位的二进制位或者309

11、位位十进制位。十进制位。16RSA算法算法Examplen1.选择素数选择素数:p=17&q=11（保密）（保密）n2.计算计算n=pq=1711=187n3.计算计算(n)=(p1)(q-1)=1610=160n4.选择选择e使其与使其与(n)互素且小于互素且小于(n): gcd(e,160)=1; 选选择择e=7n5.确定确定 d: de = 1 mod 160 and d160，d=23因为因为237=161=1160+1（保密）（保密）n6.公钥公钥 KU=7,187n7.私钥私钥 KR=23,17,11（保密）（保密）17RSA实现中的问题实现中的问题n（1）如何计算）如何计

12、算ab mod nn中间结果非常大中间结果非常大n幂运算的效率幂运算的效率n（2）密钥产生）密钥产生n如何找到足够大的素数如何找到足够大的素数p和和q?n选择选择e或或d计算另外一个计算另外一个18对对RSA算法的攻击算法的攻击n(1) 强力攻击（穷举法）：尝试所有可能的强力攻击（穷举法）：尝试所有可能的私有密钥私有密钥n(2)数学分析攻击：各种数学方法，等价与数学分析攻击：各种数学方法，等价与两个素数乘积的因子分解两个素数乘积的因子分解n(3) 对对RSA实现的攻击实现的攻击19加密算法小结加密算法小结n对称密码算法对称密码算法n运算速度快、密钥短、多种用途（随机数产生、运算速度快、密钥短、

13、多种用途（随机数产生、Hash函数）、历史悠久函数）、历史悠久n密钥管理困难（分发、更换）密钥管理困难（分发、更换）n对称的，通信方是平等的（不能为发送者提供保护）对称的，通信方是平等的（不能为发送者提供保护）.n非对称密码算法非对称密码算法n只需保管私钥、可以相当长的时间保持不变、需要的数只需保管私钥、可以相当长的时间保持不变、需要的数目较小目较小n运算速度慢、密钥尺寸大、历史短运算速度慢、密钥尺寸大、历史短n非对称的，通信方是不平等的，因为加密消息和验证签非对称的，通信方是不平等的，因为加密消息和验证签名的人不能解密同一信息和产生同样的签名名的人不能解密同一信息和产生同样的签名20加密算法

14、小结加密算法小结n公钥算法加密解密速度慢，对称密钥技术公钥算法加密解密速度慢，对称密钥技术速度比较快，所以经常使用公钥算法加密速度比较快，所以经常使用公钥算法加密少量的数据如签名、身份验证信息等，而少量的数据如签名、身份验证信息等，而对称密钥算法用来加密大批量的数据。对称密钥算法用来加密大批量的数据。n误区误区:n公开密钥密码算法更安全（公开密钥密码算法更安全（error）n公开密钥密码使对称密钥密码过时了（公开密钥密码使对称密钥密码过时了（error）n公钥的分发是简单和一目了然的（公钥的分发是简单和一目了然的（error）21outlinen公钥密码体制的基本原理（公钥密码体制的基本原理（

15、Chapter9）nRSA算法的简介（算法的简介（Chapter9）n消息认证和消息认证和hash函数简介（函数简介（Chapter11）n消息认证消息认证nHash函数函数22基本的概念基本的概念n消息认证（消息认证（Message Authentication)：是一个证实收到的消息来自可信的源点且是一个证实收到的消息来自可信的源点且未被篡改的过程。未被篡改的过程。n 散列函数（散列函数（ Hash Functions)：一个散列一个散列函数以一个变长的报文作为输入，并产生函数以一个变长的报文作为输入，并产生一个定长的散列码，有时也称报文摘要，一个定长的散列码，有时也称报文摘要，作为输出。

16、作为输出。n数字签名（数字签名（Digital Signature）是一种防是一种防止源点或终点抵赖的鉴别技术。止源点或终点抵赖的鉴别技术。23消息认证消息认证n认证的主要目的有两个方面：认证的主要目的有两个方面：n第一，验证信息的发送者是真正的，而不是冒充的，此第一，验证信息的发送者是真正的，而不是冒充的，此为信源识别；为信源识别；n第二，验证信息的完整性，在传送或存储过程中未被篡第二，验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等。改，重放或延迟等。n认证模型认证模型n一个单纯认证系统的模型一个单纯认证系统的模型24消息认证消息认证n消息认证系统组成：消息认证系统组成：n首先要

17、选好恰当的首先要选好恰当的认证函数认证函数，该函数产生一个鉴别标识，该函数产生一个鉴别标识，然后在此基础上，给出合理的认证协议然后在此基础上，给出合理的认证协议(Authentication Protocol)，使接收者完成消息的鉴别。，使接收者完成消息的鉴别。n认证函数：认证函数：可用来做认证的函数分为三类：可用来做认证的函数分为三类：n(1) 消息加密函数消息加密函数(Message encryption)用完整信息的用完整信息的密文作为对信息的认证。密文作为对信息的认证。n(2) 消息认证码消息认证码MAC(Message Authentication Code)公开函数公开函数+密钥产

18、生一个固定长度的值作为认证标识密钥产生一个固定长度的值作为认证标识n(3) 散列函数散列函数(Hash Function)是一个公开的函数，它将是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。任意长的信息映射成一个固定长度的信息。25Message Authentication Coden使用一个双方共享的秘密密钥生成一个固定大小的使用一个双方共享的秘密密钥生成一个固定大小的小数据块，并加入到消息中，称小数据块，并加入到消息中，称MAC，或密码校，或密码校验和验和(cryptographic checksum)n用户用户A和用户和用户B，共享密钥，共享密钥K，对于，对于消息消息M，

19、 MAC=CK(M)n如果接收方计算的如果接收方计算的MAC与收到的与收到的MAC匹配，则匹配，则n接收者可以确信消息接收者可以确信消息M未被改变未被改变n接收者可以确信消息来自所声称的发送者接收者可以确信消息来自所声称的发送者n如果消息中含有序列号，则可以保证正确的消息顺序如果消息中含有序列号，则可以保证正确的消息顺序nMAC函数类似于加密函数，但不需要可逆性。因函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少此在数学上比加密算法被攻击的弱点要少26MAC的基本用法的基本用法(a，b)nAB: M | CK(M)提供认证但不能提供保密性提供认证但不能提供保密性nAB

20、: EK2 M | CK1(M) 提供认证和保密性，提供认证和保密性，加密算法在加密算法在MAC之后之后27MAC的基本用法的基本用法(c)nAB: EK2 M | CK1(EK2 M)n提供认证和保密性，加密算法在提供认证和保密性，加密算法在MAC之前之前28讨论：讨论：n对称加密可以提供认证为什么还要使用分离对称加密可以提供认证为什么还要使用分离的消息认证？的消息认证？n后者适用于将同一消息广播给很多接受者。后者适用于将同一消息广播给很多接受者。n消息通信过程中，接受方负荷很大，没有时间消息通信过程中，接受方负荷很大，没有时间解密收到的消息，可以随机的选择性的对消息解密收到的消息，可以随机

21、的选择性的对消息认证。认证。n对明文形式的计算机程序进行认证是一种很有对明文形式的计算机程序进行认证是一种很有意义的服务。有些应用关心的是消息的认证而意义的服务。有些应用关心的是消息的认证而不是保密性。不是保密性。n认证和保密性分离开，可使层次结构更加灵活。认证和保密性分离开，可使层次结构更加灵活。n可以延长对消息的保护时间。可以延长对消息的保护时间。29Hash FunctionnMAC需要对全部数据进行加密需要对全部数据进行加密nMAC速度慢速度慢nHash是一种直接产生认证码的方法是一种直接产生认证码的方法nHash函数函数: h=H(x), 要求要求:n可作用于任何尺寸数据且均产生定长

22、输出可作用于任何尺寸数据且均产生定长输出nH(x)能够快速计算能够快速计算n单向性单向性: 给定给定h，找到，找到x使使h=H(x)在计算上不可行在计算上不可行nWeak Collision Resistance (WCR):给定给定x，找到，找到y x使使H(x)=H(y)在在计算上不可行计算上不可行nStrong Collision Resistance (SCR): 找到找到y x使使H(x)=H(y)在在计算上不可行计算上不可行30散列函数的基本用法（散列函数的基本用法（a、b)31散列函数的基本用法（散列函数的基本用法（c)n用公钥密码中发送方的私钥仅对用公钥密码中发送方的私钥仅对Hash码加密：可码加密：可认证，并提供数字签名功能认证，并提供数字签名功能32散列函数的基本用法（散列函数的基本用法（d)n保密加签名：发送方的私钥对保密加签名：发送方的私钥对Hash码加密（签码加密（签名），再用对称密码中的密钥对整体加密（保密性）名），再用对称密码中的密钥对整体加密（保密性）33