信息安全原理与技术ch04-公钥密码技术

信息安全原理与技术郭亚军宋建华李莉清华大学出版社2011-7-20Ch1-公钥密码技术2第4章公钥密码技术•主要知识点：--公钥密码体制--RSA密码--ElGamal密码--椭圆曲线密码--公钥分配--利用公钥密码分配对称密钥--Diffie-Hellman密钥交换2011-7-20Ch1-公钥密码技术3•公钥密码技术是为了解决对称密码技术中昀难解决的两个问题而提出的•一是对称密码技术的密钥分配问题•二是对称密码不能实现数字签名•Diffie和Hellmna于1976年在《密码学的新方向》中首次提出了公钥密码的观点，标志着公钥密码学研究的开始•1977年由Rviest，Shmair和Adlmena提出了第一个比较完善的公钥密码算法，即RSA算法。从那时候起，人们基于不同的计算问题提出了大量的公钥密码算法2011-7-20Ch1-公钥密码技术4公钥密码体制•公钥密码体制（Public-KeyCryptosystem）也称非对称密码体制(AsymmetricCryptosystem)或者双钥密码体制(Two-KeyCryptosystem)•公钥密码算法是基于数学函数（如单向陷门函数）而不是基于代换和置换•公钥密码是非对称的，它使用两个独立的密钥，即公钥和私钥，任何一个都可以用来加密，另一个用来解密•公钥可以被任何人知道，用于加密消息以及验证签名；私钥仅仅自己知道的，用于解密消息和签名•加密和解密会使用两把不同的密钥，因此称为非对称2011-7-20Ch1-公钥密码技术5•一个公钥密码体制有6个部分构成：明文，加密算法，公钥和私钥，密文，解密算法•可以构成两种基本的模型：加密模型和认证模型•在加密模型中，发送方用接收方的公钥作为加密密钥，用接收方私钥作解密密钥，由于该私钥只有接收方拥有，因此即只有接收者才能解密密文得到明文•在认证模型中，发送方用自己的私钥对消息进行变换，产生签名。接收者用发送者的公钥对签名进行验证以确定签名是否有效。只有拥有私钥的发送者才能对消息产生有效的签名，任何人均可以用签名人的公钥来检验该签名的有效性2011-7-20Ch1-公钥密码技术6消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PRBPUB图4.1公钥加密模型2011-7-20Ch1-公钥密码技术7消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PUAPRA图4.2公钥认证模型2011-7-20Ch1-公钥密码技术8消息加密算法解密算法消息MXC接收方B发送方A密钥源PUAPRA图4.3公钥密码体制的保密和认证加密算法X解密算法M密钥源PRBPUB2011-7-20Ch1-公钥密码技术9公钥密码系统满足的要求•同一算法用于加密和解密，但加密和解密使用不同的密钥。•两个密钥中的任何一个都可用来加密，另一个用来解密，加密和解密次序可以交换。•产生一对密钥（公钥和私钥）在计算上是可行的。•已知公钥和明文，产生密文在计算上是容易的。•接收方利用私钥来解密密文在计算上是可行的。•仅根据密码算法和公钥来确定私钥在计算上不可行。•已知公钥和密文，在不知道私钥的情况下，恢复明文在计算上是不可行的。2011-7-20Ch1-公钥密码技术10•上面要求的实质是要找一个单向陷门函数•单向函数指计算函数值是容易的，而计算函数的逆是不可行的•陷门单向函数则存在一个附加信息，当不知道该附加信息时，从函数逆是困难的，但当知道该附加信息时，求函数逆就变得容易了•陷门单向函数在附加信息未知时是单向函数，而当附加信息已知时，就不再是单向函数了•通常把附加信息称为陷门信息，陷门信息作为私钥，公钥密码体制就是基于这一原理而设计的•其安全强度取决于它所依据的问题的计算复杂度。2011-7-20Ch1-公钥密码技术11公钥密码分析•和对称密码体制一样，如果密钥太短，公钥密码体制也易受到穷举搜索攻击•但公钥密码体制所使用的可逆函数的计算复杂性与密钥长度是比线性函数增大更快函数。密钥长度太大又会使得加密和解密运算太慢而不实用•目前提出的公钥密码体制的密钥长度已经足够抵抗穷举攻击，但也使它加密和解密速度变慢，因此公钥密码体制一般用于加密小数据，如会话钥，目前主要用于密钥管理和数字签字。•对公钥密码算法的第二种攻击是从公钥计算出私钥。目前为止，还没有在数学上证明这个方面是不可行的。2011-7-20Ch1-公钥密码技术12RSA密码•RSA算法是1977年由Rivest、Shamir、Adleman提出的非常著名的公钥密码算法•它是基于大合数的质因子分解问题的困难性•RSA算法是一种分组密码，明文和密文是0到n-1之间的整数，通常n的大小为1024位二进制数或309位十进制数.2011-7-20Ch1-公钥密码技术13算法描述1.密钥的产生•随机选择两个大素数p,q•计算n=p×q•计算秘密的欧拉函数ϕ(n)=(p-1)(q-1)•选择e使得1eϕ(n)，且gcd(e,ϕ(n))=1•解下列方程求出ded≡1modϕ(n)，且0≤d≤n•公开公钥：PU={e,N}•保存私钥：PR={d,p,q}2011-7-20Ch1-公钥密码技术142.加密过程•加密时明文以分组为单位进行加密，每个分组m的二进制值均小于n，对明文分组m作加密运算：c=memodn,且0≤mn3．解密过程密文解密m=cdmodn4.签名过程计算签名s=mdmodn5．签名验证过程签名验证m=semodn2011-7-20Ch1-公钥密码技术15例4.1选择素数：p=47和q=71。•计算n=pq=47×71=3337，ϕ(n)=(p–1)(q-1)=46×70=3220。•选择e：使gcd(e,3220)=1，选取e=79；决定d：de≡1mod3220，得d=1019•公开公钥{79,3337}，保存私钥{1019,47,71}；•假设消息为M=6882326879666683，进行分组，分组的位数比n要小，我们选取M1=688，M2=232，M3=687，M4=966，M5=668，M6=003。•M1的密文为C1=68879mod3337=1570，继续进行类似计算，可得到昀终密文为C=1570275620912276158•解密时计算M1=15701019mod3337=688，类似可以求出其他明文。2011-7-20Ch1-公钥密码技术16RSA算法的安全性•RSA密码体制的安全性是基于分解大整数的困难性假设•RSA算法的加密函数c=memodn是一个单向函数，所以对于攻击者来说，试图解密密文是计算上不可行的•对于接收方解密密文的陷门是分解n=pq，由于接收方知道这个分解，他可以计算ϕ(n)=(p-1)(q-1)，然后用扩展欧几里德算法来计算解密私钥d。•对RSA算法的攻击有下面几个方法：穷举攻击，数学攻击，选择密文攻击，公共模数攻击，计时攻击2011-7-20Ch1-公钥密码技术17•昀基本的攻击是穷举攻击，也就是尝试所有可能的私钥•数学攻击的实质是试图对两个素数乘积的分解•计时攻击也可以用于对RSA算法的攻击。计时攻击是攻击者通过监视系统解密消息所花费的时间来确定私钥。时间攻击方式比较独特，它是一种只用到密文的攻击方式2011-7-20Ch1-公钥密码技术18ElGamal密码•ElGamal是1985年由T.EIGamal提出的一个著名的公钥密码算法•该算法既能用于数据加密也能用于数字签名•其安全性是依赖于计算有限域上离散对数这一难题2011-7-20Ch1-公钥密码技术191.密钥产生•任选一个大素数p，使得p-1有大素因子，g是模p的一个本原根，公开p与g。•使用者任选一私钥x，x∈[0,p-1]•计算公钥•公开公钥：y,p,g•保密私钥：xpgyxmod=2011-7-20Ch1-公钥密码技术202.加密过程•对于明文m，选取一个r，r∈[0,p-1]•计算•则密文为3.解密过程•先计算•再计算出明文pgcrmod1=pymcrmod2×=},{21ccpcwxmod)(11−=pwcmmod2×=2011-7-20Ch1-公钥密码技术214.签名过程•假设对消息m签名，任选一个随机数k，使k∈[0,p-1]•计算•签名为(5)签名验证过程•pgrkmod=)1mod()(1−×−=−prxmks},{sr)(modpgrymsr=×2011-7-20Ch1-公钥密码技术22•需要说明的是，为了避免选择密文攻击，ElGamal是对消息m的hash值进行签名，而不是对m签名•与RSA方法比较，ElGamal方法具有以下优点：(1)系统不需要保存秘密参数，所有的系统参数均可公开；(2)同一个明文在不同的时间由相同加密者加密会产生不同的密文•但ElGamal方法的计算复杂度比RSA方法要大。2011-7-20Ch1-公钥密码技术23椭圆曲线密码•大多数公钥密码系统都使用具有非常大数目的整数或多项式，计算量大•人们发现椭圆曲线是克服此困难的一个强有力的工具•椭圆曲线密码体制(Ellipticcurvecryptosystem,ECC)的依据是定义在椭圆曲线点群上的离散对数问题的难解性•椭圆曲线系统第一次应用于密码学上是于1985年由Koblitz与Miller分别提出•两个较著名的椭圆曲线密码系统；一是利用ElGamal的加密法，二是Menezes-Vanstone的加密法2011-7-20Ch1-公钥密码技术24椭圆曲线的定义•在实数系中，椭圆曲线可定义成所有满足方程E:y2=x3+ax+b的点(x,y)所构成的集合•若x3+ax+b没有重复的因式或4a3+27b2≠0，则E:y2=x3+ax+b能定义成为一个群•椭圆曲线是连续的，并不适合用于加密•必须把椭圆曲线变成离散的点，即将椭圆曲线定义在有限域上•密码学中关心的是有限域上的椭圆曲线2011-7-20Ch1-公钥密码技术25•椭圆曲线密码体制中使用的变元和系数均为有限域中元素的椭圆曲线•密码应用中所使用的两类椭圆曲线是定义在素域Zp上的素曲线(primecurve)和在GF(2m)上构造的二元曲线•对于素域Zp上的素曲线，我们使用三次方程，其中的变量和系数在集合{0,1,2,…,p-1}上取值，运算为模p运算•对于在GF(2m))上的二元曲线，变量和系数在GF(2m)内取值，且运算为GF(2m)里的运算2011-7-20Ch1-公钥密码技术26•密码系统在素域Zp或者GF(2m)下定义为椭圆曲线E:y2=x3+ax+b，其中4a3+27b2≠0，a和b是小于p(p为素数)的非负数。•在GF(2m)下定义为椭圆曲线E:y2+xy=x3+ax+b，其中b≠0，2011-7-20Ch1-公钥密码技术27•椭圆曲线有一个特殊的点，记为O，它并不在椭圆曲线上，此点称为无限远的点或零点•用E(K)表示在K上椭圆曲线E所有的点所构成的集合，如E(Zp)表示在素域Zp上椭圆曲线E所有的点所构成的集合，而E(GF(2m))则表示在GF(2m)上椭圆曲线E所有的点所构成的集合•椭圆曲线上的所有点E(K)集合通过定义一个加法运算，满足一定的运算规则可以构成一个Abel群•点P=（x,y）对X坐标轴反射的点为-P=（x,-y），而称-P为点P的负点。若nP=O，且n为昀小的正整数，则n为椭圆曲线E上点的阶•除了无限远的点O之外，椭圆曲线E上任何可以生成所有点的点都可视为是E的生成数(generator)2011-7-20Ch1-公钥密码技术28•椭圆曲线上的两个相异的点相加与双倍(doubling)的点P的几何含义如下。•两个相异的点相加：假设P和Q是椭圆曲线上两个相异的点，而且P不等于-Q。若P+Q=R，则点R是经过P、Q两点的直线与椭圆曲线相交的唯一交点的负点。如图4.5所示。•双倍的点P：令P+P=2P，则点2P是经过P的切线与椭圆曲线相交之唯一交点的负点。如图4.6所示。2011-7-20Ch1-公钥密码技术29两个相异点相加和双倍点2011-7-20Ch1-公钥密码技术30椭圆曲线运算规则1.椭圆曲线在素域Zp上的运算规则说明一