公钥密码体制及典型算法-RSA.ppt

《公钥密码体制及典型算法-RSA.ppt》由会员分享，可在线阅读，更多相关《公钥密码体制及典型算法-RSA.ppt（147页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、字。 单钥密码体制在进行密钥分配时, 要求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求则完全依赖于密钥分配中心的可靠性。 第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。 1976年W.Diffie和M.Hellman对解决上述两个问题有了突破，从而提出了公钥密码体制。,公钥密码体制的基本概念,4,对称密码体制的缺陷,密钥分配问题 通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现； 密钥

3、管理困难问题 在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大 。 n用户保密通信网，用户彼此间进行保密通信需要 个密钥。 n=1000：499500个密钥 n=5000：12497500个密钥 没有签名功能，无法实现抗抵赖问题：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B。 陌生人间不便进行保密通信问题,5,别名： 公钥密码体制，双钥密码体制 两个密钥： 公开密钥（公钥）：可以被任何人知道, 用于加密或验证签名 秘密密钥（私钥）：只能被消息的接收者或签名者知道,用于解密或签名。 加密或验证签名

4、者不能解密或生成签名（已知密码算法和加密密钥，求解密密钥在计算上是不可行的）。 安全性基础： 基于数学难题 标志性文献 W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654,公钥密码体制的基本概念,6,由私钥及其他密码信息容易计算出公开密钥 (a polynomial time (P-time) problem) 由公钥及算法描述,计算私钥是难的 (an NP-time problem

5、) 因此,公钥可以发布给其他人(wishing to communicate securely with its owner ) 密钥分配问题不是一个容易的问题(the key distribution problem ),公钥密码体制的基本概念,7,公钥算法分类,Public-Key Distribution Schemes (PKDS，公钥分配系统) 用于交换秘密信息(依赖于双方主体) 常用于对称加密算法的密钥 Public Key Encryption (PKE，公钥加密) 用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 任何公钥加密方案能够用于密钥分配方案PKDS

6、 许多公钥加密方案也是数字签名方案 Signature Schemes（签名方案） 用于生成对某消息的数字签名 私钥的拥有者生成数字签名 任何人可以用公钥验证签名,8,公钥密码系统可用于以下三个方面： (1) 通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。,9,(2) 数字签名：将私钥作为加密密钥，公钥作为解 密密钥，可实现由一个用户对数据加密而使多个用户解读。,10,(3) 密钥交换：通信双方交换会话密钥，以 加密通信双方后续连接所传输的信息。 每次逻辑连接使用一把新的会话密钥， 用完就丢弃。,11,公开密钥算法的特点:,（1）发送者用加密密钥

7、PK对明文X加密后，在接收者用解密密钥SK解密，即可恢复出明文，或写为： DSK(EPK(X) X 解密密钥是接收者专用的秘密密钥，对其他人都保密。 此外，加密和解密的运算可以对调，即 EPK(DSK(X) X （2）加密密钥是公开的，但不能用它来解密，即 DPK(EPK(X) X,12,公开密钥算法的特点:,（3）在计算机上可以容易地产生成对的PK和SK。 （4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可能的”。 （5）加密和解密算法都是公开的。,13,公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，简称公开钥，用于加密

8、；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公钥密码体制也称为双钥密码体制。算法有以下重要特性： 已知密码算法和加密密钥，求解密密钥在计算上是不可行的。,公钥密码体制的原理,14,图 公钥体制加密的框图,15,加密过程有以下几步： 要求接收消息的端系统，产生一对用来加密和解密的密钥，如图中的接收者B，产生一对密钥PKB，SKB，其中PKB是公开钥，SKB是秘密钥。 端系统B将加密密钥（如图中的PKB）予以公开。另一密钥则被保密（图中的SKB）。,公钥密码体制的原理,16, A要想向B发送消息m，则使用B的公开钥加密m，表示为c=EPKBm,其中c是密文，E是

9、加密算法。 B收到密文c后，用自己的秘密钥SKB解密，表示为m=DSKBc，其中D是解密算法。,公钥密码体制的原理,17,公钥密码体制认证框图,18,因为只有B知道SKB，所以其他人都无法对c解密。 公钥加密算法不仅能用于加、解密，还能用于对发方A发送的消息m提供认证，如下图所示。用户A用自己的秘密钥SKA对m加密，表示为c=ESKAm 将c发往B。B用A的公开钥PKA对c解密，表示为m=DPKAc,公钥密码体制认证的原理,19,因为从m得到c是经过A的秘密钥SKA加密，只有A才能做到。因此c可当做A对m的数字签字。 另一方面，任何人只要得不到A的秘密钥SKA就不能篡改m，所以以上过程获得了对

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

11、，所以消息不能被他人篡改，但却能被他人窃听。这是因为任何人都能用用户的公开钥对消息解密。为了同时提供认证功能和保密性，可使用双重加、解密。如下图所示。,公钥密码体制认证的原理,22,公钥密码体制的认证、保密框图,23,发方首先用自己的秘密钥SKA对消息m加密，用于提供数字签字。再用收方的公开钥PKB第2次加密，表示为 c=EPKBESKAm 解密过程为 m=DPKADSKBc 即收方先用自己的秘密钥,再用发方的公开钥对收到的密文两次解密。,公钥密码体制认证的原理,2020/10/19,24,公钥保密和认证体制,25,公钥密码算法应满足以下要求: 接收方B产生密钥对（公开钥PKB和秘密钥SKB）

12、在计算上是容易的。 发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKBm 在计算上是容易的。 收方B用自己的秘密钥对c解密，即m=DSKBc在计算上是容易的。,公钥密码算法应满足的要求,26, 敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的。 敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的。 加、解密次序可换，即 EPKBDSKB(m)=DSKBEPKB(m) 其中最后一条虽然非常有用，但不是对所有的算法都作要求。,公钥密码算法应满足的要求,27,以上要求的本质之处在于要求一个陷门单向函数。 单向函数是两个集合X、Y之间的一个映射，使得Y中每一元素y都有惟一的一个

13、原像xX，且由x易于计算它的像y，由y计算它的原像x是不可行的。这里所说的易于计算是指函数值能在其输入长度的多项式时间内求出，即如果输入长n比特，则求函数值的计算时间是na的某个倍数，其中a是一固定的常数。这时称求函数值的算法属于多项式类P，否则就是不可行的。例如，函数的输入是n比特，如果求函数值所用的时间是2n的某个倍数，则认为求函数值是不可行的。,公钥密码算法应满足的要求,28,注意这里的易于计算和不可行两个概念与计算复杂性理论中复杂度的概念极为相似，然而又存在着本质的区别。在复杂性理论中，算法的复杂度是以算法在最坏情况或平均情况时的复杂度来度量的。而在此所说的两个概念是指算法在几乎所有情

14、况下的情形。 称一个函数是陷门单向函数，是指该函数是易于计算的，但求它的逆是不可行的，除非再已知某些附加信息。当附加信息给定后，求逆可在多项式时间完成。,公钥密码算法应满足的要求,29,总结为： 陷门单向函数是一族可逆函数fk，满足 Y=fk(X)易于计算（当k和X已知时）。 X=f-1k(Y)易于计算（当k和Y已知时）。 X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）。 因此，研究公钥密码算法就是要找出合适的陷门单向函数。,公钥密码算法应满足的要求,30,和单钥密码体制一样，如果密钥太短，公钥密码体制也易受到穷搜索攻击。因此密钥必须足够长才能抗击穷搜索攻击。然而又由于公钥密码体制所

15、使用的可逆函数的计算复杂性与密钥长度常常不是呈线性关系，而是增大得更快。所以密钥长度太大又会使得加解密运算太慢而不实用。因此公钥密码体制目前主要用于密钥管理和数字签字。 对公钥密码算法的第2种攻击法是寻找从公开钥计算秘密钥的方法。目前为止，对常用公钥算法还都未能够证明这种攻击是不可行的。,对公钥密码体制的攻击,31,还有一种仅适用于对公钥密码算法的攻击法，称为可能字攻击。例如对56比特的DES密钥用公钥密码算法加密后发送，敌手用算法的公开钥对所有可能的密钥加密后与截获的密文相比较。 如果一样，则相应的明文即DES密钥就被找出。因此不管公钥算法的密钥多长，这种攻击的本质是对56比特DES密钥的穷

16、搜索攻击。抵抗方法是在欲发送的明文消息后添加一些随机比特。,对公钥密码体制的攻击,32,强力攻击(对密钥) 密钥不能太短，防止密钥穷举 但也不能太长，以免影响速度 公开密钥算法本身可能被攻破 赖以安全的基石-数学难题被破解 可能报文攻击(对报文本身的强力攻击) 对所有可能报文加密，直到与截获密文相同,对公钥密码体制的攻击,33,RSA算法是1978年由罗纳德李维斯特（Ron Rivest）、阿迪萨莫尔（Adi Shamir）和伦纳德阿德曼（Leonard Adleman）提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。 它既可用于加密、又可用于数字

17、签字。 RSA算法的安全性基于数论中大整数分解的困难性。 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,2 RSA算法,34,由Rivest, Shamir和 Adleman在1978年提出 数学基础: 大整数因子分解的困难性，Euler定理,35,1. 密钥的产生 选两个保密的大素数p和q (各100200位十进制数字，且p不等于q) 。 计算n=pq

18、，(n)=(p-1)(q-1),其中(n)是n的欧拉函数值。 随机选一整数e，满足1e(n)，且gcd(n),e)=1。 计算d，满足de1 mod (n),即d是e在模(n)下的乘法逆元，因e与(n)互素，由模运算可知，它的乘法逆元一定存在。 d=e -1 (mod (n) 以e,n为公开钥,d,n为秘密钥。(p, q不再需要，可以销毁),算法描述,36,2. 加密 加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算： cme mod n,RSA加密算法描述,37,3. 解密 对密文分组的解密运算为：mcd mod n 下

19、面证明RSA算法中解密过程的正确性。 证明： 由加密过程知cme mod n，所以 cd mod nmed mod nm1 mod (n) mod nmk(n)+1 mod n,RSA解密算法描述,38,下面分两种情况： 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，先看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

20、，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾。,39,由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)+1=m+rcpq=m+rcn 即mk(n)+1m mod n，所以cd mod nm。(证毕),RSA解密算法证明,40,例： 选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的

21、d，因为775=385=496+1，所以d为77，因此公开钥为5，119，秘密钥为77，119。 设明文m=19，则由加密过程得密文为 c195 mod 1192476099 mod 11966 解密为 6677mod 11919,RSA解密算法证明,41,RSA算法实例,例 假设Alice和Bob 使用RSA密码体制进行全英文字符的保密通信。假设Alice 选择 、 、 ，Bob选择 、 ，并采用双字母加、解密方式。 （1）说明Alice和Bob建立RSA密码体制的方法。 （2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。,42,4、RSA算法实例,例 （1）说

22、明Alice和Bob建立RSA密码体制的方法。,解 Alice计算：,43,4、RSA算法实例,例 （1）说明Alice和Bob建立RSA密码体制的方法。,解 Bob计算 ：,44,4、RSA算法实例,例5-1 （2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。,解 Alice加密： “public”代换为数字并按双字母分组：1520 0111 0802,45,4、RSA算法实例,例 （2）若Alice欲秘密发送消息“public”给Bob，试给出加密和解密过程。,解 Bob解密 ： 密文“0095 1649 1410”,明文: public,46,1. RSA的

23、加密与解密过程 RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677 mod 119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质： (ab) mod n=(a mod n)(b mod n) mod n 就可减小中间结果。,RSA算法中的计算问题,47,再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。 求am可如下进行，

24、其中a，m是正整数： 将m表示为二进制形式bk bk-1b0，即 m=bk2k+bk-12k-1+b12+b0 因此,RSA算法中的计算问题,48,例如：19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1)2a1 从而可得以下快速指数算法： 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 return d.,RSA算法中的计算问题,49,其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结

25、果无任何贡献，算法中完全可将之去掉。,RSA算法中的计算问题,50,例求7560 mod 561。 将560表示为1000110000， 所以7560 mod 561=1。,51,2. RSA密钥的产生 产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。 因为n=pq在体制中是公开的，因此为了防止敌手通过穷搜索发现p、q，这两个素数应是在一个足够大的整数集合中选取的大数。如果选取p和q为10100左右的大素数，那么n的阶为10200，每个明文分组可以含有664位（102002664），即83个8比特字节，这比DES的数据分组（8个8比特字节）大得多，这时就能看出RSA算法的优

26、越性了。因此如何有效地寻找大素数是第一个需要解决的问题。,RSA密钥产生,52,寻找大素数时一般是先随机选取一个大的奇数（例如用伪随机数产生器），然后用素性检验算法检验这一奇数是否为素数，如果不是则选取另一大奇数，重复这一过程，直到找到素数为止。 素性检验算法通常都是概率性的，但如果算法被多次重复执行，每次执行时输入不同的参数，算法的检验结果都认为被检验的数是素数，那么就可以比较有把握地认为被检验的数是素数。例如Miller-Rabin算法。,RSA密钥产生,53,可见寻找大素数是一个比较繁琐的工作。然而在RSA体制中，只有在产生新密钥时才需执行这一工作。 p和q决定出后，下一个需要解决的问题

27、是如何选取满足1e(n)和gcd(n),e)=1的e，并计算满足de1 mod (n)的d。这一问题可由推广的Euclid算法完成。,RSA密钥产生,54,RSA的安全性是基于分解大整数的困难性假定，之所以为假定是因为至今还未能证明分解大整数就是NP问题，也许有尚未发现的多项式时间分解算法。 如果RSA的模数n被成功地分解为pq，则立即获得(n)=(p-1)(q-1)，从而能够确定e模(n)的乘法逆元d，即de-1 mod (n)，因此攻击成功。,RSA的安全性,55,随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解。 例如RSA-129（即n为129位十进制数，大约428

28、个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解。,RSA的安全性,56,对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。分解算法过去都采用二次筛法，如对RSA-129的分解。而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%。 将来也可能还有更好的分解算法，因此在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。,RSA的安全性,57,是否有不

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

30、举例,例：n=143,目标：分解n 解：,60,（2） p-1和q-1都应有大素因子 这是因为RSA算法存在着可能的重复加密攻击法。设攻击者截获密文c，可如下进行重复加密：,RSA的安全性,61,RSA的安全性,62,设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能被容易地确定。,RSA的安全性,63,RSA中P、q选择不当(p-1或q-1没有

31、大素因子)的举例,例：p=17，q=11，e=7，则n=187。设m=123，则： C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文m经过4次加密，恢复成明文。,64,RSA存在以下两种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的。 1. 共模攻击 在实现RSA时，为方便起见，可能给每一用户相同的模数n，虽然加解密密钥不同，然而这样做是不行的。,对RSA的攻击,65,设两个用户的公开钥分别为e1和e2，且e1和e2互素（一般情况都成立），明文消息是m，密文分别是c1me1

32、(mod n) c2me2(mod n) 敌手截获c1和c2后，可如下恢复m。用推广的Euclid算法求出满足 re1+se2=1 的两个整数r和s，其中一个为负，设为r。再次用推广的Euclid算法求出c-11，由此得 (c-11)-rcs2m(mod n)。,对RSA的攻击,66,2. 低指数攻击 假定将RSA算法同时用于多个用户（为讨论方便，以下假定3个），然而每个用户的加密指数（即公开钥）都很小。设3个用户的模数分别为ni(i=1,2,3)，当ij时，gcd(ni,nj)=1，否则通过gcd(ni,nj)有可能得出ni和nj的分解。设明文消息是m，密文分别是: c1m3(mod n1)

33、 c2m3(mod n2) c3m3(mod n3) 由中国剩余定理可求出m3(mod n1n2n3)。由于m3n1n2n3，可直接由m3开立方根得到m。,67,另一种欺骗性的攻击RSA,68,思考题,1.,2.,69,RSA 参数选择,需要选择足够大的素数 p, q 通常选择小的加密指数e,且与(N) 互素 e 对所有用户可以是相同的 最初建议使用e=3 现在3太小 常使用 e=216-1 = 65535 解密指数比较大,70,(1) n =pq的确定： p与q必须为强素数 强素数p的条件： (a)存在两个大素数p1和p2，p1|(p1)，p2|(p1) (b)存在4个大素数r1, s1,

34、r2及s2，使r1|(p11), r2|(p21), s1|(p11), s2|(p21)。 p1和p2为二级素数； r1, r2, s1和s2为三级素数,RSA参数的选择,71,采用强素数的理由如下： 若 ，pi为素数，ai为正整数 分解式中piB，B为已知一个小整数 则存在一种p1的分解法，使我们易于分解n 令n=pq，且p1满足上述条件，piB 令aai，i=1, 2, , t 可构造 显然(p1)R，由费尔马定理2R1 mod p 令2R=x mod n，若x =1则选3代2，直到出现x1 此时，kR = 1 mod p 有解的充要条件是 kR = x mod n (p, n)=p |

35、 x-1 由GCD(x1, n)=p，就得到n的分解因子p和q,RSA参数的选择,72,p与q之差要大 若p与q之差很小，则可由n=pq估计(pq)/2 =n1/2， 由(pq)/2)2n=(pq)/2)2，等式右边为小的平方数， 可以试验给出p, q的值 例：n = 164009，估计(pq)/2405， 由4052n=16=42，可得 (pq)/2=405，(pq)/2=4， p=409，q=401,RSA参数的选择,73,p1与q1的最大公因子要小 惟密文攻击下，设破译者截获密文y=x e mod n 破译者做下述递推计算： xi=xi-1e mod n=(xe)i mod n 若ei=

36、1 mod (n)，则有xi=x mod n，且ei+1=e mod (n)，即xi+1=x 若i小，则由此攻击法易得明文x。 由Euler定理知，i=(p1)(q1)， 若p1和q1的最大公因子小，则i值大， 如i=(p1)(q1)/2，此攻击法难于奏效。,RSA参数的选择,74,p，q要足够大，以使n分解在计算上不可行,RSA参数的选择,75,e的选取原则 (e, (n)=1条件易于满足，因为两个随机数互素的概率约为3/5 e不可过小：若e小，x小，y=xe mod n，当xen，则未取模， 由y直接开e次方可求x，易遭低指数攻击 e小时，加密速度快，Knuth和Shamir曾建议采用e=

37、3 但e太小存在一些问题 选e在mod (n)中的阶数i(ei 1 mod (n)达到(p1)(q1)/2,p，q要足够大，以使n分解在计算上不可行,RSA参数的选择,76,d的选择 e选定后可用Euclidean算法在多项式时间内求出d d小，签字和解密快，在IC卡中尤为重要(复杂的加密和验证签字可由主机来做) d要大于n1/4：类似于加密下的情况，d不能太小 否则由已知明文攻击，构造y=xe mod n，猜测d的值： 做yd mod n，直到试凑出ydx mod n Wiener给出对小d的系统攻击法， 证明了当d长度小于n的1/4时， 由连分式算法，可在多项式时间内求出d值,RSA参数的

38、选择,77,不可用公共模 由一密钥产生中心(KGC)采用一公共模，分发多对密钥，公布相应公钥ei 这当然使密钥管理简化，存储空间小，且无重新分组问题 但如前所述，它在安全上会带来问题。 明文熵要尽可能地大 明文熵要尽可能地大，以使在已知密文下， 要猜测明文无异于完全随机等概情况。 用于签字时，要采用Hash函数,RSA体制实用中的其它问题,78,RSA理论,RSA 基于Fermats Theorem: if N = pq where p, q are primes, then:X(N) = 1 mod N for all x not divisible by p or q, ie gcd(x,

39、(N)=1 where (N)=(p-1)(q-1) 但在 RSA 中，e 破译该体制等价于对大整数的分解。 RSA中选取的公开钥e满足1e(n)，且gcd(e,(n)=1。Rabin密码体制则取e=2。,Rabin密码体制,99,1. 密钥的产生 随机选择两个大素数p、q，满足pq3 mod 4，即这两个素数形式为4k+3；计算n=pq。以n作为公开钥，p、q作为秘密钥。,Rabin密钥的产生,100,2. 加密 cm2 mod n 其中m是明文分组，c是对应的密文分组。,Rabin加密描述,101,3. 解密 解密就是求c模n的平方根，即解x2c mod n，由中国剩余定理知解该方程等价于

40、解方程组 由于pq3 mod 4，下面将看到，方程组的解可容易地求出，其中每个方程都有两个解，即 xm mod p,x-m mod p xm mod q,x-m mod q,Rabin解密描述,102,经过组合可得4个同余方程组 由中国剩余定理可解出每一方程组的解，共有4个，即每一密文对应的明文不惟一。为了有效地确定明文,可在m中加入某些信息,如发送者的身份号、接收者的身份号、日期、时间等。,Rabin解密描述,103,下面证明，当pq3 mod 4，两个方程x2c mod p, x2c mod q的平方根都可容易地求出。 由p3 mod 4得，p+1=4k，即1/4(p+1)是一整数。因c是

41、模p的平方剩余，故,104,所以 和 是方程x2c mod p的两个根。同理 和 是方程x2c mod q的两个根。 由以前知识知，求解方程x2a mod n与分解n是等价的，所以破译Rabin密码体制的困难程度等价于大整数n的分解。,Rabin解密描述,105,已经说过，为保证RSA算法的安全性，它的密钥长度需一再增大，使得它的运算负担越来越大。相比之下，椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得同样的安全性，因此具有广泛的应用前景。ECC已被IEEE公钥密码标准P1363采用。,5 椭圆曲线密码体制,106,椭圆曲线并非椭圆，之所以

42、称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。一般来讲，椭圆曲线的曲线方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e (4.1) 其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷点的元素，记为O。下图是椭圆曲线的两个例子。,5.1 椭圆曲线,107,椭圆曲线的两个例子,108,从图可见，椭圆曲线关于x轴对称。 椭圆曲线上的加法运算定义如下： 如果其上的3个点位于同一直线上，那么它们的和为O。进一步可如下定义椭圆曲线上的加法律（加法法则）： O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。,椭圆曲线的描述,109, 设P1=(x,y)

43、是椭圆曲线上的一点（如图所示），它的加法逆元定义为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, 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义如下： 画一条通过Q、R的直线与椭圆曲线交于P1（这一交点是惟一的，除非所做的直线是Q点或R点的切线，此时分别取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定

44、义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，等。 以上定义的加法具有加法运算的一般性质，如交换律、结合律等。,椭圆曲线的描述,111,密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程 y2x3+ax+b(mod p) (a,bGF(p),4a3+27b2(mod p)0)定义的曲线。,5.2 有限域上的椭圆曲线,112,例： p=23，a=b=1，4a3+27b2(mod 23)80 ，方程为y2x3+x+1，其图形是连续曲线。然而我们感兴趣的是曲线在第一象限中的整数点。

45、 设Ep(a,b)表示方程(4.2)所定义的椭圆曲线上的点集(x,y)|0 xp,0yp，且x,y均为整数并上无穷远点O。本例中E23(1,1)由表4.6给出，表中未给出O。,有限域上的椭圆曲线,113,一般来说，Ep(a,b)由以下方式产生： 对每一x(0 xp且x为整数），计算x3+ax+b(mod p)。 决定中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0 时只有一个平方根）。,有限域上的椭圆曲线,114,Ep(a,b)上的加法定义如下： 设P，QEp(a,b)，则 P+O=P。 如果P=(x,y)，那么(x, y)+(x, -

46、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)中。,有限域上椭圆曲线的加法,115, 设P=(x1,y1)，Q=(x2,y2)，P-Q，则P+Q=(x3,y3)由以下规则确定： x32-x1-x2(mod p) y3(x1-x3)-y1(mod p) 其中,有限域上椭圆曲线的加法,116,例： 仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则 所以P+Q=（17,20）

47、，仍为E23(1,1)中的点。,有限域上椭圆曲线的加法,117,若求2P则 所以2P=(7,12)。,有限域上椭圆曲线的加法,118,倍点运算仍定义为重复加法，如4P=P+P+P+P。 从上例看出，加法运算在E23(1,1)中是封闭的，且能验证还满足交换律。对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以Ep(a,b)是一个Abel群。,有限域上椭圆曲线的加法,119,为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。 在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，QEp(a,b)，kp，则由k和P

48、易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。Diffie-Hellman密钥交换和ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这两种密码体制。,5.3 椭圆曲线上的密码,120,1. Diffie-Hellman密钥交换 首先取一素数p2180和两个参数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,两用户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)