网络信息安全技术课件 第2章 密码学基础

第2章密码学基础密码学概述传统密码学对称密码体制公钥密码体制2.1密码学概述1.专业术语密码学(Cryptology):是研究信息系统安全保密的科学。密码编码学(Cryptography):主要研究对信息进行编码，实现对信息的隐蔽。密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造。1.专业术语图2-1密码通信系统2.密码算法分类（1）根据密钥的使用方式分类对称密码体制（私钥密码体制,秘密密钥密码体制）:加密密钥和解密密钥相同，或实质上等同，即从一个容易推出另一个。非对称密码体制（公钥密码体制）：加密密钥和解密密钥不相同,从一个很难推出另一个。加密密钥可以公开，称为公钥；解密密钥必须保密，称为私钥。2.密码算法分类（2）根据明文和密文的处理方式分类分组密码体制：设M为明文，分组密码将M划分为一系列明文块Mi，通常每块包含若干字符，并且对每一块Mi都用同一个密钥Ke进行加密。如：M=(M1,M2,…,Mn)，C=(C1,C2,…,Cn,)，其中Ci=E(Mi,Ke)，i=1,2…,n。序列密码体制：将明文和密钥都划分为位(bit)或字符的序列，并且对明文序列中的每一位或字符都用密钥序列中对应的分量来加密。M=(M1,M2,…,Mn)，Ke=(ke1,ke2,…,ken)，C=(C1,C2,…,Cn)，其中Ci=E(mi,kei)，i=1,2,…,n。3.密码分析学研究分析解密规律的科学称作密码分析学。接收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。3.密码分析学攻击类型攻击者拥有的资源唯密文攻击加密算法截获的部分密文已知明文攻击加密算法截获的部分密文和相应的明文选择明文攻击加密算法加密黑盒子，可加密任意明文得到相应的密文选择密文攻击加密算法解密黑盒子，可解密任意密文得到相应的明文表2-1密码算法经受的攻击4.密码算法的安全性无条件安全(Unconditionallysecure)：无论破译者计算能力有多强，无论截获多少密文，都无法破译明文。计算上安全(Computationallysecure)：破译的代价超出信息本身的价值；破译的时间超出信息的有效期5.密钥算法公开的必要性攻击者总能设法找到算法。除非你就是个密码学家，并开发了自己的算法，否则你就必须相信开发出算法的公司不会将算法有意无意地泄露。公开的算法更安全，算法公开后，密码分析者和计算机工程师就有了检验它弱点的机会。思考和启示密码算法公开后，让更多的密码分析者去检验它。检验出它的弱点，密码学家再修改或者再设计新的密码算法。在这样不断的破解和创建的过程中，不断的促进密码算法的发展，也会让我们的信息更安全。引申：这个不断破解和创建的过程中，就像是我们每个人的一生，只有不断的发现自身的问题，不断的改进，甚至破而后立，我们才能不断的成长，不断的向前发展。2.2传统密码学1.换位密码换位密码是在简单的纵行换位中，明文以固定的宽度水平的写在一张图表纸上，密文按垂直方向读出，解密就是密文按相同的宽度垂直的写在图表纸上，然后水平的读出明文。1.换位密码明文：COMPUTERCRAPHICSMAYBESLOWBUTATLEASTTIE’SEXPENSIVECOMPUTERCRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVE密文:CAELPOPSEEMHLANPIOSSUCWTITSBIVEMUTERATSCYAERBTX2.恺撒密码恺撒密码的替换方法是通过排列明文和密文字母表，密文字母表示通过将明文字母表向左或向右移动一个固定数目的位置。例如，当偏移量是左移3的时候（解密时的密钥就是3）：明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ；密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC。2.恺撒密码

2.3对称密码体制2.3.1DES1.数据加密标准简介DES全称为DataEncryptionStandard，即数据加密标准，是一种使用密钥加密的块算法，1977年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），并授权在非密级政府通信中使用，随后该算法在国际上广泛流传开来。2.DES的地位里程碑：第一个公开的公用算法。（公钥体制）分组密码设计的典范：重要的设计思想，经得住分析和时间考验。分组密码的教科书：DES的出现，吸引了全世界密码学者对分组密码的兴趣，使分组密码的水平提高。培养了一批密码学家。在应用领域退出，但在理论研究上有价值。3.DES加解密原理DES是一种对称密码体制，它所使用的加密和解密密钥是相同的，是一种典型的按分组方式工作的密码。其基本思想是将二进制序列的明文分成每64bit一组，用长为64bit(56bit)的密钥对其进行16轮代换和置换加密，最后形成密文。3.DES加解密原理加密前，先将明文分成64bit的分组，然后将64bit二进制码输入到密码器中，密码器对输入的64位明文进行初始置换，然后在64bit主密钥产生的16个子密钥控制下进行16轮乘积变换，接着再进行逆置换就得到64位已加密的密文。3.DES加解密原理（1）初始置换IP和初始逆置换IP-1初始置换IP和初四逆置换是将64位比特的位置进行置换，得到一个乱序的64bit明文组。图2-3初始置换IP图2-4初始逆置换IP-13.DES加解密原理（2）迭代变换迭代变换是DES算法的核心部分。明文经过初始IP置换后，会将数据分为左右分别32位的两组，在迭代过程中彼此左右位置交换，每次迭代只对右边的32位和子密钥Ki进行加密变换。每一轮迭代的过程如图所示，DES需要进行16轮这样的迭代。3.DES加解密原理①E扩展运算E扩展运算是扩位运算，将32比特扩展为48比特，用方阵形式可以容易地看出其扩位其中粗方框中的为原始输入数据。3.DES加解密原理②S盒运算将前面送来的48bit数据自左至右分成8组，每组6bit。然后并行送入8个S盒，每个S盒为一非线性代换网络，有4个输出。3.DES加解密原理S-盒运算由8个S-盒函数构成，S(x1x2...x48)=S1(x1...x6)||S2(x7...x12)||...||S8(x43...x48)其中，每一个S-盒函数都是6比特的输入，4比特的输出Si(h1...h3)的值就是对应表Si中(h1h6)2行和(h2h3h4h5)2列上的值。3.DES加解密原理③P置换P置换是对8个S盒的输出进行变换，可以扩散单个P盒的效果。16172021291228171152326518311028241432273919133062211425表2-3P置换3.DES加解密原理（3）子密钥生成器将64位初始密钥经过置换选择PC-1，循环移位、置换选择PC-2，得到每次迭代加密用的子密钥Ki，如图所示。4.DES的解密解密算法与加密算法相同，只是子密钥的使用次序相反。DES解密时将64位密文作为输入，第一次迭代时用子密钥K16，第二次K15、......，最后一次用K1，算法本身并没有任何变化。5.DES的安全性DES的安全性主要依赖于S盒，而且S盒是其唯一的非线性部分。S盒子的设计标准(其实也就是整个算法的设计标准)并未公开，人们怀疑这些盒子的设计可能隐藏着一种可以使得了解S盒子弱点的敌对方成功地进行密码分析的隐患。多年来的确有不少S盒子的规律性以及未曾料到的行为被发现。尽管如此，至今还没有人成功地发现S盒子想象中的致命缺陷。5.DES的安全性①弱密钥DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k，各轮的子密钥都相同，即有k1=k2=…=k16，就称给定密钥k为弱密钥(Weakkey)。若k为弱密钥，则有 DESk(DESk(x))=x DESk-1(DESk-1(x))=x即以k对x加密两次或解密两次都可恢复出明文。其加密运算和解密运算没有区别。5.DES的安全性②密钥长度对于DES算法评价的最一致看法就是56比特的密钥长度不足以抵御穷举式攻击。1997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56比特的DES。美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元。事实证明56位的密钥不能经受住穷举攻击，DES安全的事实已成为过去。6.多重DES①双重DES

用DES进行两次加密，但这是否就意味着两重DES加密的强度等价于112bit密钥的密码的强度？答案是否定的。C=EK2(EK1(P))

X=EK1(P)=DK2(C)

给定明文密文对(P,C)。对所有256个密钥,加密P,把结果存在表中并排序。用可能256个可能的密钥进行解密，每次解密后将结果在表中寻找匹配。若匹配，用新的明文密文对检测所得到的两个密钥。如果正确，密钥就是正确的。可以看出，计算代价为256+256=2576.多重DES②三重DES对付中间攻击的明显方法是用三个密钥进行三阶段加密。然而，56*3=168bit，密钥有点过大。作为一种替代方案，使用两个密钥的三重加密方案，已经被用于密钥管理标准ANSX9.17和ISO8732中，并在保密增强邮递(PEM)系统中得到利用。破译它的穷举密钥搜索量为2112

5×1035量级，而用差分分析破译也要超过1052量级。此方案仍有足够的安全性。6.多重DES图2-9三重DES的加解密过程2.3.2AES1.AES概述AES的设计思想：采用Rijndael结构，不属于Feistel结构；加密、解密相似但不对称；支持128/32=Nb数据块大小；支持128/192/256(/32=Nk)密钥长度；有较好的数学理论作为基础；结构简单、速度快。2．AES加密原理AES加密数据块分组长度可以有3种选择，即128、192和256位，用Nb表示分组长度，单位为32位字，则Nb=4、6、8；密钥长度可以是128位、192位、256位中的任意一个（如果数据块及密钥长度不足时，会补齐），用Nk表示密钥长度，单位为32位字，则Nk=4、6、8。AES也通过若干轮连续的迭代来对明文进行加密。Nr的取值Nb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414表2-6AES加密轮数Nr的取值2．AES加密原理AES加密有很多轮的重复和变换。大致步骤如下：a.密钥扩展（KeyExpansion）;b.初始轮（InitialRound）;c.重复轮（Rounds），每一轮又包括：SubBytes、ShiftRows、MixColumns、AddRoundKey;d.最终轮（FinalRound），最终轮没有MixColumns。AES-128的加解密过程2．AES加密原理各轮AES加密循环（除最后一轮外）均包含4个步骤：AddRoundKey—矩阵中的每一个字节都与该次回合金钥（roundkey）做XOR运算；每个子密钥由密钥生成方案产生。SubBytes—通过个非线性的替换函数，用查找表的方式把每个字节替换成对应的字节。ShiftRows—将矩阵中的每个横列进行循环式移位。MixColumns—为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每列的四个字节。

最后一个加密循环中省略MixColumns步骤，而以另一个AddRoundKey取代。2．AES加密原理以AES-128为例，128位的明文分组采用128位的密钥加密，分别介绍轮变换中的4个步骤。在进行变换之前，首先将128位的明文以字为单位分别写入“状态”矩阵中。状态的矩阵表示：S00S01S02S03S04S05S06S07S08S09S10S11S12S13S14S152．AES加密原理

2．AES加密原理②行移位变换（ShiftRows（））行移位变换ShiftRows（）是线性变换，其目的是使密码信息达到充分的混乱，提高非线性度。行移位变换在状态矩阵的每行间进行，对每行实施左循环移动，移动字节数根据行数和密钥长度来确定。当Nb=4,Nk=4时，第零行不移位，第一行移1位，第二行移2位，第三行移3位。如图所示。2．AES加密原理③列混合MixColumn变换列混合是对状态列的代替操作，将状态列看作有限域GF(28)上的4维向量并被有限域GF(28)上的一个固定可逆方阵A乘所得的新状态列。2．AES加密原理④轮密钥加变换AddRoundKey（）AES的每一轮变换都需要一个轮密钥，每个轮密钥都是128位。AES-128采用128位密钥时，需迭代10轮，需11个轮密钥，即44个32位字（w0,w1,…，w43）。在进行密钥加之前，将128位的密钥以字为单位分别写入“密钥”矩阵中。K0K4K8K12K1K5K9K13K2K6K10K14K3K7K11K152．AES加密原理w0=k0k1k2k3,w1=k4k5k6k7,w2=k8k9k10k11,w3=k12k13k14k15。之后的每个轮密钥wi根据wi-1和wi-4来计算。3．AES安全性分析AES有更长的密钥，密钥长度可为128bits、192bits和256bits三种情况，明显提高了加密的安全性，同时，对不同机密级别的信息，可采用不同长度的密钥，执行灵活性较高。AES的均衡对称结构既可以提高执行的灵活度，又可防止差分分析方法的攻击。3．AES安全性分析AES算法的迭代次数最多为14次，S盒只有一个，较之DES的16次迭代和8个S盒要简单得多。使用有限域逆运算构造的S盒，可使线性逼近和差分均匀分布。有效抵抗了线性攻击和差分攻击。AES算法在所有的平台上都表现良好。对目前所有已知攻击而言，AES是安全的。2.3.3对称密码的工作模式1.电子密码本（ECB）模式(a)ECB加密过程(b)ECB解密过程1.电子密码本

（ECB）模式电子密码本模式是使用分组密码最明显的方式：一个明文分组加密成一个密文分组，Ci=EK(Pi)

Pi=DK(Ci)。因为相同的明文永远被加密成相同的密文分组，所以理论上制作一个包含有明文及其对应的密文的密码本是可能的。但是，如果分组的大小为64位，那么密码本就有264项，对于预计算和存储来说，实在是太大了。2.密码分组链接

（CBC）模式（a）CBC的加密过程（b）CBC的解密过程2.密码分组链接

（CBC）模式CBC模式下，每加密一组明文消息P，首先随机生成一个初始向量IV。第一组明文分组P1与IV异或后再代入加密算法，之后的每个明文分组都要先和前一个分组的密文进行异或，然后再进行加密，即Ci=EK(Ci-1

Pi)

Pi=DK(Ci)

Ci-1需要注意的是，IV和所有密文分组一起构成最后的密文段，发送到接收端。接收端在没有IV的情况下将无法对密文进行解密。3.密文反馈

（CFB）模式采用密文反馈模式CFB是将64位的初始值IV使用密钥K进行加密后，取密文中的j位和明文Pi进行以后运算，得到密文Ci。密文Ci作为下一组的初始值再参与下一组的加密运算。（a）CFB模式的加密过程（b）CFB模式的解密过程2.4公钥密码体制2.4.1概述1.对称密码体制的不足密钥管理量的困难密钥协商和交换的安全性问题数字签名的问题2.基本概念公钥密码体制指一个加密系统的加密密钥和解密密钥是不一样的，或者说不能由一个推导出另一个。其中一个称为公钥用于加密，是公开的；另一个称为私钥用于解密，是保密的。公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此也称为双密钥体制。双钥体制的公钥是公开的，因此也称为公钥算法。3.公开密钥密码的重要特性公钥密码体制的加密与解密由不同的密钥完成：加密:X

Y:Y=EKU(X)解密:Y

X:X=DKR(Y)=DKR(EKU(X))知道加密算法，从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)X=DKR(EKU(X))=EKU(DKR(X))4.公钥密码体制的应用（1）基于公开密钥的加密模型4.公钥密码体制的应用（2）基于公开密钥的鉴别过程4.公钥密码体制的应用（3）公钥密码的应用范围加密/解密：发送方用接收方的公开密钥加密报文数字签名：发送方用自己的私有密钥签署报文。密钥交换：两方合作以便交换会话密钥算法加/解密数字签名密钥交换RSA是是是Dieffie-Hellman否否是DSS否是否5.常用的公开密钥算法当今最流行的公钥密码体制有两大类：基于大整数因子分解问题的，比如RSA体制、Rabin体制基于离散对数问题的，比如ElGamal体制、椭圆曲线密码体制ECC、Diffie-Hellman密钥交换2.4.2RSA算法RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的，也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。1.RSA算法描述（1）密钥产生选两个保密的大素数p和q。计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。选一整数e，满足1<e<φ(n)，且gcd(φ(n),e)=1。计算d，满足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。以{e,n}为公钥,{d,n}为私钥。1.RSA算法描述（2）加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：c≡memodn（3）解密对密文分组的解密运算为：m≡cdmodn1.RSA算法描述证明RSA算法中解密过程的正确性。证明：由加密过程知c≡memodn，所以cdmodn≡medmodn≡m1modφ(n)modn≡mkφ(n)+1modn分两种情况：m与n互素，则由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn，即cdmodn≡m。gcd(m,n)≠1，mkφ(n)+1≡mmodn，所以cdmodn≡m。2.RSA算法举例选择素数:p=17&q=11计算n=pq=17×11=187计算ø(n)=(p–1)(q-1)=16×10=160选择e:gcd(e,160)=1;选择e=7确定d:de=1mod160andd<160，d=23因为23×7=161=1×160+1公钥KU={7,187}7.私钥KR={23,17,11}2.RSA算法举例RSA的加解密为:给定消息M

=

88(

88<187)加密:C=887mod187=11解密:M=1123mod187=883.RSA算法的安全性分析RSA的安全性是基于分解大整数的困难性假定，之所以假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。如果RSA的模数n被成功地分解为p×q，则立即获得φ(n)=(p-1)(q-1)，从而能够确定e模φ(n)的乘法逆元d，即d≡e-1modφ(n)，因此攻击成功。若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来。3.RSA算法的安全性分析随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130已于1996年4月被成功分解。对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。4.RSA实现中的问题（1）如何计算ammodn（2）密钥产生素数选取e和d的选取5.RSA可能遭受的攻击（1）RSA的选择密文攻击E（攻击者）监听A的通信，收集由A的公开密钥加密的密文e，E想知道消息的明文m，s使m=cdmodn。E首先选择随机数r，使r＜n。然后用A的公开密钥e计算：x=remodny=xemodnt=r-1modn如果x=remodn,则r=xdmodn。现在E让A对y签名，即解密y,A向E发送u=ydmodn。E计算tumodn=r-1ydmodn=r-1xdcdmodn=cdmodn=m5.RSA可能遭受的攻击（2）对RSA的攻击－共模攻击在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明文消息是m，密文分别是c1≡me1(modn)；c2≡me2(modn)。敌手截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足re1+se2=1的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c-11，由此得(c-11)-rcs2≡m(modn)。思考大家学习了DES和RSA两种不同的加密机制，觉得那种更简单，更快速？

真正在运行的过程中，DES会更快，效率更高。DES虽然看起来变换多，但是都是简单的置换运算，运算速度是非常快的，而RSA算法看起来简单，但在真正运行的过程中，因为涉及到大素数的乘积运算，运算速度会很慢。引申

在我们日常生活中也一样，我们不能只看到事情的表面，看起来复杂的过程，可能真正处理起来反而更简单快速；而看起来简单的事情，其实内里反而要我们静下来去花心思和时间来解决。所以，我们一定要多看，多思考，多比较，深入观察和理解事物的本质，才能不断的提升自己。2.4.3Diffie-Hellman密钥交换算法Diffie-Hellman密钥交换算法是第一个公钥方案，使用在一些商业产品中。该方案不能用于交换任意信息，允许两个用户可以安全地建立一个秘密信息，用于后续的通讯过程，该秘密信息仅为两个参与者知道。算法的安全性依赖于有限域上计算离散对数的难度。1.Diffie-Hellman密钥交换算法的数学基础素数p的原根定义：如果a是素数p的原根，则数amodp，a2modp，…，ap-1modp是不同的并且包含1到p-1的整数的某种排列，也即{amodp，a2modp，…，ap-1modp}={1，2，…，p-1}=Zp*对任意的整数b和素数p的原根a，可以找到唯一的指数x满足b=axmodp0<=x<=(p-1)x称为b以a(modp)为底数的指数（离散对数），记作x=logabmodp。2.Diffie-Hellman密钥交换算法描述双方选择素数p以及p的一个原根a用户A选择一个随机数Xa<p，计算Ya=aXamodp用户B选择一个随机数Xb<p，计算Yb=aXbmodp每一方保密X值，而将Y值交换给对方用户A计算出K=YbXamodp用户B计算出K=YaXbmodp双方获得一个共享密钥(aXaXbmodp)素数p以及p的原根a可由一方选择后发给对方3.Diffie-Hellman

实例用户Alice和Bob想交换密钥：约定素数p=353，a=3随机选择密钥：A选择xA=97,B选择xB=233计算公钥：YA=397mod353=40(Alice)YB=3233mod353=248(Bob)计算共享的会话密钥：KAB=YBxAmod353=24897=160(Alice)KAB=YAxBmod353=40233=160(Bob)4.Diffie-Hellman密钥交换的安全性分析Diffie-Hellman密钥分配方案必须结合实体认证才有用，否则会受到中间入侵攻击中间人攻击的过程如下：

双方选择素数p以及p的一个原根a(假定O知道)A选择Xa<p,计算Ya=aXamodp,A

B:YaO截获Ya,选Xo,计算Yo=aXomodp,冒充A

B:YoB选择Xb<p,计算Yb=aXbmodp,B

A:YbO截获Yb,冒充B

A:YoA计算:(Yo)Xa

(aXo)Xa

aXoXamodpB计算:(Yo)Xb

(aXo)XXb

aXoXbmodpO计算:(Ya)Xo

aXaXomodp,(Yb)Xo

aXbXomodpO无法计算出aXaXbmodp；O永远必须实时截获并冒充转发，否则会被发现。2.4.4ElGamal

密码体制ElGamal密码体制的安全性是基于求解离散对数问题的困难性。ElGamal密码体制是非确定性的，因为每次加密要选择一个随机数，相同的明文随着加密前随机数的不同而产生不同的密文。ElGamal密码体制既可以用于加密，也可以用于签名，其安全性依赖于有限域上计算离散对数的难度。1.ElGamal密码体制的算法描述密钥的产生：要产生一对密钥，首先选择一素数p，整数模p的一个原根g，随机选取x，g和x都小于p，然后计算：y=gxmodp公开密钥是y,g,p，g,p可以为一组用户共享私有密钥是x1.ElGamal密码体制的算法描述ElGamal加密算法：将明文信息M表示成{0,1,…,p-1}范围内的数。秘密选择随机数k,计算：a=gkmodpb=ykMmodpC=(a,b)作为密文ElGamal解密算法：设密文为C=(a,b),则明文为M=b/ax=modp验证：ax

gkxmodp,b/ax

ykM/ax

gxkM/gxk

Mmodp2.ElGamal

密码体制实例生成密钥：使用者Alice选取素数p=2357及Z2357*的生成g=2，Alice选取私钥x=1751并计算：gxmodp=21751mod2357=1185A的公钥是p=2357,g=2,gx=1185加密：为加密信息m=2035,Bob选取一个随机整数k=1520并计算：a=21520mod2357=1430，b=2035×11851520mod2357=697。Bob发送a,b给Alice解密：Alice计算a-x≡1430p-1-x

≡1430605≡872(mod2357)M≡b/ax

≡ba-x

≡697×872≡2035(mod2357)3.ElGamal

数字签名Elgamal数字签名主要也是利用离散对数的特性来实现签名，具体方式如下：（1）选择一个大素数P，一个本原元g，一个随机整数d，d属于[2，p-2]；

（2）生成β，β=gdmodP；

（3）此时P、g、β就是公钥，记作Kpub;3.ElGamal

数字签名（4