《新编密码学》课件第5章 公钥密码

5.1公钥密码体制的基本原理

公钥密码学解决的两个问题：密钥分配数字签名起源

1976年两位美国密码学者W.Diffie和M.Hellman在该年度的美国国家计算机会议上提交了一篇名为“密码学的新方向（NewDirectionsinCryptography）”的论文，文中首次提出了公钥密码体制的新思想。它为解决传统经典密码学中面临的诸多难题提供了一个新的思路。公钥密码的基本思想

密钥分成两个部分：公开密钥（简称公钥）用于消息的加密，公开的私有密钥（简称私钥）用于消息的解密，秘密的

公钥密码体制

双钥密码体制（非对称密码体制）

传统的经典密码体制

单钥密码体制（对称密码体制）公钥密码体制的基本流程发送方加密算法密钥空间接收方解密算法

C

AB公钥算法应满足的要求公钥密码体制：

M

：明文

C

：密文

K

：密钥对

E：加密变换

D：解密变换（续）

1）K中每一个公私密钥对，在E中存在：一个加密变换：一个解密变换：

使得，任意明文消息均可以找到一个唯一的；满足：（续）

2）对于任意的公私钥对，加密变换和解密变换都是多项式可计算的函数。知道公钥的情况下推知私钥是计算上不可行的。

公钥体制的核心：

加密变换和解密变换的设计

在密码算法中，加解密变换是互逆的，由条件2）知在公钥密码体制中加解密变换不能简单的直接互推。

用陷门单向函数构造公钥密码体制

注陷门单向函数

思想：

一个可逆函数，对于定义域中的任意满足：计算函数值是容易的；由求在计算上是不可行的，除非知道某些辅助信息（称为陷门信息）；一个可行的公钥算法应满足的要求（续）小结公钥密码体制通常将其安全性建立在某个尚未解决（且尚未证实能否有效解决）的数学难题的基础上。

好处：

简化了密钥分配任务；对密钥协商与密钥管理，数字签名与身份认证产生了深刻的影响；是密码学发展史上的一次革命；5.2背包算法

起源：

R.Merkle和M.Hellman在1978年根据组合数学中背包问题提出第一个公钥密码算法。又称为MH背包算法。

背包问题

设有一堆物品，体积各不相同，问能否从这堆物品中找出几个正好装满一个给定容量的背包？（假定物品之间不留空隙）数学描述：

记物品的体积分别为，背包的容量为C，则背包问题可表示为：其中，等于1或者0。

表示第i个物品在背包中；

表示第i个物品不在背包中；称物品体积的序列为背包向量。

（续）理论上讲，通过检查背包向量的所有子集，计算出每个子集的元素之和，总可找出一个子集作为背包问题的解，因此背包问题又称为子集和问题。事实上，背包问题是一类完全（）问题。有一类特殊的背包问题是容易求解的

超递增背包问题当背包的长度n过大时对全部子集进行穷举式搜索是不可能的超递增背包问题设是一个背包向量，若V满足：则称V是一个超递增向量。

序列就是一个超递增序列。

例：超递增背包问题的解法：

设背包的容量为C，从左到右依次检查超递增背包向量V中的每个元素；

若

，则在解中，对应的应为1，并将C的值更新为；

若

，则不在解中，对应的应为0,C的值保持不变；然后，对依次重复上述过程，并判断C是否减少到0。

C为0，则问题的解存在；

不为0，则问题的解不存在；例5.1故，问题的解为110101。非超递增向量t和k互素，确保t在模k下的乘法逆元存在。令则U是一个非超递增向量。背包算法的描述

思想：

私有密钥设置为：将超递增向量转换为非超递增向量的参数、和；公开密钥设置为：非超递增向量；加密变换：所得结果为密文解密变换：例5.2设V=(1,3,7,13,26,65,119,267)是一个超递增向量；取模数k=523，乘数t=467，则：计算公钥：并对外公布U。（续）

发送方：

有一消息m=10101100,用公钥U对m加密得到密文；（续）接收方：

1）利用公钥U与私钥和k还原出超递增背包V;2)计算出：

3）以99作为背包的容量去解超递增背包问题；则解密得到明文分组为：10101100，即为原m。背包算法的安全性

背包算法利用难解的一般背包问题作为公开密钥，对明文进行加密；

私有密钥则利用易解的超递增背包问题给出一个解密的简单方法。不知道私钥的攻击者要想破译密文在计算上看似是不可行的。背包算法破解

基本思想：

找出一对任意的和，使得用公开的背包向量U模乘后得到一个超递增向量。

Why?

MH背包体制的公开密钥是由超递增向量变换而来，虽经过模乘置乱，但超递增向量内在的规律并不能完全被隐藏，给攻击者留下可乘之机。（续）背包算法是第一个使公钥密码体制成为现实的密码算法，它说明了如何将数学难题应用于公钥密码算法的设计。

优点：加解密速度很快

缺点：不安全性5.3

RSA算法

大数分解问题：计算两个素数的乘积非常容易；分解该乘积却异常困难；特别是在这两个素数都很大的情况下起源：

1978年美国MIT的三名数学家R.Rivest，A.Shamir和L.Adleman提出了著名的公钥密码体制：RSA公钥算法。

思想：

RSA算法基于指数加密概念，以两个大素数的乘积作为算法的公钥来加密消息，密文的解密必须知道相应的两个大素数。（续）

RSA公钥算法特点：

思想最简单；

分析最透彻；

应用最广泛；易于理解和实现；

经受住了密码分析，具有一定的可信度。5.3.1RSA算法的描述

独立选取两个大素数p

和q

；计算：

随机选取一个满足且的整数e，则e在模下的逆元为：

n和e为公钥，d为私钥。

为了获得最大程度的安全性，选取的p和q的长度应差不多，都应位长度在100位以上的十进制数字。注：p和q不再需要时，可以销毁，但一定不能泄露。加密变换：

将信息划分成数值小于n的一系列数据分组。

对每个明文分组m进行如下的加密变换得到密文c：解密变换：

证明：由欧拉定理知：如果两个整数a和b互素，那么，。 在RSA算法中，明文m必与两个素数p和q中至少一个互素。由知，存在整数k使得

若m与p和q都不互素，那么m既是p的倍数也是q的倍数，于是m也是n的倍数，这与m<n矛盾。情况一：m仅与p、q二者之一互素假设m与p互素且与q不互素，则存在整数a使得：由欧拉定理知：

故存在一个整数t使得：给上式两边同乘，得到：即：情况二：m和p、q都互素

此时m和n也互素，故得：

RSA算法实质：—单表带换系统例5.3

选取p=5，q=11，则有：n=55且明文分组应取1到54的整数。

选取加密指数e=7，则e满足

且与互素，故解密指数为d=23。

假如有一个消息m=53197，分组可得：，，。

分组加密得到：密文的解密为：最后恢复出明文5.3.2RSA算法的安全性缺点：

密钥产生和加/解密过程都很复杂，系统运行速度比较慢。攻击方法具体实现：现状：模数为129位十进制数字的RSA-129已于1994年4月在Internet上通过分布式计算被成功分解出一个64位和一个65位的因子。

更困难的RSA-130也于1996年被分解出来，紧接着RSA-154也被分解。

据报导158位的十进制整数也已被分解，这意味着512比特模数的RSA已经不安全了。RSA算法安全性（续）

更危险的安全威胁来自于大数分解算法的改进和新算法的不断提出。

破解RSA-129采用的是二次筛法；

破解RSA-130使用的算法称为推广的数域筛法；尽管如此，密码专家们认为一定时期内1024到2048比特模数的RSA还是相对安全的。该算法使破解RSA-130的计算量仅比破解RSA-129多100%。攻击方法（续）除了对RSA算法本身的攻击外，RSA算法还面临着攻击者对密码协议的攻击。

利用RSA算法的某些特性和实现过程对其进行攻击。共用模数攻击前提：RSA的实现中，多个用户选用相同的模数

n，但有不同的加解密指数

e和

d。共用模数优点：

—

算法运行简单缺点：

—

算法不安全

共用模数攻击（续）

设

和

是两个互素的加密密钥，共用的模数为

n。对同一个明文消息

m加密得:

攻击者知道n，

，

，

和

，他可以用如下方法恢复出明文

:

共用模数攻击（续）由于

和

互素，由扩展的欧几里德算法可找到

r和

s，使其满足：由此可得：

明文消息

m

被恢复出来。r和

s必有一个为负整数，上述计算需要用扩展的欧几里德算法算出

或者

在模

n下的逆.低加密指数攻击较小加密指数

e：

—可以加快消息加密的速度

—太小会影响RSA系统的安全性原理：在多个用户采用相同的加密密钥

e和不同的模数n的情况下，如果将同一个消息（或者一组线性相关的消息）分别用这些用户的公钥加密，那么利用中国剩余定理可以恢复出明文。低加密指数攻击（续）

假设取e=3，三个用户不同模数分别是n1,n2,和n3，将消息x用这三组密钥分别加密为：根据中国剩余定理，由y1,y2和y3求出：低加密指数攻击（续）由于：因此：于是：低加密指数攻击（续）

如何抵抗攻击？

—加密指数e必须足够大；

—对较短的消息进行独立的随机数填充；破坏明文消息的相关性，以防止低加密指数攻击。中间相遇攻击

指数运算具有可乘性，这种可乘性有可能招致其他方式的攻击。如果明文m可被分解成两项之积那么：这意味着明文的分解可导致密文的分解，明文分解容易使得密文分解也容易。密文分解容易将导致中间相遇攻击。攻击方法描述由RSA的可乘性得：前提：攻击方法（续）

1）攻击者先创建一个有序的序列：

2）搜索这个有序序列，尝试从中找到两项和满足：

3）攻击者能在步操作之内找到和，由此获得明文。攻击方法（续）RSA算法的参数选择

1）模数n的确定

不能在多个用户之间共用模数

模数n是两个大素数p和q的乘积多用户之间共用模数会招致共用模数攻击N的确定问题可转化为如何恰当地选择p和q模数n的确定（续）

p和q应满足的要求：

p和q要足够大

p和q应为强素数

p和q之差要合适

p-1和q-1的最大公因子要小至少100位以上的十进制整数P和q的取值会影响分解模数n的困难性防止迭代攻击模数n的确定（续）若一个素数p称为强素数或一级素数，则p满足以下条件：

存在两个大素数p1和p2，使得p1|(p-1)，p2|(p+1);

存在四个大素数r1,r2,s1和s2，使得r1|(p1-1),s1|(p1+1),r2|(p2-1),s2|(p2+1);称p1和p2为2级素数；r1,s1,r2,s2为3级素数。模数n的确定（续）

p和q不是强素数：

假设p-1有k个素因子，由算术定理可得：其中，为素数，为正整数()。如果很小，设（A为已知的小整数）构造：其中，，显然有。模数n的确定

任意小于素数p的正整数t均与p互素，设t=2由欧拉定理可知：因而：计算：

若X=1，令t=3，重新计算直到

若

，由，得到n的分解因子p和q。若p和q之差很小：

由：可得：所以与近似。令：由大于的整数依次尝试u且，从而解出p与q。

若p和q之差很大：如果两者之差很大，则其中一个必然较小，那么可以从一个小的素数开始依次尝试，最终分解n。

p和q之差要适当，一般是长度相差几个比特。迭代攻击

假设攻击者截获了密文，则可进行如下迭代攻击：记：其中：若存在t使得：则有整数k使得：迭代攻击（续）

由欧拉定理可知：还有：所以：因而：若t较小，则这种迭代攻击很容易成功。迭代攻击（续）

由欧拉定理可知：如果p-1与q-1的最大公因子较小，则t较大。如果t大到（p-1）(q-1)的一半，则迭代攻击难以奏效。加密密钥e的选取需要满足以下几个要求：

1）e要与模数n的欧拉函数值互素，否则无法计算解密密钥d。

2）e不能太小，否则容易遭受低加密指数攻击。

如果e和m都很小且满足，此时密文可直接得到，则c开e次方可得明文m。

3）e在模数下的阶要足够大。一般达到

(p-1)(q-1)。解密密钥d的选取

加密密钥e选定之后，利用扩展的欧几里得算法可以求出解密密钥d。

解密密钥d不能太小，否则易受已知明文攻击。

解密密钥d的选取（续）因此，一般要求d不能小于。5.4

Rabin算法

5.4.1求解数模下的平方根问题

证明：根据已知条件：由同余理论可知：

（续）

由a是模的平方剩余可知：有两个模的解，分别记为：可得一系列的一次同余方程组：

其中，可取或者。

由中国剩余定理可知每一个这样的一次同余式都有唯一的模n解。（续）（续）证明：根据a是模p的平方剩余，由Euler准则可知：

于是：5.4.2Rabin算法描述

Rabin算法既可看成是RSA算法的一个特例，也可看成对RSA算法的一个修正。Rabin算法是一个被证明其破解难度正好等价于大整数分解的公钥密码算法，它是第一个可证明安全的公钥密码算法。Rabin算法的安全性基于求解合数模下的平方根的困难性。Rabin算法描述Rabin算法描述（续）加密变换：明文消息m,通过计算得到密文c。

解密变换：为了解出密文c，需求解二次同余方程：Rabin算法描述（续）令，则上面方程可改写为：

再令，则方程进一步改写为：

因此，解密问题归结为求C模n的平方根。Rabin算法描述（续）

方程有四个解，当时：

方程

的两个解为：

方程的两个解为：Rabin算法描述（续）

组合得到四个一次同余方程组：解这四个同于方程组，其解是C模n的四个平方根，要寻找的明文就是四个解的其中之一。Rabin算法描述（续）

Rabin算法的加密函数不是单射，解密具有不确定性，合法用户不能确切地知道到底哪一个解是真正的明文。

如果加密之前在明文消息中插入一些冗余信息，可以帮助收信者准确的识别解密后的明文。Rabin算法描述（续）Rabin算法的解密过程是寻找C模

n

的平方根，这个问题的难度等价于n的因子分解。尽管计算模为素数的平方根是多项式时间可解的，但其过程仍然很复杂。要求p与q是模4同余3的限制条件是为了使解密的计算和分析变的更容易Rabin算法的特例取b=0时：可看成加密指数e=2的RSA算法。

加密变换：

解密变换：例5.4

假设模数，对明文加密，则密文为：

解密时：

1）计算227模19和模23的平方根；

（续）由于19和23都是模4同余3的，则可得：

277模19的平方根：

277模23的平方根：（续）

2）解下面同于方程组：

分别是因此，原始明文是这四个解之一。5.4.3Rabin算法的修正

Rabin算法具有解密不确定性的缺陷

Williams方案：

取两个不同的满足的大素数p和q，以为模数。

取一个小整数s,且s不是模n的平方剩余。

n和s为公钥对外公布，保密的私钥为：（续）

加密变换：

对于消息m，先确定参数；

m是模n的平方剩余，取0；

m不是模n的平方剩余，取1；计算：三元组为得到密文。

（续）

解密变换：

对于密文，根据计算出；的符号由确定：

时，取负；

时，取正；故，明文为：例5.5消息为m=19时，不是模21的平方剩余，取于是：故，加密所得到的密文为（16,1,1）。（续）

解密时：

计算：于是

解密唯一（续）Rabin算法对选择明文攻击是安全的，但已经证明它确实不能抵抗选择密文攻击。此外，针对RSA算法的一些攻击方法对Rabin算法也有效。5.5

ElGamal算法

ElGamal密码体制也是一种具有广泛应用的公钥密码体制，它的安全性基于有限域上计算离散对数问题的困难性。离散对数问题离散对数问题（续）设a是素数p的本原根，那么

在模p下互不相同且正好产生1到

的所有值。对于

,一定存在唯一的

，满足

。

称x为模p下以a为底b的离散对数，并记为

离散对数问题(续)

如果已知a，p和x，那么使用快速指数算法可以轻易地算出b；如果仅知a，p和b，特别是当p的取值特别大时，要想求出x是非常困难的。为了使基于离散对数问题的公钥密码算法具有足够的密码强度，一般要求模数p的长度在150位以上。5.5.2ElGamal算法的描述5.5.2ElGamal算法的描述

加密变换：

对于消息m，秘密选取一个随机数计算：和并构成密文，即密文为因此，密文的长度是明文的两倍。

（续）解密变换：

由加密变换可知：解密结果是正确的。

例5.6设p=2579，取模p

,乘法群的生成元g=2，私钥x=765。计算：若明文消息m=1299，选择随机数k=853,则可计算密文为：（续）对密文进行解密变换可计算出明文m：

由于密文不仅取决于明文，还依赖于加密者每次选择的随机数k，因此ElGamal公钥体制是非确定性的。

同一明文多次加密得到的密文可能不同；

同一明文最多会有多达

p-1个不同的密文；ElGamal算法的描述（续）（续）（续）加密变换：对于明文分组m，随机选取，计算密文：其中，，。解密变换：

ElGamal算法的安全性有学者曾提出模p生成的离散对数密码可能存在陷门，一些“弱”素数p下的离散对数较容易求解。

仔细地选择p，且g应是模p的本原根；

p应该至少是300位的十进制整数；

p-1应该至少有一个较大的素数因子；一般认为这类问题是困难的，而且目前尚未发现有效地解决该问题的多项式时间算法。（续）加密的不确定性：

ElGamal体制的一个显著特征是在加密过程中引入了随机数。相同的明文可能产生不同的密文，能够给密码分析者制造更大的困难。算法体制自身泄露信息：（续）（续）当一个明文消息不属于由g生成的子群的时候，ElGamal密码体制就成为一种确定性的体制。由于确定性加密体制允许使用多次“尝试”的方法来寻找小的明文消息，因此泄露了部分信息。所以，在应用ElGamal公钥体制，特别是推广的ElGamal体制的时候一定要注意生成元g的选择，确保每一个可能的明文消息都是由g生成的。5.6椭圆曲线密码

椭圆曲线理论在公钥密码领域有着重要的应用，以椭圆曲线上的点为元素定义的Abel群是构造多种公钥密码体制的基础。优点：

—较短的密钥获得同样的密码强度现状：已成为近年来一个非常有吸引力的研究领域，特别是在移动通信安全方面。椭圆曲线密码体制已被IEEE公钥密码标准P1363采用。5.6.1椭圆曲线的定义及性质

Weierstrass方程：

通常所说的椭圆曲线是指由Weierstrass方程所确定的平面曲线，其中a,b,c,d,e取自某个域F并满足一些简单条件。椭圆曲线通常用字母E表示，满足曲线方程的序偶（x,y）就是域F上的椭圆曲线E上的点。

可以是数域，也可以是某个有限域。除了满足曲线方程的所有点（x,y）之外，还包括一个特殊点O，称为无穷点。椭圆曲线的图形并非椭圆，只是因为它的曲线方程与计算椭圆周长的方程类似，而将其叫做椭圆曲线。Weierstrass方程

上面的Weierstrass方程用代替，得到：其中，，，。因此，椭圆曲线关于x轴对称。椭圆曲线的例子椭圆曲线的定义及性质在椭圆曲线E上定义一个二元运算，使其成为Abel群，通常称这个运算为加法，并用表示，其定义如下：（续）这是因为P与

的连线延长到无穷远时将经过无穷远点O，所以P,和O三点共线，即

＝O，

，

。而椭圆曲线E是关于x轴对称的，所以可以将－P定义为P点关于x轴的对称点

此外还有，－O＝O。即是P与Q的连线L交椭圆曲线E上另一点R关于x轴的对称点。因为，所以R是唯一的。P(x1,y1)Q(x2,y2)-RR点P和Q不同时求解点R:(x3,-y3)(x3,y3)P(x1,y1)R-R点P和Q相同时求解点R:(x3,y3)(x3,-y3)在密码学中使用的椭圆曲线通常定义在有限域上，也就是说椭圆曲线方程中的所有系数都取自某个有限域

。其中，最常用的是由有限域

（p为素数）上的同余方程

，且满足确定的椭圆曲线。由此同余方程的所有解

，再加上一个特殊的无穷远点O，在上述加法运算下构造的Abel群。用

来表示这样得到的Abel群。（续）在实数域中是保证方程

存在三个不同解（对于给定的y）的充分必要条件。否则，方程的三个解中至少有两个相同，并称这样的椭圆曲线为奇异椭圆曲线。（续）

假设和是椭圆曲线上的点；

※

如果P和Q关于x轴对称：

※

否则：则根据椭圆曲线的方程和P、Q连线的方程可以计算出R点的坐标(x3,y3)如下：(续)实际上，Zp上的椭圆曲线只是一些不连续的点，并不像实数域上椭圆曲线有直观的几何解释，但同样定义的加法运算能够保证

仍然是一个Abel群。其中：例5.7

给定上的一条椭圆曲线，按下述步骤可计算出中的所有点（无穷远点除外）对每个，计算出同余式的值a。利用Euler准则判定上一步算出的每一个值a是否是模11的平方剩余。计算出每一个平方剩余的平方根。由命题5.4.1可知，本例中是计算。Euler准则：

计算结果：是否为平方剩余06否18否25是4，7（2,4）（2,7）33是5，6（3,5）（3,6）48否54是2，9（5,2）（5,9）68否74是2，9（7,2）（7,9）89是3，8（8,3）（8,8）97否104是2，9（10,2）（10,9）（续）选取为生成元，我们来计算g的幂。注意这里的运算是群上的加法，所以群里的幂就是倍乘，即。（续）

1）先计算，这里图示（续）所以有：因此，。（续）

2）计算，这里，所以有：因此，。图示（续）

依次可计算出生成元g的所有幂，结果如下：可以看