非对称密码体制

《非对称密码体制》由会员分享，可在线阅读，更多相关《非对称密码体制（53页珍藏版）》请在金锄头文库上搜索。

1、第6章 非对称密码体制6.1 概述o1976年W.Diffie和M.E.Hellman发表了杰出的论文 -密码学的新方向，该文奠定了公开密钥密码 体制的基础。o区别于传统的单密钥密码体制(或称对称密钥密码体 制)，公开密钥密码体制是所谓的双密钥密码体制， 加密密钥可以公开，即任何人都可以用这个公开的 密钥进行加密,而相应的脱密密钥是秘密的，任何第 三者想利用已知的公开密钥求脱密密钥是计算上困 难的。o只有掌握相应的秘密的脱密密钥的人才可以脱密。第6章 非对称密码体制o公钥密码体制由于用户私钥的私有性，公钥密 码在实现数字签名和防抵赖性方面有着巨大的 优势。 注：教材的6.1.1节所述内容基本上

2、都是片面的或 错误的。o记E和D分别为加、脱密变换，m为明文，M为 明文空间，c是密文，C是密文空间。o一个公开密钥密码体制必须满足以下基本要求: （1）脱密的唯一性mM，有D(E(m)=m； （2）实现E和D的有效性存在(低次)多项式时间算法实现加、脱密； （3）安全性从已知的加密变换，求得脱密变换D或与等效的D ，使得mMM,有D(E(m)=m在计算上是 不可行的。其中M是M的一个足够大的子集； （4）可行性任何用户要构造一对加、脱密密钥是容易的，比如 说能使用某种概率多项式时间算法来实现； （5）可交换性C=M，mM，有E(D(m)=m。o其中的可交换性并不是每一个公钥体制所必备的。如果

3、一个公钥体制满足这一条，那么它就可以用 作数字签名。6.2 DH密钥交换协议o系统包括一个大素数p(512比特长度)以及GF(p) 中的本原元g。用户U、V双方要建立共享秘密，步 骤如下： 1. U从ZP-1中产生一个随机数x，计算X=gxmodp， 并将它传送给V； 2. V从ZP-1中产生一个随机数y，计算Y=gymodp， 并将它传送给U； 3. U计算：Yxmodp=gyxmodpV计算：XYmodp=gxymodp 于是U、V双方拥有了共享的秘密K=gxymodp。6.2 DH密钥交换协议oD-H密钥建立协议的安全性基础是计算有限 域上的离散对数是“困难的”问题。o中间人攻击6.2

4、DH密钥交换协议1UV：X=gx modp； 2E(U)V：X=gx modp； 3VE(U)：Y=gy modp； 4E(V)U：X=gx modp； 5U计算Xx modp=gxx modp，V计算Xy modp=gyx modp，E计算Xx modp=gxxmodp，Xy modp=gyx modp。 于是，U和E共享gxx modp=ku，V和E共享gyx modp=kv， 其中E表示攻击者，E(U)和E(V)分别表示E冒充U和V。 6.3 RSA公钥密码体制及其实现o公钥RSA密码体制是1978年由美国麻省理工学院的 M.Rivest，A.Shamir和L.Adlman三人提出的，它

5、是 建立在大合数分解是计算上不可行基础上的公钥密码体 制。1. RSA公钥密码体制及其工作过程o记ZN*=a:aZN,(a,N)=1，容易证明ZN*对模乘法 构成一个交换群，称为模N乘群。o引理 设p和q是两个不同的素数，N=pq，则mZN 以及任意的非负整数k，有 mk(N)+1=m modN 证明 若p不整除m，由欧拉定理mp-1=1 modp，从而有6.3 RSA公钥密码体制及其实现mk(N)+1=m modp 若p整除m，则m=0 modp，从而仍然有 mk(N)+1=m modp 因此对于任意的m，恒有 mk(N)+1=m modp 同理可证对于任意的m，恒有 mk(N)+1=m m

6、odq 由于p和q是两个不同的素数，从而有mk(N)+1=m modNo下面我们介绍RSA的原理及工作过程 （1）首先随机选取两个大素数p和q，pq，并计 算出 N=pq及(N)=(p-1)(q-1)； （2）选取加密指数e:(e,(N)=1，并利用欧几 里德算法求出的逆元d(de)，使得 ed=1 mod(N) 其中d脱密指数； （3）公开密钥：N和e； （4）秘密密钥：d和（p、q）。6.3 RSA公钥密码体制及其实现（5）加密过程如果A要向某用户B传送消息，则A利用B用户公开 的加密密钥，计算 c=me modN 将c传送给用户B ； （6）脱密过程用户B接收到密文c之后，利用自己秘密的

7、脱密密钥 d，计算 cd modN 从而得到m=cd modN。例：B选择素数p=7，q=17，则 N=pq=119，(N)=(7-1)(17-1)=96 B选择加密指数e=5，这里5与96互素，由欧几里 德算法得到 (N)=19e+1，即1(N)+(-19e)=1 因此d=-19=77 mod(N)，于是 e=5和N=119是B的公钥，d=77是B的私钥。o现假设A想发送明文m=19给B，A计算： c=me modN=195 mod119=66 并将c发送给B，B收到后，计算： cd modN=6677 mod119=19 从而得到明文m。 6.3 RSA公钥密码体制及其实现2. RSA公钥

8、密码体制的实现o从目前的密码分析水平来看,要想实现一个安全的RSA 公钥密码体制,大合数的规模至少要在1024比特以上， 因此是否存在有效的随机产生大素数的算法以及RSA在 这种规模下的加、脱密运算的速度等问题自然提了出来 。 （1）产生大素数的算法o判定一个非负整数是否为素数的工作称为素性检测，我 们介绍Rabin提出的有效的产生素数的概率算法-素 性检测算法，这个算法的原理基于欧拉定理，即： 6.3 RSA公钥密码体制及其实现aZn*，有a(n)=1 modn。而当n是素数时，有an1=1 modn 设n2，则n是奇数，令n-1=2eu，其中2不能整除u， 这样上式变为:则下式至少有一个成

9、立： au=1 modn 或存在一个i(0ie-1)，使得o由此Rabin引入了素性集：o判定n是素数的算法如下： step1：任取一个大奇数n； Step2：取a2,3,n-1； Step3：如果(a,n)=1，且a不属于Pn，则n是素数，否则 n是合数。oRabin证明了由上述算法所产生的素数的误判概率为 o根据这个结论,我们将算法中的第(2)和(3)步骤重复k次 ，这样判定n为素数的误判概率小于或等于4-k。关于这 一点的证明请参看相关文献。6.3 RSA公钥密码体制及其实现（2）有关RSA算法实现的几个问题o关于加法、减法和乘法按照系统指令所能支持的最大的字展开进行运算。o利用窗口法进

10、行指数运算 以512比特加密指数为例：其中 加密过程为：me modN=6.3 RSA公钥密码体制及其实现o在上述计算过程中，对e是按比特进行处理的， 为加快实现速度，我们可以对e按两位或三位进 行处理(这取决于模数的规模和运算的软、硬件 环境)，以两位为例得到:其中o当要对明文进行加密时，可先进行预处理，计 算出和,这种方法我们称之为窗口法。通过实验 证明，这种方法对提高RSA的加、脱密速度是 十分有效的。 o模数处理方法第一种方法：先预计算模数N的倍数；第二种方法：直接进行除法运算；第三种方法：蒙哥马利方法。o提高脱密运算速度的一种方法 普通的脱密运算为m=cd modN，现在记 c1=c

11、 modp，c2=c modq d1=d mod(p-1)，d2=d mod(q-1) m1=m modp，m2=m modq 则由c1、c2、d1、d2求得利用孙子定理，由同余式组即可求出明文m。6.3 RSA公钥密码体制及其实现oRSA设计的基本要求以及安全性分析 1. RSA设计的基本要求 （1）p和q不能太接近o由于 (p+q)2=4N+(p-q)2 如果p和q太接近，则|p-q|就相对地较小，这样我 们就可以通过穷尽p-q，求出p+q，从而得到p 和q。o注意开平方运算存在多项式时间算法。 6.3 RSA公钥密码体制及其实现（2）p+1、p-1和q+1、q-1不能有太多的小因子，必须

12、 存在大的素因子o如果p+1、p-1和q+1、q-1由小的素因子乘积而得， 我们就可以通过穷尽小素数的方法，根据已知的N，有 可能求出p和q。o由此，在许多的场合都要求p和q是安全素数定义：设p是素数，p2，p=2p1+1，若p1仍然是素 数，则称p是安全素数。 （3）脱密指数d应满足o否则，可由连分数的方法进行攻击。o另外，还可能要求加密指数e为错乱指数。 6.3 RSA公钥密码体制及其实现（4）模数规模o从目前的攻击水平看,模数的位数应至少设计在1024比 特以上,取2048比特更为安全。o这种增加的安全性是以牺牲运算速度和增加软硬件资源 为代价的。 2. RSA公钥密码体制的安全性分析

13、结论1: 求(N)的难度与分解N的难度等价。证明：如果能分解N，则就可以求出(N)。反之，如果 能求出(N)，则由(p+q)=N-(N)+1，以及pq=N 或 ，便可求出p和q。6.3 RSA公钥密码体制及其实现结论2: 求脱密指数d的难度与分解N等价。该定理的证明比较复杂，这里略去。 结论3: 求(N)的难度与分解N等价。 结论 4: 能够猜出1比特明文信息的难度与猜出整个明 文的难度等价。 结论 5: 由非平凡不动点可能分解N。o所谓不动点,即使得me=m modN明文m。o显然对于任意的RSA体制，m=0,1,-1均为其不动 点，这些不动点，被称为平凡不动点。o该结论 的证明与结论 2的

14、证明过程类似。 3. 共模RSA公钥密码体制的安全性分析o如果若干个用户同时共用相同的合数N(即共模)，那么 这时的RSA体制安全性又有其新的特点。 结论1: 已知一对加、脱密指数时，即可分解公用的模数 N。 这一结论的证明与结论2的证明过程类似。 结论2: 已知一对加、脱密指数时，不分解也可以求出其 它用户等价的脱密密钥。 如果已知加、脱密密钥eA和dA，则可求出eAdA-1，而 eAdA-1是(N)的倍数，从而可由公开的其它用户的加 密密钥eB，求出等价的脱密密钥dB。 3. 共模RSA公钥密码体制的安全性分析结论3: 通播信息是不安全的。如果某一用户向n个其它用户发送相同的消息m，于是

15、攻击者就可以得到： c1=me1 ，c2=me2 ，cn=men modN如果n比较大。我们就有很大的可能性找到两个互素的 加密指数，设为ei和ej满足(ei,ej)=1，于是存在s和t， 使得eis+ejt=1，这样就可以由截获的密文ci和cj通过 下式： ciscjt=meismejt=m modN 从而得到明文。 6.4 非对称密码体制-椭圆曲线密码体制(ECC)o椭圆曲线的概念与分类椭圆曲线是一个具有两个变元的三次方程，它 是满足 y2+axy+by=x3+cx2+dx+e的所有点(x,y)的集合，外加一个零点或无穷远 点。 6.4 非对称密码体制- ECC1有限域GF(p)上的椭圆曲

16、线 y2=x3+ax+b modp 其中a,bGF(p),x,y均在GF(p)中取值。定理：(Hasse定理)如果E是定义在GF(p)上的椭圆曲 线，N是E上的点的个数，则 |N-(P+1)|2p1/2 6.4 非对称密码体制- ECC例：GF(23)上的一个椭圆曲线为y2=x3+x mod23，则该 方程在GF(23)上的解（即该椭圆曲线上的点）为 (0,0),(1,5), (1,18), (9,5), (9,18), (11,10), (11,13), (13,5), (13,18), (15,3), (15,20), (16,8), (16,15), (17,10), (17,13), (18,10),(18,13), (19,1), (19,22), (20,4), (20,19), (21,6), (21,1