《应用密码学》课件第5章.pptVIP

第5章非对称密码体制

5.1概述

5.2数学基础

5.3非对称密码体制概述

5.4RSA密码算法

5.5ElGamal密码算法

5.6椭圆曲线密码体制

5.7RSA、ElGamal及椭圆曲线密码比较

5.8其他非对称密码体制简介

5.1概述

通过前面的学习，我们对分组密码和序列密码都有了一

定的了解。众所周知，两个用户在用对称密码体制进行必威体育官网网址

通信时，必须要有一个双方共享的密钥。那么，如何才能让

两个不在同一个地方的用户安全地拥有共享密钥呢？我们可

能想到的方式有：

（1）派一个人来传递；

（2）通过邮件传递；

（3）用电话或电报等方式传递。

首先我们要清楚，通过第三种方式传递是不安全的，因

为在没有共享密钥前，双方只能用明文的方式进行通信，显

然是不安全的；第二种方式的时间需求比较大；第一种方式

从时间和代价上来看，都难以符合需要。在非对称密码体制

产生前，用得较多的解决办法就是第二种方式，但效率是比

较低的。那么如何才能有效地解决这个问题，以用较小的代

价、较高的效率实现通信双方的密钥传递呢？正是由于这个

需求，促使了非对称密码体制的产生。

5.2数学基础

xb1(modm1)



xb(modm)

22

...



xbn(modmn)

的解为：

例5－1韩信点兵。有兵若干，若列成5行纵队，则末

行1人，若列成6行纵队，则末行5人，若列成7行纵队，则末

行4人，若列成11行纵队，则末行10人，求兵数。

解：由题意得

x≡1(mod5)，x≡5(mod6)，x≡4(mod7)，x≡10(mod11)

令m1＝5，m2＝6，m3＝7，m4＝11，b1＝1，b2＝5，b3＝4，b4＝10。则

m＝2310，M1＝462，M2＝385，M3＝330，M4＝210

5.2.2离散对数

基于离散对数难题的密码学算法和应用比较多，从最开

始的密钥交换算法DH(DiffieHellman)算法、ElGamal加密

算法，到后来作为美国国家数字签名标准的

DSA(DigitalSignatureAlgorithm)算法，后面介绍的Schnorr

盲签名算法，以及很多特殊的签名算法，都是以离散对数难

题为基础进行构造的。因此，掌握和理解离散对数的相关知

识很重要。

设p为奇素数，对于整数g，1gp，使得g?≡1(modp)

成立的最小正整数如果是p-1,则g就是模p的原根。

5.2.4勒让得符号

设p为奇素数，a为整数，定义勒让得(Legendre)符号为：

1,若a是模p的平方剩余

a

-1，若a是模p的平方剩余

p

0，若p|a

若需对勒让得符号的性质有更进一步的了解，读者可以

参考其他有关初等数论的书籍。通过计算勒让得符号，容易

判断二次方程x2≡a(modp)(p是奇素数)是否有解。

5.2.5素数的产生

1.Miller-Rabin概率检测算法

Miller-Rabin概率检测算法的理论基础是费尔马定理，

即设n是正奇整数，如果n是素数，由费尔马定理，对于任意

整数b(1bn-1)，有bn-1≡1(modn)。如果n是素数，该等式一

定成立；如果n不是素数，该等式一般不成立。如果n不是素

数而又使得该等式成立，称n为对于基b的拟素数。拟素数表

示不是素数，而是合数。整数63是合数，当b=8时，该等式

成立，称整数63是对于基b=8的拟素数。

由此可知，如果对于整数b(1bn-1)，(n,b)=1,使得

bn-1≡1(modn)不成立，则n是一个合数。

由上面的讨论可知，判断一个正奇整数是不是合数，可

以通过尝试找整数b(1bn-1)，(n,b)=1,看bn-1≡1(modn)成

立与否。如果不成立，则n是一个合数，如果成立，则n可能

是素数，可以通过再找别的整数b(1bn-1)进行尝试。

根据上面的论述，Miller-Rabin概率检测算法的实现思

路可以描述为：计算n-1=2st，则有

s1s2

bn11(b2t1)(b2t1)...(bt1)(bt1)

根据这个原理，