第6章公钥密码体制

InformationSecurity：Principles&Applications第6章公钥密码体制Char7pp.2本章概要公钥密码的概念、特点和应用范围。数论基础RSA算法加、解密过程。其它公钥算法简介。教学要求：原理要清楚，数论不深究。InformationSecurity：Principles&Applications6.1公钥密码的基本思想Char7pp.4密钥分配:通信密钥太多，管理和分发困难。传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500数字签名和认证传统加密算法无法实现抗抵赖的需求对称密钥面临的困题Char7pp.5密码体制上的突破Diffie&Hellman,密码学新方向(NewDirectioninCryptography),1976。首次公开提出了“公开密钥密码编码学”的概念。这是一个与对称密码编码截然不同的方案：公钥算法是基于数学函数；传统对称密码算法基于替换和置换。公钥密码学是非对称的，它使用两个独立的密钥；传统对称密码使用一个密钥。Char7pp.6公钥密码的定义（1）用抽象的观点来看，公钥密码是一种陷门单向函数。单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=f(x)是容易的；(2)给定y,计算x使x=f-1(y)是困难的。(所谓计算x=f-1(y)困难是指计算上相当复杂，已无实际意义)(3)存在δ，已知δ时,对给定的任何y，若相应的x存在，则计算x使x=f-1(y)是容易的。仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ称为陷门信息；满足（1）、（2）、（3）就是单向陷门函数，公钥密码就是基于这一原理设计的，将辅助信息（陷门信息）作为秘密密钥。Char7pp.7当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为KU。f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密钥匙，记为KR。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有KR，他自然可以解出x=f-1(y)。单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。公钥密码的定义（2）Char7pp.8一对（两个）密钥：使用一个密钥进行加密，用另一个相关的密钥进行解密用加密密钥生成的密文只有使用其对应的解密密钥才能解密。两个密钥的关系满足：两个密钥是不相同；在仅知道密码算法和加密密钥的情况下，要推断解密密钥在计算上是不可行的。两个密钥中的任何一个都可以用来加密，另一个用来解密。（如RSA）公钥算法基本特征Char7pp.9密钥管理加密密钥是公开的；解密密钥需要妥善保存；在当今具有用户量大、消息发送方与接收方具有明显的信息不对称特点的应用环境中表现出了令人乐观的前景。数字签名和认证只有解密密钥能解密，只有正确的接收者才拥有解密密钥。公钥密码体制优点Char7pp.10明文：算法的输入。可读信息或数据。加密算法：对明文进行各种转换。公钥和私钥：算法的输入。一个用于加密，一个用于解密。算法执行的变换依赖于公钥和私钥。密文：算法的输出。依赖于明文和密钥，对于给定的消息，不同的密钥产生不同明文。解密算法：接收密文和相应的密钥，并产生原始的明文。公钥密码组成Char7pp.11公钥密码加密/解密模型对称密码通信模型Char7pp.12公钥密码/加解过程每一用户产生一对密钥，用来加密和解密消息。用户将其中一个密钥存于公开的寄存器或其他可访问的文件中，该密钥称为公钥，另一个密钥是私有的，称为私钥。用户可以拥有若干其他用户的公钥若Bob要发消息给Alice，则Bob用Alice的公钥对消息加密。Alice收到消息后，用其私钥对消息进行解密。由于只有Alice知道其自身的私钥，所以其他接收者均不能解密出消息。在公钥密码中，通信各方均可以访问公钥，而私钥是各通信方在本地产生的，不进行分配。只要控制了私钥，通信就是安全的。在任何时候，用户可以改变其私钥并公布相应的公钥以代替原来的公钥。Char7pp.13公钥密码通信保密性分析图对称密码保密性Char7pp.14公钥密码通信保密性分析消息源A产生消息X=[X1,X2,…,Xm],其中X的M个元素是某个有穷字母表上的字符，A欲将消息X发送给B。B产生公钥KUb和私钥KRb，其中只有B知道KRb，而KUb则是公开的可访问的，所以A也可访问KUb。对作为输入的消息X和加密密钥KUb，A生成密文Y=[Y1,Y2,…,Yn]:Y=EKUb(X)期望的接收方因为拥有相应的私钥，所以可进行逆变换：X=DKRb(Y)攻击者可以观察到Y并且可以访问KUb，但是它不能访问KRb或者X，所以他无法知道X，从而实现了保密通信。Char7pp.15公钥密码认证模型Char7pp.16公钥密码认证过程每一用户产生一对密钥，用来加密和解密消息。每一个用户将其中一个密钥存于公开的寄存器或其他可访问的文件中，该密钥称为公钥，另一个密钥是私有的。每一个用户可以拥有其他若干个其他用户的公钥。若Bob要发消息给Alice，且需要向Alice提供认证，则Bob用私钥对消息加密。Alice收到消息后，用Bob的公钥对消息进行解密。由于只有Bob知道其自身的私钥，所以其他发送者均不能生成能用Bob公钥解密的消息。由此可以确认此消息来源于Bob。Char7pp.17公钥密码认证分析图Char7pp.18公钥密码认证分析消息源A产生消息X=[X1,X2,…,Xm],其中X的M个元素是某个有穷字母表上的字符，A欲将消息X发送给B。A产生公钥KUa和私钥KRa，其中只有A知道KRa，而KUa则是公开的可访问的，所以B也可访问KUa。A向B发送消息前，先用A的私钥对消息加密，B则用A的公钥对消息解密。由于是用A的私钥对消息加密，所以只有A可加密消息，因此，整个加密后的消息就是数字签名。除此之外只有拥有A的私钥才能产生上述加密后的消息，因此该消息可用于认证源与数据完整性。作为任何第三方只要都可以很容易的收到认证消息Y，因此该过程不提供保密。Char7pp.19公钥密码的保密与认证图Char7pp.20公钥密码保密与认证过程分析对于单次加密只提供认证或保密的问题，可以采用两次运用公钥密码的方式即提供加密又提供认证：Z=EKUb[EKRa(X)]X=DKUa[DKRb(Z)]发送方首先用其私钥对消息加密，得到数字签名，然后再用接收方的公钥加密，所得密文只有被拥有私钥的接收方解密。这样可保证消息的保密性。缺点：在每次通信中要执行四次复杂的公钥算法。Char7pp.21常见公钥算法适用范围Char7pp.22对称密码和公钥密码比较（1）对称密码运行条件：1、加密和解密使用同一个密钥和一个算法。2、发送方和接收方必须共享密钥和算法。公钥密码运行条件：1、用同一个算法进行加密和解密，而密钥有一对，其中一个用于加密，另一个用于解密。2、发送方和接收方每个拥有一对相互匹配的密钥中的一个(不是同一个)。Char7pp.23对称密码和公钥密码比较（2）对称密码安全条件：1、密钥必须保密。2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。3、知道所用的算法加上密文的样本必须不足以确定密钥。公钥密码安全条件：1、两个密钥中的一个必须保密。2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。3、知道所用的算法加上一个密钥加上密文的样本必须不足以确定密钥。Char7pp.24公钥密码的保密与认证图Char7pp.25公钥密码保密与认证过程分析对于单次加密只提供认证或保密的问题，可以采用两次运用公钥密码的方式即提供加密又提供认证：Z=EKUb[EKRa(X)]X=DKUa[DKRb(Z)]发送方首先用其私钥对消息加密，得到数字签名，然后再用接收方的公钥加密，所得密文只有被拥有私钥的接收方解密。这样可保证消息的保密性。缺点：在每次通信中要执行四次复杂的公钥算法。Char7pp.26常见公钥算法适用范围Char7pp.27对称密码和公钥密码比较（1）对称密码运行条件：1、加密和解密使用同一个密钥和一个算法。2、发送方和接收方必须共享密钥和算法。公钥密码运行条件：1、用同一个算法进行加密和解密，而密钥有一对，其中一个用于加密，另一个用于解密。2、发送方和接收方每个拥有一对相互匹配的密钥中的一个(不是同一个)。Char7pp.28对称密码和公钥密码比较（2）对称密码安全条件：1、密钥必须保密。2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。3、知道所用的算法加上密文的样本必须不足以确定密钥。公钥密码安全条件：1、两个密钥中的一个必须保密。2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。3、知道所用的算法加上一个密钥加上密文的样本必须不足以确定密钥。Char7pp.29公钥密码算法应满足条件假设消息源为A，要发送的消息为M，消息接收方为B。B的公钥KUb，私钥KRb。B产生一对密钥（公钥KUb，私钥KRb）在计算上是容易的。已知公钥KUb和要加密的消息M，发送方A产生相应的密文在计算上是容易的：C=EKUb（M）接收方B使用其私钥对接收方的密文解密以恢复明文在计算上是容易的：M=DKRb（C）=DKRb[EKUb（M）]已知公钥时，攻击者要确定私钥，在计算上是不可行的。已知公钥和密文，攻击者要恢复明文M在计算上是不可行的。加密和解密函数的顺序可以交换：M=DKUb[EKRb（M）]=EKUb[DKRb（M）]目前只有两个满足这些条件的算法：RSA、椭圆密码体制Char7pp.30(1)基于大整数因子分解的RSA算法；(2)椭圆曲线公钥算法；(3)基于因子分解问题的Rabin算法；(4)基于有限域中离散对数难题的ElGamal公钥密码算法(5)基于代数编码系统的McEliece公钥密码算法；(6)基于“子集和”难题的Merkle-HellmanKnapsack公钥密码算法；(7)目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。公钥密码算法InformationSecurity：Principles&Applications6.2数论简介Char7pp.32数论术语最大公因子：任意有限个整数的公因子中的最大一个。必然存在并且惟一，记为。最小公倍数：任意有限个整数的公倍数中的最小一个。必然存在并且惟一，记为。同余式：设n是一个正整数，如果，则称a和b模n同余，记作：，称整数n为同余模。加法逆元：设，如果存在满足，则称x是a的模n加法逆元。乘法逆元：设，如果存在满足，则称x是a的模n乘法逆元，记为a-1(modn)。naaa,,,21),,,gcd(21naaanaaa,,,21),,,(21naaalcmZba,nbnamodmod)(modnbanZanZx)(mod0naxnZanZx)(mod1naxChar7pp.33整数和模定义：设a,b,c是任意的三个整数，若满足b=ac则称a整除b,a(或c）是b的因子，b是a（或c）的倍数，记为a∣b;若a不能整除b，记为a！b.性质：（1）若b∣a,则下列各式成立(b≠0)(―b)∣a,b∣(―a),(―b)∣(―a),∣b∣┃∣a∣（2）若c∣b且b∣a(c≠0,b≠0),则c∣a（3）若b∣a(b≠0),则b∣ac（4）若b∣a且b∣c(b≠0),则b∣(a±c)（5）若a∣b且b∣a(a≠0,b≠0),则a=±bChar7pp.34定理6.2.1设a,b是两个整数，b≥1，则存在唯一确定的整数q、r使满足a=bq+r；其中0≤