密码学4公钥密码课件.ppt

本科生学位课：现代密码学,第四章 公钥密码,主讲教师：董庆宽研究方向：密码学与信息安全Email ：qkdongmail.xidian.edu,2,4.1 密码学中常用数学知识4.2 公钥密码体制的基本概念4.3 RSA算法4.4 背包体制4.5 Rabin体制 4.6 NTRU公钥密码系统4.7 椭圆曲线密码体制4.8 基于身份的密码体制,本章提要,3,4.1 密码学中的常用数学知识,群、环、域、素数模运算费尔马定理ap-1=1 mod p ，p是素数欧拉函数(n)：小于n的且与n互素的正整数个数a(n)=1 mod n 素性检验1.爱拉托斯散筛法(Eratosthenes)依次删去小于 素数的倍数2. Miller-Rabin概率检测法3.AKS,欧几里得算法、扩展欧几里德算法求最大公约数和乘法的逆元中国剩余定理求一次同余方程组的解离散对数，本原根平方剩余计算复杂性,4,4.2 公钥密码体制的基本概念,公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。为密码学发展提供了新的理论和技术基础公钥密码算法基本工具不再是代换和置换，而是数学函数以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，即密钥分配和数字签字,5,对称密码算法的缺陷密钥分配问题： 通信双方加密通信前要通过秘密的安全信道协商加密密钥，这种安全信道可能很难实现；对这个信道安全性的要求比正常传送消息信道的安全性要高密钥管理问题： 在多用户网络中，任何两个用户之间都需要有共享的秘密钥，n个用户需要Cn2=n(n-1)/2个密钥，n=5000时，Cn2=12,497,500，系统开销非常大没有签名功能： 当主体A收到主体B的电子文挡时，无法向第三方证明此电子文档确实来源于B， 传统单钥加密算法无法实现抗抵赖的需求,6,公钥密码的主要作用公钥加密用于加密任何消息，象分组密码一样使用 任何人可以用公钥加密消息，私钥的拥有者可以解密消息 数字签名 (Digital Signature) 用于生成对某消息的数字签名私钥的拥有者生成数字签名，任何人可以用公钥验证签名签名时可将公钥加密算法逆用来实现，也可单独设计公钥签名算法基于公钥的密钥分配(Key Distribution)用于交换秘密信息，常用于协商对称加密算法的密钥可采用公钥加密的算法实现密钥分配也可使用单独设计的密钥交换算法，如DH密钥交换协议实现密钥分配其它应用：零知识证明，公平抛币等等，（用于各种目的的认证）,7,公钥密码的发展概况1976年Diffie和Hellman在其“密码学新方向”一文中提出公钥密码：W.Diffie and M.E.Hellman, “New Directions in Cryptography”, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976：644-6541978年Merkle和Hellman基于背包问题提出了首个公钥密码体制，但两年后被破译1978年Rivest，Shamir & Adleman基于大数分解的困难性提出了RSA公钥算法，成为迄今为止最为成熟和完善的公钥密码体制1985年出现了基于求解离散对数困难性的公钥密码算法DLP90年代逐步出现椭圆曲线(ECC)等其他公钥算法当前的公钥密码算法主要是基于大数分解困难性和离散对数困难性来构造的，椭圆曲线上也可构造这类体制，相同密钥长度下其安全性更高参考资料：公钥密码学等,8,4.2.1 公钥密码体制的原理,公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开一个密钥是公开的，称为公开密钥，简称公开钥，用于加密、验证签名，可以被任何人知道另一个密钥是为用户专用，因而是保密的，只能被消息的接收者或签名者知道，称为秘密密钥，简称秘密钥，用于解密、产生签名因此公钥密码体制也称为双钥密码体制算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的因此加密和签名的验证者不能解密和生成签名,9,公钥体制的加密过程 密钥的产生：要求接收消息的端系统，产生一对用来加密和解密的密钥PKB和SKB，如图中的接收者B，其中PKB是公开钥，SKB是秘密钥。因此，公钥可以发布给其他人 公开钥的分发：端系统B将加密密钥(PKB)予以公开。另一密钥则被保密(SKB) 加密：A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKBm其中c是密文，E是加密算法 解密：B收到密文c后，用自己的秘密钥SKB解密，即m=DSKBc，其中D是解密算法。因为只有B知道SKB，所以其他人都无法对c解密。,10,公钥体制的认证过程公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证用户A用自己的秘密钥SKA对m加密，表示为c=ESKAm将c发往B。B用A的公开钥PKA对c解密，表示为m=DPKAc因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对消息来源和消息完整性的认证。,11,认证符：通过单向压缩函数解决长文件的签字(hash)用户数目很多时，单纯加解密的认证方法需要很大的存储空间因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证符,12,认证符具有这样一个性质： 如果保持认证符的值不变而修改文件，在计算上是不可行的签名过程中，往往用发送者的秘密钥对认证符加密，加密后的结果为原文件的数字签字。(详见第7章),13,公钥体制同时提供加密和认证的过程认证过程中，由于消息是由用户自己的秘密钥加密的，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密先签名后加密：发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为c=EPKBESKAm先解密再验证：解密过程为m=DPKADSKBc即收方先用自己的秘密钥，再用发方的公开钥对收到的密文两次解密。如果先加密后签名是不安全的，别人可以先将签名去掉，再签上自己的签名，从而实现了篡改。,14,4.2.2 公钥密码算法应满足的要求,公钥密码算法应满足以下要求 收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。由私钥及其他密码信息容易计算出公开密钥(P问题) 发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKBm在计算上是容易的 收方B用自己的秘密钥对c解密，即m=DSKBc在计算上是容易的 敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的 敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的 加、解密次序可换，即EPKBDSKB(m)=DSKBEPKB (m)其中最后一条虽然非常有用，但不是对所有的算法都作要求。在构建盲签字等算法时需要类似要求以上要求的本质之处在于要求一个陷门单向函数。,15,单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个原像xX，且由x易于计算它的像y，由y计算它的原像x是不可行的“易于计算”是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na 的某个倍数，其中a是一固定的常数这时称求函数值的算法属于多项式类P，否则就是不可行的，例如，函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的,16,易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。这时可能对某些情况很容易求解，复杂度很低而在此所说的两个概念是指算法在几乎所有情况下的情形,17,陷门单向函数称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成总结为： 陷门单向函数是一族可逆函数fk，满足当k和X已知时，Y=fk(X)易于计算当k和Y已知时，X=fk-1(Y)易于计算当Y已知但k未知时，X=fk-1(Y)计算上是不可行的研究公钥密码算法就是要找出合适的陷门单向函数,18,4.2.3 对公钥密码体制的攻击,以下讨论的攻击是指对所有公钥密码体制都有效的平凡的攻击涉及到公钥算法所基于的困难问题的安全性和参数空间大小的安全性第一种平凡的攻击：（穷搜索攻击与密钥长度）如果密钥太短，公钥密码体制也易受到穷搜索攻击然而又由于公钥密码体制所使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用因此公钥密码体制目前主要用于密钥管理和数字签字。即处理短消息如密钥和hash值,19,第二种平凡的攻击是寻找从公开钥计算秘密钥的方法目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的第三种平凡的攻击：(可能字攻击)仅适用于对公钥密码算法的攻击例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，攻击的本质是对56比特DES密钥的穷搜索攻击抵抗方法是在欲发送的明文消息后添加一些随机比特不同的公钥密码算法在设计和实现中的密码协议是影响安全性的主要方面，不同算法的攻击不同。公钥的安全性是指计算上的安全性,20,4.3 RSA算法,1978年由R.Rivest, A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，已得到广泛的应用R L Rivest, A Shamir, L Adleman, On Digital Signatures and Public Key Cryptosystems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978它既可用于加密、又可用于数字签字。RSA算法的安全性是基于数论中大整数分解的困难性(但可能达不到大数分解的困难强度),21,4.3.1 算法描述,1密钥的产生 选两个保密的大素数p和q 计算n=pq，(n)=(p-1)(q-1)，其中(n)是n的欧拉函数值 选一整数e，满足1e (n)，且gcd(n),e)=1 计算d，满足de1 mod (n)，即d是e在模(n)下的乘法逆元，因e与(n)互素，模(n)的乘法逆元一定存在 以e,n为公开钥,d,p,q为秘密钥秘密钥也可记为d，或d, n，如果是系统负责产生密钥，则用户可能不知道p,q,22,2加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算： cme mod n3解密对密文分组的解密运算为： mcd mod n,23,RSA算法中解密过程的正确性证明证明： 由cme mod n，可知 cd mod nmed mod nmk(n)+1 mod n下面分两种情况： m与n互素，则由Euler定理得m(n)1 mod n，mk(n)1 mod n，mk(n)+1m mod n即cd mod nm gcd(m,n)1，因n=pq，所以m是p的倍数或q的倍数，不妨设m=cp，其中c为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾。由gcd(m,q)=1及Euler定理得m(q)1 mod q，所以mk(q)1 mod q，(mk(q)(p)1 mod q，即 mk(n)1 mod q因此存在一整数r，使得mk(n)1+rq，两边同乘以m=cp 得 mk(n)1m+rcpqm+rcn即mk(n)1m mod n，所以cd mod nm。(证毕),24,【例4-24】： 选p=7，q=17。求n=pq=119，(n)=(p-1)(q-1)=96取e=5，满足1e(n)，且gcd(n),e)=1确定满足de=1 mod 96且小于96的d，因为775=385=496+1，所以d为77公开钥为5，119，秘密钥为77设明文m=19，则由加密过程得密文为c195 mod 1192476099 mod 11966解密为6677mod 11919【例4-25】略加密长消息时相当于一个分组密码算法首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n,25,4.3.2 RSA算法中的计算问题,1. RSA的加密与解密过程模运算的累次乘法RSA的加密、解密过程都为求一个整数的整数次幂，再取模如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。用模运算的性质：即采用累次乘法，可减小中间结果(ab) mod n=(a mod n)(b mod n) mod n,26,快速指数算法考虑如何提高加、解密运算中模指数运算的有效性。例如求x16，直接计算需做15次乘法。若重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法求am可如下进行，其中a，m是正整数： 将m表示为二进制形式bkbk-1b0，即m=bk2k+bk-12k-1+b12+b0因此 am 例如：19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1)2a1,27,快速指数算法：c=0; d=1；for i=k downto 0 do c=2c; /仅为验证以上过程，而在具体算法中可删去d=(dd) mod n;/计算平方if bi=1 then c=c+1; /仅为验证以上过程，而在具体算法中可删去d=(da) mod n / bi=1时与a相乘return d.其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，算法中完全可将之去掉,28,计算复杂度:lW(m)次模乘（m为模指数）l为指数的bit长，W(m)为指数m的重量(二进制比特1的个数)例： 求7560 mod 561。将560表示为1000110000，算法的中间结果如表4-6所示所以7560 mod 561=1(5613x11x17, (561)=2x10 x16=320, 780=1 mod 561),29,一种改进的RSA实现方法 (即4.3.3节） RSA的加密很快，因为加密指数e一般选择得很小解密指数d很大，需要计算模 300digits (or 1024bits) 的乘法，计算机不能直接处理这么大的数，计算速度很慢，需要考虑其它技术，加速RSA的实现如果知道p和q，可采用中国剩余定理CRT：CRT 对RSA解密算法生成两个解密方程（利用M=Cd mod N，N=pq）即：M1 = M mod p = (C mod p)d mod (p-1) mod p M2 = M mod q = (C mod q)d mod (q-1) mod q解方程 M = M1 mod p M = M2 mod q 具有唯一解（利用CRT ）： M = M1q(q1mod p)+ M2p(p1mod q) mod N不考虑CRT的计算代价，改进的算法的解密速度是原来的4倍若考虑CRT的计算代价，改进后的算法解密速度是原来的3倍多,30,2. RSA密钥的产生需考虑两个大素数p、q的选取，以及e的选取和d的计算n(=pq) 是公开的，为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数(1) 如何有效地寻找大素数是第一个需要解决的问题寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止素性检验算法通常都是概率性的，常用Miller-Rabin概率检测算法实现寻找大素数是一个比较繁琐的工作，然而在RSA体制中，只有在产生新密钥时才需执行这一工作,31,(2) p和q决定出后，下一个需要解决的问题是如何选取满足1e(n)和gcd(n),e)=1的e，并计算满足de1 mod (n)的d这一问题可由推广的Euclid算法完成注意：RSA的模很长，如模n为1024比特的RSA一次加密约1024比特明文，相当于16次DES加密，但一次RSA比16次DES要慢很多，不在一个数量级上）,32,4.3.4 RSA的安全性,RSA的安全性是基于分解大整数的困难性假定之所以为假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法如果RSA的模数n被成功地分解为pq，则立即求得(n)，从而能够确定e模(n)的乘法逆元d，即de-1 mod (n)，因此攻击成功随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解RSA-130 已于2019年4月被成功分解RSA-140 已于2019年2月被成功分解RSA-155（512bit）已于2019年8月被成功分解RSA-158，2019年被成功分解,33,量子计算：可能解决大整数分解问题 （分解15和21）对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进分解算法过去都采用二次筛法，如对RSA-129的分解而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%。 对RSA-140和RSA-155的分解也采用此法将来也可能还有更好的分解算法因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的,34,是否有不通过分解大整数的其他攻击途径？下面证明由n直接确定(n)等价于对n的分解设n=pq中，pq，由 (n)=(p-1)(q-1)，则有 p+q=n(n)+1，以及 p-q= 由此可见，由p、q确定(n)和由(n)确定p、q是等价的,35,为保证算法的安全性，对p和q提出以下要求： (1) |p-q|要大由(p+q)2/4n=(p+q)2/4pq=(pq)2/4，如果|p-q|小，则(pq)2/4也小，因此(p+q)2/4稍大于n，(p+q)/2稍大于n1/2。可得n的如下分解步骤： 顺序检查大于n的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。 由x2-n=y2，得n=(x+y)(x-y)。(2) p-1和q-1都应有大素因子(强素数)这是因为RSA算法存在着可能的重复加密攻击法。,36,重复加密攻击法设攻击者截获密文c，可如下进行重复加密： 若 ，即 ，则有 ，即 所以在上述重复加密的倒数第2步就已恢复出明文m这种攻击法只有在 t 较小时才是可行的。为抵抗这种攻击，p、q的选取应保证使 t 很大。设m在模n下阶为k，由 得 ，所以k|(et-1)，即et1(mod k)，t 取为满足前式的最小值（为e在模k下的阶）。又当e与k互素时t|(k)。为使t大，k就应大且(k)应有大的素因子。又由k|(n)，所以为使k大，p-1和q-1都应有大的素因子 此外，研究表明，如果en且dn1/4，则d能被容易地确定,37,4.3.5 对RSA的攻击,RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的1. 共模攻击在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明文消息是m，密文分别是 c1me1(mod n) c2me2(mod n)敌手截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足 re1+se2=1的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c1-1，由此得(c1-1)-rc2sm(mod n)。,38,2. 低指数攻击假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni(i=1,2,3)，当ij时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，加密指数e3，密文分别是: c1m3(mod n1) c2m3(mod n2) c3m3(mod n3)由中国剩余定理可求出m3(mod n1n2n3)。由于m3n1n2n3，可直接由m3开立方根得到m。最初建议使用e=3，不安全，e是有下限的明文消息空间太小时，消息需要填充,39,4.4 背包密码体制,设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原则上讲，通过检查A的所有子集，总可找出问题的解（若有解的话）本例A的子集共有210=1024个（包括空集）。然而如果A中元素个数n很大，子集个数2n将非常大。如A中有300个元素，A的子集有2300。寻找满足要求的A的子集没有比穷搜索更好的算法，因此背包问题是NPC问题。,40,由背包问题构造公钥密码体制同样是要构造一个单向函数f将x(1x2n-1)写成长为n的二元表示0001, 0010， 0011, , 1111, f(x)定义为A中所有ai的和，其中x的二元表示的第i位为1，即f(1)=f(0001)=anf(2)=f(0010)=an-1f(3)=f(0011)=an-1+an f(2n-1)=f(1111)=a1+a2+an使用向量乘(内积)，有f(x)=ABx，其中Bx是x二元表示的列向量。上例中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。,41,用f对明文消息m加密时，首先将m写成二元表示，再将其分成长为n的分组（最后一个分组不够长的话，可在后面填充一些0），然后求每一分组的函数值，以函数值作为密文分组。例如，明文消息是英文文本，则可将每个字母用其在字母表中的序号表示，再将该序号转换为二进制形式（5位即可），如表4.5所示，其中符号 表示空格。表47 英文字母表及字母的二进制表示,42,背包向量仍取上例中的A，设待加密的明文是SAUNA AND HEALTH。因为A长为10，所以应将明文分成长为10比特（即两个明文字母）的分组SA，UN，A ，AN，D ，HE，AL，TH相应的二元序列为1001100001，1010101110，0000100000，0000101110，0010000000，0100000101，0000101100，1010001000。分别对以上二元序列作用于函数f，得密文为（2942，3584，903，3326，215，2817，2629，819）。为使接收方能够解密，就需找出单向函数f(x)的陷门。为此需引入一种特殊类型的背包向量。,43,定义背包向量A=(a1,a2,an)称为超递增的，如果 ，j1,2,n超递增背包向量对应的背包问题很容易通过以下算法求解。已知s为背包容积，对A从右向左检查每一元素，以确定是否在解中。若san，则an在解中，令xn=1；若san，则an不在解中，令xn=0。下面令s 对an-1重复上述过程，一直下去，直到检查出a1是否在解中。检查结束后得 x=(x1x2xn)，Bx=(x1x2xn)T,44,敌手如果也知道超递增背包向量，同样也很容易解密为此可用模乘对A进行伪装，模乘的模数k和乘数t皆取为常量，满足 ，gcd(t,k)=1，即t在模k下有乘法逆元。设 bitai mod k, i=1,2,n得一新的背包向量B=(b1,b2,bn)，记为BtA mod k，用户以B作为自己的公开钥，A,t,k为私钥【例4-10】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=(x1x2xn)的加密运算为c=f(x)=BBxtABx mod k对单向函数f(x)，t、t-1和k可作为其秘密的陷门信息，即解密密钥。,45,解密时首先由st-1c mod k，求出s作为超递增背包向量A的容积，再解背包问题即得x=(x1x2xn)。这是因为t-1c mod kt-1tABx mod kABx mod k，而由 ，知ABx701，得x10=1；令s=734-701=33，由33349，得x9=0；重复该过程得第一个明文分组是1001100001，它对应的英文文本是SA；类似地得其他明文分组，解密结果为SAUNA AND HEALTH。,46,背包密码体制是Diffie和Hellman 1976年提出公钥密码体制的设想后的第一个公钥密码体制，由Merkle和Hellman 1978年提出。它表示了如何将NP完全问题用于公开密钥算法。然而又过了两年该体制即被破译破译的基本思想是不必找出正确的模数k和乘数t（即陷门信息），只须找出任意模数k和乘数t，使得用k和t去乘公开的背包向量B时，能够产生超递增的背包向量即可。,47,4.5 Rabin密码体制,对RSA密码体制，n被分解成功，该体制便被破译，即破译RSA的难度不超过大整数的分解。但还不能证明破译RSA和分解大整数是等价的，虽然这一结论已得到普遍共识Rabin密码体制已被证明对该体制的破译与分解大整数一样困难Rabin密码体制是对RSA的一种修正，它有以下两个特点： 它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文;破译该体制等价于对大整数的分解。RSA中选取的公开钥e满足1e (n)，且gcd(e, (n)=1。Rabin密码体制则取e=2,48,1. 密钥的产生随机选择两个大素数p、q，满足pq3 mod 4，Blum数，即这两个素数形式为4k+3；计算n=pq。以n作为公开钥，p、q作为秘密钥。2. 加密 cm2 mod n 其中m是明文分组，c是对应的密文分组。3. 解密解密就是求c模n的平方根，即解x2c mod n，由中国剩余定理知解该方程等价于解方程组,49,由于pq3 mod 4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即 xm1 mod p，xm1 mod p xm2 mod q，xm2 mod q经过组合可得4个同余方程组 ， ， ， 由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。,50,下面证明，当pq3 mod 4，两个方程x2c mod p, x2c mod q的平方根都可容易地求出由p3 mod 4得，p+1=4k，即(p+1)/4是一整数因c是模p的平方剩余，故 c(p-1)/21 mod p， c(p-1)/2cc mod p所以 和p- 是方程x2c mod p的两个根。同理 和q- 是方程x2c mod q的两个根。由以前知识知，求解方程x2a mod n与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。,51,4.6 NTRU公钥密码系统,NTRU是一种基于环的公钥密码系统，由Jeffrey Hoffstein 等人在2019年提出系统的特点是密钥短且容易产生，算法的运算速度快，所需的存储空间小。系统建立在整系数多项式环上。设R表示最高次数不超过N1的所有整系数多项式集合，设aa0+a1x+aN1xN1, ba0+b1x+bN1xN1,是R上的两个元素，R上的加法定义为 a+b(a0+b0)+(a1+b1)x+(aN-1+bN-1)xN1,乘法定义为 a*bc0+c1x+cN-1xN1其中k阶系数cka0bk+a1bk-1+akb0+ak+1bN-1+ak+2bN-2+aN-1bk+1 容易验证R在如上定义的加法和乘法运算下构成一个环（Abel群，半群，可分配）,52,1.算法的参数参数包括3个整数(N,p,q)和4个次数为N-1的整系数多项式集合Lf , Lg, L, Lm，其中p和q不要求是素数，但满足gcd(p,q)=1，且qp2.密钥的产生密钥的产生由接收方完成：随即选取两个多项式f, gLg，其中多项式f在模q和模p下均可逆，其逆元分别表示为Fq和Fp，即：Fq*f=1 mod q 和 Fp*f=1 mod p。计算hFq*g mod q，以h为公钥，f作为秘密钥，接收方同时还需保存Fp 3.加密设发送方欲将消息mLm发送给接收方，可对m作如下加密：随机选取多项式L ，用公钥h对消息进行加密ep*h+m (mod q)将e发送给接收方。,53,4.解密接收方收到e后，使用秘密钥f对其作如下解密。首先计算a=f*e(mod q), a的系数选在-q/2到q/2之间.将a作为一个整系数多项式，计算Fp*a(mod p)即可恢复明文m解密原理：a=f*ef*p*h+f*m (mod q) f*p*Fq*g +f*m (mod q) p*g +f*m (mod q) p*g +f*m 最后一步是由于若选择的参数合适，可保证多项式p*g +f*m的系数在-q/2到q/2之间，所以对p*g +f*m模q运算后结果不变而Fp*aFp*p*g +Fp*f*m (mod p)m (mod p),54,4.7 椭圆曲线密码体制,为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景ECC已被IEEE公钥密码标准P1363采用,55,4.7.1 椭圆曲线,椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e (4-1)其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。从图可见，椭圆曲线关于x轴对称。,56,椭圆曲线上的加法运算定义如下： 如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）： O为加法单位元，即对椭圆曲线上任一点P，有 P+O=P 设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,57, 设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+，以上定义的加法具有加法运算的一般性质，如交换律、结合律等。,58,4.7.2 有限域上的椭圆曲线,密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式(4-1)中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）其中最为常用的是由方程(4-2)定义的曲线 y2x3+ax+b(mod p) (4-2) (a,bGF(p),4a3+27b2(mod p)0),59,因为(a/3)3+(b/2)2=(4a3+27b2)/108是方程x3+ax+b0的判别式，当4a3+27b2 0时方程有重根，设为x0，则点Q0(x0,0)是方程(4-2)的重根即x3+ax+b(x-x0)3或者(x-x0)2(x-x1)，重根将使得一阶导数3x2a在该Q0点为0令F(x,y)=y2x3axb，则F/x|Q0=F/y|Q0=0所以dy/dx=F/x/F/y(3x2a)/2y在Q0点无定义，即曲线y2x3+ax+b在Q0点的切线无定义，因此点Q0的倍点运算无定义,60,例： p=23，a=b=1，4a3+27b2(mod 23)80，方程为y2x3+x+1(mod 23)，感兴趣的是曲线在GF(23)中的整数点设Ep(a,b)表示方程(4-2)所定义的椭圆曲线上的点集(x,y)|0 xp,0yp，且x,y均为整数并上无穷远点O本例中E23(1,1)由表4-8给出，表中未给出O表46 椭圆曲线上的点集E23(1,1),61,一般来说，Ep(a,b)由以下方式产生： 对每一x(0 xp且x为整数），计算x3+ax+b(mod p)。 决定中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根 (y=0 时只有一个平方根)。即判断是否是模p的平方剩余Ep(a,b)上的加法定义如下： 设P，QEp(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)，而-7 mod 2316，所以-P=(13, 16)，也在E23(1,1)中。,62, 设P=(x1,y1)，Q=(x2,y2)，P-Q，则P+Q=(x3,y3)由以下规则确定： x32x1x2(mod p) y3(x1x3)y1(mod p)其中 切线【例429】仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则(7-10)/(9-3)=-1/2=12111 mod 23x31123910917 mod 23y311(317)1016420 mod 23所以P+Q=（17,20），仍为E23(1,1)中的点。若求2P则 (3321)/(210)=5/20=14112206 mod 23 x36233307 mod 23 y36(37)103412 mod 23 所以2P=(7,12),63,公式推导示例,64,倍点运算仍定义为重复加法，如4P=P+P+P+P快速倍点运算 kP可采用类似于快速指数运算的相同算法即令k=bt2t+bt-12t-1+b12+b0，则可写出2倍点和加法运算的迭代形式Ep(a,b)是一个Abel群对一般的Ep(a,b)，可证其上的加法运算是封闭