公钥密码课件

第8章公钥喜玛

2011-7-10

1

公钥密码

一、基本概念与简单算法

二、RSA公钥密码体制

三、离散对数公钥密码体制

四、可证明性安全公钥密码体制

2011-7-102

一.公钥密码体制的基本概念

BasicConceptofPublicKey

Cryptography

2011-7-10

为什么需要公钢密码体制？

•畲铜管理的方便

•数李签名的需要

2011-7-10

钥加密体制的问题9

私钥\!私钥

SecretKey、、、、，/SecretKey

Bob

Alice

2011-7-105

单钥加密体制的问题

•若N个人相互保密通信，每人必须拥有CN-1J

个私钥，N很大时，需要保存的私钥很多。

如何解决？

•可信中心分发：共需要发N*(NT)/2个私钥

N=1000时，999*1000/2=499500

•双方事先约定：用户之间自己秘密会面

r第一次运距离通信如何办？)

2011-7-106寿洋/孝

基本概念

•1976年,StandfordUni.Diffie博士和其导

师Hellman在IEEETrans,onIT上发文

“NewDirectioninCryptography”

•这一体制的出现在密码学史上是划时代的

事件，它为解决讦算机信息网中的安全提

供了新的理论和技术基础。被公认为现代

密码学诞生的标志。

2011-7-107

基本概念

•公钥密钥保密、认证系统的的安全性主

要取决于构造双钥算法所依赖的数学问题

。要求加密函数具有单向性，即求逆的困

难性。因此，设计双钥体制的关键是先要

寻求一个合适的陷门单向函数。

2011-7-108

基本概念9

公钥

/（X）Y

尸(y)

私钥

2011-7-109

基本概念

单向函数：一个可逆函数£•AfB,若它满足:

1°对所有丫£人易于计算/'（X）。

2。对“几乎所有在由/V）求产极为困难”

,以至于实际上不可能做到，则称f为一单向

（One-way）函数。

•定义中的“易于计算”是指函数值能在其输

入长度的多项式时间内求出，即若输入长度

为n,计算函数的时间是na的倍薮，a为一固

定的常数。

•若计算函数时间是a。的倍数，则为不可能做

到Mo

2011-7-1010

基本概念

•陷门单向函数：单向函数是求逆困难的函数，而

单向陷门函数，是在不知陷门信息下求逆困难的

函数，当知道陷门信息后，求逆是易于实现的。

这是Diffie和Hellmam[1976]引入的概念。

•例：号码锁。

如何给陷门单向函数下定义则很棘手，因为

(1)陷门函数其实就不是单向函数，因为单向函

数是在任何条件下求逆都是困难的；

(2)陷门可能不止一个，通过试验,一个个陷门就

可容易地找到逆。如果陷门信息的保密性不

嘉加。求逆也就不难。a

基本概念

•单向函数是求逆困难的函数，而单向陷门函

数（Trapdoorone-wayfunction）,是在不知

陷门信息下求逆困难的函数，当知道陷门信

息后，求逆是易于实现的。

•限门单向函数是一族可逆函数fk，满足

1.Y=fk（X）易于计算（当k和X已知）

2.X=f-\（Y）易于计算（当k和Y已知）

3.乂=广二（丫）计算上不可行（Y已知但k未知）

研究公钥密码算法就是找出合适的单向限门函数

2011-7-1012

基本概念建

・公钥密码基于的数学难题：

-背包问题

-大整数分解问题(TheInteger

FactorizationProblem,RSA体制)o

-Diffie-HelIman问题。

2011-7-1013

基本概念

-二次剩余问题。

-模n的平方根问题。

-离散对数问题：

-有限域的乘法群上的离散对数问题(The

DiscreteLogarithmProblem,ELGamal体制)

-定义在有限域的椭圆曲线上的离散对数问题(

TheEllipticCurveDiscreteLogarithm

Problem,类比的ELGamal体制)。

2011-7-1014

基本概念攀

P1

CipherText

PlainText

Alice

公钥密码体制的原理Key

2011-7-1015

基本概念

•基于公钥的加密过程：

B的公钥5的私钥

明文输入加密算法解密算法明文输出

2011-7-1016

/基本概念、❺

公钥密码体制的原理

•每个用户都有一对选定的密钥（公钥PK；私

钥SK）也称为双钥加密系统

•加密用（接收方的）公钥,解密用私钥

•无需事先分配密钥一解决了密钥分配问题！

2011-7-1017

基本概念

•公钥密码体制的数学描述：满足如下条件的五元组

(M,C,K,E,D)

(1)M是可能消息的集合;

(2)C是可能密文的集合；

(3)K是可能密钥的有限集

(4)对每一个k=(PK,SK)eK,有EPKeE,DSKeD,

满足对所有勿eM,〃SK(与K(血)=山

(5)对所有k,EPK少DSK是计算上不可能的。

2011-7-10海寿94

基本概念S

公钥密码体制的模型由以下算法组成

•密钥生成KG():根据输入的安全参数，输

出公钥和私钥对(PK,SK)

•加密E():根据输入的公钥和消息，输出密

文。

•解密D():根据输入的解密私钥和密文.算

法输出消息或输出表示密文不合法的特殊符号

a?”

2011-7-1019

基本概念

•公钥密码算法应满足的要求：

-接收方B产生密钥对在计算上是容易的

-发方A用B公钥对消息M加密成C在计算上是容

易的

-收方B用自己的私钥对C解密成M在计算上是容

易的

-敌人由B的公钥求B的私钥计算上不可行

-敌人由B的公钥和C求明文M,计算上不可行

-加，解密次序可换

2011-7-1020

基本概念

私钥系统与公钥系统的区别

・单钥〈-一）双钥

•对称〈一->非对称

•双向性〈—>单向性

•保险柜〈一〉邮箱

・私钥分发<—>公钥管理

2011-7-1021

基本概念f

•对公钥密码体制的攻击：

由于公钥体制的加密变换是公开的，

使得任何人都可以采用选择明文来攻击双钥

体制，因此，明文空间必须足够大才能防止

穷尽搜索明文空间攻击。一种更强有力的攻

击法是选择密文攻击,攻击者选择密文,而

后通过某种途径得到相应的明文，多数双钥

体制对于选择密文攻击特别敏感。

2011-7-1022

基本概念

通常采用两类选择密文攻击：

在接收到待攻击的密文之前，可以向攻击者提供他

们所选择的密文的解密结果。

自适应选择密文攻击，攻击者可能利用（或接入）被

攻击者的解密机（但不知其秘密钥），而可以对他

所选择的、与密文有关的待攻击的密文，以及以

前询问得到的密文进行解密

2011-7-1023

基本概念

•公钥密码标准:

ISO

ISO

国际标准

RSALabsIEEE

PKCSA

PKCSP1363ANSIX9

非官方工业标准工业标准银行标准

NIST

FTPS

联邦标准

2011-7-1024

简单算法

•背包密码体制：由Merkle和Hellman

1978年提出的第一个公钥密码算法。它

利用背包问题构造构造公钥密码，只适

用于加密，修正后方可用于数字签名。

•背包问题描述：给定重量分别为

的n个物品，装入一个背包中要求重量

满足一个给定值，找出究竟是哪些物品

2011-7-1025

简单算法

•0・1背包问题：1972年由Karp提出的，已知向量

/=(4,a2其中/为正整数,

称其为背包向量。给定向量%=(巧,％2,…,%〃)，/£｛。」｝

求和s=很容易，只需要ml次加法。但已知N

和S，求X则‘非常困难，称其为背包问题，又称子

集合问题。用穷举搜索法，布〃种可能，n非常

大时，相当困难。背包问题是一个NP完全问题

2011-7-1026

©

简单算法

•用背包问题构建公钥密码，关键在于有两类

背包，一类可以在线性时间内求解，而另一

类则不能。把易解得背包问题转换成难解的

背包问题，便可实现。即

-公开密钥使用难解的背包问题

-私钥使用易解的背包问题

2011-7-1027

简单算法O

•易解的背包即简单背良：及名超递增背包，若背包向至

Z-1

A=(a.9a)满足%>£与,i=1,2…N

称为超递增背包向量，相应背包为7简单背包。

简单背包很易求解，因为给定4=(4,〃2,…，氏)及S,

易知

_1。SN/

%=<

I0o5van

由此可得出解此背包的所谓贪心算法。先取最大的放入

背包，若能放入，则另相应的为1，否则另相应

为0。从中减去，再试，以此类推，置到决定出X1的取

值。

2011-7-1028

简单算法

•转换背包(Merkle-HeiIman陷门背包)：这一体制的基

本想法是将一个简单背包进行伪装，使得对所有其他人

为一个困难背包，而对合法用户则为简单的背包。构造

方法如下：

(1)各用户随机地选择一个超递增序列

4°=（的°,劭°,…,〃N°）O

(2)将其进行随机排列得至《矢量

/'=（为’,的’,…,许')O

(3)随机地选择两个整数〃和假

w>2aN°

U>〉:CL

2011-7-1029

简单算法

且gcd（〃，w）=10〈正〃

由Euclidean算法可得出a,b且l=a>b%由此

可得出bw=1modu,即wx=bmodu

（4）计算为=〃,mod〃，/=1,…，N构造出新

的（雄的）背包矢量…

（5）陷门信息为〃和肥“。且用户收到加密信息y

且，先转成为整数S,而后计算S=（庐1・6

mod〃且最看句由简单背包

N

S—、/」、xIaI.

1—1

解出X=（X],A：2，・・”XN）。

2011-7-1030

简单算法

•］正明S=w-1-5,modu

N

-1

=WVxz4Zzmodw

z=l

N

=£(w-1•(w•aimodz/))modu

i=l

N

-1

YxL(w-w•modw))modu

i=l〜

=>、jc.ct.mod"

z=1

NNN

a

三£w.(因£xiai<22tv〃)

i=\i=\i=l

•这样就把有s直接解难背包通过代-转化为

解简单背包

2011-7-1031

简单算法

•基于背包问题的公钥密码系统（MH公钥算法

）:

-加密：将明文分为长度为H的块V=…，K）

、然后用公钥将明文加密成密

文S=E（X）=>%x

-解密：先计算S=w~1Smodu在求解简单

背包问题S'=»xI.I

2011-7-1032

简单算法9

•例子：从私钥计算公钥

-私钥｛2,3,6,13,27,52｝

-w=31,u=l05

2*31modl05=62

3*31modl05=93

6*31modl05=81

13*31modl05=88

27*31modl05=102

52*31modl05=37

-公钥｛62,93,81,88,102,37)

2011-7-1033

简单算法

•例子：加密

-消息=011000110101101110

-明文011000

-背包62,93,81,88,102,37

-密文：93+81=174

-011000对应93+81=174

-110101对应62+93+88+37=280

-101110对应62+81+88+102=333

2011-7-1034

,简单算法

•例子：解密

-解密者知道亿3，6,13,27,52},n,u

一计算)=1mod(u),

-174*61modl05=9=3+6对应0110的t=61

-280*61modl05=70=2+3+13+52对应H0101

-333*61modl05=48=2+3+13+27对应101110

-因此消息为011000110101101110

2011-7-1035

//简单算法❺

•背包密码系统的意义：

-是Diffe和Hellman1976年提出公钥密

码体制的设想后的第一个公钥密码体制

）由Merkle和HeiIman在1978年提出。

-由较好的理论价值。

2011-7-1036

简单算法

•背包体制的缺陷：背包体制的加，解密的速度远比

RSA体制快的多，它大约只需要200次加法运算，

速度可与对称加密算法相比，但有一些致命的弱点

-MH背包体制已经证明不安全，大多数背包方案

都已被破解。

-MH背包不是满射，因而不能用作数字签字。

Shamir曾提出一种可用于签字的背包体制

[1978]9被Odlyzko波984]破译。

-消息扩展太大，/7=200,每个密钥分量为400

bit序列，公钥80kb长!

2011-7-1037

二、RSA公钢密码体制

2011-7-10

38

RSA算法

2011-7-1039

RSA算法

概况：

•MIT三位年青数学家R.L.Rivest,A.Shamir和

L.Adleman&1978全发现了一种用数论构造双

钥体制的方法，称作MIT体制，后来被广泛称

之为RSA体制。

•它既可用于加密、又可用于数字签名。

•RSA算法的安全性基于数论中大整数分解的困

难性。

2011-7-1040

RSA算法

•数论基础：算术基本定理

-任意大于1的整数a都能被因式分解为如

下的唯.一形式：

a]a?at

a=Pip2…Pt

-其中Pi>P2>--Pt都是素数

?而且每^一>个>0(i=l,23.・.t)o

2011-7-1041京考/4

RSA算法

•数论基础：中国剩余定理

设自然数mx.m2,…％两两互素，并记N=加］%•••%，

则同余方程组

x=b}modmx

x=b2modm2

x三久modmr

在模N同余的意义下有唯一解

2011-7-1042

/RSA算法命

•数论基础：FermafsTheorem

-Fermat定理：p是素数）a是整数且不

能被P整除,贝帖「"三Imodp

-推论：p是素数，a是任意整数，贝U：

ap=amodp

•在公钥理论和素性检测中很重要。

2011-7-1043

/RSA算法

•数论基础：Euler,sFunction

-模n的非负最小完全剩余系是{0」23..…n-1}

-如果一个模n的剩余类里面的数与n互素，就把

他叫做一个与模n互素的剩余系。

-与模n的全部剩余系中，从每一个系中各取一

个数组成的数的集合叫做模n的一个简化剩余

系。

-Euler函麹⑺：定义为小于n且与n互素的正整

数个数。

2011-7-1044

RSA算法

•数论基础：Euler,sTheorem

-Euler定理：若a与n为互素的正整数,

贝4：a"”)=1modn

-是Fermat定理的推广。

-例子：a=3?n=10,0(%)=4；因此

34=81=lmod10

2011-7-1045定考J孝

RSA算法©

•数论基础：欧拉定理推论

-关n=pq,p手q是素数

,k是任意整数，则：

加(P-i)S-i)+i三加modn,对任意

0<m<n

2011-7-1046

RSA算法1

算法描述-密钥产生KG():

•选取两互异大素数0和4

•计算n=p义q和其欧拉函数值。®=(〃-1)(4-1)

•选一整数e,1<6<0(力，使得gcd(03,e)=l

•在模0(刀)下，计算e的逆元d即求d,使得

ed=1mod(p(n)

•以(功e)为公钥。d为秘密钥。

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

2011-7-1047京笄J孝

RSA算法

算法描述-加密E()和解密D()：

•加密：将明文分组，各组对应的十进制数

欣化计算

c3(而三酢modn

6

•解密：7=D(c)三cmodn

2011-7-1048

/RSA算法二❷

解密正确性证明：

Euler定理若〃与〃互素，则

=Imodn

如，a=3,n=10时34=81=1mod10

2011-7-1049

RSA算法

解密正确性证明：

•^ilcdmodn=m.由加密过程

cdmodn=dmodn

=的)+imodn(ec/=7mod(p(n))

1)若与〃互素,由欧拉定理=1modn

有mk(p{n}三1mod%

mk(p(n)+\=mmodn

2011-7-1050

RSA算法

解密正确性证明：

2）若阳与〃不互素，即gcd（叫"）w1,则股

是夕的信教或夕的信教，不妨设jn=cp（c<q）

此时gcdGw,夕）=1,由欧拉定理，

=1modq,［旭仪也即3三1modg

即旭无砍〃）三1modq,

于是存在〜整数力使M秋加三1+,夕，

两边同乘加="，得

mk^+i=m+rcpq=m+rcn,即阳儿灰加十1三〃imodn

2011-7-1051

RSA算法

一个例子：

•密钥生成

-取，/T=17,疔11那么n=pq=17义11=187,

-计算夕㈤=(0-1)(,-1)=16x10=160

-选取与0(")=160互素的整数e=7

-按照扩展的欧几里德算法计算公£一1mod(p(6

=7Tmodl60=23

-公开密钥为(氏c)=(187,7),私钥为大23.

2011-7-1052

RSA算法

一个例子:

•加密

c=nPmodn

为了对消息勿=88加密，按照如下步骤计算密文

c=zzfmod/2=8印mod187=11

2011-7-1053

RSA算法

一个例子:

•解密：当收到密文c后，利用私钥计

算明文

m=ll23mod(187)=88

2011-7-1054

RSA算法

•RSA加密实质上是一种474上的单表代换

!给定力寸和合法明文其相应密文

y=^modneZno对于xw犬必有户匕。4

中的任一元素（0,A,%的倍数除夕卜）是一

个明文，但它也是与某个明文相对应的一个

密文。因此，RSA是4-4的一种单表代换

密码，关键在于力极大时在不知陷门信息下

极难确定这种对应关系，而用模指数算法又

易于实现一种给定的代换。正由于这种——

对应性使RSA不仅可以用于加密也可以用于

数字签字。

2011-7-1055

对RSA的攻击与参数选取奥

•单向性是如何表现的？

•f：x今f(x)"modn

容易

•f-1:f(x)X困难

•陷门：私钥"

f(x)dmodn=3)dmodn=x

2011-7-1056

对RSA的攻击与参数选取i

•RSA的安全性是基于分解大整数的困难性

假定(尚未证明分解大整数是NP问题)

?/«=D(c)三cAmodnd?

•如果能分解n=pXq,则立即可得cp(n)=

(p-1)(q-1),从而能够确定e的模(p(n)

乘法迎d

2011-7-1057

对RSA的攻击与参数选取

数学技术=乂0116丫？

•RSA-129历时8个月于1994年4月被成功分解

(600多位科学家，100$)

•RSA-130于1996年4月被成功分解

•RSA-140于1999年2月被成功分解

•RSA-155于1999年8月被成功分解

•密钥长度应该介于1024bit到2048bit之间

•由n直接求§(n)等价于分解n

2011-7-1058

对RSA的攻击与参数选取

因子分解复杂度：

密钥长(bit)所需的MIPS-年*

116（Blacknet密钥）400

1295,000

51230,000

768200,000,000

1024300,000,000,000

2048300,000,000,000,000,000,000

*MIPS-年指以每秒执行1,000,000条指令的计算机运

2011-7-1059定考J孝

对RSA的攻击与参数选取

对RSA的攻击:

(1)迭代攻击法：Simmons和

Norris曾提迭代或福环攻击法。例如,

给定一RSA的参数为(4⑦力=(35,17,

3),可由/=y=3讦算%=317=33mod35O

再由无计算为=PJ7=3mod35,从而得到

明文mod35一般对明文x加密

多次)直到再现x为止O。Rivest证明,当

0-1和02-1中含宥大素数因子，宜人足

够大时，这种攻去法成功的概率趋于0。

2011-7-1060

对RSA的攻击与参数选取.

(2)选择明文攻击\\

(a)消息、破译。攻击者收集用户A以公

钥e加密的密文片犬modn,并想分析出消

息X。选随机数叱算为=/mod刀,这

意味T可Jmodno计算为=%xymodno

令才=厂1modn,贝modno现在攻

击者请A对消息为进行签字(用秘密钥，但不

能用H啰h函数))得到品墟modno攻击

d

者计算tsmod/7=y1-xy2dmodn=y^

dxydxjdmodn=y^modn=x,得至U了明

文。

2011-7-1061

(b)骗取仲裁签字。在有仲裁情况下，A

有一个文件要求仲裁，可先将其送给仲

T以RSA的秘密钥进行签署后回送给

A(未用单向Hash函数，只以秘密钥对整

个消息加密)O

攻击者有一个消息要T签署，但T并

不情愿给他签，因为可能有伪造的时戳

,也可能是来自另外人的消息。但攻击

者可用下述方法骗取T签字。

2011-7-1062

(c)骗取用户签字。攻击者可制作两

条消息片和巧,凑出所要的毛三百XX]

modno

、首先他可得到用户A对3和巧的、签

定xjmodn和勺dmodn,贝|可计

d

算疗modmodn)•(^2mod

n)modno

因此，任何时候不要为不相识的

人签署随机性文件，最好先采用单向

Hash函数。ISO9796的分组格式可以

防止这类攻击。

2011-7-1063

对RSA的攻击与参数选取S

令攻击者的消息为x,他首先任意选一个数N,

计算尸肝mod刀（e是T的公函）,而后计算

M=yx,送给T,T将签字的结果"mod刀送给

攻击者,则有（点modn）N~\mod

刀=（"d・"imod刀=〃产"1modn=^NN~x

modn=j^modn,此为T对x的签字。

所以能有这类攻击是因为指数运算保持了输

入的乘法结构。

2011-7-1064

对RSA的攻击与参数选取箍

(3)共模攻击:

•每一用户有相同的模数n

•设用户的公开密钥分别为ei，e2，且e2互素，明文

消息为m,密文为

ex

cx=mmodn

e

e2=m^modn

•因为(e「e2)=l,用欧几里德算法可求

rC]+s从而由Euclidean算法可计算

c1r*02s=勿modn

2011-7-1065

对RSA的攻击与参数选取

（4）低加密指数攻击：令网中三用户的加密钥£均选

3,而有不同的模可，%，4，若有一用户将消息M专

给三个用户的密文分别为

%=x3modx<4

3

y2=xmodn2x<n2

3

y3=xmodn3

一般选4，刀2，刀3互素（否则,可求出公因子，

而降低安全性），利角中国余定理，可从加左，73

3

求由广£mod（4n2q）。簿每x&i英*<叫,

x<nv可得4・巧，•nv故有

2011-7-1066

对RSA的攻击与参数选取❺

(5)定时攻击法：

定时(Timing)攻击法由P.Kocher提出，利

用测定RSA解密所进行的模指数运算的时间来估

计解密指数a而后再精确定出d的取值。R.

Rivest曾指出，这一攻击法可以通过将解密运

算量与参数d无关挫败。另外还可采用盲化技术

,即先将数据进行盲化，再进行加密运算，而

后做去盲运算。这样做虽然不能使解密运算时

间保持不变，但计算时间被随机化而难于推测

解密所进行的指数运算的时间。

2011-7-1067

对RSA的攻击与参数选取

RSA的参数选取:

(1)〃的确定

-n=pxxp],当与巧必须为强素数。

强素数〃的条件：(a)存在两个大素数为和

,0|(2-1),221G9+1]。(b)存在4个大素数乙,

S1，丁2及$2，使小(筠A以「sj(0+1)，r2|(p2-

1),S2IS2+I)。称心,'—0，Si和$2；0和，2为二级

素数。

2011-7-1068

采用强素数的理由如下：若

，a为素数，分为正整数。分解式中a褂

,夕为已知一个小整数，则存在一种2-1

的分解法，使我们易于分解力。个n=pq,

旦2-1满足上述条彳牛，p.[<B。令心为，

/=152,…，to即可构造

显然（2-1）1凡由费尔马定理2『1

modp。令2R=xmodno若x=1则选3代

2,直到出现胫L此时，由GCD（x-l,

6=P，就得到力的分解因子丽久

2011-7-1069

简单算法

-巧与巧之差要大。若巧与巧之差很小，则可

由力”估计（0+0+/2=刀1/2,贝由（（巧+

见）/2）2-刀=（3-〃）/2）2。上式右边为小

的车方数,可以试装给由百，当的值。

-p,q要足够大，以使n分解在计算上不可行

~Pi-1与。2一1的最大公因子要小。在惟密文

攻击下，设破译署截获密文片丫，modno

破译者做下述递推计算：

毛=巧._『mod力=（犬）imodn

2011-7-1070

简单算法

（2）£的选取原则

（£,0（力）=1的条件易于满足，因为两个随机数为

互素的概率约为3/5。e小时，加密速度快，Knuth和

Shamir曾建议采用户3。但e太小存在一些问题。

不可过小：若c小，X小，y=xGmodn,当KS,

则未取模，由"直接开£次方可求月易遭低指数攻

击。

-由选e在mod。（刀）中的阶数，即工e[=1mod

（P（玲，/达到（0-1）（0一1）/2。

2011-7-1071

简单算法

（3）d的选择:

£选定后可用Euclidean算法在多项式时间内

求出心盛大于"/、冽、，签字和解密运算快，

这在IC卡中尤为重要（复杂的加密和验证签字可

由主机来做）。类似于加密下的情况，d不能太小

，否则由已知明文攻击，构造（迭代地做）

modn,再猜测d值，做/modn,直到试凑出

川三1mod刀是d值就行了。Wiener给出对，］、d的

系统攻击法，证明了当d长度小于4的1/4时，由

连分式算法，可在多项式时间内求出d值。这是

否可推广至1/2还不知道。

2011-7-1072

小结

•公钥加密体制的基本思想

•公钥加密体制的要求和特点

•单向函数的基本特点

•RSA的具体方案和安全性考虑

•如何实现安全的RSA体制?

2011-7-1073

三、离散对教公钥密码体制

2011-7-10

74

9

ElGamal密码体制

ElGamal密码体制:由ElGamal[1984,1985]

提出，是一种基于离散对数问题的公钥密码

体制，既可用于加密，又可用于签字。

2011-7-1075

ElGamal密码体制

•ElGamal方案：

（1）Zp.〃个元素的有限域p:一个素数

g：是4*（4中除去°元素）中的一个本原

元或其生成元。

明文集"：4/密文集cZp*

公钥：选定g（g〈〃的生成元），计算公钥

庐史modp

秘密钥：a<p

2011-7-1076

ElGamal密码体制

（2）加密：选择随机数h4T，且（£〃-

1）=1,计算：

%=gkmodp（随机数%被加密）

%=M供mod〃（明文被随机数%和公钥力口密）

碇发送明文组。密文由无、为级连构成，

即密文1为。

2011-7-1077

ElGamal密码体制目

特点：密文由明文和所选随机数々来定，因

而是非确定性加密，一般称

之为随机化加密，对同一明文由于不

同时刻的随机数左不同而给出不同的

密文。代价是使数据扩展一'倍。

(3)解密：收到密文组集，计算

kkocakkot

姑乃/%。=跖/<g=J^/^modp

2011-7-1078

ElGamal密码体制

•例子：

-生成密钥：使用者A选取素数p=2357及Z2357*的生成

元2,A选取私钥x=1751并计算

gxmodp-21751mod2357=1185

A的公钥是p=2357,g=2,g'=1185

-加密：为加密信息m=2053,B选一个随机整数

k=1520,并计算

a=21520mod2357=1430

然后发送给A。5=2035x11851520mod2357=697

一解密：Xn1x605

x

a~三1430P—I三1430605三872mod2357

m=bIax=ba三697x872=2035mod2357,

201171079定穿/与

ElGamal密码体制

•上述方案是基于乘法群Zp*建立的ElGamal公

钥密码体制，实际上可基于任何离散对数问

题难处理的群实现ElGamal公钥密码体制。

下面介绍推广的ElGamal公钥密码体制。

・设群G是一运算符为x的有限群，子群H是

由a生成的，且满足其上的离散对数问题是难

解的,具体推广如下：

2011-7-1080

ElGamal密码体制

•系统参数:G为运算符为x的有限群，aeG,H={ali>0]

（即〃是由。生成的），选计算。=/

则私钥：d公钥：

•加密：对于消息m,选随机数

ke-1]则密文为e七（m,k）=（匕，无）

其中Pi==%乂04

•解密：消息接受者解密

4261,）=、2x（y「）1

2011-7-1081

ElGamal密码体制

•ElGamal签名：

公钥：夕素数（可由一组用户共享）

g<P（可由一组用户共享）

y—gxmodp

zXvp

签名：随机选取k,与夕-1互素

4（签名）=g"modp

6（签名）7茜足M={xa+kb）mod（p-1）

验证：如果yc，abmodp-gMmod），签名有效

2011-7-1082

♦■

ElGamal密码体制

•ElGamal的安全性：

-攻击该算法等价于解离散对数难题

-要使用不同的随机数k来加密不同的消息

,否则很容易被破解。假设用同一个k来加

密两个消息ml和m2,所得的密文分别为(

al,bl),(a2,b2),则bl/b2=ml/m2,故当ml已

知，m2可以很容易的计算出来。

2011-7-1083

安全性分析

•离散对数难题：

计算y=gxmodp

-已知g,x,p时计算y是容易的。

-已知y,g,p时计算x是困难的。

•一般的描述：

条件：设群G是运算符为x的有限群，。£6,££〃,其中//=卜，此0},即

〃是由生成的。

问题：能否找到唯一的整数1],满足/="我

们记为y=log

2011-7-1084

安全性分析

・密码学中常用的离散对数：

-有限域GF(p)上的乘法群

-有限域GFp)上的乘法群

-有限域F上的椭圆曲线群

安全性分析

•求离散对数的算法介绍：Pohlig-Hellman算法

Q是Zp*的本原元，q是素数，且p-1=Omodqc,p-1^Omodqc+\

c

则算法用来计算满足log=tatqmod/的

z=0

(00,4],"2'…"c—1)

1yj=a"-'>'"modp?jw[0,4—1]

2,4,白勺初女台值为i—b>6t—J3

VKhile

iMc—1

do

3^=J3\P—')Q(modp>

找一^个户茜定5=y.

ai—j>g+i行iCL—aqiH-1.

2011-7-10

安全性分析

能

果

计算离散对数与因子分解有紧密的关系如

问

题

秦

类

解决离散对数问题，那么就能解决因子数

,（逆命题的正确性还未被证明）。目法

域上有3种方法计算：线性筛选法，高撕?

和NFS。

•基本的扩展计算必须在每个域上做一次，之后，

单个的对数就能快速进行计算，对基于这些域的

家统而言，是一b小安全羲陷。所以，不同的用户

采用不同的素数域很重要。

2011-7-1087

安全性分析

•Diffie-HEllman假定

•一般可认为有两类假定。

一，计算Difl加假定(

ComputationalDiffie-HellmanAssumption9CDH)

o

二，决定Diffie-Hellman假定(Decisional

Diffie-HellmanAssumption,DDH)。

•两类假定均有Diffie-HeHmaii问题引出，当在某个

群或裁上求解Diffie・HeUman问题是困难时，就认

为假定在该群或域上成立。

2011-7-1088

/安全性分析❺

•CDH

Diffie-Hellman函数定义为：

abab

DHg(g,g)=g

如果在一个群上没有有效的算法能够

计算Diffie-Hellman函薮,那么该群满定

CDH假定。即已知

g'g’没有有效算法计算gab。

2011-7-1089

安全性分析

•DDH

给定群(S3上的任意一个三元组

，没有有效的概率算法

能够当c二而时，输出“真”，否则输出“

假”。

•除CDH和DDH夕卜，还有推广的问题如

BDHP(BilinearDiffie-HellmanProblem),

BIDHP(BilinearInverseDiffie-Hellman

Problem)等。

2011-7-1090京著）4

椭圆曲线密码体制

•简要历史

椭圆曲线（E11ipticcurve）作为代数几何中的

重要问题已有100多年的研究历史

1985年，N.Koblitz和V.Miller独立将其引

入密码学中，成为构造公钥密码体制的一个宥力工

具。

利用有限域斯（2口）上的椭圆曲线上点集所构成

的群上定义的离散对数系统，可以构造出基于有限

域上离散对数的一些公钥体制一椭圆曲线离散对数

密码体制（ECDLC），如Diffie-Hellman,ElGamal,

Schnorr,DSA等

2011-7-1091

椭圆曲线密码体制

•实数上的椭圆曲线：

y2+oxy+by-x3+ex2+dx+e

•其中的人是满足简单条件的

实数

•一些曲线上的点连同无穷远点O的集合。

2011-7-1092

椭圆曲线密码体制9

•实数上的椭圆曲线例子:FY+X+1

2011-7-1093

椭圆曲线密码体制

•运算定义：

若曲线三点在一条直线上，则其和为O,

。用作加法的单位：O=—O;P+O=P，

一条竖直线交由两点）1，夕2则

夕1+夕2+O=O,于是P1=一22，

如果两个点。和尺的，轴不同，则画一连线，

得到第三个点21，贝1」。+尺+夕1=0,

2倍，一个点。的2倍是，找到它的切线与曲

线的另一交点S,于是。+。=-S

2011-7-1094

椭圆曲线密码体制

•有限域上的椭圆曲线：

y2=x3+ax+bmodp

夕是奇素数，且4/+27/wOmod夕

•模P椭圆群记为马（。，司:群中的元素（x,y）是满足

以上方程的小于P的非负整数另外加上无穷远点

O

•计算吗（〃4）：

针对所有的0Vx<p,计算/+ax+bmodp

确定是否可以求出有效的R得到曲线上的点

（羽天）,其中工）<夕，记为Ep（a,b]

2011-7-1095京著）4

椭圆曲线密码体制

•号（%6）的力口法规贝

-P+O=P

一如果P=（X,田,则尸+（­）=。,（—）点是。的负

点，记为—P。而且（羽-y）也在号（。/）中

_如果尸=（七,%），。=（%2，歹2），则尸+。=（巧，歹3）为

2

x3=2—xl—x2modp

y3=丸（/一0）―ymodp

其中，如果PwQ,则；1=（%—£）/（%—/）

如果p=Q,则X=（3x；+a）/（2为）

2011-7-1096

椭圆曲线密码体制

•ECC的力口解密：

-选择石夕（%b）的元素G,使得G的