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

信息安全原理与技术第3版第4章公钥密码技术主要知识点：

--公钥密码体制

--RSA密码

--ElGamal密码

--椭圆曲线密码

--SM2

--公钥分配

--利用公钥密码分配对称密钥

--Diffie-Hellman密钥交换2024/4/5Ch1-公钥密码技术2公钥密码技术是为了解决对称密码技术中最难解决的两个问题而提出的一是对称密码技术的密钥分配问题二是对称密码不能实现数字签名Diffie和Hellmna于1976年在《密码学的新方向》中首次提出了公钥密码的观点，标志着公钥密码学研究的开始1977年由Rviest，Shmair和Adlmena提出了第一个比较完善的公钥密码算法，即RSA算法。从那时候起，人们基于不同的计算问题提出了大量的公钥密码算法2024/4/5Ch1-公钥密码技术3公钥密码体制

公钥密码体制（Public-KeyCryptosystem）也称非对称密码体制(AsymmetricCryptosystem)或者双钥密码体制(Two-KeyCryptosystem)公钥密码算法是基于数学函数（如单向陷门函数）而不是基于代换和置换公钥密码是非对称的，它使用两个独立的密钥，即公钥和私钥，任何一个都可以用来加密，另一个用来解密公钥可以被任何人知道，用于加密消息以及验证签名；私钥仅仅自己知道的，用于解密消息和签名加密和解密会使用两把不同的密钥，因此称为非对称2024/4/5Ch1-公钥密码技术4一个公钥密码体制有6个部分构成：明文，加密算法，公钥和私钥，密文，解密算法可以构成两种基本的模型：加密模型和认证模型在加密模型中，发送方用接收方的公钥作为加密密钥，用接收方私钥作解密密钥，由于该私钥只有接收方拥有，因此即只有接收者才能解密密文得到明文在认证模型中，发送方用自己的私钥对消息进行变换，产生签名。接收者用发送者的公钥对签名进行验证以确定签名是否有效。只有拥有私钥的发送者才能对消息产生有效的签名，任何人均可以用签名人的公钥来检验该签名的有效性2024/4/5Ch1-公钥密码技术5消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PRBPUB图4.1公钥加密模型2024/4/5Ch1-公钥密码技术6消息加密算法解密算法消息MMC攻击者接收方B发送方A密钥源PUAPRA图4.2公钥认证模型2024/4/5Ch1-公钥密码技术7消息加密算法解密算法消息MXC接收方B发送方A密钥源PUAPRA图4.3公钥密码体制的保密和认证加密算法X解密算法M密钥源PRBPUB2024/4/5Ch1-公钥密码技术8公钥密码系统满足的要求同一算法用于加密和解密，但加密和解密使用不同的密钥。两个密钥中的任何一个都可用来加密，另一个用来解密，加密和解密次序可以交换。产生一对密钥（公钥和私钥）在计算上是可行的。已知公钥和明文，产生密文在计算上是容易的。接收方利用私钥来解密密文在计算上是可行的。仅根据密码算法和公钥来确定私钥在计算上不可行。已知公钥和密文，在不知道私钥的情况下，恢复明文在计算上是不可行的。2024/4/5Ch1-公钥密码技术9上面要求的实质是要找一个单向陷门函数单向函数指计算函数值是容易的，而计算函数的逆是不可行的陷门单向函数则存在一个附加信息，当不知道该附加信息时，求函数逆是困难的，但当知道该附加信息时，求函数逆就变得容易了陷门单向函数在附加信息未知时是单向函数，而当附加信息已知时，就不再是单向函数了通常把附加信息称为陷门信息，陷门信息作为私钥，公钥密码体制就是基于这一原理而设计的其安全强度取决于它所依据的问题的计算复杂度。2024/4/5Ch1-公钥密码技术10公钥密码分析

和对称密码体制一样，如果密钥太短，公钥密码体制也易受到穷举搜索攻击但公钥密码体制所使用的可逆函数的计算复杂性与密钥长度是比线性函数增大更快函数。密钥长度太大又会使得加密和解密运算太慢而不实用目前提出的公钥密码体制的密钥长度已经足够抵抗穷举攻击，但也使它加密和解密速度变慢，因此公钥密码体制一般用于加密小数据，如会话钥，目前主要用于密钥管理和数字签字。对公钥密码算法的第二种攻击是从公钥计算出私钥。目前为止，还没有在数学上证明这个方面是不可行的。2024/4/5Ch1-公钥密码技术11RSA密码

RSA算法是1977年由Rivest、Shamir、Adleman提出的非常著名的公钥密码算法它是基于大合数的质因子分解问题的困难性RSA算法是一种分组密码，明文和密文是0到n-1之间的整数，通常n的大小为1024位二进制数或309位十进制数.2024/4/5Ch1-公钥密码技术12算法描述

1.密钥的产生

随机选择两个大素数p,q

计算n=p×q计算秘密的欧拉函数

(n)=(p-1)(q-1)选择e使得1<e<

(n)，且gcd(e,

(n))=1解下列方程求出d

ed

≡1mod

(n)，且0≤d≤n

公开公钥：PU={e,N}保存私钥：PR={d,p,q}2024/4/5Ch1-公钥密码技术132.加密过程加密时明文以分组为单位进行加密，每个分组m的二进制值均小于n，对明文分组m作加密运算：c=memodn,且0≤m<n3．解密过程密文解密m=cd

modn

4.签名过程计算签名s=mdmodn5．签名验证过程签名验证m=se

modn2024/4/5Ch1-公钥密码技术14例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，类似可以求出其他明文。2024/4/5Ch1-公钥密码技术15RSA算法的安全性

RSA密码体制的安全性是基于分解大整数的困难性假设RSA算法的加密函数c=memodn是一个单向函数，所以对于攻击者来说，试图解密密文是计算上不可行的对于接收方解密密文的陷门是分解n=pq，由于接收方知道这个分解，他可以计算

(n)=(p-1)(q-1)，然后用扩展欧几里德算法来计算解密私钥d。对RSA算法的攻击有下面几个方法：穷举攻击，数学攻击，选择密文攻击，公共模数攻击，计时攻击

2024/4/5Ch1-公钥密码技术16最基本的攻击是穷举攻击，也就是尝试所有可能的私钥数学攻击的实质是试图对两个素数乘积的分解计时攻击也可以用于对RSA算法的攻击。计时攻击是攻击者通过监视系统解密消息所花费的时间来确定私钥。时间攻击方式比较独特，它是一种只用到密文的攻击方式2024/4/5Ch1-公钥密码技术17ElGamal密码

ElGamal是1985年由T.EIGamal提出的一个著名的公钥密码算法该算法既能用于数据加密也能用于数字签名其安全性是依赖于计算有限域上离散对数这一难题2024/4/5Ch1-公钥密码技术181.密钥产生任选一个大素数p，使得p-1有大素因子，g是模p的一个本原根，公开p与g。使用者任选一私钥x，x∈[0,p-1]计算公钥公开公钥：y,p,g保密私钥：x2024/4/5Ch1-公钥密码技术192.加密过程对于明文m，选取一个r，r∈[0,p-1]计算则密文为3.解密过程先计算再计算出明文2024/4/5Ch1-公钥密码技术204.签名过程假设对消息m签名，任选一个随机数k，使k∈[0,p-1]计算签名为(5)签名验证过程

2024/4/5Ch1-公钥密码技术21需要说明的是，为了避免选择密文攻击，ElGamal是对消息m的hash值进行签名，而不是对m签名与RSA方法比较，ElGamal方法具有以下优点：(1)系统不需要保存秘密参数，所有的系统参数均可公开；(2)同一个明文在不同的时间由相同加密者加密会产生不同的密文但ElGamal方法的计算复杂度比RSA方法要大。2024/4/5Ch1-公钥密码技术22椭圆曲线密码

大多数公钥密码系统都使用具有非常大数目的整数或多项式，计算量大人们发现椭圆曲线是克服此困难的一个强有力的工具椭圆曲线密码体制(Ellipticcurvecryptosystem,ECC)的依据是定义在椭圆曲线点群上的离散对数问题的难解性椭圆曲线系统第一次应用于密码学上是于1985年由Koblitz与Miller分别提出两个较著名的椭圆曲线密码系统；一是利用ElGamal的加密法，二是Menezes-Vanstone的加密法2024/4/5Ch1-公钥密码技术23椭圆曲线的定义

在实数系中，椭圆曲线可定义成所有满足方程E:y2=x3+ax

+b的点(x,y)所构成的集合若x3+ax

+b没有重复的因式或4a3+27b2≠0，则E:y2=x3+ax

+b能定义成为一个群椭圆曲线是连续的，并不适合用于加密必须把椭圆曲线变成离散的点，即将椭圆曲线定义在有限域上密码学中关心的是有限域上的椭圆曲线

2024/4/5Ch1-公钥密码技术24椭圆曲线密码体制中使用的变元和系数均为有限域中元素的椭圆曲线密码应用中所使用的两类椭圆曲线是定义在素域Zp上的素曲线(primecurve)和在GF(2m)上构造的二元曲线对于素域Zp上的素曲线，我们使用三次方程，其中的变量和系数在集合{0,1,2,…,p-1}上取值，运算为模p运算对于在GF(2m))上的二元曲线，变量和系数在GF(2m)内取值，且运算为GF(2m)里的运算2024/4/5Ch1-公钥密码技术25密码系统在素域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，2024/4/5Ch1-公钥密码技术26椭圆曲线有一个特殊的点，记为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)2024/4/5Ch1-公钥密码技术27椭圆曲线上的两个相异的点相加与双倍(doubling)的点P的几何含义如下。两个相异的点相加：假设P和Q是椭圆曲线上两个相异的点，而且P不等于-Q。若P+Q=R，则点R是经过P、Q两点的直线与椭圆曲线相交的唯一交点的负点。如图4.5所示。双倍的点P：令P+P=2P，则点2P是经过P的切线与椭圆曲线相交之唯一交点的负点。如图所示。2024/4/5Ch1-公钥密码技术28两个相异点相加和双倍点

2024/4/5Ch1-公钥密码技术29椭圆曲线运算规则

1.椭圆曲线在素域Zp上的运算规则说明一点，在椭圆曲线运算中，大写参数表示点，小写参数表示数值。加法规则：

2024/4/5Ch1-公钥密码技术30其中乘法规则：2024/4/5Ch1-公钥密码技术31椭圆曲线在GF(2m)上的运算规则

加法规则：

2024/4/5Ch1-公钥密码技术32乘法规则：2024/4/5Ch1-公钥密码技术33椭圆曲线密码算法椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合，连同一个定义的加法运算构成一个Abel群在等式kP

=P+P+…+P=Q中，已知k和点P求点Q比较容易，反之已知点Q和点P求k却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题(EllipticCurveDiscreteLogarithmProblem,ECDLP)椭圆曲线密码算法正是利用这个困难问题而设计的2024/4/5Ch1-公钥密码技术34ElGamal的椭圆曲线密码算法

(1)密钥产生假设系统公开参数为一个椭圆曲线E及模数p。使用者执行：任选一个整数k，任选一个点，并计算公钥为，私钥为k。2024/4/5Ch1-公钥密码技术35(2) 加密过程令明文M为E上的一点。首先任选一个整数，然后计算密文密文为两个点。(3) 解密过程计算明文2024/4/5Ch1-公钥密码技术36Menezes-Vanstone椭圆曲线密码算法

Menezes-Vanstone椭圆曲线密码算法是效率比较高的椭圆曲线加密法其明文没有限制一定要落于椭圆曲线E上2024/4/5Ch1-公钥密码技术372024/4/5Ch1-公钥密码技术38椭圆曲线密码的性能

椭圆曲线密码体制的安全性是建立在椭圆曲线离散对数的数学难题之上椭圆曲线离散对数问题被公认为要比整数分解问题(RSA方法的基础)和模p离散对数问题(DSA算法的基础)难解得多目前解椭圆曲线上的离散对数问题的最好算法是Pollardrho方法，其计算复杂度上是完全指数级的，而目前对于一般情况下的因数分解的最好算法的时间复杂度是亚指数级的ECC算法在安全强度、加密速度以及存储空间方面都有巨大的优势。如161位的ECC算法的安全强度相当于RSA算法1024位的强度2024/4/5Ch1-公钥密码技术39SM2SM2是国家商用密码管理局于2010年12月17日发布的公钥算法。它是基于椭圆曲线点群上的离散对数问题的难解性。一个合适的椭圆曲线应具有的性质为：

--有限域上椭圆曲线在点加运算下构成有限交换群，且其阶与基域规模相近；

--类似于有限域乘法群中的乘幂运算，椭圆曲线多倍点运算构成一个单向函数。在多倍点运算中，已知多倍点与基点，求解倍数的问题称为椭圆曲线离散对数问题。

2024/4/5Ch1-公钥密码技术40SM2公钥算法选择素域Fp的椭圆曲线。素域Fp的特征为：p是奇素数p，素域中的元素用整数0,1,2，···，p−1表示。a)加法单位元是整数0；b)乘法单位元是整数1；c)域元素的加法是整数的模p加法，即若a，b∈Fp，则a+b

=(a+b)modp；d)域元素的乘法是整数的模p乘法，即若a，b∈Fp，则a·b=(a·b)modp。

SM2推荐素域Fp(p是大于3的素数)上的椭圆曲线方程为：y2=x3+ax+b，a，b∈Fp，且(4a3+27b2)modp≠0。有限域上的椭圆曲线E(Fp)定义为：

E(Fq)={(x，y)|x，y∈Fp，且满足上式}∪{O}，其中O是无穷远点。2024/4/5Ch1-公钥密码技术41椭圆曲线E(Fp)上的点的数目用#E(Fq)表示，称为椭圆曲线E(Fp)的阶。有限域Fq上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P(非无穷远点)的坐标表示为P=(xP，yP)，其中xP，yP为满足一定方程的域元素，分别称为点P的x坐标和y坐标。

2024/4/5Ch1-公钥密码技术42SM2密钥对生成输入：一个有效的Fq(q

=p且p为大于3的素数，或q=2m)上椭圆曲线系统参数的集合。输出：与椭圆曲线系统参数相关的一个密钥对(d，P)。a)用随机数发生器产生整数d∈

[1，n−2]；b)G为基点，计算点P=(xP，yP)=[d]G；c)密钥对是(d，P)，其中d为私钥，P为公钥。其中[d]G表示椭圆曲线上点G的d倍点

2024/4/5Ch1-公钥密码技术43公钥的验证

输入：一个有效的Fp(p>3且p为素数)上椭圆曲线系统参数集合及一个相关的公钥P。输出：对于给定的椭圆曲线系统参数，若公钥P是有效的，则输出“有效”；否则输出“无效”。a)验证P不是无穷远点O；b)验证公钥P的坐标xP和yP是域Fp中的元素；(即验证xP和yP是区间[0;p−1]中的整数。)

c)验证；

d)验证[n]P=O；

e)如果通过了所有验证，则输出“有效”；否则输出“无效”。2024/4/5Ch1-公钥密码技术44加密算法设需要发送的消息为比特串M，klen为M的比特长度。对明文M进行加密运算步骤如下：A1：用随机数发生器产生随机数k∈[1,n-1]；A2：计算椭圆曲线点C1=[k]G=(x1,y1)，将C1的数据类型转换为比特串；A3：计算椭圆曲线点S=[h]PB，若S是无穷远点，则报错并退出；A4：计算椭圆曲线点[k]PB=(x2,y2)，将坐标x2、y2

的数据类型转换为比特串；A5：计算t=KDF(x2||y2,klen)，若t为全0比特串，则返回A1；A6：计算C2=M⊕t；A7：计算C3=Hash(x2||M||y2)；A8：输出密文C=C1||C2||C3。

2024/4/5Ch1-公钥密码技术45解密算法

klen为密文中C2的比特长度。对密文C=C1||C2||C3

进行解密的运算步骤如下：B1：从C中取出比特串C1，将C1的数据类型转换为椭圆曲线上的点，验证C1是否满足椭圆曲线方程，若不满足则报错并退出；B2：计算椭圆曲线点S=[h]C1，若S是无穷远点，则报错并退出；B3：计算[dB]C1=(x2,y2)，将坐标x2、y2的数据类型转换为比特串；B4：计算t=KDF(x2||y2,klen)，若t为全0比特串，则报错并退出；B5：从C中取出比特串C2，计算M′=C2⊕t；B6：计算u=Hash(x2||M′||y2)，从C中取出比特串C3，若u≠C3，则报错并退出；B7：输出明文M′。2024/4/5Ch1-公钥密码技术46公钥分配公钥密码体制的密钥分配与对称密码体制的密钥分配有着本质的差别对称密码体制的密钥分配中必须同时确保密钥的秘密性、真实性和完整性公开密钥密码体制中有两个密钥，私钥由自己保管，不需要进行分配公钥密码体制不需要保证公钥的秘密性,只需确保公钥的真实性和完整性，这样就能保证公钥没有被攻击者替换或篡改公钥的分配方法可归纳为四种：公开发布、公用目录表、公钥授权和公钥证书。2024/4/5Ch1-公钥密码技术47公开发布公开发布指用户将自己的公钥发给其他用户，或广播给某一团体这种方法虽然简单，但有一个较大的缺点，即任何人都可伪造这种公开发布如果某个用户假装是用户A并以A的名义向另一用户发送或广播自己的公开钥，则在A发现假冒者以前，这一假冒者可解读所有意欲发向A的加密消息，而且假冒者还能用伪造的密钥获得认证。2024/4/5Ch1-公钥密码技术48公用目录表公用目录表指一个公用的公钥动态目录表公用目录表的建立、维护以及公钥的分布由某个可信的实体或组织承担，称这个实体或组织为公用目录的管理员与第一种分配方法相比，这种方法的安全性更高该方法有以下一些组成部分：(1)管理员为每个用户在目录表中建立一个目录，目录中有两个数据项：一是用户名，二是用户的公开钥。2024/4/5Ch1-公钥密码技术49(2)每一用户都亲自或以某种安全的认证通信在管理者那里为自己的公开钥注册。(3)用户可以随时用新密钥替换现有的密钥。这可能由于自己的公钥用过的次数太多或由于与公钥相关的私钥已泄漏。(4)管理员定期公布或定期更新目录表。例如，像电话号码本一样公布目录表或在发行量很大的报纸上公布目录表的更新。(5)用户可通过电子手段访问目录表。此时，从管理员到用户必须有安全的认证通信。这种方案的安全性明显高于公开发布的安全性，但仍易受到攻击。如果敌手成功地获得管理员的私人密钥，就可伪造一个公钥目录表，以后既可以假冒任一用户又可以监听发往任一用户的消息。2024/4/5Ch1-公钥密码技术50公钥授权与公用目录表类似，假定有一个公钥管理机构来为用户建立、维护动态的公钥目录但同时对系统提出以下要求，即：每个用户都可靠地知道管理机构的公钥，而只有管理机构自己知道相应的私钥图4.7是典型的公钥分配方案，在这个分配方案中完成了两个功能，一是获得需要的公钥；二是双方相互认证2024/4/5Ch1-公钥密码技术512024/4/5Ch1-公钥密码技术52公钥证书公钥授权中的管理机构有可能成为系统的瓶颈，而且由管理机构维护的公钥目录表也易被攻击者篡改。分配公钥的另一方法是公钥证书用户通过交换公钥证书来互相交换自己的公钥公钥证书类似人们使用的纸类证书，如驾驶执照、毕业证等，两者都包括拥有者的属性，可以验证证书一般由第三方发行，这个第三方称为证书权威中心（certificateauthority,CA）。证书由CA