1、第第7章章 纠错码与通信系统的保密纠错码与通信系统的保密 7.1 基于纠错码的公钥密码体制基于纠错码的公钥密码体制 7.2 基于纠错码的私钥密码体制基于纠错码的私钥密码体制 7.3 基于纠错码的身份认证基于纠错码的身份认证 7.4 基于纠错码的数字签名基于纠错码的数字签名 7.1 基于纠错码的公钥密码体制基于纠错码的公钥密码体制 7.1.1 M公钥密码体制 M公钥密码体制是1978年McEliece利用一般线性码的译码问题是一个难解的数学问题和Goppa码有快速译码算法的特点，最早提出的一个基于纠错码的公钥密码体制，简称为M公钥体制。该体制的公钥是随机产生的一个线性分组码的生成阵，公钥隐藏了线
2、性分组码的快速译码算法，它是一种局部随机的密码体制。下面介绍M公钥密码体制的加、解密原理。设G是二元（n，k，d)Goppa码的生成矩阵，其中n2m，d2t1，kn-mt。随机地选取两个二元矩阵S和P，则公钥G为 GSGP （71）式中：Skk阶可逆矩阵；Gkn阶Goppa码生成矩阵；Pnn阶置换矩阵。私钥：S，G，P。加密过程：对于任意一个明文mGF(2)k，密文加密算法如下：cmGe (72)式中：eGF(2n）上重量为t随机矢量。解密过程：收方收到一个密文c以后，计算 cP1mSGPP1ePlmSGe，因为P是置换距阵，所以W(z)W(z)t，然后利用Goppa的快速译码算法将其译成mm
3、S，密文c对应的明文为mmS-1。则用户收到密文c后，用自己的秘密钥进行解密的步骤为（1）计算cP-1mGP-1+eP-1(mS)GeP-1；（2）对cP-1用有效的Goppa码译码算法进行译码译得mS；（3）计算(mS)S-1得明文m。McEliece系统的缺点是密钥长度较大，数据扩展率太大，优点是对同一公钥，一个明文可以对应许多个密文，从而增加了从密文破译的困难。对McEliece系统的破译一方面是求出密钥S-1，P-1，G；另一方面是由具体密文c来求对应的明文m。由现有的系统安全性分析可知，这两种破译方法都未发现有有效的算法。此系统还可纠正密文在传送中发生的错误，这种系统称为既加密又纠错
4、的系统。7.1.2 N公钥密码体制 N公钥密码体制是1986年Niederreiter提出的另一个基于纠错码的公钥密码体制，该体制是一个背包型公钥密码体制，简称N公钥密码体制。N公钥密码体制的公钥为随机产生的线性分组码的监督阵，与M公钥不同的是N公钥隐藏了具有快速译码算法的线性分组码的监督阵。下面介绍这个公钥密码体制的加、解密原理。设C是有q元线性（n，k，2t1)Goppa码，取两个q元矩阵 M、P，则公钥H为 HMHP （73）式中：H码C的(nk)n监督矩阵；Mq元(nk)(nk)非奇异矩阵；Pq元nn阶置换矩阵。私钥：H，M，P。加密算法：zy(H)T (74)式中：znk维密文；(H
5、)TH的转置矩阵；y重量为t的q元n维明文。解密运算：由zy(MHP)T知：z(MT)1y(PT)HT，由码的快速译码算法得到yPT，因此可以求出y。7.1.3 M公钥密码体制与N公钥密码体制的关系 李元兴、王新梅等于1994年在IEEE信息论汇刊上发表论文,证明了M公钥和N公钥密码体制是等价的。假定M公钥密码体制和N公钥密码体制采用的是相同的（n，2t+1）线性码C，则M密码体制的公钥为 GS1GP （75）式中：S1价可逆矩阵；Pnn阶置换矩阵；G码C的生成矩阵。M公钥密码体制的私钥：S1，G，P。N密码体制的公钥为 S2HP （76）式中：S(n-)(n-)阶可逆矩阵；Pnn阶可逆矩阵；
6、码C监督矩阵。N公钥密码体制的私钥：S2，H，P。M公钥密码体制中的加密方程：cmGe （77）将方程（77）两端乘(H)T得：zc(H)TmG(H)T e(H)Te(H)T 给定z和，若e能被发现，也就是说若N体制被打破，则M体制被打破，即密文m可以在多项式时间内被获得。因此，破译M体制不会比破译N体制难。N密码体制中的加密方程：zy(H)T （78）则在多项式时间里可以求得一个长为n的码字c，使得：zc(H)T （79）又因为c可以表示成为 cmGy （710）式中：m一个维明文。7.1.4 Ms公钥密码体制 在M公钥密码体制中，密文通过信道时不能有干扰。若密文通过信道时有干扰，则收端收到
7、的密文为 ccz （711）式中：mGe；z信道产生的错误图样。这时，在解密过程中错误图样ze的汉明重量很可能大于码的纠错能力，若进行译码，就得到错误的码字，这样势必得到与原明文不同的错误明文。事实上没有纠错能力的所有密码体制都存在这个问题。接收端得到错误明文后，由于看不懂明文，知道在传输过程中产生了错误，可以要求对方重发，这样就降低了通信效率，而重发又增加了通信的不安全性。王新梅给出克服上述缺点的另一个方法，对M公钥进行了修正，使其具有一定的纠错能力或检错能力。下面介绍这种修正的M公钥体制，即Ms公钥体制。设明文为m，则对应的密文为 csmGses （712）式中：GsSGP；es是一个长为
8、n的二进制随机序列,且它的重量为 W(es)=tst 显然，当tst时，Ms公钥就是M公钥，因此M公钥可以看成Ms公钥的特殊情况，Ms公钥体制可以看成是M公钥的推广。Ms公钥体制解密算法与M公钥密码体制的基本相同。所不同的是，当密文在有扰信道中传输时，若信道产生的错误图样e的重量(e)t-ts，则Ms公钥体制能保证解密后所得明文的正确性，而M公钥体制不具有这个性能。攻击M公钥的有关算法都可用来攻击Ms公钥体制，由于tst，所以Ms公钥体制的安全性要比M公钥体制弱，但也有足够的强度。表71列出用（2048，1388，121）Goppa码，取ts55时构造的Ms公钥体制复杂度与错误个数的关系，采用
9、的攻击是LeeBrickell攻击。表71 复杂度与错误的关系 7.1.5 M公钥的安全性 M密码体制使用的是二元既约Goppa码，Goppa码的数量随参数的增加而快速增加。对M公钥密码体制的攻击可以归结为下列问题：对于一个加密矩阵G，若存在一个kk阶可逆矩阵S，nn阶可逆矩阵P，密码分析者知道其快速译码算法的C的生成阵G，且 GSGP。若这种情况发生，M公钥密码体制就可被攻破。但这种情况发生的概率是很小的。下面给出M公钥的几种攻击方法。1.已知码字的攻击 密码分析者随机地选n比特密文中的k比特，k比特没有错误的概率为 与kn阶矩阵G相对应的kk阶矩阵可逆的概率为qk，因此，任意取密文c的k比
10、特，它既没有错误且对应的kk阶子矩阵可逆的概率为qkpk，求一个kk阶可逆矩阵逆的时间复杂度为(k3)，因此，这种攻击的工作因子为(k3qkpk)。这是1978年McEliece给出的一种攻击方法。/ntnkk 2.错误图样攻击 随机地选取kn阶矩阵G的k列j1，j2，jk，且使其构成kk阶可逆矩阵Gk，令yk，zk分别表示由n维矢量y和z的第j1，j2，jk个分量构成的k维矢量，因此ykzkmGk,(ykzk)(Gk)-1mG。取k比特码字zk,zk的汉明重量小于等于j(jc)，若y(yk+zk)(Gk)-1 G的重量为t，则zk=zk,因此密文m(ykzk)(Gk)-1，否则选另一个k维矢
11、量zk重复上面的步骤。若重量小于等于j的k比特矢量被用完，但消息还未恢复出来，取kn阶矩阵G的另一个kk阶子矩阵，重复上面的步骤，直到明文m被发现为至。3.最小汉明重量的码字攻击 设yxGz是一个接收码字，这里G是(n，k，d)线性码的生成矩阵，z是重量为t的错误矢量;(k1)n阶矩阵G/z是(n,k1，t)线性码的生成阵。因此，发现一个码的最小重量的码字对应于发现错误矢量z。若有算法能发现一个码的最小重量的码字，就可被用来攻击M体制。但发现一个码的最小重量的码字是一个NP完全问题，因此，通过这种方法攻击，似乎也是很困难的。4.消息重发攻击 1997年，Berson提出两种对McEliece体
12、制的攻击方法，即消息重发攻击(messaGeresendattack)和相关消息攻击(relatedmessaGeattack)。考查具有如下参数的McEliece体制，n1024，k524，t50，下面先介绍消息重发攻击。5.相关消息攻击 若两个消息m1，m2被加密，假定密码分析者知道m1m2，那么密码分析者知道：c1m1e1，c2m2Ge2 这里m1m2，e2e1。因此，c1c2m1e1m2Ge2 (m1m2)e1+e2 由于预先知道m1m2，可计算(m1m2)G，因此，c1c2(m1m2)e1e2 类似于消息重发攻击，仅需要次数比较少的猜测就能攻击成功。消息重发攻击可看成相关消息攻击的特
13、例。虽说Berson的分析不够严密，但他给出的攻击方法从一定程度上也指出了M公钥存在的弱点。7.1.6 M公钥的变型 下面给出为了抗击Berson的两种攻击，HunGMinSun提出的如下变型的M公钥方案。1.变型1 1)加密 c(m+h(e)Ge (713)式中：e重量为t的n比特随机矢量；h输入为n比特、输出为k比特的单向Hash函数。2)解密 由M公钥的解密算法可得mh(e)，然后计算m(m+h(e)h(e)。3)安全性 设m1和m2是两个消息。假定m1m2，则c1c2(h(e1)h(e2)Ge1e2,(h(e1)h(e2)G。由于不知道h(e1)，h(e2)，因此也不知道(h(e1)h
14、(e2)G，密码分析者很难确定出错误位置，消息重发攻击不会成功。假定密码分析者知道m1m2的值，那么 c1c2(m1m2h(e1)+h(e2)Ge1e2 虽然密码分析者知道m1m2的值，但不知道h(e1)，h(e2)，因此也不知道(m1m2h(e1)h(e2)G，密码分析者很难确定出错误位置，相关消息攻击也不能成功。对M公钥进行以下变型，也能够防止erson的两种攻击方法。2.变型2 1)加密 cf(m，e)Ge (714)式中：e重量为t的n比特随机矢量；f单向函数。单向函数f满足给定f(m，e)而确定m，e在计算上是不可行的，但在知道f(m,e)，e时，很容易计算m。2)解密 首先利用M公
15、钥的解密算法求得f(m,e)，e，然后利用f(m,e)，e求得m。7.1.7 增加M公钥的传信率 M公钥的传信率比较低，大约为0.5，因此有些学者提出了改进M公钥传信率的方法。1)加密 设消息m(ma，mb)。密文cmaGe，这里eG(mb)，G是一个将mb映射到重量为t的n比特错误矢量的可逆映射。2)解密 ma可以通过M公钥的解密算法得到，同时也就得到了G(mb)，那么mbg1g(mb)。3)信息率 通过这种方法可以改变M公钥的信息率。例如若k524，n1024，t50时，M公钥的信息率为0.51，变型后的M公钥的信息率为0.79；若k654，n1024，t37时，M公钥的信息率为0.63，
16、变型后的M公钥的信息率为0.87。4)安全性 变型后的M公钥体制的基本思想与原M公钥的基本相同，其主要差别是错误矢量的随机性问题。变型后的M公钥的错误矢量不是真正随机的，它由mb确定，这是一种确定性加密。设m(m1a，m1b)，m2(m2a，m2b)是两个要加密的消息，变型后的M公钥将消息分成两部分，因此它也暴露出如下可能的弱点。（1)若知道m1a，那么，G(m1b)c1m1aG，m1bG1(G(mb)。（2)若知道m1b，那么m1aGcG(m1b)，通过解方程，能很快算出m1a。（3)若知道m1am2a，m1bm2b，那么e1e2，c1c2（m1am2a)Ge1e2，因此可以获得有关错误位置
17、的一些信息。（4)若知道m1am2a，m1bm2b，那么(m1am2a)Gc1c2，因此通过解方程能很快地算出m1am2a。（5)若知道m1am2a的值和m1bm2b，那么c1c2（m1am2a)Ge1e2，e1e2c1c2（m1a G，因此可以获得有关错误位置的一些信息。7.2 基于纠错码的私钥密码体制基于纠错码的私钥密码体制 7.2.1 Rao私钥密码体制 Rao私钥密码体制是由T.R.Rao于1984年提出的一个私钥密码体制，其基本思想是将McEliece公钥用于私钥密码体制。1)加密 令Zz|zGF(2)n，z的汉明重量为，m是k比特的明文，其对应的n比特密文c为 cmSGPz (71
18、5)式中：G二进制线性Goppa码(n，k,2t1)的生成矩阵；Skk阶二元可逆矩阵；Pnn阶置换矩阵；z从Z中随机选取的n比特矢量。私钥：G，S，P，SGP。2)解密 计算cPT，通过译码得到mS，计算mSS1得明文m。7.2.2 RaoNam私钥密码体制 从密码分析的角度看，当错误矢量的汉明重量约等于n2时，大数表决攻击方法不能成功。在此情况下，码字的每个码元被正确猜测的概率为12，这是最佳的。因此，RaoNam提出使用预先定义取自码C不同剩余类，其汉明重量约等于n2错误码字。同时他们还提出利用简单的纠错码(汉明重量小于等于6，码长最多为250比特)来获得私钥密码系统。设G是(n，k)Go
19、ppa码的生成矩阵，z是一个特指的错误图样，它的平均汉明重量大约为n2。1)加密方法令m是k比特的明文，则密文c为 c(mGz)P (716)式中：Gn阶加密矩阵（GSG）；S阶可逆矩阵；G汉明重量小于等于6的(n，)线性码的生成矩阵；Pnn阶置换矩阵；z随机选取的一个错误矢量。密钥：S，P，G，H，伴随错误表。2)解密方法 由加密运算公式（716）得：c(mGz)PmSGPzPmGPzP（717）令ccPT，则 cmGz （718）由（718）得：cHTmGHTzHTzHT （719）具体解密步骤如下：(1)利用公式（718）计算c；(2)根据公式（719）计算m；(3)通过伴随错误表，可以
20、找到z，同时可以算出mS。(4)根据mSS-1计算明文m。由于这个私钥密码体制安全性在很大程度上依靠于z的选取，所以，1989年RaoNam给出了下列选取z的方法：有限域GF(2)上的n维矢量空间GF(2)n关于(n，)线性码C有2n个陪集，每一个陪集对应于惟一一个伴随式，在每一个陪集中选定一个重量大约等于n2的码字，这样就形成2n-个重量大约等于n2的n重矢量。7.2.3 LW私钥密码体制 根据RaoNam方案，李元兴和王新梅提出了一个可用作加密和认证的私钥密码体制。这一方案被称为LW私钥密码体制。1.基本原理 假定码率R0.5，即kn-k，则L-W体制的加、解密方法如下所述。1)加密 （1
21、)将消息m分成k比特的组。（2)通信双方秘密地商定一种算法，从m中选定nk比特，构成nk比特的组m1。（3)将m1作为伴随式，通过查伴随错误表找出与其对应的n比特矢量z，zHTm1。（4)根据公式（716）计算密文c。2)解密（1）利用公式（718）计算。（2）根据公式（719）计算m1（m1zHT）。（3)利用伴随错误表，找出错误矢量z，并恢复mS。（4)根据mSS1恢复明文m。（5)收方利用他与发方商定的选取方法，从m中选取n比特，并与第二步算出的m1进行比较。若传输中没有错误，选取的nk比特与m1相等，则消息m是明文，且m被认证。若传输中有错误，或密文被敌手篡扰过，这时收方收到的密文是：
22、c*cze （720）即 c*mSGPzemSGP(zz*e)P （721）式中:z*ezePT。2.一个等价方案 下面介绍的加密和解密算法等价于LW方案。先给出一个定义：令GB是(2k-n)n阶二元矩阵，其右逆为G-1B，HB为GB生成的线性码的监督矩阵。定义集合：H(xA，y)|yxGfA(x)，xB0，xAGF（2）nk 为了便于叙述，令yH（xA），xA H1（sB）。1)加密 k比特明文x对应的n比特密文：yB(x)GBH（A(x)（722）2)解密 计算 sByHTB，xAH1(sB)xB(yH（xA）G-RB 则明文为 x1(xA)1(xB)（723）密钥：GB，HB，H，H1，
23、集合A，B。3.安全性分析 LW私钥密码体制与RaoNam密码体制的基本思想相同，其惟一的差别是此私钥密码体制的错误矢量被用作认证和加密两个目的。为了便于密码分析，1994年J.vanTilberG给出下述一个与LW方案等价的定义。设nkk，A是在集合1，2，k中随机的选取一个子集a1，a2，,ank，这里a1a2tA且能被译码器发现，则译码器发出一指令表示收到的Cj有误，要求用户重发签名，若E0，则译码器正确译码，得到Cj和Ej。(3)右乘JA。D3(Cj)CjJA (EjMSAGA)PAP-1AG*AS-1A EjG*AS-1AM （738）(4)计算。D4(Cj)D3(Cj)EjWA E
24、jG*AS-1A+MEjG*AS-1AM（739）若此时得到的M与收到的M相同，则签名正确，否则签名有误。由以上讨论可知，若PA是一个nn阶置换矩阵，则W(E)W(EP-1A)，因而如果W(Ej)en且W*A满足以下关系：AW*AIn （750）签名方法如下：用户A随机地选择一个汉明重量W(E)tA的二元n重E，以及长为ln的二元随机矢量Z，且W(Z)l2，则用户A对消息M的签名是长为l的序列 C（Ef（M，E）EG*A GA）PA ZW*AAZ (751)A把M，C，f（M，E）送给用户B。2.Xinmei修正方案 Xinmei修正方案是2000年，王新梅应用类似于AW方案，对原来的Xinm
25、ei方案进行修正，得到比AW方案更为简单的修正Xinmei方案。其签名算法如下：C（Eh（M，E）SAGA）PA (753)或 C（Eh（M，E，t）SAGA）PA，C （Eh（M，t）SAGA）PA （754）式中：h(x，y)和h(x，y，t)非线性单向Hash函数；t签名时间；M长为k的消息序列；E长为n的重量W(E)tA的二元随机序列；h(M，E)、h(M，E，t)和h（M，t）长为k的二元序列。因此修正Xinmei方案的公钥、私钥及签名算法与原Xinmei方案的相同，仅仅多了一次Hash函数h(M，Ej)或h(M，Ej，tj)的计算。用户A把(M，Cj)或(M，Cj，tj)送给用户B
26、。用户B的验签过程与原Xinmei方案的相同，这里不再重复。用户B在验签过程中得到h(M，E)或h(M，Ej，tj)和Ej后，再由收到的M和Ej计算h(M,Ej)，若 h(M,E)h(M,E j)（755）则说明签名有效，否则签名无效，要求用户A重发签名。7.4.4 对AW方案和Xinmei方案的通用伪造攻击 AW方案和Xinmei修正方案对AW攻击是安全的。1994年AlabbadiM等提出了两种对AW方案和Xinmei方案的通用伪造攻击方法。由Xinmei方案可知，用户A对消息M的签名是：C（EM SAGA）PA EPAMSAGAPA Ej MQA （756）式中：EjEPA；QASAGA
27、PA。若攻击者已知QA以及至少知道任一个E j，则可用以下方法伪造签名。设攻击者需对消息M1伪造签名，则仅需计算：C1EjM1QA （757）显然C1能通过验签运算。这种伪造签名方法对AW方案是有效的。可用以下方法找到QA。令Cj和Cj分别是消息Mj和Mj的签名，Ej是这两个签名过程中所用的相同的错误图样，则对于Xinmei方案有：CjCj（MjMj）Q （758）对修正Xinmei方案有：CjCj （h（M，E）h（M，E）Q（759）如果能得到k对消息的签名：Cj，Cj(1，2，k)且每对所用的E相同，则可得：C1C1（M1 M1）QAC2C2 （M2 M2）QA CkCk（Mk Mk）Q
28、A 由此可得：CMQA （760）式中：11112222KkKkCCMMCCMMCMCCMM 若M矩阵为满秩，则可以找到QAMC，其工作因子仅为(k)。因此只要找到k对线性无关的消息，且每对消息使用相同的E，就可找到QA。由此可知，这种攻击方法成功的关键是找到使用相同E的签名C和Cj。假定用户A在签名过程中，E是在所有可能的错误图样数目1/21!(1)(2)!()!AAttAAiAAAAnnne ntNttitntt （761）中等概地选取，则由生日攻击可知，预期所需的签名数目约为 ，就能以大于12的概率得到一对有相同E的签名。因此这种攻击方法成功的概率约为()On1()cpkO n(762)
29、7.4.5 签名、加密和纠错相结合的公钥体制 1.体制的构造 用户A和B各从GF(2)上选择不同的 （n，k，d2t1)既约Goppa码 A和 B。并分别公布以下公钥：HAAPA HBP 式中:HA和HB分别是A和的监督矩阵，PA和 P是nn阶的GF(2)上不同的满秩随机矩阵。用户A和B保留各自的私钥:HA，PA和H，P。设A选取的消息集合SM是GF(2)上(n-k)维线性空间中的一个子集，且对任一个消息MASM，通过等式(译码)MAEAHTA （763）总能很快找到一个EA，且其汉明重量W(EA)t，SM中的元素数目为N。用户A和B正式通信前，A先要把SM中的N个消息矢量依次按图71，或通过
30、安全信道送给B，B按图72接收，则可恢复出这个矢量。A和B都秘密存储SM，并约定A和B的消息空间是SM。图71 签名、加密和纠错编码的实现 MA乘法器右乘 PA乘法器右乘(HB)TCACA EeEe图72 纠错译码、解密和验签的实现乘 法 器 右乘 PBMAEACA Ee 2.签名、加密和纠错编码的实现 1)签名 用户A将消息MASM送入A码的译码器，由SM的性质可知，MA经过译码后必然惟一地得到EA，且W(EA)t，即 MAEAHTA (764)对EA右乘(PTA)PA，便得到了对MA的签名EA：EAEAPA (765)2)加密 A利用HB的转置矩阵(HB)T，对EA右乘运算，得到(n-k)
31、维矢量：SAEA(HB)T (766)3)纠错编码 A把HB看作是A码的对偶码B的生成矩阵。由对偶码的性质可知，B码一定是（n，n-k，d2t1)Goppa码，这里d是B上的最小距离。利用 B码编码器对SA进行纠错编码，从而得到消息MA经签名、加密和编码后的n重密文：CASAHB (767)用户B收到的是 CA=CAEe 式中:Ee是信道干扰引起的错误图样。1)纠错 只要W(Ee)t，则CA送入B码译码器后，总可纠正Ee，从而得到CA。首先用P-1B右乘CA，得到：CAP-1B（CAEe）P-1 SAHBP-1BEeP-1B =SAPP-1EeP-1B =SAEeP-1B (768)2)解密
32、用B译码器对SA译码，因W(EAP-TB)t，故译码器可以得到EAPTB，并计算EAPTBPBEA得到EA。3)验签 对EA右乘(HA)T，由式(764)、(765)得：EA(HA)TEAPAPTAHTAEAHTA=MA （769）3.体制的安全性分析 1)加密方案安全性 由式(764)知，攻击者已知密文CA和公钥HB 后，求出SA用多项式时间，故可以假设攻击者已知SA、HA和HB。攻击者寻求MA的方法可以有以下几种：(1)求出EA。若已知EA，则由式(7-69)可求得消息MA。求EA的方法有以下几种：(a)根据式(766)和已知的SA、(HB)T，便可得到EA。但因HB 是一般线性码的一致监
33、督矩阵，且W(EA)t因此求 A相当于一般线性码的译码，这是一个NPC问题。(b)随机猜测EA，其计算复杂度为 (c)分解HB，得到HB和PB，再用B译码器译出EA，但分解HB为HB与PB的乘积很困难。用穷搜索方法的计算复杂度为(n!)或(2mt)。0tinOi (d)根据方程CAEA（HB)THB=EAHB，和已知的CA和(HB)THB，解方求EA。但由于HB不是满秩的nn阶矩阵，且W(EA)t，因此求EA也是NPC问题。(2)直接猜测MA，此时的计算复杂度是(2nk)。2)签名方案的安全性 (1)若攻击者已知SM，则有以下几种方法伪造A的签名：(a)根据式(769)和已知的MA、(HA)T，求出MA的签名EA，显然这也是一个NPC问题。(b)分解HA得到HA和PA，再利用式(764)和式(765)，就可伪造用户A的签名。但这种分解的计算复杂度为（n！）或（2mt）。（c）随机猜测消息MA的签名EA，此时的计算复杂度为 (2)若攻击者不知道SM，则他想伪造用户A的签名比已知 SM时的更为困难。0tinOi
