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

信息安全原理与技术第2版郭亚军宋建华李莉董慧慧清华大学出版社

2022/10/131Ch1-公钥密码技术第4章公钥钥密码技技术主要知识识点：--公钥密码码体制--RSA密码--ElGamal密码--椭圆曲线线密码--公钥分配配--利用公钥钥密码分分配对称称密钥--Diffie-Hellman密钥交换换2020-02-112Ch1--公钥密密码技术术公钥密码码技术是是为了解解决对称称密码技技术中最最难解决决的两个个问题而而提出的的一是对称称密码技技术的密密钥分配配问题二是对称称密码不不能实现现数字签签名Diffie和Hellmna于1976年在《密码学的的新方向向》中首次提提出了公公钥密码码的观点点，标志志着公钥钥密码学学研究的的开始1977年由Rviest，Shmair和Adlmena提出了第第一个比比较完善善的公钥钥密码算算法，即即RSA算法。从从那时候候起，人人们基于于不同的的计算问问题提出出了大量量的公钥钥密码算算法2020-02-113Ch1--公钥密密码技术术公钥密码码体制公钥密码码体制（Public--KeyCryptosystem）也称非对称密密码体制(AsymmetricCryptosystem)或者双钥密码码体制(Two-KeyCryptosystem)公钥密码码算法是是基于数学函数数（如单单向陷门门函数）而不是是基于代代换和置置换公钥密码码是非对称的，它使使用两个个独立的的密钥，，即公钥钥和私钥钥，任何一个个都可以以用来加加密，另另一个用用来解密密公钥可以以被任何何人知道道，用于于加密消消息以及及验证签签名；私私钥仅仅仅自己知知道的，，用于解解密消息息和签名名加密和解解密会使使用两把把不同的的密钥，，因此称称为非对对称2020-02-114Ch1--公钥密密码技术术一个公钥钥密码体体制有6个部分构构成：明明文，加加密算法法，公钥钥和私钥钥，密文文，解密密算法可以构成成两种基本本的模型型：加密密模型和和认证模模型在加密模型型中，发送送方用接接收方的的公钥作作为加密密密钥，，用接收收方私钥钥作解密密密钥，，由于该该私钥只只有接收收方拥有有，因此此即只有有接收者者才能解解密密文文得到明明文在认证模型型中，发送送方用自自己的私私钥对消消息进行行变换，，产生签签名。接接收者用用发送者者的公钥钥对签名名进行验验证以确确定签名名是否有有效。只只有拥有有私钥的的发送者者才能对对消息产产生有效效的签名名，任何何人均可可以用签签名人的的公钥来来检验该该签名的的有效性性2020-02-115Ch1--公钥密密码技术术消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PRBPUB图4.1公钥加密模型2020-02-116Ch1--公钥密密码技术术消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PUAPRA图4.2公钥认证模型2020-02-117Ch1--公钥密密码技术术消息加密算法解密算法消息MXC接收方B发送方A密钥源PUAPRA图4.3公钥密码体制的保密和认证加密算法X解密算法M密钥源PRBPUB2020-02-118Ch1--公钥密密码技术术公钥密码码系统满满足的要要求同一算法法用于加加密和解解密，但但加密和和解密使使用不同同的密钥钥。两个密钥钥中的任任何一个个都可用用来加密密，另一一个用来来解密，，加密和和解密次次序可以以交换。。产生一对对密钥（（公钥和和私钥））在计算算上是可可行的。。已知公钥钥和明文文，产生生密文在在计算上上是容易易的。接收方利利用私钥钥来解密密密文在在计算上上是可行行的。仅根据密密码算法法和公钥钥来确定定私钥在在计算上上不可行行。已知公钥钥和密文文，在不不知道私私钥的情情况下，，恢复明明文在计计算上是是不可行行的。2020-02-119Ch1--公钥密密码技术术上面要求求的实质质是要找找一个单向陷门门函数单向函数数指计算函函数值是是容易的的，而计计算函数数的逆是是不可行行的陷门单向向函数则存在一一个附加加信息，，当不知知道该附附加信息息时，从从函数逆逆是困难难的，但但当知道道该附加加信息时时，求函函数逆就就变得容容易了陷门单向向函数在在附加信信息未知知时是单单向函数数，而当当附加信信息已知知时，就就不再是是单向函函数了通常把附附加信息息称为陷门信息息，陷门信信息作为为私钥，，公钥密密码体制制就是基基于这一一原理而而设计的的其安全强强度取决决于它所所依据的的问题的的计算复复杂度。。2020-02-1110Ch1--公钥密密码技术术公钥密码码分析和对称密密码体制制一样，，如果密密钥太短短，公钥钥密码体体制也易易受到穷穷举搜索索攻击但公钥密密码体制制所使用用的可逆逆函数的的计算复复杂性与与密钥长长度是比比线性函函数增大大更快函函数。密密钥长度度太大又又会使得得加密和和解密运运算太慢慢而不实实用目前提出出的公钥钥密码体体制的密密钥长度度已经足足够抵抗抗穷举攻攻击，但但也使它它加密和和解密速速度变慢慢，因此此公钥密密码体制制一般用用于加密密小数据据，如会会话钥，，目前主主要用于于密钥管管理和数数字签字字。对公钥密密码算法法的第二二种攻击击是从公公钥计算算出私钥钥。目前前为止，，还没有有在数学学上证明明这个方方面是不不可行的的。2020-02-1111Ch1--公钥密密码技术术RSA密码RSA算法是1977年由Rivest、Shamir、Adleman提出的非非常著名名的公钥钥密码算算法它是基于于大合数数的质因因子分解解问题的的困难性性RSA算法是一一种分组组密码，，明文和和密文是是0到n-1之间的整整数，通通常n的大小为为1024位二进制制数或309位十进制制数.2020-02-1112Ch1--公钥密密码技术术算法描述述1.密钥的产产生随机选择择两个大大素数p,q计算n=p×q计算秘密密的欧拉拉函数(n)=(p-1)((q-1)选择e使得1<e<(n)，且gcd((e,(n))=1解下列方方程求出出ded≡1mod(n)，且0≤d≤n公开公钥钥：PU={e,N}保存私钥钥：PR={d,p,q}2020-02-1113Ch1--公钥密密码技术术2.加密过程程加密时明明文以分分组为单单位进行行加密，，每个分分组m的二进制制值均小小于n，对明文文分组m作加密运运算：c=memodn,且0≤m<n3．解密过过程密文解密密m=cdmodn4.签名过程程计算签名名s=mdmodn5．签名验验证过程程签名验证证m=semodn2020-02-1114Ch1--公钥密密码技术术例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，类似可可以求出出其他明明文。2020-02-1115Ch1--公钥密密码技术术RSA算法的安安全性RSA密码体制制的安全全性是基基于分解解大整数数的困难难性假设设RSA算法的加加密函数数c=memodn是一个单单向函数数，所以以对于攻攻击者来来说，试试图解密密密文是是计算上上不可行行的对于接收收方解密密密文的的陷门是分解n=pq，由于接接收方知知道这个个分解，，他可以以计算(n)=(p-1)((q-1)，然后用用扩展欧欧几里德德算法来来计算解解密私钥钥d。对RSA算法的攻攻击有下下面几个个方法：：穷举攻击击，数学学攻击，，选择密密文攻击击，公共共模数攻攻击，计计时攻击击2020-02-1116Ch1--公钥密密码技术术最基本的的攻击是是穷举攻击击，也就是是尝试所所有可能能的私钥钥数学攻击击的实质是是试图对对两个素素数乘积积的分解解计时攻击击也可以用用于对RSA算法的攻攻击。计时攻击击是攻击击者通过过监视系系统解密密消息所所花费的的时间来来确定私私钥。时时间攻击击方式比比较独特特，它是是一种只只用到密密文的攻攻击方式式2020-02-1117Ch1--公钥密密码技术术ElGamal密码ElGamal是1985年由T.EIGamal提出的一一个著名名的公钥钥密码算算法该算法既既能用于于数据加加密也能能用于数数字签名名其安全性性是依赖赖于计算算有限域域上离散散对数这这一难题题2020-02-1118Ch1--公钥密密码技术术1.密钥产生生任选一个个大素数数p，使得p-1有大素因因子，g是模p的一个本本原根，，公开p与g。使用者任任选一私私钥x，x∈[0,,p-1]计算公钥钥公开公钥钥：y,p,g保密私钥钥：x2020-02-1119Ch1--公钥密密码技术术2.加密过程程对于明文文m，选取一一个r，r∈[0,,p-1]计算则密文为为3.解密过程程先计算再计算出出明文2020-02-1120Ch1--公钥密密码技术术4.签名过程程假设对消消息m签名，任任选一个个随机数数k，使k∈[0,,p-1]计算签名为(5)签名验证证过程

2020-02-1121Ch1--公钥密密码技术术需要说明明的是，，为了避避免选择择密文攻攻击，ElGamal是对消息息m的hash值进行签签名，而而不是对对m签名与RSA方法比较较，ElGamal方法具有有以下优优点：(1)系统不需需要保存存秘密参参数，所所有的系系统参数数均可公公开；(2)同一个明明文在不不同的时时间由相相同加密密者加密密会产生生不同的的密文但ElGamal方法的计计算复杂杂度比RSA方法要大大。2020-02-1122Ch1--公钥密密码技术术椭圆曲线线密码大多数公公钥密码码系统都都使用具具有非常常大数目目的整数数或多项项式，计计算量大大人们发现现椭圆曲曲线是克克服此困困难的一一个强有有力的工工具椭圆曲线线密码体体制(Ellipticcurvecryptosystem,ECC))的依据是是定义在在椭圆曲曲线点群群上的离离散对数数问题的的难解性性椭圆曲线线系统第第一次应应用于密密码学上上是于1985年由Koblitz与Miller分别提出出两个较著著名的椭椭圆曲线线密码系系统；一一是利用用ElGamal的加密法法，二是是Menezes-Vanstone的加密法法2020-02-1123Ch1--公钥密密码技术术椭圆曲线线的定义义在实数系系中，椭椭圆曲线线可定义义成所有有满足方方程E:y2=x3+ax+b的点(x,y)所构成的的集合若x3+ax+b没有重复复的因式式或4a3+27b2≠0，则E:y2=x3+ax+b能定义成成为一个个群椭圆曲线线是连续续的，并并不适合合用于加加密必须把椭椭圆曲线线变成离散的点点，即将椭椭圆曲线线定义在在有限域域上密码学中中关心的的是有限域上上的椭圆圆曲线2020-02-1124Ch1--公钥密密码技术术椭圆曲线线密码体体制中使使用的变元和系数均为有限域中元素的的椭圆曲曲线密码应用用中所使使用的两类椭圆圆曲线是定义在在素域Zp上的素曲曲线(primecurve))和在GF(2m)上构造的的二元曲曲线对于素域Zp上的素曲曲线，我们使使用三次次方程，，其中的的变量和和系数在在集合{0,1,2,,…,p-1}上取值，，运算为为模p运算对于在GF(2m))上的二元元曲线，变量和和系数在在GF(2m)内取值，，且运算算为GF(2m)里的运算算2020-02-1125Ch1--公钥密密码技术术密码系统统在素域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，2020-02-1126Ch1--公钥密密码技术术椭圆曲线线有一个个特殊的的点，记记为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)2020-02-1127Ch1--公钥密密码技术术椭圆曲线线上的两两个相异异的点相加与双倍(doubling))的点P的几何含含义如下下。两个相异异的点相相加：假设P和Q是椭圆曲曲线上两两个相异异的点，，而且P不等于-Q。若P+Q=R，则点R是经过P、Q两点的直直线与椭椭圆曲线线相交的的唯一交交点的负负点。如如图4.5所示。双倍的点点P：令P+P==2P，则点2P是经过P的切线与与椭圆曲曲线相交交之唯一一交点的的负点。。如图4.6所示。2020-02-1128Ch1--公钥密密码技术术两个相异异点相加加和双倍倍点2020-02-1129Ch1--公钥密密码技术术椭圆曲线线运算规规则1.椭圆曲线线在素域域Zp上的运算算规则说明一点点，在椭椭圆曲线线运算中中，大写写参数表表示点，，小写参参数表示示数值。。加法规则则：2020-02-1130Ch1--公钥密密码技术术其中乘法规则则：2020-02-1131Ch1--公钥密密码技术术椭圆曲线线在GF(2m)上的运算算规则加法规则则：2020-02-1132Ch1--公钥密密码技术术乘法规则则：2020-02-1133Ch1--公钥密密码技术术椭圆曲线线密码算算法椭圆曲线线上所有有的点外外加一个个叫做无无穷远点点的特殊殊点构成成的集合合，连同一个个定义的的加法运运算构成成一个Abel群在等式kP=P+P+…++P=Q中，已知知k和点P求点Q比较容易易，反之已知知点Q和点P求k却是相当当困难的的，这个问题题称为椭圆曲线线上点群群的离散散对数问问题(EllipticCurveDiscreteLogarithmProblem,,ECDLP)椭圆曲线线密码算算法正是是利用这这个困难难问题而而设计的的2020-02-1134Ch1--公钥密密码技术术ElGamal的椭圆曲曲线密码码算法(1)密钥产生生假设系统统公开参参数为一一个椭圆圆曲线E及模数p。使用者者执行：：任选一个个整数k，任选一个个点，，并计算算公钥为，，私钥钥为k。2020-02-1135Ch1--公钥密密码技术术(2)加密过程程令明文M为E上的一点点。。首首先任选选一个整整数，然然后计算算密文密文为两两个点。。(3)解密过程程计算明文文2020-02-1136Ch1--公钥密密码技术术Menezes-Vanstone椭圆曲线线密码算算法Menezes-Vanstone椭圆曲线线密码算算法是效效率比较较高的椭椭圆曲线线加密法法其明文没没有限制制一定要要落于椭椭圆曲线线E上2020-02-1137Ch1--公钥密密码技术术2020-02-1138Ch1--公钥密密码技术术椭圆曲线线密码的的性能椭圆曲线线密码体体制的安安全性是是建立在在椭圆曲曲线离散散对数的的数学难难题之上上椭圆曲线线离散对对数问题题被公认认为要比比整数分分解问题题(RSA方法的基基础)和模p离散对数数问题(DSA算法的基基础)难解得多多目前解椭椭圆曲线线上的离离散对数数问题的的最好算算法是Pollardrho方法，其其计算复复杂度上上是完全全指数级级的，而而目前对对于一般般情况下下的因数数分解的的最好算算法的时时间复杂杂度是亚亚指数级级的ECC算法在安安全强度度、加密密速度以以及存储储空间方方面都有有巨大的的优势。。如161位的ECC算法的安安全强度度相当于于RSA算法1024位的强度度2020-02-1139Ch1--公钥密密码技术术公钥分配配公钥密码码体制的的密钥分分配与对对称密码码体制的的密钥分分配有着着本质的的差别对称密码码体制的的密钥分分配中必必须同时时确保密密钥的秘密性、、真实性性和完整整性公开密钥钥密码体体制中有有两个密密钥，私私钥由自自己保管管，不需需要进行行分配公钥密码码体制不不需要保保证公钥钥的秘密密性,只需确保公钥钥的真实实性和完完整性，这样就就能保证证公钥没没有被攻攻击者替替换或篡篡改公钥的分分配方法法可归纳纳为四种种：公开开发布、、公用目目录表、、公钥钥授权和和公钥证证书。2020-02-1140Ch1--公钥密密码技术术公开发布布公开发布布指用户户将自己己的公钥钥发给其其他用户户，或广广播给某某一团体体这种方法法虽然简简单，但但有一个个较大的的缺点，，即任何何人都可可伪造这这种公开开发布如果某个个用户假假装是用用户A并以A的名义向向另一用用户发送送或广播播自己的的公开钥钥，则在在A发现假冒冒者以前前，这一一假冒者者可解读读所有意意欲发向向A的加密消消息，而而且假冒冒者还能能用伪造造的密钥钥获得认认证。2020-02-1141Ch1--公钥密密码技术术公用目录录表公用目录录表指一一个公用用的公钥钥动态目目录表公用目录录表的建建立、维维护以及及公钥的的分布由由某个可可信的实实体或组组织承担担，称这这个实体体或组织织为公用用目录的的管理员员与第一种种分配方方法相比比，这种种方法的的安全性性更高该方法有有以下一一些组成成部分：：(1)管理员为为每个用用户在目目录表中中建立一一个目录录，目录录中有两两个数据据项：一一是用户户名，二二是用户户的公开开钥。2020-02-1142Ch1--公钥密密码技术术(2)每一用户户都亲自自或以某某种安全全的认证证通信在在管理者者那里为为自己的的公开钥钥注册。。(3)用户可以以随时用用新密钥钥替换现现有的密密钥。这这可能由由于自己己的公钥钥用过的的次数太太多或由由于与公公钥相关关的私钥钥已泄漏漏。(4)管理员定定期公布布或定期期更新目目录表。。例如，，像电话话号码本本一样公公布目录录表或在在发行量量很大的的报纸上上公布目目录表的的更新。。(5)用户可通通过电子子手段访访问目录录表。此此时，从从管理员员到用户户必须有有安全的的认证通通信。这种方案案的安全全性明显显高于公公开发布布的安全全性，但但仍易受受到攻击击。如果果敌手成成功地获获得管理理员的私私人密钥钥，就可可伪造一一个公钥钥目录表表，以后后既可以以假冒任任一用户户又可以以监听发发往任一一用户的的消息。。2020-02-1143Ch1--公钥密密码技术术公钥授权权与公用目目录表类类似，假假定有一一个公钥钥管理机机构来为为用户建建立、维维护动态态的公钥钥目录但同时对对系统提提出以下下要求，，即：每个用户户都可靠靠地知道道管理机机构的公公钥，而而只有管管理机构构自己知知道相应应的私钥钥图4.7是典型的的公钥分分配方案案，在这这个分配配方案中中完成了了两个功功能，一一是获得得需要的的公钥；；二是双双方相互互认证2020-02-1144Ch1--公钥密密码技术术2020-02-1145Ch1--公钥密密码技术术公钥证书书公钥授权权中的管管理机构构有可能能成为系系统的瓶瓶颈，而而且由管管理机构构维护的的公钥目目录表也也易被攻攻击者篡篡改。分配公钥钥的另一一方法是是公钥证书书用户通过过交换公公钥证书书来互相相交换自自己的公公钥公钥证书书类似人人们使用用的纸类类证书，，如驾驶驶执照、、毕业证证等，两两者都包包括拥有有者的属属性，可可以验证证证书一般般由第三三方发行行，这个第第三方称称为证书书权威中中心（certificateauthority,,CA）。证书书由CA签名表明明证书的的拥有者者所具有有的公钥钥等信息息。证书书由CA用它的私私钥签名名，其他他用户可可以用CA的公钥验验证证书书的真假假。2020-02-1146Ch1--公钥密密码技术术使用公钥钥证书分分配公钥钥过程非非常简单单事先由CA对用户的的证书签签名，证证书中包包含有与与该用户户的私钥钥相对应应的公钥钥及用户户的身份份等信息息所有的数数据项经经CA用自己的的私钥签签名后就就形成证证书用户可将将自己的的公钥通通过公钥钥证书发发给另一一用