第6章 公钥密码体制

1第6章公钥密码体制信息工程学院景旭[e-mail]2本讲主要内容•公钥密码的概念、特点和应用范围。•RSA算法加、解密过程。•其它公钥算法简介。•教学要求：原理要清楚，数论不深究。3对称密钥面临的困题•密钥分配:通信密钥太多，管理和分发困难。–传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:–n=100时，C(100,2)=4,995–n=5000时，C(5000,2)=12,497,500•数字签名和认证–传统加密算法无法实现抗抵赖的需求4密码体制上的突破•Diffie&Hellman,密码学新方向(NewDirectioninCryptography),1976。•首次公开提出了“公开密钥密码编码学”的概念。•这是一个与对称密码编码截然不同的方案：–公钥算法是基于数学函数；传统对称密码算法基于替换和置换。–公钥密码学是非对称的，它使用两个独立的密钥；传统对称密码使用一个密钥。5公钥密码的定义（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）就是单向陷门函数，公钥密码就是基于这一原理设计的，将辅助信息（陷门信息）作为秘密密钥。6公钥密码的定义（2）•当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为KU。f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密钥匙，记为KR。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有KR，他自然可以解出x=f-1(y)。•单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。7公钥算法基本特征•一对（两个）密钥：–使用一个密钥进行加密，用另一个相关的密钥进行解密•用加密密钥生成的密文只有使用其对应的解密密钥才能解密。–两个密钥的关系满足：•两个密钥是不相同；•在仅知道密码算法和加密密钥的情况下，要推断解密密钥在计算上是不可行的。•两个密钥中的任何一个都可以用来加密，另一个用来解密。（如RSA）8公钥密码体制优点•密钥管理–加密密钥是公开的；–解密密钥需要妥善保存；–在当今具有用户量大、消息发送方与接收方具有明显的信息不对称特点的应用环境中表现出了令人乐观的前景。•数字签名和认证–只有解密密钥能解密，只有正确的接收者才拥有解密密钥。9公钥密码组成•明文：算法的输入。可读信息或数据。•加密算法：对明文进行各种转换。•公钥和私钥：算法的输入。一个用于加密，一个用于解密。算法执行的变换依赖于公钥和私钥。•密文：算法的输出。依赖于明文和密钥，对于给定的消息，不同的密钥产生不同明文。•解密算法：接收密文和相应的密钥，并产生原始的明文。10公钥密码加密/解密模型对称密码通信模型11公钥密码/加解过程•每一用户产生一对密钥，用来加密和解密消息。•用户将其中一个密钥存于公开的寄存器或其他可访问的文件中，该密钥称为公钥，另一个密钥是私有的，称为私钥。用户可以拥有若干其他用户的公钥•若Bob要发消息给Alice，则Bob用Alice的公钥对消息加密。•Alice收到消息后，用其私钥对消息进行解密。由于只有Alice知道其自身的私钥，所以其他接收者均不能解密出消息。•在公钥密码中，通信各方均可以访问公钥，而私钥是各通信方在本地产生的，不进行分配。只要控制了私钥，通信就是安全的。在任何时候，用户可以改变其私钥并公布相应的公钥以代替原来的公钥。12公钥密码通信保密性分析图对称密码保密性13公钥密码通信保密性分析•消息源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，从而实现了保密通信。14公钥密码认证模型15公钥密码认证过程•每一用户产生一对密钥，用来加密和解密消息。•每一个用户将其中一个密钥存于公开的寄存器或其他可访问的文件中，该密钥称为公钥，另一个密钥是私有的。每一个用户可以拥有其他若干个其他用户的公钥。•若Bob要发消息给Alice，且需要向Alice提供认证，则Bob用私钥对消息加密。•Alice收到消息后，用Bob的公钥对消息进行解密。由于只有Bob知道其自身的私钥，所以其他发送者均不能生成能用Bob公钥解密的消息。由此可以确认此消息来源于Bob。16公钥密码认证分析图17公钥密码认证分析•消息源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，因此该过程不提供保密。18公钥密码的保密与认证图19公钥密码保密与认证过程分析•对于单次加密只提供认证或保密的问题，可以采用两次运用公钥密码的方式即提供加密又提供认证：Z=EKUb[EKRa(X)]X=DKUa[DKRb(Z)]•发送方首先用其私钥对消息加密，得到数字签名，然后再用接收方的公钥加密，所得密文只有被拥有私钥的接收方解密。这样可保证消息的保密性。•缺点：在每次通信中要执行四次复杂的公钥算法。20常见公钥算法适用范围21对称密码和公钥密码比较（1）对称密码运行条件：1、加密和解密使用同一个密钥和一个算法。2、发送方和接收方必须共享密钥和算法。公钥密码运行条件：1、用同一个算法进行加密和解密，而密钥有一对，其中一个用于加密，另一个用于解密。2、发送方和接收方每个拥有一对相互匹配的密钥中的一个(不是同一个)。22对称密码和公钥密码比较（2）对称密码安全条件：1、密钥必须保密。2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。3、知道所用的算法加上密文的样本必须不足以确定密钥。公钥密码安全条件：1、两个密钥中的一个必须保密。2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。3、知道所用的算法加上一个密钥加上密文的样本必须不足以确定密钥。23公钥密码算法应满足条件假设消息源为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、椭圆密码体制24公钥密码算法(1)基于大整数因子分解的RSA算法；(2)椭圆曲线公钥算法；(3)基于因子分解问题的Rabin算法；(4)基于有限域中离散对数难题的ElGamal公钥密码算法(5)基于代数编码系统的McEliece公钥密码算法；(6)基于“子集和”难题的Merkle-HellmanKnapsack公钥密码算法；(7)目前被认为安全的Knapsack型公钥密码算法Chor-Rivest。25RSA算法简介•分组密码，安全性依赖于大数的因子分解。•第一个较为完善的公钥算法。•能够同时用于加密和数字签名，且易于理解和操作。•RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥算法之一。•目前仍然无法从理论上证明它的保密性能究竟如何，因为目前人们并没有从理论上证明破译RSA的难度与大整数分解问题的难度等价。26RSA算法描述（1）•设分组长度为l–bit，每个分组M被看作是一个l–bit的二进制值。–取某一个整数n，使对所有M，有Mn•一般，n的取值满足2ln≤2l+1。–加密算法•C=Memodn。–解密算法•M=Cdmodn=(Me)dmodn=Medmodn。–加密密钥（公开密钥）为KU={e,n}。–解密密钥（私有密钥）为KR={d,n}。27RSA算法描述（2）•要求：–{e,d,n}使对所有Mn都有：M=Medmodn–对所有Mn，Me和Cd的计算相对简单。–给定{e,n}，要推断d在计算上不可行。•问题：怎样找到满足M=Medmodn的{e,d,n}？•需要利用数论作为其数学基础。28数论术语•最大公因子：任意有限个整数的公因子中的最大一个。必然存在并且惟一，记为。•最小公倍数：任意有限个整数的公倍数中的最小一个。必然存在并且惟一，记为。•同余式：设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29欧拉函数•欧拉函数（Euler’stotientfunction）–欧拉函数φ(n)：表示小于n且与n互素的正整数的个数；–欧拉函数的性质：•对任意素数p，有φ(p)=p–1；•对任意两个素数p、q，则对n=pq有：φ(n)=φ(pq)=φ(p)φ(q)=(p–1)(q–1)30欧拉定理如a和n是互素的整数，则有：等价形式：nanmod1)(fnanmoda)+1(f31欧拉定理与RSA算法•RSA算法要求：M=Medmodn•欧拉定理推论：–有两个素数p和q,令n=pq,对任意整数k和m(0mn),有下列等式成立：m=mkφ(n)+1modn其中：φ(n)=(p-1)(q-1)。32RSA算法描述–选取足够大的两个素数p和q,令n=pq,则φ(n)=(p-1)(q-1)。–选取适当的加密密钥e和解密密钥d，使之满足。–公开n和e，保密p,q和d。–加密运算：–解密运算：)(mod1nedfnxxEekmod)(nZxnyyDdkmod)(nZy33RSA算法实现步骤密钥的产生•生成两个大素数p和q，p≠q；•计算，；•选择随机数e（即加密密钥）,使之满足,；•计算解密密钥；•公布整数n和加密密钥e，公钥KU={e，n}。•私钥KR={d，n}。qpn)1)(1()(qpnf)(0nbf))(,gcd(nef)(mod1nedf=1加密明文Mn密文C=Me(modn)解密密文C明文M=Cd(modn)34RSA算法的特殊要求（１）密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则