第五章 公钥密码学与典型算法

教学要求掌握公钥密码体制的基本思想掌握RSA公钥密码算法了解EIGamal密码算法掌握椭圆曲线域的计算方法了解椭圆曲线密码体制的基本原理第5章非对称密码体制与典型算法1现在是1页\一共有117页\编辑于星期一5.1公钥密码体制概述一、对称密码体制的问题密钥管理困难n用户保密通信网，用户彼此间进行保密通信需要个密钥。n=1000：499500个密钥n=5000：12497500个密钥陌生人间不便进行保密通信无法实现抗抵赖的数字签名2现在是2页\一共有117页\编辑于星期一二、非对称密码体制别名：公钥密码体制，双钥密码体制两个密钥：公开密钥（公钥）：用于加密秘密密钥（私钥）：用于解密。安全性基础：基于数学难题标志性文献W.DiffieandM.E.Hellman,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-6543现在是3页\一共有117页\编辑于星期一公钥密码体制的数学模型由于速度比对称密码算法要慢几个数量级，因此公钥密码算法至今主要用于数据安全，或用于短数据和密钥的加密。4现在是4页\一共有117页\编辑于星期一对公钥密码体制的要求（1）参与方B容易通过计算产生一对密钥（公开密钥PUb和私有密钥PRb）。（2）发送方A容易通过计算产生密文：c＝ePUb（m）（3）接收方B容易通过计算解密密文：m＝dPRb©＝dPRb(ePUb(m))（4）他人即使知道公开密钥PUb，要确定私有密钥PRb在计算上是不可行的。（5）他人即使知道公开密钥PUb和密文c，要想恢复报文m在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个来使用:

m＝dPRb(ePUb(m))m=ePUb(dPRb(m))5现在是5页\一共有117页\编辑于星期一满足下列条件：给定x，容易计算y=f(x)给定y=f(x),难以计算出x存在陷门δ，已知δ时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的三、陷门单向函数陷门单向函数是公钥密码的核心Trap-DoorOne-WayFunction实践证明安全的3类公钥密码体制

大整数因式分解困难性：RSA离散对数难解性：DH，DSA椭圆曲线离散对数难解性：ECC6现在是6页\一共有117页\编辑于星期一四、公钥密码系统的分析方法强力攻击(对密钥)密钥不能太短，防止密钥穷举但也不能太长，以免影响速度公开密钥算法本身可能被攻破赖以安全的基石----数学难题被破解可能报文攻击(对报文本身的强力攻击)对所有可能报文加密，直到与截获密文相同7现在是7页\一共有117页\编辑于星期一5.2RSA算法由Rivest,Shamir和Adleman在1978年提出数学基础:大整数因子分解的困难性，Euler定理陷门8现在是8页\一共有117页\编辑于星期一明文空间P＝密文空间C=Zn密钥的生成选择互异素数p,q，计算n=p·q,(n)=(p-1)(q-1)；选择整数e使gcd(e,(n))=1,1<e<(n),计算d=e-1mod(n)公钥PU={e,n}公开私钥PR={d,n}中d保密加密(用e,n)明文：m<n密文：c=memodn解密(用d,n)

密文：c明文：m=cdmodn一、RSA算法描述为了安全，p、q至少为150位十进制数以上1、算法描述9现在是9页\一共有117页\编辑于星期一位十进制数位十进制数位十进制数位十进制数位十进制数位十进制数10现在是10页\一共有117页\编辑于星期一2、RSA要求p、q应为150位以上的十进制数，但数值不应很接近，长度最好相差几位。应该很小。（p-1）和（q-1）、（p+1）和（q+1）都应有一个大的素因子。p/q不应是一个接近于带有小分子或小分母的有理数。模n不能共享。公钥e的值应使计算得到的私钥。为了满足这个要求，通常是先选私钥d，满足且，然后再由私钥d计算公钥e：。一旦私钥d暴露，应立即改变p、q和e、d。11现在是11页\一共有117页\编辑于星期一互异素数p,q，n=p·q,(n)=(p-1)(q-1),选择整数e使gcd(e,(n))=1,1<e<(n),计算d=e-1mod(n)加密(用e,n)明文：m<n密文：c=memodn解密(用d,n)

密文：c明文：m=cdmodn3、RSA算法证明m=cdmodn=(memodn)dmodn=medmodn=m1+k(n)modn=(m.mk

(n))modn==[m.(m

(n))k]modn=[m.(m

(n)modn)k]modn=[m.1k]modn(扩展欧拉定理)=med=1mod(n)ed=k(n)+112现在是12页\一共有117页\编辑于星期一4、RSA算法实例例5-1假设Alice和Bob使用RSA密码体制进行全英文字符的保密通信。假设Alice选择、、，Bob选择、，并采用双字母加、解密方式。（1）说明Alice和Bob建立RSA密码体制的方法。（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。

13现在是13页\一共有117页\编辑于星期一4、RSA算法实例例5-1（1）说明Alice和Bob建立RSA密码体制的方法。解①Alice计算：14现在是14页\一共有117页\编辑于星期一4、RSA算法实例例5-1（1）说明Alice和Bob建立RSA密码体制的方法。解②Bob计算：15现在是15页\一共有117页\编辑于星期一4、RSA算法实例例5-1（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。

解

①Alice加密：“public”代换为数字并按双字母分组：15200111080216现在是16页\一共有117页\编辑于星期一4、RSA算法实例例5-1（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。

解

②Bob解密：密文“009516491410”明文:public17现在是17页\一共有117页\编辑于星期一如何产生大素数p和q?如何快速计算ammodn？二、RSA算法的实现问题18现在是18页\一共有117页\编辑于星期一1、产生大素数p和q二、RSA算法的实现问题WITNESS(a,n)；a是基数，判断奇数n是否为素数将(n-1)表示为二进制形式bkbk-1…b0;d1;forikdownto0do{xd;d(dd)modn;if(d=1)and(x1)and(xn-1)thenreturnFALSE;if(bi=1)thend(da)modn;}if(d1)thenreturnFALSE;returnTRUE;

返回值FALSE：n一定不是素数TRUE:

n可能是素数19现在是19页\一共有117页\编辑于星期一1、产生大素数p和q二、RSA算法的实现问题例判断n=97是否素数，选择a=2。解n-1=96=（1100000）2ibixdd61112512440864306422202296109610011素数课堂练习判断n=57是否素数，选择a=2。合数20现在是20页\一共有117页\编辑于星期一2、快速计算模指数abmodn要点1：(a×b)modn=[(amodn)×(bmodn)]modn降阶要点2：a16=aaaaaaaaaaaaaaaa计算15次乘法 a2,a4,a8,a16计算4次乘法启示：将ab的b表示为二进制形式bkbk-1…b0,即例:19=（10011）21现在是21页\一共有117页\编辑于星期一快速模指数算法计算y=abmodnb=(bkbk-1…b0

)2//yy2(bi=0)//yy2×a(bi=1)x0;y1forikdownto0dox2×xy(y×y)modnifbi=1thenxx+1y(y×a)modnreturny22现在是22页\一共有117页\编辑于星期一例计算7560mod561x0;y1forikdownto0dox2×xy(y×y)modnifbi=1thenxx+1y(y×a)modnreturny解560=（1000110000）2ibid(初值=1）9112×7=7mod5618072=49mod56170492=2401=157mod561601572=24649=526mod561515262×7=1936732=160mod561411602×7=179200=241mod561302412=58081=298mod561202982=88804=166mod561101662=27556=67mod56100672=4489=1mod5617560mod561=1本题利用欧拉定理可以直接得到结果23现在是23页\一共有117页\编辑于星期一3167mod561=504x0;y1forikdownto0dox2×xy(y×y)modnifbi=1thenxx+1y(y×a)modnreturny课堂练习：计算3167mod561解167=10100111ibid(初值=1）7112×3=3mod5616032=9mod5615192×3=243mod561402432=59049=144mod561301442=20736=540mod561215402×3=874800=201mod561112012×3=121203=27mod56101272×3=2187=504

mod56124现在是24页\一共有117页\编辑于星期一DES和RSA性能比较（同等强度）美国目前允许出口到我国的密码产品为512bitsRSA和40bits的某些私钥密码，说明美国已经有了破解方法！25现在是25页\一共有117页\编辑于星期一5.3EIGamal算法由TaherEIGamal于1984年提出安全性基于离散对数问题的难解性密文几乎是明文的2倍目前仅用于数字签名DSS中采用EIGamal26现在是26页\一共有117页\编辑于星期一一、离散对数问题尤其是p极大时，如何通过上式计算出x在数学上还没有有效的解决方法。假设p是素数，g是素域GF(p)的一个生成元。如果给定一个正整数，要寻找一个正整数x，，使得

成立，则该x应为：容易计算难以计算离散对数问题的难解性！27现在是27页\一共有117页\编辑于星期一二、EIGamal算法1、密钥生成选取一个大素数p，满足GF(p)中的离散对数问题是难处理的。寻找GF(p)的一个生成元g，它能生成GF(p)中所有的非0元素。选取私钥，满足。计算公钥y:私钥x保密，公钥y和p、g公开。28现在是28页\一共有117页\编辑于星期一二、EIGamal算法2、加密随机选择一个正整数，满足计算明文的密文和：3、解密对于合法密文和，，且，解密得到明文：数据扩展！正确接收时，C1≠0！29现在是29页\一共有117页\编辑于星期一二、EIGamal算法解密公式证明：接收方不知道r，也可正确解密。密文的结果与r有关，将不再是惟一。素数p应为300位十进制数以上，每次加密应选不同的r

。模数相同的EIGamal算法与RSA算法的安全性大致相当。30现在是30页\一共有117页\编辑于星期一EIGamal算法举例

例5-4假设Bob采用EIGamal密码体制，并选择素数p=2579，私钥x=765，且已知GF(p)的一个生成元g=2。（1）计算Bob的公钥y。（2）若Alice想秘密发送消息m=1299给Bob，且她选择的随机数r=853，试给出Alice和Bob的加密和解密过程。31现在是31页\一共有117页\编辑于星期一EIGamal算法举例

例5-4假设Bob采用EIGamal密码体制，并选择素数p=2579，私钥x=765，且已知GF(p)的一个生成元g=2。（1）计算Bob的公钥y:32现在是32页\一共有117页\编辑于星期一EIGamal算法举例

例5-4假设Bob采用EIGamal密码体制，并选择素数p=2579，私钥x=765，且已知GF(p)的一个生成元g=2。（2）若Alice想秘密发送消息m=1299给Bob，且她选择的随机数r=853，试给出Alice和Bob的加密和解密过程。Alice加密:33现在是33页\一共有117页\编辑于星期一EIGamal算法举例

例5-4假设Bob采用EIGamal密码体制，并选择素数p=2579，私钥x=765，且已知GF(p)的一个生成元g=2。（2）若Alice想秘密发送消息m=1299给Bob，且她选择的随机数r=853，试给出Alice和Bob的加密和解密过程。Bob解密:34现在是34页\一共有117页\编辑于星期一5.4椭圆曲线密码体制由NealKoblitz和VictorMiller在1985年分别提出安全性基于椭圆曲线域离散对数问题的难解性是目前已知公钥密码体制中每位提供加密强度最高的一种体制35现在是35页\一共有117页\编辑于星期一ECC与RSA和分组密码的密钥比较在安全性能大致相当的情况下36现在是36页\一共有117页\编辑于星期一一、椭圆曲线及其运算定义椭圆曲线是两个变元x、y满足形如三次方程y2+axy+by=x3+cx2+dx+e的所有点(x,y)的集合，外加一个零点或无穷远点O。Ellipticcurvesarenotellipses.Theyaresonamedbecausetheyaredescribedbycubicequations,similartothosecalculatingthecircumferenceofanellipse.37现在是37页\一共有117页\编辑于星期一1、实数域上的椭圆曲线实数域上的椭圆曲线E(a,b)是对于固定的a、b值，满足形如三次方程

y2=x3+ax+b

的所有点的集合，外加一个零点或无穷远点O其中a、b是实数，x和y在实数域上取值构成阿贝尔群38现在是38页\一共有117页\编辑于星期一E（-1,0）E（1,1）实数域椭圆曲线的几何图形互逆点互逆点39现在是39页\一共有117页\编辑于星期一几何定义如果椭圆曲线上的三个点位于一条直线上，那么它们的和为O。实数域椭圆曲线的运算规则互逆点基本运算为加法运算40现在是40页\一共有117页\编辑于星期一加法单位元为O，满足实数域椭圆曲线的运算规则互逆点P、Q，满足且41现在是41页\一共有117页\编辑于星期一实数域椭圆曲线的运算规则非互逆点P、Q的加法规则若λ=∞，则R为无穷远点O42现在是42页\一共有117页\编辑于星期一实数域椭圆曲线的运算规则倍点规则若λ=∞，则R为无穷远点O43现在是43页\一共有117页\编辑于星期一实数域椭圆曲线的运算规则交换律结合律标量乘法m个44现在是44页\一共有117页\编辑于星期一实数域椭圆曲线运算举例

例5-5已知实数域的椭圆曲线E(-1,0)为，其上的两个点分别为和。（1）计算。（2）计算。（3）计算。（4）U点和R点是什么关系？45现在是45页\一共有117页\编辑于星期一实数域椭圆曲线运算举例

例5-5已知实数域的椭圆曲线E(-1,0)为，和。（1）计算。46现在是46页\一共有117页\编辑于星期一实数域椭圆曲线运算举例

例5-5已知实数域的椭圆曲线E(-1,0)为，和。（2）计算。47现在是47页\一共有117页\编辑于星期一实数域椭圆曲线运算举例

例5-5已知实数域的椭圆曲线E(-1,0)为，和。（3）计算。48现在是48页\一共有117页\编辑于星期一实数域椭圆曲线运算举例

例5-5已知实数域的椭圆曲线E(-1,0)为，和。（4）U点和R点是什么关系？互逆点关系结论无普遍意义！49现在是49页\一共有117页\编辑于星期一2、素域GF(p)上的椭圆曲线

GF(p)域上的椭圆曲线E(a,b)是对于固定的a、b值，满足形如三次方程

y2=x3+ax+b(modp)

的所有点的集合，外加一个零点或无穷远点O其中a、b、x和y在GF(p)域上取值这类椭圆曲线通常也用来表示

50现在是50页\一共有117页\编辑于星期一Hasse定理如果是定义在GF(p)域上的椭圆曲线，N是上的点的个数，则：51现在是51页\一共有117页\编辑于星期一图5-3椭圆曲线上点的分布52现在是52页\一共有117页\编辑于星期一与实数域相同，但所有的运算都是modp运算的结果。分数运算时，既可以进行分数约简，也可以对分子、分母进行模运算，以便整除。素域GF(p)上椭圆曲线的运算规则53现在是53页\一共有117页\编辑于星期一素域GF(p)上椭圆曲线的运算举例

例5-6素域GF(23)上的椭圆曲线为，其上的两个点分别为和。（1）计算。（2）计算。（3）计算。（4）U点和R点是否互逆点？54现在是54页\一共有117页\编辑于星期一素域GF(p)上椭圆曲线的运算举例

例5-6素域GF(23)上的椭圆曲线为，和。（1）计算。55现在是55页\一共有117页\编辑于星期一素域GF(p)上椭圆曲线的运算举例

例5-6素域GF(23)上的椭圆曲线为，和。（2）计算。56现在是56页\一共有117页\编辑于星期一素域GF(p)上椭圆曲线的运算举例

例5-6素域GF(23)上的椭圆曲线为，和。（3）计算。57现在是57页\一共有117页\编辑于星期一素域GF(p)上椭圆曲线的运算举例

例5-6素域GF(23)上的椭圆曲线为，和。（4）U点和R点是否互逆点？U点和R点不是互逆点58现在是58页\一共有117页\编辑于星期一3、有限域GF(2n)上的椭圆曲线是对于固定的a、b值，满足形如三次方程

y2+xy=x3+ax2+b

的所有点的集合，外加一个零点或无穷远点O其中a、b、x和y在GF(2n)域上取值GF(2n)域上的元素是n位的串，共2n个元素常用表示，b≠0时构成阿贝尔群实际应用中，n必须足够大，至少n=160(相当于1024bitsRSA)59现在是59页\一共有117页\编辑于星期一例子

例5-7由不可约多项式定义的有限域有一个生成元。（1）列出上所有的非0元素，表明它们与生成元的关系，并验证。（2）若椭圆曲线是即，检验是否为上的点，并列出上所有非0点的坐标值，画出上点的分布图。60现在是60页\一共有117页\编辑于星期一例子

例5-7由不可约多项式定义的有限域有一个生成元。（1）列出上所有的非0元素，表明它们与生成元的关系，并验证。g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)61现在是61页\一共有117页\编辑于星期一例子

例5-7

（1）验证。62现在是62页\一共有117页\编辑于星期一例子

例5-7由不可约多项式定义的有限域有一个生成元。（2）若椭圆曲线是即，检验是否为上的点，并列出上所有非0点的坐标值，画出上点的分布图。是63现在是63页\一共有117页\编辑于星期一例子

例5-7由不可约多项式定义的有限域有一个生成元。（2）若椭圆曲线是即，检验是否为上的点，并列出

上所有非0点的坐标值，画出上点的分布图。64现在是64页\一共有117页\编辑于星期一65现在是65页\一共有117页\编辑于星期一十进制描述例5-7的坐标值66现在是66页\一共有117页\编辑于星期一GF(2n)域上椭圆曲线的运算规则在n次不可约多项式m(x)定义的有限域中进行运算要点：加法：按位模2加乘法、除法：使用生成元注意，67现在是67页\一共有117页\编辑于星期一GF(2n)域上椭圆曲线的运算规则加法单位元为，满足互逆点P、Q，满足且68现在是68页\一共有117页\编辑于星期一GF(2n)域上椭圆曲线的运算规则非互逆点的加法规则若λ=∞，则R为无穷远点O69现在是69页\一共有117页\编辑于星期一GF(2n)域上椭圆曲线的运算规则倍点规则若λ=∞，则R为无穷远点O70现在是70页\一共有117页\编辑于星期一GF(2n)域上椭圆曲线的运算规则交换律结合律标量乘法m个71现在是71页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-8（1）计算P+Q=R。（2）计算2P=S。（3）计算P-Q=U。（4）计算8P=V。72现在是72页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（1）计算P+Q=R。例5-873现在是73页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（1）计算P+Q=R。例5-874现在是74页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（2）计算2P=S。例5-875现在是75页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（2）计算2P=S。例5-876现在是76页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（3）计算P-Q=U。例5-877现在是77页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（3）计算P-Q=U。例5-878现在是78页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（3）计算P-Q=U。例5-879现在是79页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（4）计算8P=V。例5-880现在是80页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（4）计算8P=V。例5-881现在是81页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)（4）计算8P=V。例5-882现在是82页\一共有117页\编辑于星期一定义设G是椭圆曲线上的一点，若存在最小的正整数h，使得则称h为G点的阶。由于时，因此，P的阶h=8。椭圆曲线密码体制中，要求使用阶h非常大的点G作为本原元来生成椭圆曲线子群。这样的点G称为基点。83现在是83页\一共有117页\编辑于星期一二、椭圆曲线密码体制1、椭圆曲线离散对数问题已知椭圆曲线和曲线上的一点G，随机选择一个整数d，容易计算。但给定G和Q，要计算d却非常困难。椭圆曲线离散对数84现在是84页\一共有117页\编辑于星期一二、椭圆曲线密码体制2、椭圆曲线密码体制（1）建立系统①选一个基域（或），其中p是素数，n是正整数。②选一条定义在基域（或）上的椭圆曲线（或），寻找一个h阶基点G，满足以G为本原元生成的椭圆子群上的离散对数问题是难处理的。③公开基域、椭圆曲线、基点G及阶h。85现在是85页\一共有117页\编辑于星期一二、椭圆曲线密码体制2、椭圆曲线密码体制（2）生成密钥③公钥Q公开，私钥d保密。①选择一个大整数d作为私钥，满足②根据基点G和私钥d，计算公钥Q：86现在是86页\一共有117页\编辑于星期一二、椭圆曲线密码体制2、椭圆曲线密码体制（3）加密算法①查找Bob的公钥QBAlice发送消息给Bob②将消息划分为域元素，满足③随机选择一个整数k，满足④计算：如果，则返回③重新选择一个整数⑤将和密文发送给Bob，R供收方解密用87现在是87页\一共有117页\编辑于星期一二、椭圆曲线密码体制2、椭圆曲线密码体制（4）解密算法Bob收到和密文①用Bob自己的私钥，计算②使用中的，从密文计算出明文88现在是88页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（1）若Bob选择私钥，计算Bob的公钥（2）若Alice要发送消息m=（00101010）给Bob，给出Alice的加密过程（3）给出Bob的解密过程89现在是89页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（1）若Bob选择私钥，计算Bob的公钥90现在是90页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（1）若Bob选择私钥，计算Bob的公钥91现在是91页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（1）若Bob选择私钥，计算Bob的公钥92现在是92页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（1）若Bob选择私钥，计算Bob的公钥93现在是93页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（1）若Bob选择私钥，计算Bob的公钥不是互逆点94现在是94页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（1）若Bob选择私钥，计算Bob的公钥95现在是95页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（1）若Bob选择私钥，计算Bob的公钥96现在是96页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程①查找Bob的公钥②将消息划分为域元素，满足③随机选择一个整数k=3，满足④计算密文97现在是97页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文P、G不是互逆点（1）中计算得到98现在是98页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文99现在是99页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文100现在是100页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文101现在是101页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文102现在是102页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文103现在是103页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文U、Q不是互逆点104现在是104页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文105现在是105页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文106现在是106页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例5-9（2）Alice发送消息m=（00101010）给Bob的加密过程④计算密文107现在是107页\一共有117页\编辑于星期一g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(10