《信息安全原理与技术ch04-公钥密码技术40255.pptx》由会员分享，可在线阅读，更多相关《信息安全原理与技术ch04-公钥密码技术40255.pptx（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息安全原理与技术信息安全原理与技术第2版郭亚军 宋建华 李莉 董慧慧清华大学出版社 2023/3/141Ch1-公钥密码技术第4章 公钥密码技术主要知识点主要知识点：-公钥密码体制 -RSA密码 -ElGamal密码 -椭圆曲线密码 -公钥分配 -利用公钥密码分配对称密钥 -Diffie-Hellman 密钥交换 2023/3/142Ch1-公钥密码技术公钥密码技术是为了解决对称密码技术中最难解决的两个问题而提出的一是对称密码技术的密钥分配问题二是对称密码不能实现数字签名Diffie和Hellmna于1976年在密码学的新方向中首次提出了公钥密码的观点，标志着公钥密码学研究的开始1977年由
2、Rviest，Shmair和Adlmena提出了第一个比较完善的公钥密码算法，即RSA算法。从那时候起，人们基于不同的计算问题提出了大量的公钥密码算法 2023/3/143Ch1-公钥密码技术公钥密码体制 公钥密码体制公钥密码体制（Public-Key Cryptosystem）也称非对称密码非对称密码体制体制(Asymmetric Cryptosystem)或者双钥密码体制双钥密码体制(Two-Key Cryptosystem)公钥密码算法是基于数学函数（如单向陷门函数数学函数（如单向陷门函数）而不是基于代换和置换公钥密码是非对称非对称的，它使用两个独立的密钥，即公钥和私钥，任何一个都可以用
3、来加密，另一个用来解密 公钥可以被任何人知道，用于加密消息以及验证签名；私钥仅仅自己知道的，用于解密消息和签名加密和解密会使用两把不同的密钥，因此称为非对称2023/3/144Ch1-公钥密码技术一个公钥密码体制有6个部分构成：明文，加密算法，公钥和私钥，密文，解密算法可以构成两种基本的模型：加密模型和认证模型在加密模型加密模型中，发送方用接收方的公钥作为加密密钥，用接收方私钥作解密密钥，由于该私钥只有接收方拥有，因此即只有接收者才能解密密文得到明文在认证模型认证模型中，发送方用自己的私钥对消息进行变换，产生签名。接收者用发送者的公钥对签名进行验证以确定签名是否有效。只有拥有私钥的发送者才能对
4、消息产生有效的签名，任何人均可以用签名人的公钥来检验该签名的有效性 2023/3/145Ch1-公钥密码技术消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PRBPUB图4.1 公钥加密模型2023/3/146Ch1-公钥密码技术消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PUAPRA图4.2 公钥认证模型2023/3/147Ch1-公钥密码技术消息加密算法解密算法消息MXC接收方B发送方A密钥源PUAPRA图4.3 公钥密码体制的保密和认证加密算法X解密算法M密钥源PRBPUB2023/3/148Ch1-公钥密码技术公钥密码系统满足的要求同一算法用于加密和解密，但加密
5、和解密使用不同的密钥。两个密钥中的任何一个都可用来加密，另一个用来解密，加密和解密次序可以交换。产生一对密钥（公钥和私钥）在计算上是可行的。已知公钥和明文，产生密文在计算上是容易的。接收方利用私钥来解密密文在计算上是可行的。仅根据密码算法和公钥来确定私钥在计算上不可行。已知公钥和密文，在不知道私钥的情况下，恢复明文在计算上是不可行的。2023/3/149Ch1-公钥密码技术上面要求的实质是要找一个单向陷门函数单向陷门函数单向函数单向函数指计算函数值是容易的，而计算函数的逆是不可行的陷门单向函数陷门单向函数则存在一个附加信息，当不知道该附加信息时，从函数逆是困难的，但当知道该附加信息时，求函数逆
6、就变得容易了陷门单向函数在附加信息未知时是单向函数，而当附加信息已知时，就不再是单向函数了通常把附加信息称为陷门信息陷门信息，陷门信息作为私钥，公钥密码体制就是基于这一原理而设计的其安全强度取决于它所依据的问题的计算复杂度。2023/3/1410Ch1-公钥密码技术公钥密码分析 和对称密码体制一样，如果密钥太短，公钥密码体制也易受到穷举搜索攻击但公钥密码体制所使用的可逆函数的计算复杂性与密钥长度是比线性函数增大更快函数。密钥长度太大又会使得加密和解密运算太慢而不实用目前提出的公钥密码体制的密钥长度已经足够抵抗穷举攻击，但也使它加密和解密速度变慢，因此公钥密码体制一般用于加密小数据，如会话钥，目
7、前主要用于密钥管理和数字签字。对公钥密码算法的第二种攻击是从公钥计算出私钥。目前为止，还没有在数学上证明这个方面是不可行的。2023/3/1411Ch1-公钥密码技术RSA密码 RSA算法是1977年由Rivest、Shamir、Adleman提出的非常著名的公钥密码算法它是基于大合数的质因子分解问题的困难性RSA算法是一种分组密码，明文和密文是0到n-1之间的整数，通常n的大小为1024位二进制数或309位十进制数.2023/3/1412Ch1-公钥密码技术算法描述 1.密钥的产生密钥的产生 随机选择两个大素数 p,q 计算 n=pq计算秘密的欧拉函数(n)=(p-1)(q-1)选择 e使得
8、1e(n)，且gcd(e,(n)=1 解下列方程求出 d ed 1 mod(n)，且 0dn 公开公钥：PU=e,N 保存私钥：PR=d,p,q 2023/3/1413Ch1-公钥密码技术2.加密过程加密过程加密时明文以分组为单位进行加密，每个分组m的二进制值均小于n，对明文分组m作加密运算：c=me mod n,且0mn3解密过程解密过程 密文解密m=cd mod n 4.签名过程签名过程 计算签名 s=md mod n5签名验证过程签名验证过程 签名验证m=se mod n2023/3/1414Ch1-公钥密码技术 例例4.1选择素数：p=47 和 q=71。计算 n=pq=4771=33
9、37，(n)=(p1)(q-1)=4670=3220。选择e：使gcd(e,3220)=1，选取e=79；决定d：de1 mod 3220，得d=1019公开公钥 79,3337，保存私钥 1019,47,71；假设消息为 M=6882326879666683，进行分组，分组的位数比n要小，我们选取M1=688，M2=232，M3=687，M4=966，M5=668，M6=003。M1的密文为C1=68879 mod 3337=1570，继续进行类似计算，可得到最终密文为 C=1570275620912276158解密时计算M1=15701019 mod 3337=688，类似可以求出其他明文
10、。2023/3/1415Ch1-公钥密码技术RSA算法的安全性 RSA密码体制的安全性是基于分解大整数的困难性假设RSA算法的加密函数c=me mod n是一个单向函数，所以对于攻击者来说，试图解密密文是计算上不可行的对于接收方解密密文的陷门陷门是分解n=pq，由于接收方知道这个分解，他可以计算(n)=(p-1)(q-1)，然后用扩展欧几里德算法来计算解密私钥d。对RSA算法的攻击有下面几个方法：穷举攻击，穷举攻击，数学攻击，选择密文攻击，公共模数攻击，计时数学攻击，选择密文攻击，公共模数攻击，计时攻击攻击 2023/3/1416Ch1-公钥密码技术最基本的攻击是穷举攻击穷举攻击，也就是尝试所
11、有可能的私钥数学攻击数学攻击的实质是试图对两个素数乘积的分解 计时攻击计时攻击也可以用于对RSA算法的攻击。计时攻击是攻击者通过监视系统解密消息所花费的时间来确定私钥。时间攻击方式比较独特，它是一种只用到密文的攻击方式 2023/3/1417Ch1-公钥密码技术ElGamal密码 ElGamal是1985年由T.EIGamal提出的一个著名的公钥密码算法该算法既能用于数据加密也能用于数字签名其安全性是依赖于计算有限域上离散对数这一难题 2023/3/1418Ch1-公钥密码技术1.密钥产生密钥产生任选一个大素数p，使得p-1有大素因子，g是模p的一个本原根，公开p与g。使用者任选一私钥x，x0
12、,p-1计算公钥公开公钥：y,p,g保密私钥：x2023/3/1419Ch1-公钥密码技术2.加密过程加密过程对于明文m，选取一个r，r0,p-1计算则密文为 3.解密过程解密过程先计算再计算出明文2023/3/1420Ch1-公钥密码技术4.签名过程签名过程假设对消息m签名，任选一个随机数k，使k0,p-1计算签名为(5)签名验证过程签名验证过程 2023/3/1421Ch1-公钥密码技术需要说明的是，为了避免选择密文攻击，ElGamal是对消息m的hash值进行签名，而不是对m签名与RSA方法比较，ElGamal方法具有以下优点：(1)系统不需要保存秘密参数，所有的系统参数均可公开；(2)
13、同一个明文在不同的时间由相同加密者加密会产生不同的密文但ElGamal方法的计算复杂度比RSA方法要大。2023/3/1422Ch1-公钥密码技术椭圆曲线密码 大多数公钥密码系统都使用具有非常大数目的整数或多项式，计算量大人们发现椭圆曲线是克服此困难的一个强有力的工具椭圆曲线密码体制椭圆曲线密码体制(Elliptic curve cryptosystem,ECC)的依据是定义在椭圆曲线点群上的离散对数问题的难解性椭圆曲线系统第一次应用于密码学上是于1985年由Koblitz与Miller分别提出两个较著名的椭圆曲线密码系统；一是利用ElGamal的加密法，二是Menezes-Vanstone的
14、加密法 2023/3/1423Ch1-公钥密码技术椭圆曲线的定义 在实数系中，椭圆曲线可定义成所有满足方程E:y2=x3+ax+b的点(x,y)所构成的集合若x3+ax+b没有重复的因式或4a3+27b2 0，则E:y2=x3+ax+b能定义成为一个群椭圆曲线是连续的，并不适合用于加密必须把椭圆曲线变成离散的点离散的点，即将椭圆曲线定义在有限域上密码学中关心的是有限域上的椭圆曲线有限域上的椭圆曲线 2023/3/1424Ch1-公钥密码技术椭圆曲线密码体制中使用的变元变元和系数系数均为有限域有限域中元素的椭圆曲线密码应用中所使用的两类椭圆曲线两类椭圆曲线是定义在素域素域Zp上的素曲线上的素曲线
15、(prime curve)和在GF(2m)上构造的二元曲线上构造的二元曲线对于素域素域Zp上的素曲线上的素曲线，我们使用三次方程，其中的变量和系数在集合0,1,2,p-1上取值，运算为模p运算对于在GF(2m)上的二元曲线上的二元曲线，变量和系数在GF(2m)内取值，且运算为GF(2m)里的运算2023/3/1425Ch1-公钥密码技术密码系统在素域素域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，2023/3/1426Ch1-公钥密码
16、技术椭圆曲线有一个特殊的点，记为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的生成数生成数(gen
17、erator)2023/3/1427Ch1-公钥密码技术椭圆曲线上的两个相异的点相加相加与双倍双倍(doubling)的点P的几何含义如下。两个相异的点相加两个相异的点相加：假设P和Q是椭圆曲线上两个相异的点，而且P不等于-Q。若P+Q=R，则点R是经过P、Q两点的直线与椭圆曲线相交的唯一交点的负点。如图4.5所示。双倍的点双倍的点P：令P+P=2P，则点2P是经过P的切线与椭圆曲线相交之唯一交点的负点。如图4.6所示。2023/3/1428Ch1-公钥密码技术两个相异点相加和双倍点 2023/3/1429Ch1-公钥密码技术椭圆曲线运算规则 1.椭圆曲线在素域椭圆曲线在素域Zp上的运算规则上
18、的运算规则 说明一点，在椭圆曲线运算中，大写参数表示点，小写参数表示数值。加法规则：加法规则：2023/3/1430Ch1-公钥密码技术其中乘法规则乘法规则：2023/3/1431Ch1-公钥密码技术椭圆曲线在GF(2m)上的运算规则 加法规则：加法规则：2023/3/1432Ch1-公钥密码技术乘法规则乘法规则：2023/3/1433Ch1-公钥密码技术椭圆曲线密码算法 椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合，连同一个定义的加法运算构成一个Abel群群在等式kP=P+P+P=Q中，已知k和点P求点Q比较容易，反之已知点Q和点P求k却是相当困难的，这个问题称为椭圆曲线上点群的
19、离散对椭圆曲线上点群的离散对数问题数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP)椭圆曲线密码算法正是利用这个困难问题而设计的 2023/3/1434Ch1-公钥密码技术ElGamal的椭圆曲线密码算法(1)密钥产生假设系统公开参数为一个椭圆曲线E及模数p。使用者执行：任选一个整数k，任选一个点 ，并计算公钥为 ，私钥为k。2023/3/1435Ch1-公钥密码技术(2)加密过程令明文M为E上的一点 。首先任选一个整数，然后计算密文密文为两个点。(3)解密过程计算明文2023/3/1436Ch1-公钥密码技术Menezes-Vanston
20、e椭圆曲线密码算法 Menezes-Vanstone椭圆曲线密码算法是效率比较高的椭圆曲线加密法其明文没有限制一定要落于椭圆曲线E上 2023/3/1437Ch1-公钥密码技术2023/3/1438Ch1-公钥密码技术椭圆曲线密码的性能 椭圆曲线密码体制的安全性是建立在椭圆曲线离散对数的数学难题之上椭圆曲线离散对数问题被公认为要比整数分解问题(RSA方法的基础)和模p离散对数问题(DSA算法的基础)难解得多目前解椭圆曲线上的离散对数问题的最好算法是Pollard rho方法，其计算复杂度上是完全指数级的，而目前对于一般情况下的因数分解的最好算法的时间复杂度是亚指数级的ECC算法在安全强度、加密
21、速度以及存储空间方面都有巨大的优势。如161位的ECC算法的安全强度相当于RSA算法1024位的强度2023/3/1439Ch1-公钥密码技术公钥分配 公钥密码体制的密钥分配与对称密码体制的密钥分配有着本质的差别对称密码体制的密钥分配中必须同时确保密钥的秘密性、真实性和完整性秘密性、真实性和完整性公开密钥密码体制中有两个密钥，私钥由自己保管，不需要进行分配公钥密码体制不需要保证公钥的秘密性,只需确保确保公钥的真实性和完整性公钥的真实性和完整性，这样就能保证公钥没有被攻击者替换或篡改公钥的分配方法可归纳为四种：公开发布、公用目录表、公钥授权和公钥证书。2023/3/1440Ch1-公钥密码技术公
22、开发布 公开发布指用户将自己的公钥发给其他用户，或广播给某一团体这种方法虽然简单，但有一个较大的缺点，即任何人都可伪造这种公开发布如果某个用户假装是用户A并以A的名义向另一用户发送或广播自己的公开钥，则在A发现假冒者以前，这一假冒者可解读所有意欲发向A的加密消息，而且假冒者还能用伪造的密钥获得认证。2023/3/1441Ch1-公钥密码技术公用目录表 公用目录表指一个公用的公钥动态目录表公用目录表的建立、维护以及公钥的分布由某个可信的实体或组织承担，称这个实体或组织为公用目录的管理员与第一种分配方法相比，这种方法的安全性更高 该方法有以下一些组成部分：(1)管理员为每个用户在目录表中建立一个目
23、录，目录中有两个数据项：一是用户名，二是用户的公开钥。2023/3/1442Ch1-公钥密码技术 (2)每一用户都亲自或以某种安全的认证通信在管理者那里为自己的公开钥注册。(3)用户可以随时用新密钥替换现有的密钥。这可能由于自己的公钥用过的次数太多或由于与公钥相关的私钥已泄漏。(4)管理员定期公布或定期更新目录表。例如，像电话号码本一样公布目录表或在发行量很大的报纸上公布目录表的更新。(5)用户可通过电子手段访问目录表。此时，从管理员到用户必须有安全的认证通信。这种方案的安全性明显高于公开发布的安全性，但仍易受到攻击。如果敌手成功地获得管理员的私人密钥，就可伪造一个公钥目录表，以后既可以假冒任
24、一用户又可以监听发往任一用户的消息。2023/3/1443Ch1-公钥密码技术公钥授权 与公用目录表类似，假定有一个公钥管理机构来为用户建立、维护动态的公钥目录但同时对系统提出以下要求，即：每个用每个用户都可靠地知道管理机构的公钥，而只有户都可靠地知道管理机构的公钥，而只有管理机构自己知道相应的私钥管理机构自己知道相应的私钥图4.7是典型的公钥分配方案，在这个分配方案中完成了两个功能，一是获得需要的公钥；二是双方相互认证 2023/3/1444Ch1-公钥密码技术2023/3/1445Ch1-公钥密码技术公钥证书 公钥授权中的管理机构有可能成为系统的瓶颈，而且由管理机构维护的公钥目录表也易被攻
25、击者篡改。分配公钥的另一方法是公钥证书公钥证书用户通过交换公钥证书来互相交换自己的公钥公钥证书类似人们使用的纸类证书，如驾驶执照、毕业证等，两者都包括拥有者的属性，可以验证证书一般由第三方发行证书一般由第三方发行，这个第三方称为证书权威中心（certificate authority,CA）。证书由CA签名表明证书的拥有者所具有的公钥等信息。证书由CA用它的私钥签名，其他用户可以用CA的公钥验证证书的真假。2023/3/1446Ch1-公钥密码技术使用公钥证书分配公钥过程非常简单事先由CA对用户的证书签名，证书中包含有与该用户的私钥相对应的公钥及用户的身份等信息所有的数据项经CA用自己的私钥签
26、名后就形成证书用户可将自己的公钥通过公钥证书发给另一用户，接收方可用CA的公钥对证书加以验证，这样接收方就能知道发送方的公钥由于证书是由CA私钥加密，任何其他人不能伪造该证书。2023/3/1447Ch1-公钥密码技术利用公钥密码分配对称密钥 由于公钥算法速度很慢，在通信中一般不使用公钥加密消息，而是使用会话钥（对称密码密钥）因此一般的做法是用会话钥加密消息，用公钥来实现会话钥的分配。一种简单的会话钥分配方法如下：-A产生一对公私钥PUa和PRa，将公钥PUa和自己的身份标识IDA传给B -B产生一个会话钥Ks，用A的公钥PUa加密后EPUa(Ks)传给A -由于只有A有私钥PRa，所以A能够
27、得到会话钥Ks。随后双方用会话钥Ks加密双方需要传输的消息。2023/3/1448Ch1-公钥密码技术Diffie-Hellman 密钥交换 Diffie-Hellman密钥交换是W.Diffie和M.Hellman于1976年提出的第一个公开密钥算法已在很多商业产品中得以应用算法的惟一目的是使得两个用户能够安全地交换密钥交换密钥，得到一个共享的会话密钥算法本身不能用于加、解密该算法的安全性基于求离散对数求离散对数的困难性。2023/3/1449Ch1-公钥密码技术假定p是一个素数，是其本原根，将p和公开。假设A和B之间希望交换会话钥。-用户A：-用户B：2023/3/1450Ch1-公钥密码技术Diffie-Hellman密钥交换协议很容易受到中间人攻中间人攻击击一个主动的窃听者C可能截取A发给B的消息以及B发给A的消息，他用自己的消息替换这些消息并分别与A和B完成一个Diffie-Hellman密钥交换密钥交换协议完毕后，A实际上和C建立了一个会话密钥，B和C建立了一个会话密钥当A加密一个消息发送给B时，C能解密它而B不能。类似地，当B加密一个消息发送给A时，C能解密它而A不能防止Diffie-Hellman密钥交换协议中间人攻击的一个方法是让A和B分别对消息签名。2023/3/1451Ch1-公钥密码技术