密码学教程 课件 -5-公钥密码

第五章公钥密码

5．1概述

5．2RSA公钥加密算法

5．3ElGamal公钥加密算法

5．4椭圆曲线上公钥加密算法

5.5数字签名

5.6

SM2

5.7*后量子密码公开钥明文密文私钥明文秘密钥秘密钥明文密文明文5．1概述公钥密码与对称密码的比较：公钥密码：

不需共享密钥；可证明安全；易产生数字签名;速度慢、密钥长.对称密码：

速度快，密钥短，可作为基本单元构建各种密码

工具,如伪随机数产生器、Hash函数；

需要实现共享密钥，密钥管理困难；不具有（类似公钥的）可证明安全性；对称密码：有效的大量数据加密和一些数据完整性应用。

因速度快（多次迭代轮函数，产生“随机性”）。公钥密码与对称钥密码的应用：公钥密码：产生有效的数字签名，密钥管理；

公钥加密常用于加密对称密钥，这样的系统

称为混合密码系统（密钥封装机制KEM）。主要用于认证主要用于加密

单向函数(OWF--onewayfunction)：

由x计算

y=f(x)是容易的，但反之是计算困难的。计算难易：

以“计算复杂性理论”为基础。数论+计算陷门(trapdoor)单向函数：

有陷门（私钥）可以求f的逆。

用于构造单向函数的（数论）计算困难问题：公钥密码对明文的处理方式：不是像分组密码那样依靠轮函数的多次迭代；公钥密码是依靠计算困难问题（构成的单向函数）。计算都是在一个代数结构中进行的，例如：

密码的安全性在于：由公钥找不到私钥；不知道私钥，由密文找不到明文。

一个155位十进制长（约500比特）的整数：1999年（网络）分解为：当今分解技术更强。目前RSA的n至少1024比特长。同样，ElGamal算法的素数p也应较大。128个字节。而AES的一个分组只16个字节2002年图灵奖5．2

RSA公钥加密算法第一个公钥算法1978年

一、RSA算法：Rivest-Shamir-Adleman(1)选择一对不同的大素数p和q，将p和q保密。

1.密钥生成

2.加密过程3.解密过程解密过程的正确性：上面最后一个等式是因为：当m与n互素时，由欧拉定理可得；

这里是模q例题-1：（1）密钥生成：p＝11,q=23,n=pq=11×23=253,

取e=3，gcd(3,220)=1，e为公钥；由扩展欧几里的算法求出3mod220的逆为d=147。（2）加密过程：

对于明文m=165，则密文（3）解密过程：

二、模幂和模逆算法模幂算法：例题-2：只要大于253，就模运算求剩余。因此平方后就进行mod运算。147＝128＋16＋3

＝10010011

为下一步做准备！x存放中间结果！从右到左迭代法！

x=xy

x=xy

x=xy

x=xy

再如：322mod12=9

上面的平方乘算法是“从右到左”，还有“从左到右”：

x的平方相当于指数上左移1位二进制；每次乘以m，速度快

模逆算法：

可以写出迭代算法：

注意商放在哪一行！i022010173301211-73例题-1中3-1mod220，可由下表得出：

gcd(220,3)=1=220-73*3

3-1mod220=-73=147

三、RSA的安全性

所以p和q以上方程的解，此方程是容易解的。

强素数是p-1、p+1都有大素因子p1、p2，并且p1

1，p2

1还有大素因子。

4、e和d的选择

e不能太小，应使其阶最大。d应大于n的长度的1/4。

5、随着计算能力的不断增加和因子分解算法能力不断提高，

p和q的选择越来越大。目前较安全的RSA的n一般为

1024bit或2048bit。3、p和q应为安全素数或强素数。

p=2p1+1的素数为安全素数，其中p1为素数。

6、单纯的RSA不能抵抗选择密文攻击。泄漏一些信息，如明文奇偶性，还有：同态特性

解：7101501221-11-23

161=7*23gcd(27,161)=1一、离散对数问题群元素的阶：乘法群中满足的最小正整数m。

称为g在群中的阶。是乘法群，群的阶为6。循环群：群G的每一个元都是G的某一个固定元g的乘方。

g称为G的生成元。

本原元：循环群中的生成元称为域的本原元。性质：域的乘法群是一个循环群！5．3

ElGamal公钥加密算法群中元素的个数。是域，3和5是它的本原元。例题-3：

例题-4：

对于一般离散对数问题，没有有效算法（多项式时间的）。只有指数时间的算法，所以是困难的…….

明文空间为，密文空间为

对于任意明文，秘密随机选取一个整数,密文为：

二、ElGamal密码体制

1.密钥生成2.加密过程

3.解密过程

对任意密文明文为（1）选取素数p＝19，生成元

g=2

；

例题-5：A将（14，17）发送给B；

三、ElGamal密码体制的安全性

2、素数p至少为300位十进制数；3、p-1至少有一个大素因子。

数论算法举例：1、Miller-Rabin素性检测算法2、Pollard整数分解算法3、二次筛和数域筛分解算法4、Baby-step-giant-step离散对数算法5、Pohlig–Hellman离散对数算法6、椭圆曲线（ECC）的方法7、类群（class

group）方法

等等（算法数论）一、有限域上的椭圆曲线(ellipticcurve)

椭圆曲线就是方程所确定的平面曲线。经过坐标变换可转化为

系数在实数域R上的，称为R上的椭圆曲线；（画图）

椭圆曲线上的点，关于定义的加法，构成交换群。5．4椭圆曲线上公钥加密算法系数域的特征不是2，3实数域上的椭圆曲线才能画出连续的曲线有限域（p为大于3的素数）上的椭圆曲线：由点再加上一个无穷远点------所组成的集合E。保证有三个根可以在椭圆曲线上定义加法运算：对于任意点

设PQ直线的方程为：将带入当P≠Q时：

根据根和系数的关系：因为PQ和E的第三个交点为：可以证明：椭圆曲线E关于加法构成一个交换群。当P＝Q时：的导数为

如何求出椭圆曲线的加法群？对每个x，计算再求同余方程：

阶的证明例题-6：设p＝11，E是由下列方程确定的Z11上的椭圆曲线。试确定E的所有点。06681874258933974810454是否平方剩余06No18No25Yes4，733Yes5，648No54Yes2，968No74Yes2，989Yes3，897No104Yes2，900112439455363758994101或者：所以E的所有点为：

(2，4),(2，7),(3，5),(3，6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9),再加上无穷远点O，共13个点。

设，计算：（5,2）同样可计算：所以，的阶是13，是循环群E的生成元。

椭圆曲线上的离散对数问题：设p>3是一个素数，E是有限域上的椭圆曲线，

设G是E的一个循环子群，二、椭圆曲线ElGamal公钥密码体制是G的一个生成元，求满足已知的唯一整数n。加群！

ECC-ElGamal公钥密码体制:

加群的阶数

系数不是模p，而是模加群的阶数

三、椭圆曲线上公钥密码的特点

5.5数字签名概述在密码学中利用数字签名和认证技术来实现信息完整性、认证性和不可否认性等。

发布消息（电子政务）电子银行（电子商务）

用户记帐（（支出＋日期）的签名）电子现金（银行的签名）电子合同：

（条款＋日期）的签名假定A发送一个对消息M的数字签名给B，A的数字签名应该满足下述三个条件：（1）

B能够证实A对消息M的签名；（可验证性）（2）

任何人都不能伪造A的签名；（不可伪造性）（3）如果A否认对消息M的签名，可通过仲裁解决A与B之间的争议。（不可否认性、可仲裁性）Signature利用对称钥加密可以实现签名，但需要一个可信第三方（TTP－TrustedThirdParty）

所以一般的签名指得是公钥体制实现的签名：知道A和B的密钥！利用私钥签名；利用公钥验证。附加功能的签名：盲签名、群签名、代理签名、指定验证者签名等等。数字签名方案的三个部分：（1）密钥生成：

生成签名者所需的公私钥对；（2）签名过程：

对于m，利用私钥进行签名s=S(m)，输出(m,s)；（3）验证过程：

验证者验证签名，如果验证方程成立，则承认该签名；

否则拒绝。签名的实现过程：签名算法(m,s)私钥待签名的消息摘要编码Hash

验证算法公钥合格

一、RSA签名方案实用中，如果A要求向B传送加密的消息-签名对，则A必须发送

而B收到密文后首先应当解密，得到A的消息-签名对。

之后，B再验证A的签名是否有效。

签名后再加密，即签密方案（二步合在一起的专用方案）。

（1）若你截获由A发给B的密文C=86，试求明文M；（2）若A对消息M进行签名S，并发给B，试求签名S；（3）若B收到了加密的签名，求原来的明文和签名是什么？如何判断它的正确性？在一个RSA公钥密码体制中，已知A的公开密钥是

B的公开密钥是例题-8：解：（1）（注意：为防止算错，应对求逆结果进行验证！）（2）（3）

可分别验证与前面的结果一致。

i11=1011

0123

i7=111

012

i13=1101

0123（2）如果消息的签名分别是，则任何知道的人都可以伪造对于消息的签名

RSA签名的安全性：

(1)对于任意，任何人都可以计算所以任何人都可以伪造对于随机消息x

的签名；（3）当消息较大时，先将消息进行hash函数变换。同样前两项的问题，也可以利用hash函数来解决。1.密钥生成产生一个随机大素数p，和一个乘法群的生成元g；选择一个随机数x，1≤x≤p-2，计算：y是公开密钥（或者（p，g，y））；私钥是x。2.签名过程设m是待签名的消息，选择秘密随机数k：二、ElGamal签名方案

3.验证过程

处于指数位置的量

例题-9：ElGamal签名（2）签名过程

若A对消息m=5进行签名，秘密选取k=9（1）密钥生成设p＝11，g＝2是Z11的本原元，选x＝8，则（3）验证过程

所以签名为（6，3）。三、Schnorr签名方案

（使用Hash）1.密钥生成过程

/∫no:r/

2.签名过程3.验证过程

mod

q形成指数位置上的数加密签名RSAElGamalECC

5.6、SM22012年3月颁布中华人民共和国密码行业标准GM/T0003-2012：《SM2椭圆曲线公钥密码算法》，共含5个文件，其中包含由椭圆曲线实现的数字签名、密钥协商和公钥加密三个算法。SM2数字签名算法（基于身份的密码（标识密码））

系统参数：

签名者A对消息M的签名过程为：

我国商用密码标准SM9（2016/3）：

基于身份的密码（标识密码）；

利用椭圆曲线上双线性对实现，也分数字签名、密钥协商和公钥加密三个算法。美国NIST-PQC签名算法（2022/8）：

CRYSTALS-Dilithium

Falcon

SPHINCS+5.7*

后量子密码PQC

postquantumcryptography能抵抗量子攻击的密码，也称抗量子计算密码。量子算法：

Shor算法：利用量子傅里叶变换求元素阶数，

可有效求解大数分解、离散对数等问题；

Grover算法：在集合中搜索指定元素，

可比经典搜索时间指数上快1/2；

Simon算法：有效求出周期函数的周期f(x)=f(x+s)