密码学-4公钥加密

第四章公钥加密

4．1概述

4．2RSA公钥加密算法

4．3ElGamal公钥加密算法

4．4椭圆曲线上公钥加密算法公开钥明文密文私钥明文秘密钥秘密钥明文密文明文4．1概述公钥密码与对称钥密码的比较：公钥密码：

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

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

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

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

公钥密码与对称钥密码的应用：公钥密码：产生有效的数字签名，密钥管理；

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

称为混合密码系统。大数分解问题——RSA公钥密码有限域上的离散对数问题——ElGamal公钥密码椭圆曲线上离散对数问题——MV公钥密码单向函数：计算F(m,Kp)＝c容易，但由c计算m不容易。陷门单向函数：如果已知Ks，则由c计算m是容易的。什么样的函数是单向函数？如何利用单向函数、公开钥进行加密？如何嵌入陷门？计算难易——计算复杂性理论为基础；数论困难问题(2)令n＝pq，用户公布n。计算并保密。一、RSA算法：Rivest-Shamir-Adleman(1)选择一对不同的大素数p和q，将p和q保密。(3)选取正整数e，使其满足

e是公开钥。

1.密钥生成4．2

RSA公钥加密算法2.加密过程3.解密过程解密过程的正确性：当m与n不互素时，设m=kp，可得同样结论。例题-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）解密过程：二、RSA的安全性1、RSA的安全性建立在合数n的分解是困难的基础上，如果分解已知，则就能求出密钥d；

2、如果已知，则可得到n的分解p和q；所以p和q以上方程的解，此方程是容易解的。

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

p=2p1+1的素数为安全素数，其中p1为素数。强素数是p-1、p+1都有大素因子p1、p2，并且p11，p21还有大素因子。

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

6、单纯的RSA不能抵抗选择密文攻击。泄漏一些信息，如明文奇偶性，还有：5、随着计算能力的不断增加和因子分解算法能力不断提高，

p和q的选择越来越大。目前较安全的RSA的n一般为1024bit或2048bit。三、模幂和模逆算法模幂算法：例题-2：147＝128＋16＋3

＝10010011

为下一步做准备！x存放中间结果！再如：322mod12=9定理：gcd(a,b)=sa+tb,a和b为正整数。模逆算法：

可以写出迭代算法：

i022010173301211-73例题-1中3-1mod220，可由下表得出：gcd(220,3)=1=220-73*3

3-1mod220=-73=147一、离散对数问题群元素的阶：乘法群中满足的最小正整数m。

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

g称为G的生成元。

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

ElGamal公钥加密算法是域，3和5是它的本原元。例题-3：有限域上的离散对数问题：给定一个素数p和Zp的一个本原元，对于找一个唯一整数使得通常记为例题-4：已知,求对于一般离散对数问题，没有有效算法（多项式时间的）。只有指数时间的算法，所以是困难的…….明文空间为，密文空间为选择大素数p，是一个本原元，p和是公开的；对于任意明文，秘密随机选取一个整数,密文为：随机选择整数，计算，是公钥，d

是私钥；二、ElGamal密码体制

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

3.解密过程

解密变换的正确性：对任意密文明文为（3）用户A想秘密地发送明文M＝11给用户B，A选择一个随机数，并计算（2）用户B选择整数d＝10，作为自己的私钥，计算作为自己的公钥；例题-5：（1）选取素数p＝19，生成元；A将（14，17）发送给B；

（4）B计算

三、ElGamal密码体制的安全性

1、ElGamal是基于有限域上的离散对数困难性；2、素数p至少为300位十进制数；3、p-1至少有一个大素因子。一、有限域上的椭圆曲线(ellipticcurve)

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

系数在实数域上的，称为实数域上的椭圆曲线；系数在有限域上的，称为有限域上的椭圆曲线。椭圆曲线上的点，关于定义的加法，构成交换群。4．4椭圆曲线上公钥加密算法实数域上的椭圆曲线有限域（p为大于3的素数）上的椭圆曲线的点再加上一个无穷远点所组成的集合E。是满足同余方程，其中保证有三个根可以在椭圆曲线上定义加法运算：对于任意点

设PQ直线的方程为：将带入当P≠Q时：根据根和系数的关系：因为PQ和E的第三个交点为：当P＝Q时：的导数为可以证明：椭圆曲线E关于加法构成一个交换群。Euler准则：如果p是一个奇素数，则z是模p的平方剩余当且仅当

如何求出椭圆曲线的加法群？对每个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的一个循环子群，二、Menezes-Vanstone公钥密码体制是G的一个生成元，求满足已知的唯一整数n。加群！

1.密钥生成

设p>3是一个素数，E是有限域上的椭圆曲线，是椭圆曲线上的一个点，并且阶足够大，使得由生成的循环子群中离散对数问题是难解的。p和E以及都公开。M-V公钥密码体制:随机选取整数d，，计算。是公开钥，d是保密的私钥。明文空间为密文空间为

加密时，对于任意明文

秘密随机选取一个整数k，密文为:3.解密过程2.加密过程明文为:解密过程的正确性：

例题-7：前例的椭圆曲线，设，私钥d=7,假设明文x=(9,1),随机选取的k=6,求相应的密文。

解：

计算见后页三、椭圆曲线上公钥密码的特点

优点：同样安全强度下密钥短；速度快。可以应用于计算和存储能力小的智能卡等场合。

1、在一个使用RSA的公开密钥系统中，你截获了一个发给公钥是e＝5，n＝35的用户的密文c＝10，明文是什么？

2、在一个ElGamal公钥密码体制服务系统中，密钥签发中心给用户A建立的ElGamal体制如下：选取素数p=29及

Zp的一个本原元，若交给用户A保存的秘密密

钥d＝7，则在（网络）公共服务器上公布的公开密钥

为（，，）。

（接下页