第4章公钥密码技术2

第4章公钥密码技术本章主要内容概述公钥密码提出的背景公钥密码的基本思想公钥密码的应用 RSA公钥密码体制ElGamal公钥密码体制第4章公钥密码技术4.1概述

4.1.1公钥密码提出的背景

1．密钥管理的困难性问题 传统密钥管理任何两个用户要进行通信就需要一个密钥，则n个用户需要n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。

公钥服务器传统对称加密法公钥算法公钥这一概念的真正贡献是，它减少了网络用户必须管理的密钥数。如果使用对称加密法5个用户的网络需要10个保密密钥，每个用户都得记住（并保密）4个密钥。但是在公钥系统中，每个用户只需记住他们自己的私钥，从公共场所查找所需的公钥即可第4章公钥密码技术2．系统的开放性问题

对称密码体制的密钥分发方法要求密钥共享各方互相信任，因此它不能解决陌生人间的密钥传递问题

3．数字签名问题 对称加密算法难以实现抗抵赖的安全需求。第4章公钥密码技术公钥密码学的发展概述

1976年，WhitfieldDiffie和MartinHellman发表了的“Newdirectionsincryptography”。这篇划时代的文章奠定了公钥密码系统的基础。可用于保密通信，也可用于数字签字。这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。自从公钥密码的概念被提出以来，相继提出了许多公钥密码方案，如RSA、背包体制、McEliece、ElGamal体制等。在不断的研究和实践中，有些方案被攻破了，有些方案不太实用。关于最初十年的公钥密码技术的研究和发展，可参见文献[W.Diffie.Thefirsttenyearsofpublic-keycryptography.ProceedingoftheIEEE,76(5),1988,560-577.]。公钥密码学的意义公钥密码学的发展是整个密码学发展历史中最伟大的一次革命公钥密码学和以前的传统密码学完全不同首先，公钥算法是基于数学函数而不是基于替换和置换更重要的是，与只使用一个密钥的对称传统密码不同，公钥密码是非对称的，它使用两个独立的密钥。我们将会看到，使用两个密钥在消息的保密性，密钥分配和认证领域有着重要意义。第4章公钥密码技术关于公钥密码的常见的几种误区第一种误解是从密钥分析角度看，公钥密码比传统密码更安全。从抗密码分析角度看，原则上不能说传统密码优于公钥密码，也不能说公钥密码优于传统密码第二种误解是，公钥密码是一种通用的方法，所以传统密码已经过时。其实不然，由于现有的公钥密码方法所需要的计算量大，所以取代传统密码似乎不太可能。“公钥密码学仅限于用在密钥管理和签名这类应用中，这几乎是已被广泛接受的事实”公钥服务器传统对称加密法公钥算法公钥这一概念的真正贡献是，它减少了网络用户必须管理的密钥数。如果使用对称加密法5个用户的网络需要10个保密密钥，每个用户都得记住（并保密）4个密钥。但是在公钥系统中，每个用户只需记住他们自己的私钥，从公共场所查找所需的公钥即可第4章公钥密码技术4.1.2公钥密码的基本思想

公钥密码也称为非对称密码。使用公钥密码的每一个用户都分别拥有两个密钥：加密密钥与解密密钥，它们两者并不相同，并且由加密密钥得到解密密钥在计算上是不可行的。每一个用户的加密密钥都是公开的。仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的两个密钥中的任何一个都可用来加密，另一个用来解密基于公开密钥的加密过程Joy明文输入加密算法，如RSA等解密算法明文输出Alice的私钥Bob的公钥环TedAliceMikeAlice的公钥密文传输BobAlice加密基于公开密钥的鉴别过程Bob的公钥Joy明文输入加密算法，如RSA等传输密文解密算法明文输出Bob的私钥Alice的公钥环TedBobMikeBobAlice认证对称密码公钥密码一般要求一般要求1.加密和解密使用相同的密钥和相同的算法1.同一算法用于加密和解密，但加密和解密使用不同密钥2.收发双方必须共享密钥2.发送方拥有加密或解密密钥，而接收方拥有另一密钥安全性安全安全性要求1.密钥必须是保密1.两个密钥之一必须是保密的2.若没有其他信息，则解密消息是不可能或至少是不可行的2.若没有其他信息，则解密信息是不可能或至少是不可行的3.知道算法和若干密文不足以确定密钥3.知道算法和其中一个密钥以及若干密文不足以确定另一密钥第4章公钥密码技术单向陷门函数

单向陷门函数可以被定义为如下函数f：（1）给出f的定义域中的任意元素x,f(x)的计算是容易的；（2）给出y=f(x)中的y要计算x时，若知道设计函数f时结合进去的某种信息（该信息称为陷门），则容易计算；若不知道该信息，则难以计算。 设计公钥密码体制可以转换为寻找单向陷门函数。目前人们主要是基于如下的数学上的困难问题来设计单向函数和公钥密码体制：（1）大整数分解问题(如公钥密码体制RSA)；（2）有限域上的离散对数问题(如公钥密码体制ElGamal):（3）椭圆曲线上的离散对数问题(如公钥密码体制ECC)。第4章公钥密码技术4.1.3公钥密码的应用

（1）机密性的实现发送方用接收方的公钥加密消息，接收方用自己的私钥来解密。（2）数字签名发送方用自己的私钥来签名消息，接收方通过发送方对应的公钥来鉴别消息，并且发送方不能对自己的签名进行否认。（3）密钥分发和协商发送方和接收方基于公钥密码系统容易实现在公开信道上的大规模的密钥分发和协商。费马定理和欧拉定理欧拉定理对任意互素的a和n有：aφ(n)=1modnφ(n)是小于n且与n互素的整数的个数费马定理费马定理可如下描述：若p是素数，a是正整数且不能被p整除，则 ap-1≡1（modp）另一种有用的表示形式是：若p是素数且a是任意正整数，则： ap≡a(modp)公钥加密体制:

RSA密码体制 1978年，MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字，易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制。国际上一些标准化组织ISO、ITU、及SWIFT等均已接受RSA体制作为标准。在Internet中所采用的PGP(PrettyGoodPrivacy)中也将RSA作为传送会话密钥和数字签字的标准算法。4.2.1RSA的算法描述（1）密钥的生成

1.选择两个大素数p，q，（p，q为互异素数，需要保密），

2.计算n=p×q，

(n)=(p－1)×(q－1)3.选择整数e使gcd(

(n)，e)=1,1<e<

(n)4.计算d，使d=e－1mod

(n),

得到：公钥为{e,n}；私钥为{d,n}（2）加密(用e，n)：明文：M<n，密文C=Me(modn).（3）

解密(用d，n)：密文C，明文M=Cd(modn)第4章公钥密码技术RSA密码体制1.方案：独立地选取两大素数p1和p2(各100～200位十进制数字)，计算n=p×q，其欧拉函数值

(n)=(p－1)(q－1)。随机选一整数e，1

e<

(n)，(

(n),e)=1。因而在模

(n)下，e有逆元d=e-1mod

(n)，取公钥为n，e。秘密钥为d。

(p,q不再需要，可以销毁。)

加密：将明文分组，各组在modn下可惟一地表示。各组长达200位十进数字。可用明文集Az={x：1

x<n,(x,n)=1}

密文y=xemodn解密：x=yd

modn证明：yd=(xe)d=xde，因为de

1mod

(n)而有de=q

(n)＋1。由欧拉定理，(x,n)=1意味x

(n)

1modn，故有yd=xde=xk

(n)+1

x

xk

(n)=x

1=xmodn陷门函数：Z=(p,q,d)

RSA密码体制(续）RSA算法举例(1)选择两个素数p=7,q=17；(2)计算n=p*q=7*17=119;(3)计算φ(n)=(p-1)(q-1)=(7-1)(17-1)=96(4)选择一个随机整数e=5，且1<e<φ(n)=96，满足gcd(e,φ(n))=1；则公钥Pk=（5，119）；(5)计算d，(d*e)modφ(n)=1,即(d*5)mod96=1，d=77；则私钥Sk=（77，119）；设明文P=19；加密：195mod119=66，传送密文C=66；解密：6677mod119=19，获得明文P=19。第4章公钥密码技术4.2.3RSA的安全性

RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为其困难性至今还未能证明。

若能将n分解为两个素数因子p，q，则可计算

(n)=(p－1)(q

－1)，d=e－1mod

(n)

因此，不难得出结论：破译RSA不会比大整数分解更加困难!

(1)对模n的长度必须足够长，至少为1024比特

(2)p和q的长度应该相差不多；(3)p

1和q

1都应该包含大的素因子；(4)gcd(p

1,q

1)应该很小；(5)d<n1/4。RSA的安全性（续）穷举攻击：这种方法试图穷举所有可能的私钥。数学攻击：有多种数学攻击方法，他们的实质都是试图分解两个素数的乘积。计时攻击：这类方法依赖于解密算法的运行时间。选择密文攻击：这种攻击利用了RSA算法的性质第4章公钥密码技术（1）不同的用户选用的素数不能相同（2）一般不能直接应用RSA进行加解密

由于RSA算法是决定性算法（即对相同的明文始终会给出相同的密文）和具有特殊的代数结构等原因，用RSA算法进行直接加密在很多环境下是不安全的。故在使用RSA进行加密前，需要对明文做某种预处理，一般是进行随机化的填充。4.3ElGamal公钥密码体制

4.3ElGamal公钥密码体制

ElGamal密码体制是T.ElGamal于1985年提出，是最有名的公钥密码体制之一，它的安全性是基于离散对数问题.

1．密钥的生成选取大素数p，g∈Zp*是一个本原元（生成元）。

p、g

作为系统参数所有用户共享。系统中每个用户U都随机挑选一个整数x，2≤x≤p－2，并计算：

y=gx(modp)，

y作为用户U的公开密钥，而x作为用户U的秘密密钥第4章公钥密码技术4.3ElGamal公钥密码体制（续）2.加密：(1)用户A先把明文M编码为一个在0到(p－1)之间的整数m

作为传输的明文；(2)用户A挑选一个秘密随机数r(

2≤r≤p－2)，并计算：c1＝gr(modp)；(3)