第5章 公钥密码.ppt

《第5章 公钥密码.ppt》由会员分享，可在线阅读，更多相关《第5章 公钥密码.ppt（118页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码第五讲：双钥密码一一、基基本本概概念念二二、R RS SA A密密码码体体制制三三、背背包包密密码码体体制制四四、R Ra ab bi in n密密码码体体制制五五、E El lG Ga am ma al l密密码码体体制制六六、椭椭圆圆曲曲线线密密码码体体制制七七、M Mc cE El li ie ec ce e密密码码体体制制八八、L LU UC C密密码码体体制制九九、秘秘密密共共享享

2、密密码码体体制制十十、有有限限自自动动机机密密码码体体制制2023/1/301Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码第五讲：双钥密码双(公)钥密码体制于1976年由W.Diffie和M.Hellman1976提出，同时R.Merkle1978也独立提出了这一体制。可用于保密通信，也可用于数字签字。这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。自1976年以来，双钥体制有了飞速发展

3、，不仅提出了多种算法，而且出现了不少安全产品，有些已用于NII和GII之中。本章将介绍其中的一些主要体制，特别是那些既有安全性，又有实用价值的算法。其中，包括可用于密钥分配、加解密或数字签名的双钥算法。一个好的系统，不仅算法要好，还要求能与其它部分，如协议等进行有机的组合。一、基本概念一、基本概念2023/1/302Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念 由于双钥体制的加密变换是公开的，使得任何人都可以采

4、用选择明文来攻击双钥体制，因此，明文空间必须足够大才能防止穷尽搜索明文空间攻击。这在双钥体制应用中特别重要(如用双钥体制加密会话密钥时，会话密钥要足够长)。一种更强有力的攻击法是选择密文攻击，攻击者选择密文，而后通过某种途径得到相应的明文，多数双钥体制对于选择密文攻击特别敏感。通常采用两类选择密文攻击：(1)冷漠(Indifferent)选择密文攻击。在接收到待攻击的密文之前，可以向攻击者提供他们所选择的密文的解密结果。(2)自适应选择密文攻击，攻击者可能利用(或接入)被攻击者的解密机(但不知其秘密钥)，而可以对他所选择的、与密文有关的待攻击的密文，以及以前询问得到的密文进行解密。2023/1

5、/303Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念本讲介绍双钥体制的基本原理和各种重要算法，如RSA、背包、Rabin、ElGamal、椭圆曲线、McEliece、LUC、秘密共享、有限自动机等密码算法。1.双钥密码体制的基本概念双钥密码保密、认证系统的的安全性主要取决于构造双钥算法所依赖的数学问题。要求加密函数具有单向性，即求逆的困难性。因此，设计双钥体制的关键是先要寻求一个合适的单向函数。（1）单向函数定

6、义5-1-1 令函数f是集A到集B的映射，以f：AB表示。若对任意x1x2，x1,x2A，有f(x1)f(x2)，则称f为单射，或11映射，或可逆的函数。2023/1/304Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念f为可逆的充要条件是，存在函数g：B A，使对所有xA有gf(x)=x。定义5-1-2 一个可逆函数f：AB，若它满足：p1o 对所有xA，易于计算f(x)。p2o 对“几乎所有xA”由f(x)求

7、x“极为困难”，以至于实际上不可能做到，则称f为一单向(One-way)函数。定义中的“极为困难”是对现有的计算资源和算法而言。Massey称此为视在困难性(apparent difficulty)，相应函数称之为视在单向函数。以此来和本质上(Essentially)的困难性相区分 Massey 1985。(1)单向函数单向函数2023/1/305Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念例5-1-1 令令f

8、是在有限域是在有限域GF(p)中的指数函数，其中中的指数函数，其中p是大素数，即是大素数，即 y=f(x)=x (511)式式中中，x GF(p)，x为为满满足足0 xp1的的整整数数，其其逆逆运运算算是是GF(p)中中定义的对数运算，即定义的对数运算，即 x=log x 0 xp1 (512)显显然然，由由x求求y是是容容易易的的，即即使使当当p很很大大，例例如如p 2100时时也也不不难难实实现现。为为方方便便计计算算以以下下令令=2。所所需需的的计计算算量量为为lb p次次乘乘法法，存存储储量量为为(lb p)2比比特特，例例如如p=2100时时，需需作作100乘乘法法。利利用用高高速速

9、计计算算机机由由x计计算算 x可可在在0.1毫毫秒秒内内完完成成。但但是是相相对对于于当当前前计计算算GF(p)中中对对数数最最好好的的算算法法，要要从从 x计计算算x所所需需的的存存储储量量大大约约为为 比比特特和和运运算算量量大大约约为为 。当当p=2100时时，所所需需的的计计算算量量为为 次次，以以计计算算指指数数一一样样快快的的计计算算机机进进行行计计算算需需时时约约1010.7秒秒(1年年=107.5秒秒，故故约约为为1600年年！其其中中假假定定存存储储量量的的要要求求能能够够满满足足)。可可见见，当当p很很大大时时，GF(p)中中的的f(x)=x，xp1是是个单向函数。个单向函

10、数。(1)单向函数单向函数2023/1/306Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念 Pohlig和Hellman对(p1)无大素因子时给出一种快速求对数的算法Pohlig等1978。特别是，当p=2n1时，从x求x的计算量仅需(log p)2次乘法。对于p=2160，在高速计算机上大约仅需时10毫秒。因此，在这种情况下，f(x)=x就不能被认为是单向函数。由上述我们可以得出，当对素数p，且p1有大的素因

11、子时，GF(p)上的函数f(x)=x是一个视在单向函数。寻求在GF(p)上求对数的一般快速算法是当前密码学研究中的一个重要课题。(1)单向函数单向函数2023/1/307Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念(2)陷门单向函数单向函数是求逆困难的函数，而单向陷门函数(Trapdoor one-way function)，是在不知陷门信息下求逆困难的函数，当知 道 陷 门 信 息 后，求 逆 是 易 于 实

12、 现 的。这 是 Diffie和Hellmam1976引入的有用概念。例：号码锁。但如何给陷门单向函数下定义则很棘手，因为(1)陷门函数其实就不是单向函数，因为单向函数是在任何条件下求逆都是困难的；(2)陷门可能不止一个，通过试验,一个个陷门就可容易地找到逆。如果陷门信息的保密性不强，求逆也就不难。2023/1/308Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念定义:5-1-3 陷门单向函数是一类满足下述条件的

13、单向函数：fz：AzBz，zZ，Z是陷门信息集。(1)对所有zZ，在给定z下容易找到一对算法Ez和Dz使对所有xA，易于计算fz及其逆，即 fz(x)=Ez(x)(513)Dz(fz(x)=x (514)而且当给定z后容易找到一种算法Fz，称其为可用消息集鉴别函数，对所有xA易于检验是否xAz(AzA)，Az是可用的明文集。(2)对“几乎”所有zZ，当只给定Ez和Fz时，对“几乎所有”xAz，“很难”意即“实际上不可能”从y=Ez(x)算出x。(2)陷门单向函数陷门单向函数2023/1/309Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学

14、网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念第(1)条让我们注意识别x是在允许的定义范围内。当集A未划分时，这不难做到。但是当集Az与z有关时，则应当能确信可以检验x是在Az中(这容易做到)的同时，是否在不知z下也能检验x是在Az之中，因为如果人们在不知z下使用算法Ez时就需要解决此问题。第(2)条半精确地定义了陷门单向函数为一单向函数。它表明在给定算法Ez，Dz时，对“几乎所有”xAz，至少对“大多数”zZ和“大多数”xAz，在“计算上”不可能求出逆。即使已知有限明密文对(xi,yi)，i=1,2,n，也难以

15、轻易地从Ez(x)算出x，其中xAz但不在已知的明密文对中。(3)对任一z，集Az必须是保密系统中明文集中的一个“方便”集。即便于实现明文到它的映射。(在PKC中是默认的条件)。(Diffie和Hellman定义的陷门函数中，Az=A，对所有Z成立。而实际中的Az取决于Z)。(2)陷门单向函数陷门单向函数2023/1/3010Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念（3）公钥系统公钥系统在一个公钥系统中，所

16、有用户共同选定一个陷门单向函数，加密运算E及可用消息集鉴别函数F。用户i从陷门集中选定zi，并公开Ezi和Fzi。任一要向用户i送机密消息者，可用Fzi检验消息x是否在许用明文之中，而后送y=Ezi(x)给用户i 即可。在仅知y，Ezi和Fzi下，任一用户不能得到x。但用户i利用陷门信息zi，易于得到Dzi(y)=x。定义5-1-4 对zZ和任意xX，Fi(x)yY=X。若 Fj(Fi(x)=Fi(Fj(x)(515)成立，则称F为可换单向函数。可换单向函数在密码学中更有用。2023/1/3011Copyright Yuan Copyright Yuan Email:Email: 南京航空航天

17、大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念（4）用于构造双钥密码的单向函数用于构造双钥密码的单向函数1976年Diffie和Hellman发表的文章中虽未给出陷门单向函数，但大大推动了这方面的研究工作。双钥密码体制的研究在于给出这种函数的构造方法以及它们的安全性。陷门单向函数的定义并没有给出这类函数是否存在。但他们指出“一个单钥密码体制，如果能抗击选择明文攻击，就可规定一个陷门单向函数”。以其密钥作为陷门信息，则相应的加密函数就是这类函数。这是构造双钥体制的途径。下面给出一些目前多数双钥体制所用的单向函数

18、的例子。2023/1/3012Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念 多项式求根。多项式求根。有限域GF(p)上的一个多项式y=f(x)=xnan-1xn-1a1xa0 mod p 当给定a0,a1,an-1，p及x时，易于求y，利用Honers 法则，即 f(x)=(xan-1)xan-2)xan-3)xa1)xa0 mod p。(516)最多有n次乘法和n1次加法。反之，已知y,a0,an-1，要求解

19、x需能对高次方程求根。这至少要n2(lb p)2次乘法，a表不大于a的最大整数，当n,p大时很难。离离散散对对数数DL。给定一大素数p，p1含另一大素数因子q。可构造一乘群Zp*，它是一个p1阶循环群。其生成元为整数g，1gp1。已知x，求 y=gx mod p容 易，只 需 lb2x 1次 乘 法。如 x=15=11112，g15=(1g)2g)2g)2g mod p，要用14次乘法。（4）用于构造双钥密码的单向函数用于构造双钥密码的单向函数2023/1/3013Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网

20、络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念 若已知y,g,p，求x=logg y mod p为离散对数问题。最快求解法运算次数渐近值为 (517)p=512时，。若离散对数定义在GF(2n)中的2n1阶循环群上，它的预计算量的渐近式为 (518)求一特定离散对数的计算量的渐近式为 (519)广义离散对数问题是在n阶有限循环群G上定义的。（4）用于构造双钥密码的单向函数用于构造双钥密码的单向函数2023/1/3014Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天

21、大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念大整数分解FAC(Factorization Problem)。判断一个大奇数n是否为素数的有效算法，大约需要的计算量是lb n4，当n为256或512位的二元数时，用当前计算机做可在10分钟内完成。已知FACCONP。若已知二大素数p和q，求n=pq只需一次乘法，但若由n，求p和q，则是几千年来数论专家的攻关对象。（4）用于构造双钥密码的单向函数用于构造双钥密码的单向函数2023/1/3015Copyright Yuan Copyright Yuan Email:Email: 南京航空航

22、天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念 迄今为止，已知的各种算法的渐近运行时间为：试除法：最早的也是最慢的算法，需试验所有小于sqrt(n)的素数，运行时间为指数函数。二次筛(QS)：(5110)为小于110位整数最快的算法，倍多项式二次筛(MPQS)是QS更快的变型，MPQS的双倍大指数变型还要快些。椭圆曲线(EC)：(5111）数域筛(NFS)：(5112）式中，p是n的最小的素因子，最坏的情况下p n1/2。当n 2664，要用3.8109年(一秒进行100万次运算)。虽然整数分解问题已进行了

23、几世纪研究，但至今尚未发现快速算法。目前对于大于110位的整数数域筛是最快的算法，曾用于分解第9个Fermat数。目前的进展主要是靠计算机资源实现的。T(n)与L(p)的表示式大致相同，一般当n=p时，解离散对数要更难些。（4）用于构造双钥密码的单向函数用于构造双钥密码的单向函数2023/1/3016Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念 RSA问题，是FAC问题的一个特例。n是两个素数p和q之积，给定n

24、后求素因子p和q的问题称之为RSAP。求n=pq分解问题有以下几种形式：(1)分解整数n为p和q；(2)给定整数M和C，求d使CdM mod n;(3)给定整数e和C，求M使MeC mod n;(4)给定整数x和C，决定是否存在整数y使xy2 mod n(二次剩余问题)。背包问题，可参看5.3节。Diffie-Hellman问题(DHP)。给定素数p，令为Zp*的生成元，若已知a和b，求 a b的问题为Diffie-Hellman问题，简记为DHP。若为循环群G的生成元，且已知a和b为G中的元素，求 a b的问题为广义Diffie-Hellman问题，简记为GDHP。（4）用于构造双钥密码的单

25、向函数用于构造双钥密码的单向函数2023/1/3017Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码一、基本概念一、基本概念 二次剩余问题，给定一个奇合数n和整数a，决定a是否为mod n的平方剩余。模n的平方根问题(SQROOT)，模n的平方根问题可参看5.4节。（4）用于构造双钥密码的单向函数用于构造双钥密码的单向函数2023/1/3018Copyright Yuan Copyright Yuan Email:Email: 南京航空

26、航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码二、二、RSA密码体制密码体制 概况：继M.Hellman的背包算法提出后，同年MIT三位年青数学家R.L.Rivest，A.Shamir和L.AdlemanRivest等1978,1979发现了一种用数论构造双钥的方法，称作MIT体制，后来被广泛称之为RSA体制。它既可用于加密、又可用于数字签字，易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制。国际上一些标准化组织ISO、ITU、及SWIFT等均已接受RSA体制作为标准。在Internet中所采用的PGP(Pretty

27、Good Privacy)中也将RSA作为传送会话密钥和数字签字的标准算法。RSA算法的安全性基于5-1节介绍的数论中大整数分解的困难性。2023/1/3019Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码二、二、RSA密码体制密码体制1.体制:独立地选取两大素数p和q(各100200位十进制数字)，计算 n=pq (521)其欧拉函数值 (n)=(p1)(q1)(522)随机选一整数e，1e(n)，(n),e)=1。因而在模(n)下，

28、e有逆元 d=e-1 mod(n)(523)取公钥为n，e。秘密钥为d。(p,q不再需要，销毁。)加密：将明文分组，各组在mod n下可惟一地表示(以二元数字表示，选2的最大幂小于n)。各组长达200位十进数字。可用明文集 Az=m：1mn,(m,n)=11.体制体制2023/1/3020Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码二、二、RSA密码体制密码体制 m Az的概率：的概率：密文 c=me mod n (524)解密：m=

29、cd mod n (525)证明：cd=(me)d=mde，因因为为de 1 mod (n)而而有有de=q(n)1。由欧拉定理，由欧拉定理，(m,n)=1意味意味m(n)1 mod n，故有故有cd=mde=mq(n)+1 m mq(n)=m 1=m mod n 陷门函数：Z=(p1,p2,d)例5-2-1：选选p=47，q=71，则则n=4771=3337，(n)=4670=3220。若若选选e=79，可可计计算算d=e-1(mod 3220)=1019。公公开开n=3337和和e=79。秘秘密密钥钥d=1019。销毁销毁p,q。1.体制体制2023/1/3021Copyright Yua

30、n Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码二、二、RSA密码体制密码体制令m=688 232 687 966 668 3，分组得m1=688，m2=232，m3=687，m4=966，m5=668，m6=3。m1的加密为(688)79(mod 3337)=1570=c1，类似地可计算出其他各组密文。得到密文c=1570 2756 2091 2276 2423 158。第一组密文的解密为(1570)1 019 mod 3337=688=m1。类似地可解出其他各

31、组密文。RSA加密实质上是一种ZnZn上的单表代换！给定n=pq和合法明文xZn，其相应密文y=xe mod n Zn。对于xx，必有yy。Zn中的任一元素(0,p1,p2的倍数除外)是一个明文，但它也是与某个明文相对应的一个密文。因此，RSA是ZnZn的一种单表代换密码，关键在于n极大时在不知陷门信息下极难确定这种对应关系，而用模指数算法又易于实现一种给定的代换。正由于这种一一对应性使RSA不仅可以用于加密也可以用于数字签字。1.体制2023/1/3022Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室

32、南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码二、二、RSA密码体制密码体制2.RSA的安全性（1）分分解解模模数数n。在理论上，RSA的安全性取决于模n分解的困难，但数学上至今还未证明分解模就是攻击RSA的最佳方法，也未证明分解大整数就是NP问题，可能有尚未发现的多项式时间分解算法。人们完全可以设想有另外的途径破译RSA，如求解密指数d或找到(p11)(p21)等。但这些途径都不比分解n来得容易。甚至Alexi等1988曾揭示，从RSA加密的密文恢复某些bit的困难性也和恢复整组明文一样困难。这一视在困难性问题是个NP问题，但还没人证明它为NPC问题。表5-2-1给出采

33、用广义数域筛分解不同长度RSA公钥模所需的计算机资源。2.RSA的安全性2023/1/3023Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码 表 5-2-1 密钥长(bit)所需的MIPS-年*116(Blacknet密钥)400 129 5,000 512 30,000 768 200,000,000 1024 300,000,000,000 2048 300,000,000,000,000,000,000 *MIPS-年指以每秒执行

34、年指以每秒执行1,000,000条指令的计算机运行一年条指令的计算机运行一年 二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3024Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码 RSA-129：110位位十十进进制制数数字字早早已已能能分分解解。Rivest等等最最初初悬悬赏赏$100的的RSA-129，已已由由包包括括五五大大洲洲43个个国国家家600多多人人参参加加，用用1600台台机机子子同同时时产产生生

35、820条条指指令令数数据据，通通过过Internet网网，耗耗时时8个个月月，于于1994年年4月月2日日利利用用二二次次筛筛法法分分解解出出为为64位位和和65位位的的两两个个因因子子，原原来来估估计计要要用用4亿亿亿亿年年。所所给给密密文文的的译译文文为为“这这些些魔魔文文是是容容易易受受惊惊的的鱼鱼鹰鹰”。这这是是有有史史以以来来最最大大规规模模的的数数学学运算。运算。RSA-130于于1996年年4月月10日利用数域筛法分解出来。日利用数域筛法分解出来。RSA-140于于1999年年2月分解出来。月分解出来。RSA-154待破。待破。二、二、RSA密码体制密码体制2.RSA的安全性的安

36、全性2023/1/3025Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码 512 bits(154位位)、664 bits(200位位)、1,024 bits的的模模已已有有实实用用产产品品。目目前前，512 bit模模(约约155位位)在在短短期期内内仍仍十十分分安安全全，但但大大素素数数分分解解工工作作在在WWW上上大大协协作作已已构构成成对对512 bit模模RSA的的严严重重威威胁胁。表表5-2-2给给出出以以NSF算算法法破破

37、译译RSA体体制制与与用用穷穷搜搜索索密钥法破译单钥体制的等价密钥长度。密钥法破译单钥体制的等价密钥长度。表5-2-2 单钥体制 RSA体制 56-bit 384-bit 64-bit 512-bit 80-bit 768-bit 112-bit 1792-bit 128-bit 2304-bit二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3026Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码因此，今天要用RS

38、A，需要采用足够大的整数。512 bit(154位)、1024 bit(200位)已有实用产品。若以每秒可进行100万步的计算资源分解664 bit大整数，需要完成1023步，即要用1000年。在European Institute for System Security workshop上，与会者认为1024 bit模在今后10年内足够安全。Simmons预测150位数将在本世纪被分解。数学家估计分解x10位数的困难程度约为分解x的十倍。目前，512 bit模(约155位)在短期内仍十分安全，但大素数分解工作在WWW上大协作已构成对512 bit模RSA的严重威胁，目前主要使用1 024 b

39、it的模。大整数分解算法研究是当前数论和密码理论研究的一个重要课题。二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3027Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码（2）其其它它途途径径：若能不分解n而求出(n)，则可由de=1（mod(n)）求得d，从而破译RSA。已证明，求(n)等价于分解n的困难。从n求d亦等价于分解n。前尚不知是否存在一种无需籍助于分解n攻击法。也未能证明破译RSA的任何方法都等价于大

40、整数分解问题。（3）迭迭代代攻攻击击法法：Simmons和Norris曾提出迭代或循环攻击法。例如，给定一RSA的参数为(n,e,c)=(35,17,3)，可由c0=c=3计算c1=317=33 mod 35。再由c1计算c2=c117=3 mod 35，从而得到明文m=c1=33 mod 35。一般对明文m加密多次，直到再现m为止。Rivest证明，当p1和q1中含有大素数因子，且n足够大时，这种攻击法成功的概率趋于0。二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3028Copyright Yuan Copyright Yuan Email:Email: 南京航空航

41、天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码（4）选择明文攻击）选择明文攻击(a)消消息息破破译译。攻击者收集用户A以公钥e加密的密文y=xe mod n，并想分析出消息x。选随机数rn，计算y1=re mod n，这意味r=y1d mod n。计算y2=y1y mod n。令t=r-1 mod n，则t=y1-d mod n。现在攻击者请A对消息y2进行签字(用秘密钥，但不能用Hash函数)，得到S=y2d mod n。攻击者计算ts mod n=y1-dy2d mod n=y1-dy1dyd mod n=yd mod n=x

42、，得到了明文。(b)骗骗取取仲仲裁裁签签字字。在有仲裁情况下，A有一个文件要求仲裁，可先将其送给仲裁T，T以RSA的秘密钥进行签署后回送给A(未用单向Hash函数，只以秘密钥对整个消息加密)。攻击者有一个消息要T签署，但T并不情愿给他签，因为可能有伪造的时戳，也可能是来自另外人的消息。但攻击者可用下述方法骗取T签字。二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3029Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密

43、码令攻击者的消息为x，他首先任意选一个数N，计算y=Ne mod n(e是T的公钥)，而后计算M=yx，送给T，T将签字的结果Md mod n送给攻击者，则有(Md mod n)N-1 mod n=(yx)dN-1 mod n=xdydN-1 mod n=xdNN-1 mod n=xd mod n，此为T对x的签字。所以能有这类攻击是因为指数运算保持了输入的乘法结构。(c)骗骗取取用用户户签签字字。攻击者可制作两条消息x1和x2，凑出所要的x3x1x2 mod n。首先他可得到用户A对x1和x2的签字x1d mod n 和x2d mod n，则可计算x3d mod n(x1d mod n)(x

44、2d mod n)mod n。因此，任何时候不要为不相识的人签署随机性文件，最好先采用单向Hash函数。ISO 9796的分组格式可以防止这类攻击。二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3030Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码（5）公用模攻击）公用模攻击若很多人共用同一模数n，各自选择不同的e和d，这样实现当然简单，但是不安全。若消息以两个不同的密钥加密，在共用同一个模下，若两个密钥互素(一

45、般如此)，则可恢复明文。设e1和e2是两个互素的不同密钥，共用模为n，对同一消息m加密得 c1=me1 mod n,c2=me2 mod n。分析者知道n,e1,e2,c1和c2。因为(e1,e2)=1，所以有r e1+s e2=1。假定r为负数，从而由Euclidean算法可计算(c1-1)-r c2s=mr e1+s e2=m mod n还有两种攻击共用模RSA的方法，用概率方法可分解n和用确定性算法可计算某一用户密钥而不需要分解n。二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3031Copyright Yuan Copyright Yuan Email:Emai

46、l: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码二、二、RSA密码体制密码体制（6）低加密指数攻击低加密指数攻击采用小的e可以加快加密和验证签字的速度，且所需的存储密钥空间小，但若加密钥e选择得太小，则容易受到攻击。令网中三用户的加密钥e均选3，而有不同的模n1,n2,n3，若有一用户将消息x传给三个用户的密文分别为 y1=x3 mod n1 x n1y2=x3 mod n2 x n2y3=x3 mod n3 x n3一般选n1,n2,n3互素(否则，可求出公因子，而降低安全性)，利用中国余定理，可从y1,y2,y3

47、求出 y=x3 mod(n1 n2 n3)。由xn1,xn2,xn3，可得x3 n1 n2,n3，故有 。2.RSA的安全性的安全性2023/1/3032Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码若x后加时戳 y1=(2t x+t1)3 mod n1y2=(2t x+t2)3 mod n2y3=(2t x+t3)3 mod n3t是t1,t2,t3的二元表示位数，可防止这类攻击。Hstad 将上述攻击扩展为k个用户，即将相同的消息x

48、传给k个人，只要，采用低指数亦可有效攻击。因此，为抗击这种攻击e必须选得足够大。一般，e选选为为16位位素素数数时，既可兼顾快速加密，又可防止这类攻击。对短的消息，可用随机数字填充，以防止低加密指数攻击。d小也不行，Wiener指出，对en，而dn/4，则可以攻破这类RSA体制。二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3033Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网络研究室双钥密码双钥密码（7）定时攻击法）定时攻击法定时(T

49、iming)攻击法由P.Kocher提出，利用测定RSA解密所进行的模指数运算的时间来估计解密指数d，而后再精确定出d的取值。R.Rivest曾指出，这一攻击法可以通过将解密运算量与参数d无关挫败。另外还可采用盲化技术，即先将数据进行盲化，再进行加密运算，而后做去盲运算。这样做虽然不能使解密运算时间保持不变，但计算时间被随机化而难于推测解密所进行的指数运算的时间。二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3034Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络研究室南京航空航天大学网

50、络研究室南京航空航天大学网络研究室双钥密码双钥密码 （8）消息隐匿问题）消息隐匿问题对明文x，0 xn1，采用RSA体制加密，可能出现xe=x mod n，致使消息暴露。这是明文在RSA加密下的不动点。总有一些不动点，如x=0，1和n1。一般有1+gcd(e1,p1)1+gcd(e1,q1)个不动点。由于e1，p1和q1都是偶数，所以不动点至少为9个。一般来说，不动点个数相当少而可忽略。二、二、RSA密码体制密码体制2.RSA的安全性的安全性2023/1/3035Copyright Yuan Copyright Yuan Email:Email: 南京航空航天大学网络研究室南京航空航天大学网络