公钥密码体制及典型算法演示文稿

公钥密码体制及典型算法演示文稿当前1页，总共146页。公钥密码体制及典型算法当前2页，总共146页。

在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个基本工具。而公钥密码体制则为密码学的发展提供了新的理论和技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。1公钥密码体制的基本概念当前3页，总共146页。

公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。单钥密码体制在进行密钥分配时,要求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。

1976年W.Diffie和M.Hellman对解决上述两个问题有了突破，从而提出了公钥密码体制。公钥密码体制的基本概念当前4页，总共146页。对称密码体制的缺陷密钥分配问题通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；密钥管理困难问题在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大。

n用户保密通信网，用户彼此间进行保密通信需要个密钥。

n=1000：499500个密钥

n=5000：12497500个密钥没有签名功能，无法实现抗抵赖问题：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。

陌生人间不便进行保密通信问题当前5页，总共146页。别名：公钥密码体制，双钥密码体制两个密钥：公开密钥（公钥）：可以被任何人知道,用于加密或验证签名秘密密钥（私钥）：只能被消息的接收者或签名者知道,用于解密或签名。

加密或验证签名者不能解密或生成签名（已知密码算法和加密密钥，求解密密钥在计算上是不可行的）。安全性基础：基于数学难题标志性文献

W.DiffieandM.E.Hellman,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公钥密码体制的基本概念当前6页，总共146页。由私钥及其他密码信息容易计算出公开密钥(apolynomialtime(P-time)problem)由公钥及算法描述,计算私钥是难的(anNP-timeproblem)因此,公钥可以发布给其他人(wishingtocommunicatesecurelywithitsowner)密钥分配问题不是一个容易的问题(thekeydistributionproblem)公钥密码体制的基本概念当前7页，总共146页。公钥算法分类Public-KeyDistributionSchemes(PKDS，公钥分配系统)

用于交换秘密信息(依赖于双方主体)常用于对称加密算法的密钥PublicKeyEncryption(PKE，公钥加密)

用于加密任何消息任何人可以用公钥加密消息私钥的拥有者可以解密消息任何公钥加密方案能够用于密钥分配方案PKDS许多公钥加密方案也是数字签名方案SignatureSchemes（签名方案）

用于生成对某消息的数字签名私钥的拥有者生成数字签名任何人可以用公钥验证签名当前8页，总共146页。公钥密码系统可用于以下三个方面：

(1)通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。

当前9页，总共146页。(2)数字签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读。当前10页，总共146页。(3)密钥交换：通信双方交换会话密钥，以加密通信双方后续连接所传输的信息。每次逻辑连接使用一把新的会话密钥，用完就丢弃。

当前11页，总共146页。公开密钥算法的特点:（1）发送者用加密密钥PK对明文X加密后，在接收者用解密密钥SK解密，即可恢复出明文，或写为：

DSK(EPK(X))X

解密密钥是接收者专用的秘密密钥，对其他人都保密。 此外，加密和解密的运算可以对调，即

EPK(DSK(X))X（2）加密密钥是公开的，但不能用它来解密，即

DPK(EPK(X))X

当前12页，总共146页。公开密钥算法的特点:（3）在计算机上可以容易地产生成对的PK和SK。（4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可能的”。（5）加密和解密算法都是公开的。当前13页，总共146页。

公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公钥密码体制也称为双钥密码体制。算法有以下重要特性：已知密码算法和加密密钥，求解密密钥在计算上是不可行的。公钥密码体制的原理当前14页，总共146页。图公钥体制加密的框图当前15页，总共146页。加密过程有以下几步：①要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥PKB，SKB，其中PKB是公开钥，SKB是秘密钥。②端系统B将加密密钥（如图中的PKB）予以公开。另一密钥则被保密（图中的SKB）。公钥密码体制的原理当前16页，总共146页。③A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKB[m],其中c是密文，E是加密算法。④B收到密文c后，用自己的秘密钥SKB解密，表示为m=DSKB[c]，其中D是解密算法。公钥密码体制的原理当前17页，总共146页。公钥密码体制认证框图当前18页，总共146页。

因为只有B知道SKB，所以其他人都无法对c解密。公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证，如下图所示。用户A用自己的秘密钥SKA对m加密，表示为c=ESKA[m]

将c发往B。B用A的公开钥PKA对c解密，表示为m=DPKA[c]公钥密码体制认证的原理当前19页，总共146页。

因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。另一方面，任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证。公钥密码体制认证的原理当前20页，总共146页。

在实际应用中，特别是用户数目很多时，以上认证方法需要很大的存储空间，因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容。改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符。认证符具有这样一个性质：如果保持认证符的值不变而修改文件这在计算上是不可行的。用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。公钥密码体制认证的原理当前21页，总共146页。

以上认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。如下图所示。公钥密码体制认证的原理当前22页，总共146页。公钥密码体制的认证、保密框图当前23页，总共146页。

发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为

c=EPKB[ESKA[m]]解密过程为

m=DPKA[DSKB[c]]

即收方先用自己的秘密钥,再用发方的公开钥对收到的密文两次解密。公钥密码体制认证的原理当前24页，总共146页。公钥保密和认证体制

当前25页，总共146页。公钥密码算法应满足以下要求:①接收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。②发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKB[m]在计算上是容易的。③收方B用自己的秘密钥对c解密，即m=DSKB[c]在计算上是容易的。公钥密码算法应满足的要求当前26页，总共146页。④敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的。⑤敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的。⑥加、解密次序可换，即EPKB[DSKB(m)]=DSKB[EPKB(m)]

其中最后一条虽然非常有用，但不是对所有的算法都作要求。公钥密码算法应满足的要求当前27页，总共146页。

以上要求的本质之处在于要求一个陷门单向函数。单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像x∈X，且由x易于计算它的像y，由y计算它的原像x是不可行的。这里所说的易于计算是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na的某个倍数，其中a是一固定的常数。这时称求函数值的算法属于多项式类P，否则就是不可行的。例如，函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的。公钥密码算法应满足的要求当前28页，总共146页。

注意这里的易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别。在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。而在此所说的两个概念是指算法在几乎所有情况下的情形。称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成。公钥密码算法应满足的要求当前29页，总共146页。

总结为：陷门单向函数是一族可逆函数fk，满足①Y=fk(X)易于计算（当k和X已知时）。②X=f-1k(Y)易于计算（当k和Y已知时）。③X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）。因此，研究公钥密码算法就是要找出合适的陷门单向函数。公钥密码算法应满足的要求当前30页，总共146页。

和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。对公钥密码算法的第2种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。对公钥密码体制的攻击当前31页，总共146页。

还有一种仅适用于对公钥密码算法的攻击法，称为可能字攻击。例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较。如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，这种攻击的本质是对56比特DES密钥的穷搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。对公钥密码体制的攻击当前32页，总共146页。强力攻击(对密钥)

密钥不能太短，防止密钥穷举但也不能太长，以免影响速度公开密钥算法本身可能被攻破赖以安全的基石----数学难题被破解可能报文攻击(对报文本身的强力攻击)

对所有可能报文加密，直到与截获密文相同对公钥密码体制的攻击当前33页，总共146页。RSA算法是1978年由罗纳德·李维斯特（RonRivest）、阿迪·萨莫尔（AdiShamir）和伦纳德·阿德曼（LeonardAdleman）提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。它既可用于加密、又可用于数字签字。

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

RLRivest,AShamir,LAdleman,"OnDigitalSignaturesandPublicKeyCryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb19782RSA算法当前34页，总共146页。由Rivest,Shamir和Adleman在1978年提出数学基础:

大整数因子分解的困难性，Euler定理当前35页，总共146页。1.密钥的产生①选两个保密的大素数p和q(各100～200位十进制数字，且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)互素，由模运算可知，它的乘法逆元一定存在。

d=e

-1(mod(n))⑤以{e,n}为公开钥,{d,n}为秘密钥。(p,q不再需要，可以销毁)算法描述当前36页，总共146页。2.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：c≡memodnRSA加密算法描述当前37页，总共146页。3.解密对密文分组的解密运算为：m≡cdmodn

下面证明RSA算法中解密过程的正确性。证明：由加密过程知c≡memodn，所以cdmodn≡medmodn≡m1

modφ(n)modn≡mkφ(n)+1modnRSA解密算法描述当前38页，总共146页。下面分两种情况：①m与n互素，则由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn即cdmodn≡m。②gcd(m,n)≠1，先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)≠1意味着m是p的倍数或q的倍数，不妨设m=cp，其中c为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与m<n=pq矛盾。当前39页，总共146页。

由gcd(m,q)=1及Euler定理得mφ(q)≡1modq，所以mkφ(q)≡1modq,［mkφ(q)］φ(p)≡1modq,mkφ(n)≡1modq

因此存在一整数r，使得mkφ(n)=1+rq，两边同乘以m=cp

得mkφ(n)+1=m+rcpq=m+rcn

即mkφ(n)+1≡mmodn，所以cdmodn≡m。(证毕)RSA解密算法证明当前40页，总共146页。例：选p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确定满足d·e=1mod96且小于96的d，因为77×5=385=4×96+1，所以d为77，因此公开钥为{5，119}，秘密钥为{77，119}。设明文m=19，则由加密过程得密文为

c≡195mod119≡2476099mod119≡66解密为6677mod119≡19RSA解密算法证明当前41页，总共146页。RSA算法实例例假设Alice和Bob使用RSA密码体制进行全英文字符的保密通信。假设Alice选择、、，Bob选择、，并采用双字母加、解密方式。（1）说明Alice和Bob建立RSA密码体制的方法。（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。

当前42页，总共146页。4、RSA算法实例例（1）说明Alice和Bob建立RSA密码体制的方法。解①Alice计算：当前43页，总共146页。4、RSA算法实例例（1）说明Alice和Bob建立RSA密码体制的方法。解②Bob计算：当前44页，总共146页。4、RSA算法实例例5-1（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。

解

①Alice加密：“public”代换为数字并按双字母分组：152001110802当前45页，总共146页。4、RSA算法实例例（2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。

解②Bob解密：密文“009516491410”

明文:public当前46页，总共146页。1.RSA的加密与解密过程

RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677mod119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(a×b)modn=[(amodn)×(bmodn)]modn就可减小中间结果。RSA算法中的计算问题当前47页，总共146页。再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。 求am可如下进行，其中a，m是正整数： 将m表示为二进制形式bkbk-1…b0，即

m=bk2k+bk-12k-1+…+b12+b0因此RSA算法中的计算问题当前48页，总共146页。例如：19=1×24+0×23+0×22+1×21+1×20，所以a19=((((a1)2a0)2a0)2a1)2a1从而可得以下快速指数算法：c=0;d=1；Fori=kdownto0do{ c=2×c; d=(d×d)modn; ifbi=1then { c=c+1; d=(d×a)modn } }returnd.RSA算法中的计算问题当前49页，总共146页。

其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉。RSA算法中的计算问题当前50页，总共146页。

例求7560mod561。将560表示为1000110000，所以7560mod561=1。当前51页，总共146页。2.RSA密钥的产生

产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（10200≈2664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优越性了。因此如何有效地寻找大素数是第一个需要解决的问题。RSA密钥产生当前52页，总共146页。

寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。例如Miller-Rabin算法。RSA密钥产生当前53页，总共146页。

可见寻找大素数是一个比较繁琐的工作。然而在RSA体制中，只有在产生新密钥时才需执行这一工作。

p和q决定出后，下一个需要解决的问题是如何选取满足1<e<φ(n)和gcd(φ(n),e)=1的e，并计算满足d·e≡1modφ(n)的d。这一问题可由推广的Euclid算法完成。RSA密钥产生当前54页，总共146页。RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。如果RSA的模数n被成功地分解为p×q，则立即获得φ(n)=(p-1)(q-1)，从而能够确定e模φ(n)的乘法逆元d，即d≡e-1modφ(n)，因此攻击成功。RSA的安全性当前55页，总共146页。

随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130已于1996年4月被成功分解。RSA的安全性当前56页，总共146页。

对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分解。而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%。将来也可能还有更好的分解算法，因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。RSA的安全性当前57页，总共146页。

是否有不通过分解大整数的其他攻击途径？下面证明由n直接确定φ(n)等价于对n的分解。设n=p×q中，p>q，由φ(n)=(p-1)(q-1)，则有p+q=n-φ(n)+1以及由此可见，由p、q确定φ(n)和由φ(n)确定p、q是等价的。RSA的安全性当前58页，总共146页。为保证算法的安全性，还对p和q提出以下要求：（1）|p-q|要大由，如果|p-q|小，则也小，因此稍大于n，稍大于。可得n的如下分解步骤：①顺序检查大于的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。②由x2-n=y2，得n=(x+y)(x-y)。RSA的安全性当前59页，总共146页。RSA中p、q选择不当(|p-q|不大)的举例例：n=143,目标：分解n

解：当前60页，总共146页。（2）p-1和q-1都应有大素因子这是因为RSA算法存在着可能的重复加密攻击法。设攻击者截获密文c，可如下进行重复加密：

RSA的安全性当前61页，总共146页。RSA的安全性当前62页，总共146页。

设m在模n下阶为k，由得，所以k|(et-1)，即et≡1(modk)，t取为满足上式的最小值（为e在模k下的阶）。又当e与k互素时t|φ(k)。为使t大，k就应大且φ(k)应有大的素因子。又由k|φ(n)，所以为使k大，p-1和q-1都应有大的素因子。此外，研究结果表明，如果e<n且d<n1/4，则d能被容易地确定。RSA的安全性当前63页，总共146页。RSA中P、q选择不当(p-1或q-1没有大素因子)的举例例：p=17，q=11，e=7，则n=187。设m=123，则：

C1=1237mod187=183C2=1837mod187=72C3=727

mod187=30C4=307

mod187=123

明文m经过4次加密，恢复成明文。当前64页，总共146页。RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。1.共模攻击在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。对RSA的攻击当前65页，总共146页。

设两个用户的公开钥分别为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)。对RSA的攻击当前66页，总共146页。2.低指数攻击

假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni(i=1,2,3)，当i≠j时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，密文分别是:c1≡m3(modn1)c2≡m3(modn2)c3≡m3(modn3)由中国剩余定理可求出m3(modn1n2n3)。由于m3<n1n2n3，可直接由m3开立方根得到m。当前67页，总共146页。另一种欺骗性的攻击RSA当前68页，总共146页。思考题1.2.当前69页，总共146页。RSA参数选择需要选择足够大的素数p,q

通常选择小的加密指数e,且与ø(N)

互素e

对所有用户可以是相同的最初建议使用e=3现在3太小常使用e=216-1=65535

解密指数比较大当前70页，总共146页。(1)n=p×q的确定：p与q必须为强素数强素数p的条件：

(a)存在两个大素数p1和p2，p1|(p－1)，p2|(p＋1)(b)存在4个大素数r1,s1,r2及s2，使r1|(p1－1),r2|(p2－1),s1|(p1＋1),s2|(p2＋1)。p1和p2为二级素数；r1,r2,s1和s2为三级素数RSA参数的选择当前71页，总共146页。采用强素数的理由如下：若，pi为素数，ai为正整数分解式中pi<B，B为已知一个小整数则存在一种p－1的分解法，使我们易于分解n

令n=pq，且p－1满足上述条件，pi<B

令aai，i=1,2,…,t

可构造

显然(p－1)R，由费尔马定理2R1modp

令2R=xmodn，若x=1则选3代2，直到出现x1

此时，kR=1modp有解的充要条件是 kR=xmodn(p,n)=p|x-1

由GCD(x－1,n)=p，就得到n的分解因子p和qRSA参数的选择当前72页，总共146页。p与q之差要大若p与q之差很小，则可由n=pq估计(p＋q)/2=n1/2，由((p＋q)/2)2－n=((p－q)/2)2，等式右边为小的平方数，可以试验给出p,q的值例：n=164009，估计(p＋q)/2405，由4052－n=16=42，可得

(p＋q)/2=405，(p－q)/2=4，

p=409，q=401RSA参数的选择当前73页，总共146页。p－1与q－1的最大公因子要小惟密文攻击下，设破译者截获密文y=x

emodn破译者做下述递推计算：

xi=xi-1emodn=(xe)imodn

若ei=1mod(n)，则有xi=xmodn，且ei+1=emod(n)，即xi+1=x

若i小，则由此攻击法易得明文x。由Euler定理知，i=((p－1)(q－1))，若p－1和q－1的最大公因子小，则i值大，如i=(p－1)(q－1)/2，此攻击法难于奏效。RSA参数的选择当前74页，总共146页。p，q要足够大，以使n分解在计算上不可行RSA参数的选择当前75页，总共146页。e的选取原则(e,(n))=1条件易于满足，因为两个随机数互素的概率约为3/5e不可过小：若e小，x小，y=xe

modn，当xe<n，则未取模， 由y直接开e次方可求x，易遭低指数攻击

e小时，加密速度快，Knuth和Shamir曾建议采用e=3

但e太小存在一些问题选e在mod(n)中的阶数i(ei1mod(n))达到(p－1)(q－1)/2p，q要足够大，以使n分解在计算上不可行RSA参数的选择当前76页，总共146页。d的选择

e选定后可用Euclidean算法在多项式时间内求出dd小，签字和解密快，在IC卡中尤为重要(复杂的加密和验证签字可由主机来做)d要大于n1/4：类似于加密下的情况，d不能太小否则由已知明文攻击，构造y=xemodn，猜测d的值： 做ydmodn，直到试凑出ydxmodnWiener给出对小d的系统攻击法，证明了当d长度小于n的1/4时，由连分式算法，可在多项式时间内求出d值RSA参数的选择当前77页，总共146页。不可用公共模由一密钥产生中心(KGC)采用一公共模，分发多对密钥，公布相应公钥ei

这当然使密钥管理简化，存储空间小，且无重新分组问题但如前所述，它在安全上会带来问题。明文熵要尽可能地大

明文熵要尽可能地大，以使在已知密文下，要猜测明文无异于完全随机等概情况。用于签字时，要采用Hash函数

RSA体制实用中的其它问题当前78页，总共146页。RSA理论RSA基于Fermat'sTheorem:ifN=pqwherep,qareprimes,then:

Xø(N)=1modN

forallxnotdivisiblebyporq,iegcd(x,ø(N))=1

whereø(N)=(p-1)(q-1)但在RSA中，e&d是特殊选择的iee.d=1modø(N)

或e.d=1+Rø(N)

hencehave:

M=Cd=Me.d=M1+Rø(N)=

M1.(Mø(N))R=M1.(1)R=M1modN

当前79页，总共146页。RSA举例例子：1.选素数p=47和q＝71，得n=3337,(n)=46×70＝3220；2.选择e=79，求得私钥d=e-1

1019(mod3220）。3.公开n=3337和e=79.4.现要发送明文688，计算：68879(mod3337)=15705.收到密文1570后，用私钥d＝1019进行解密：

15701019（mod3337)=688当前80页，总共146页。RSA的实现问题需要计算模300digits(or1024+bits)的乘法计算机不能直接处理这么大的数（计算速度很慢）需要考虑其它技术，加速RSA的实现当前81页，总共146页。RSA的快速实现加密很快，指数小解密比较慢，指数较大利用中国剩余定理CRT，CRT对RSA解密算法生成两个解密方程（利用M=CdmodR）即:M1=Mmodp=(Cmodp)dmod(p-1)

M2=Mmodq=(Cmodq)dmod(q-1)

解方程M=M1modpM=M2modq具有唯一解（利用CRT

）：M=[((M2+q-M1)umodq]p+M1

其中p.umodq=1当前82页，总共146页。DES和RSA性能比较（同等强度）美国目前允许出口到我国的密码产品为512bitsRSA和40bits的某些私钥密码，说明美国已经有了破解方法！当前83页，总共146页。

设A=(a1,a2,…,an)是由n个不同的正整数构成的n元组，s是另一已知的正整数。背包问题就是从A中求出所有的ai，使其和等于s。其中A称为背包向量，s是背包的容积。例如,A=（43,129,215,473,903,302,561,1165,697,1523），s=3231。由于3231=129+473+903+561+1165

所以从A中找出的满足要求的数有129、473、903、561、1165。3背包密码体制当前84页，总共146页。

原则上讲，通过检查A的所有子集，总可找出问题的解（如果有解的话）。本例A的子集共有210=1024个（包括空集）。然而如果A中元素个数n很大，子集个数2n将非常大。如A中有300个元素，A的子集有2300。寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题是NPC问题。背包密码体制当前85页，总共146页。

由背包问题构造公钥密码体制同样是要构造一个单向函数f，将x(1≤x≤2n-1)写成长为n的二元表示0…001,0…010，0…011,…,1…111,f(x)定义为A中所有ai的和，其中x的二元表示的第i位为1，即

f(1)=f(0…001)=an f(2)=f(0…010)=an-1 f(3)=f(0…011)=an-1+an … f(2n-1)=f(1…111)=a1+a2+…+an

使用向量乘，有f(x)=A·Bx，其中Bx是将x的二元表示写成的列向量。背包密码体制当前86页，总共146页。

上例中f(364)=f(0101101100)=129+473+903+561+1165=3231，类似地可求出:f(609)=2942,f(686)=3584,f(32)=903,f(46)=3326,f(128)=215,f(261)=2817,f(44)=2629,f(648)=819。由f的定义可见，已知x很容易求f(x)，但已知f(x)求x就是要解背包问题。当然在实际应用中，n不能太小，比如说，至少为200。背包密码体制当前87页，总共146页。

用f对明文消息m加密时，首先将m写成二元表示，再将其分成长为n的分组（最后一个分组不够长的话，可在后面填充一些0），然后求每一分组的函数值，以函数值作为密文分组。例如，明文消息是英文文本，则可将每个字母用其在字母表中的序号表示，再将该序号转换为二进制形式（5位即可），如表4.5所示，其中符号‘

’表示空格。（见102页表4.5）背包密码体制当前88页，总共146页。

背包向量仍取上例中的A，设待加密的明文是SAUNAANDHEALTH。因为A长为10，所以应将明文分成长为10比特（即两个明文字母）的分组SA，UN，A‘

’，AN，D‘

’，HE，AL，TH相应的二元序列为1001100001，1010101110，0000100000，0000101110，0010000000，0100000101，0000101100，1010001000。背包密码体制当前89页，总共146页。

分别对以上二元序列作用于函数f，得密文为（2942，3584，903，3326，215，2817，2629，819）。为使接收方能够解密，就需找出单向函数f(x)的陷门。为此需引入一种特殊类型的背包向量。定义背包向量A=(a1,a2,…,an)称为超递增的，如果背包密码体制当前90页，总共146页。

超递增背包向量对应的背包问题很容易通过以下算法求解。已知s为背包容积，对A从右向左检查每一元素，以确定是否在解中。若s≥an，则an在解中，令xn=1；若s<an，则an不在解中，令xn=0。下面令对an-1重复上述过程，一直下去，直到检查出a1是否在解中。检查结束后得x=(x1x2…xn)，Bx=(x1x2…xn)T。超递增背包问题当前91页，总共146页。

然而，敌手如果也知道超递增背包向量，同样也很容易解密。为此可用模乘对A进行伪装，模乘的模数k和乘数t皆取为常量，满足k>∑ai，gcd(t,k)=1，即t在模k下有乘法逆元。设bi≡t·aimodk,i=1,2,…,n得一新的背包向量B=(b1,b2,…,bn)，记为B≡t·Amodk，用户以B作为自己的公开钥。超递增背包问题当前92页，总共146页。

例：

A=(1,3,5,11,21,44,87,175,349,701)是一超递增背包向量，取k=1590，t=43，gcd(43,1590)=1，得B=(43,129,215,473,903,302,561,1165,697,1523)。在得到B后，对明文分组x=(x1x2…xn)的加密运算为c=f(x)=B·Bx≡t·A·Bxmodk对单向函数f(x)，t、t-1和k可作为其秘密的陷门信息，即解密密钥。超递增背包问题当前93页，总共146页。

解密时首先由s≡t-1cmodk，求出s作为超递增背包向量A的容积，再解背包问题即得x=(x1x2…xn)。这是因为t-1cmodk≡t-1tABxmodk≡ABxmodk，而由k>∑ai，知ABx<k，所以t-1cmodk=ABx，是惟一的。当前94页，总共146页。

例：接上例，A=(1,3,5,11,21,44,87,175,349,701)是一超递增背包向量，k=1590，t=43，得t-1≡37mod1590，设用户收到的密文是(2942,3584,903,3326,215,2817,2629,819)，由37×2942≡734mod1590,37×3584≡638mod1590,37×903≡21mod1590,37×3326≡632mod1590,37×215≡5mod1590,37×2817≡879mod1590,37×2629≡283mod1590,37×819≡93mod1590,得(734,638,21,632,5,879,283,93)。超递增背包问题当前95页，总共146页。

取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重复该过程得第一个明文分组是1001100001，它对应的英文文本是SA；类似地得其他明文分组，解密结果为SAUNAANDHEALTH。超递增背包问题当前96页，总共146页。

背包密码体制是Diffie和Hellman1976年提出公钥密码体制的设想后的第一个公钥密码体制，由Merkle和Hellman1978年提出。然而又过了两年该体制即被破译，破译的基本思想是不必找出正确的模数k和乘数t（即陷门信息），只须找出任意模数k′和乘数t′，使得用k′和t′去乘公开的背包向量B时，能够产生超递增的背包向量即可。超递增背包问题当前97页，总共146页。

对RSA密码体制，n被分解成功，该体制便被破译，即破译RSA的难度不超过大整数的分解。但还不能证明破译RSA和分解大整数是等价的，虽然这一结论已得到普遍共识。Rabin密码体制已被证明对该体制的破译与分解大整数一样困难。4Rabin密码体制当前98页，总共146页。Rabin密码体制是对RSA的一种修正，它有以下两个特点：它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文;

破译该体制等价于对大整数的分解。RSA中选取的公开钥e满足1<e<φ(n)，且gcd(e,φ(n))=1。Rabin密码体制则取e=2。Rabin密码体制当前99页，总共146页。1.密钥的产生随机选择两个大素数p、q，满足p≡q≡3mod4，即这两个素数形式为4k+3；计算n=p×q。以n作为公开钥，p、q作为秘密钥。Rabin密钥的产生当前100页，总共146页。2.加密

c≡m2modn

其中m是明文分组，c是对应的密文分组。Rabin加密描述当前101页，总共146页。3.解密解密就是求c模n的平方根，即解x2≡cmodn，由中国剩余定理知解该方程等价于解方程组由于p≡q≡3mod4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即

x≡mmodp,x≡-mmodpx≡mmodq,x≡-mmodqRabin解密描述当前102页，总共146页。

经过组合可得4个同余方程组由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。Rabin解密描述当前103页，总共146页。

下面证明，当p≡q≡3mod4，两个方程x2≡cmodp,x2≡cmodq的平方根都可容易地求出。由p≡3mod4得，p+1=4k，即1/4(p+1)是一整数。因c是模p的平方剩余，故当前104页，总共146页。

所以和是方程x2≡cmodp的两个根。同理和是方程x2≡cmodq的两个根。由以前知识知，求解方程x2≡amodn与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。Rabin解密描述当前105页，总共146页。

已经说过，为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（ellipticcurvecryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景。ECC已被IEEE公钥密码标准P1363采用。5椭圆曲线密码体制当前106页，总共146页。

椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：

y2+axy+by=x3+cx2+dx+e(4.1)

其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。5.1椭圆曲线当前107页，总共146页。椭圆曲线的两个例子当前108页，总共146页。

从图可见，椭圆曲线关于x轴对称。椭圆曲线上的加法运算定义如下：如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）：①O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。椭圆曲线的描述当前109页，总共146页。②设P1=(x,y)是椭圆曲线上的一点（如图所示），它的加法逆元定义为P2=-P1=(x,-y)。这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，还可得O=-O椭圆曲线的描述当前110页，总共146页。③设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下：画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。④点Q的倍数定义如下：在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…，等。以上定义的加法具有加法运算的一般性质，如交换律、结合律等。椭圆曲线的描述当前111页，总共146页。

密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程y2≡x3+ax+b(modp)(a,b∈GF(p),4a3+27b2(modp)≠0)定义的曲线。5.2有限域上的椭圆曲线当前112页，总共146页。

例：p=23，a=b=1，4a3+27b2(mod23)≡8≠0，方程为y2≡x3+x+1，其图形是连续曲线。然而我们感兴趣的是曲线在第一象限中的整数点。设Ep(a,b)表示方程(4.2)所定义的椭圆曲线上的点集{(x,y)|0≤x<p,0≤y<p，且x,y均为整数}并上无穷远点O。本例中E23(1,1)由表4.6给出，表中未给出O。有限域上的椭圆曲线当前113页，总共146页。一般来说，Ep(a,b)由以下方式产生：①对每一x(0≤x<p且x为整数），计算x3+ax+b(modp)。②决定①中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0时只有一个平方根）。有限域上的椭圆曲线当前114页，总共146页。Ep(a,b)上的加法定义如下：设P，Q∈Ep(a,b)，则①P+O=P。②如果P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，表示为-P。由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如上例，P=(13,7)∈E23(1,1)，-P=(13,-7)，而-7mod23≡16，所以-P=(13,16)，也在E23(1,1)中。有限域上椭圆曲线的加法当前115页，总共146页。③设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下规则确定：

x3≡λ2-x1-x2(modp) y3≡λ(x1-x3)-y1(modp)其中有限域上椭圆曲线的加法当前116页，总共146页。

例：仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则所以P+Q=（17,20），仍为E23(1,1)中的点。有限域上椭圆曲线的加法当前117页，总共146页。

若求2P则

所以2P=(7,12)。有限域上椭圆曲线的加法当前118页，总共146页。

倍点运算仍定义为重复加法，如4P=P+P+P+P。从上例看出，加法运算在E23(1,1)中是封闭的，且能验证还满足交换律。对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以Ep(a,b)是一个Abel群。有限域上椭圆曲线的加法当前119页，总共146页。

为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，Q∈Ep(a,b)，k<p，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。Diffie-Hellman密钥交换和ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制。5.3椭圆曲线上的密码当前120页，总共146页。1.Diffie-Hellman密钥交换首先取一素数p≈2180和两个参数a、b，则得方程(4.2)表达的椭圆曲线及其上面的点构成的Abel群Ep(a,b)。第2步，取Ep(a,b)的一个生成元G(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数。当前121页，总共146页。

两用户A和B之间的密钥交换如下进行：①A选一小于n的整数nA，作为秘密钥，并由PA=nAG产生Ep(a,b)上的一点作为公开钥。②B类似地选取自己的秘密钥nB和公开钥PB。③A、B分别由K=nAPB和K=nBPA产生出双方共享的秘密钥。这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA。攻击者若想获取K，则必须由PA和G求出nA，或由PB和G求出nB，即需要求椭圆曲线上的离散对数，因此是不可行的。Diffie-Hellman密钥交换当前122页，总共146页。Diffie-Hellman公钥分配方案不能用于交换任意消息可以建立共享密钥(双方共享)依赖于双方的公、私钥值基于有限域上的指数问题安全性是基于计算离散对数的困难性

当前123页，总共146页。

例：p=211，Ep(0,-4)，即椭圆曲线为y2≡x3-4，G=(2,2)是E211(0,-4)的阶为241的一个生成元，即241G=O。A的秘密钥取为nA=121，公开钥为PA=121(2,2)=(115,48)。B的秘密钥取为nB=203，公开钥为PB=203(2,2)=(130,203)。由此得到的共享密钥为121(130,203)=203(115,48)=(161,169)，即共享密钥是一对数。如果将这一密钥用作单钥加密的会话密钥，则可简单地取其中的一个，如取x坐标，或取x坐标的某一简单函数。Diffie-Hellman密钥交换当前124页，总共146页。Diffie-Hellman举例

选取素数p=97,及本根a=5

Alice选取秘密xA=36&计算公钥yA=536=50mod97

Bob选取秘密xB=58&计算公钥yB=558=44mod97

AliceandBob交换公钥(50&44respectively)Alice计算公享秘密K=4436=75mod97

Bob计算公享秘密K=5058=75mod97

当前125页，总共146页。Diffie-HellmaninPractise两个主体每次可以选择新的秘密密钥(私钥),并计算及交换新的公钥可以抵抗被动攻击,但不能抵抗主动攻击每次可以给出新的密钥为抵抗主动攻击,需要其它新的协议也可以建立长期公钥当前126页，总共146页。2.ElGamal密码体制Diffie-Hellmankeydistributionscheme的变形能够用于安全交换密钥publishedin1985byElGamal:T.ElGamal,"APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms",IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.

安全性是基于离散对数缺点：增加了消息长度（2倍）ElGamal密码体制当前127页，总共146页。(1)ElGamal密码体制的原理

密钥产生过程：首先选择一素数p以及两个小于p的随机数g和x，计算y≡gxmodp。以(y,g,p)作为公开密钥，x作为秘密密钥。ElGamal密码体制当前128页，总共146页。ElGamal加密加密过程：设欲加密明文消息M，随机选一与p-1互素的整数k，0<=k<=p-1

计算消息密钥K