山大信息安全课件第3章 公钥分发技术

1、 第3章 公钥分发技术. 公钥分配技术 涉及公钥密码技术的协议通常在描述的时候通常假定恰当部分的可信的公钥已经获得。这样便允许在一般情况下以各种不同的方式获取这些秘钥。分配公钥过程具有保证机制或可验证公钥完整性的方案主要包括以下的几种：点到点的通过可靠信道传输 通过相关用户之间的个人交流或直接的信道 获取其他相关用户的公共秘钥，并由秘钥来源方保证其真实性与完整性。这种方法在操作不太频繁（如用户的注册），或小型的封闭系统中较为实用。 另一种相关的方法是通过一非可靠的信道传输公钥及相关信息。 并通过连接一个独立的，低带宽的可靠通道获得其哈希值，由哈希值对这些消息进行认证。这种方法的缺点主要有：使用

2、的不方便；在未保证通信安全的情况下便非自动的对新的用户提出其公共秘钥申请；可靠信道的花费。2.直接连接到一个可靠的公共文件(公钥记录表) 首先建立一个保证完整性的公共数据库，将每个系统用户的名字与公钥保存在其中。该公钥登记工作由一可信的用户完成。用户直接由记录获得秘钥。在被动攻击下通过非安全信道远程访问记录是可行的。但当存在主动攻击者时远程访问需要有安全的通道。3. 使用可靠的在线服务器。 由一个可靠的在线服务器起到上面公共文件的作用来保管秘钥，响应（单个地）请求后发送签名后的公钥。这种方法的保密性是不需要特别保证的。发送请求的用户保存有服务器的签名副本。可以以之对传输的可靠性进行验证。这个方

3、案的缺点在于：服务器必须始终在线；服务器有可能成为瓶颈；通信连接必须同时由该可靠的服务器与计划中的通信方两方共同确定。4. 使用离线服务器和证书。 用户A 联系一个离线的可靠用户作为认证中心 certification authority (CA), 用来记录他的公钥并获取CA的签名验证公钥（允许验证其它用户的证书）。CA 通过将A的公钥捆绑在一信息串上验证A，从而创建证书，用户们通过交换证书或由公共目录提取获得真正的公钥。5. 使用系统本身公共参数隐式的可靠性保证。 其中包含基于身份的系统以及包含隐式验证的系统，通过算法设计,更改公共向量将导致可发现的结果，即在密码技术无折衷的失败产生。下面

4、分类具体论述：基于身份的系统（ID-based systems） 基于身份的系统与通常的公钥密码系统相类似，涉及一个私人的传输与一个公共的传输，但使用者并不象前面拥有隐藏的公钥，而是由用户公开可用的身份识别信息代替。用户的任意公开的可用的信息只要能够唯一的非否认确认该用户的均可作为标识信息。定义 基于身份的密码系统是一个非对称的系统。其中实体的标识信息起到了公钥的作用。由可信中心T将之作为输入信息由其计算实体的私钥。 当完成计算后，T通过一个安全的信道将实体的私钥传送给该实体。该秘钥并不完全由实体的标识信息计算，但其中必须包含一些仅为T所知的特权信息（T的秘钥）。这样对于防止伪造是必需的，其实

5、质是只有T可由给出的标识信息计算出可用的私钥。而相应的公共的可用的系统数据必须同时包含在加密传输中，类似于在基于证书的系统中认证权威的公钥。有时候，除了优先权IDA附加的系统定义的数据DA也要与用户A相联系。这样的系统已不再是“纯粹的”基于身份识别的了。同样，也不是单纯的DA 或IDA 验证了。隐式验证的公钥系统 （Implicitly-certified public keys） 另一种变异的公钥系统的是利用隐式验证公钥的非对称系统，这里外在于用户的公钥是存在的。外在于用户的公钥是存在的，但公钥必须重建（依原样的）而不是象基于每个基于验证的系统通过公钥证书传递。带有隐式验证公钥的系统可以这样

6、设计：1.实体的公钥可由公共数据重建（被其他用户） ( 这基本取代了证书的作用)。 2. 用来重建公钥的公共数据有： (a) 与可靠用户相关的公共数据。 (b) 使用实体的标识。 (c) 每个用户的公共附加数据3.公钥重建的完整性是不能直接验证的。 但一个“正确的”公钥只能从公钥的原作者处的公共数据重新获得。对于重建公钥的检验，系统设计中必须满足：1. 变更一个用户的标识或变更公共数据将导致重 获的秘钥不被服务器接受，但不会导致加密数据 的爆光 。 2. 对手由任意的用户的公钥均无法计算一用户对 应于公钥的私钥或构建用户身份的匹配信息。对应于某一私钥的公共数据是可计算的。重建公钥就是通过这样构

7、造进行隐式验证的。隐式公钥认证的分类 基于身份的公钥(第一类). 每一个实体A的私钥由可信的用户T基于A的身份信息和T的私钥计算。这同时是A用户特有的并经过T校正的重建用公共数据中的一个函数。A的私钥由T安全的传送给A。2. 自我验证的公钥(第二类)。 每一个实体A自己计算它的私钥和相应的公钥。A的用于重建的公共数据，A的身份信息和T的私钥由T计算。由于第三方具有通向用户私钥的入口，第一类方法需要对第三方有更多的信任。作为与第二种情况的不同，后者根据秘钥受实体本身的限制强调了“自我验证”中的“自我”。公钥分配技术的对比 图13.7中对非对称签名系统的分类做了说明，对比公钥密码系统（具有显式的公

8、钥），基于身份的系统（公钥是用户身份信息）与隐式公钥认证系统（显式的公钥由用户的公共数据重建）.主要的不同有： 基于证书的公钥系统具有显式的公钥，基于身份的系统则没有；在隐式系统中系统中的明确公钥由重建得到。公钥系统中的显式公钥(图 13.7(a)被替代为（a）基于身份验证的系统(图13.7(b)中的三元组 其中 是A的身份信息串， 是附加的公共数据（由T定义并与 的和A的私钥相关。 由可靠权威T 的可靠公钥(或系统参数)构成。 (b) 隐式公钥系统(图13.7(c)中的三元组。这时，显式的公钥 由这些信息重建。用于重建的公共数据 在这里起到了图13.7(b)中 的作用。2. 在基于证书的系统

9、中公钥的真实性可以(切必须能)被明确的验证,但在基于身份的系统和隐式验证的系统中则不然(也不必)。3. 在基于证书的公钥系统与隐式验证系统中的自我公钥验证中，可心中心不需知道用户的私钥。而在基于身份的系统和隐式验证系统中的基于身份验证中需要知道。4. 与基于身份的系统类似，隐式验证系统的公钥依赖于实体的身份信息，感觉上也是“基于身份的”。然而，基于身份的系统避免了显式完整的公钥，而隐式验证的系统并不限制使用者计算出公钥。5. 对比隐式公钥认证中的两类，可见其在用于重建的公共数据和私钥的关系上有所不同。(a) 第一类:一个用户的私钥作为一个用于重建的公共数据的函数。该公钥由可心中心计算。(b)

10、第二类:用于重建的公共数据是由用户的公钥计算的函数，相应的私钥由用户自己产生。.6. 在所有三种方案中。均在某些时段上使用了在某种程度上可靠的第三方用来建立连接。在完全未曾蒙面或除了系统参数毫无共享的用户之间传递信任。2.秘钥使用的控制技术秘钥分离与秘钥强制使用 密码技术中的秘钥信息应同时包括秘钥的限定属性和其它操作上的使用信息。包括例如秘钥拥有者，有效期，预定的使用，秘钥鉴定者等信息。秘钥的分离与不当使用的威胁 在一个简单的秘钥管理系统中，秘钥相关信息例如被授权的应用被通过上下文推断出。为了达到附加的澄清与控制功能，特别显式指定的授权使用信息可伴随秘钥分配与认证，在使用其间，尝试的使用是得到

11、授权的。如果控制信息是受到操纵的，就将它以一种保证真实性与完整行的方法将其与秘钥捆绑在一起。 秘钥的分离原则是指不同用途的秘钥应当分离。秘钥的误用的威胁可通过技术手段来解决，保证秘钥只被用于在秘钥生成时便授权的使用范围内。秘钥使用上的限制可由程序上的技术,物理保护，或下面讨论的密码技术进行。对称秘钥使用的控制技术 下面主要讨论的是控制向量的使用，为了讲清其发展过程，秘钥标记，秘钥变码与秘钥公证也将被提到。(i) 秘钥标记和秘钥变码 秘钥标记Key tag提供了一种简单的方法用来制定秘钥允许的使用。一个秘钥标记是一个位向量或一个伴随着秘钥于其整个生存期的构造的域。秘钥标记通过加密与秘钥捆绑在一起

12、，仅当该秘钥解密时才以明文形式出现. 一个早期的分离秘钥的方法是通过非安全的参数与函数由一个单独的基本秘钥base key取得秘钥结果秘钥被称为秘钥变码 key variants或源秘钥 derived keys。在这里，一种令秘钥不同的方法是秘钥偏移 key offsetting，依靠一个秘钥加密秘钥K，K的值每次使用时都会基于一个计数器变更，该计数器每次使用完后都会增加。这将防止加密秘钥的重复。变更的秘钥 被用于加密其他秘钥。接受者同样变更K去加密会话秘钥 . (ii)公证 秘钥公证是一种预防秘钥被替换的技术，主要通过请求与秘钥相关的用户的身份的明确说明实现。秘钥的验证通过利用这些身份改变

13、一个秘钥加密秘钥进行验证。其中真实身份一定要详细说明来恰当的恢复被保护的秘钥。该秘钥被称为将要利用这些身份处理的。在所有的秘钥协议中，都需要阻止秘钥被替换。公证需要合适的控制信息来恢复秘钥，并提供对隐式验证的公钥提供类似的保护。基本的技术(简单的公钥公证) 包含一个可信的服务器，或一个分享该秘钥的用户,使用一个秘钥加密秘钥K加密会话秘钥S。令源用户为 i 接收的用户为 j,则可表示为。这里假定 i与j为系统中实体的唯一标识。用户要想恢复S便必须共享K并明确地以正确地次序了解i与j，否则将恢复随机秘钥。这里假定第三方准确的鉴定用户的身份，并提供一个仅能由这些用户恢复的会话秘钥。(iii) 控制向

14、量 相对于秘钥公证可以被看作是一个秘钥鉴定的机制，控制向量利用将秘钥标记与简单的秘钥公证机制相结合的方法提供了一个控制秘钥使用的方法。与每个秘钥相联系的秘钥S 是一个控制向量C，其中包含一个数据域定义了对这个秘钥的使用授权。类似于秘钥标记，该数据域在一秘钥加密秘钥加密（ ）之前便和S捆扎在了一起。 像正确地秘钥解密秘钥一样，秘钥解密也需要恰当的指定控制向量。若结合值不正确，则一个伪造的秘钥的恢复对于对手是无用的。在秘钥S一生成便将控制向量C通过加密与之捆绑起来。阻止非授权的对C的操作,假定只有获得授权的用户具有秘钥加密秘钥K的入口。 通过利用一个或几个C的域将公证封装进C，已知用来说明身份。

15、与存取控制的标准模式相比，一个控制向量可能被用来说明某人的身份 ( )和特权( ) 关于某秘钥的使用信息( )。. 当用于一个具体的密码的操作时，控制向量像被保护的秘钥一样输入。然后检验请求操作是否依照控制向量执行，如果是这样，则用控制向量解密秘钥。若控制向量与被保护的秘钥上捆绑的信息不匹配（或K不正确），则恢复的秘钥 是假的。这里的安全性依靠假设检验与使用是分离的，且在可靠子系统中完成。 若控制信息C与秘钥K相差很小，可以在配对之前先使用一抗碰撞哈希函数。这样便允许控制信息的长度任意，这样我们可以用一个128位的秘钥K和一个输出为128位的哈希函数加密S。 。三公钥密码系统 公钥密码的观点是

16、由Diffie和Hellman于1976年在 们的论文“密码学的新方向”一文中首次提出的。他们指 明了实现在某些已知的数学难解问题上建立密码的具体 途径。 随后Rivest, Shamir和Adleman于1977年提出第一个比较完善的RSA公钥密码系统。RSA既可以用于保 密也可以用于签名。公钥密码系统是计算复杂性理论发 展的必然产物。私钥（对称）密码系统的缺陷之一是通 信双方在进行保密通信之前需要通过安全通道传送密这点在实际中是非常困难的。而公钥密码系统可使通信双 方无须事先传送密钥就可以建立保密通信。公钥密码系 统的出现为解决私钥密码系统的密钥分配问题开辟了一 条宽广的道路。在公钥密码系

17、统中每个实体都有自己的公钥和相应的私钥。在安全系统中已知公钥推算出私钥在计算上是困难的。公钥密码系统的加密变换和解密变换分别用和表示。任何实体B要向实体A发送信息m的步骤如下:实体B首先获得实体A的真实公钥 的拷贝(Authentic Copy) 实体B计算密文 并发送给实体A。实体A使用自己的私钥，计算 解密密文恢复明文。这里公钥不需要保密，但要保证它的真实性，即 确实是实体A掌握的私钥所对应的公钥。“提供真实的公钥”比“安全地分配密钥”实现起来要容易得多。这是公钥密码系统的主要优点。公钥密码系统的主要目的是提供保密性，它不能提供数据源认证(Data Origin Authenticatio

18、n)和数据完整性 (Data Integrity)。数据源认证是指：指定的数据是在以前的某个时间确实是由真正的源创建的。数据完整性是指：真正的源创建该数据后经过传输或储存没有发生改变。数据源认证和数据完整性要由其它技术来提供（如：消息认证码、数字签名）从本质上来看，公钥密码比私钥密码（如：DES、IDEA、RC5等）加密的速度要慢。通常公钥密码用在:传送密钥。以后用该密钥作为私钥密码系统的密钥来加密大量数据 在数据完整性和认证中使用 加密少量数据 公钥解密也可以提供认证保证（如：在实体认证协议、带认证的密钥协建立协议等）。公钥加密中必须有办法让发送消息的人得到想要发送到的那个人的公钥的真实拷贝

19、。否则的话就会受到伪装攻击。在实践中有很多方法分发真实的公钥，如：使用可信的公共文件、使用在线可信服务器、使用离线服务器和认证。建立在不同计算问题之上的其它几个公钥密码系统是Merkle-Hellman Knapsack (1978) 本系统及相关系统基于“子集和”问题的困难性。然而已证明除Chor-Rivest系统外各种knapsack系统都是不安全的McEliece (1978) McEliece密码系统基于代数编码系统。ElGamal (1985) 它基于有限域中离散对数问题的困难性椭圆曲线 椭圆曲线密码系统是用椭圆曲线上运算代替有限域上运算来实现已有的公钥密码系统。它的特点是运行速度快

20、、密钥长度短 从抽象的观点来看，公钥密码系统是一种单向陷门函数。我们说一个函数是单向函数(One Way Function)是指：对它的定义域中的任意元素都容易计算其函数值，反过来对值域中几乎所有元素确定它的原象都是不可行的。如果掌握某些辅助信息就容易由值域元素确定它的原象，那么这种单向函数叫单向陷门函(Trapdoor One Way Function)。这里辅助信息就是陷门。例如：p和q是两个大素数，n=p.q，e是正整数， 是单向陷门函数，其陷门是 。 3.1 RSA系统和素因子分解3.1.1 RSA密码系统简介3.1.2 RSA密码系统描述3.1.3 RSA实现3.1.4 RSA在实现

21、时要注意的问题3.1.6 有关算法3.1.7 因子分解3.1.1 RSA密码系统简介RSA是使用最广泛的公钥密码系统。它可以用在保密性和数字签名。1976年Diffie & Hellman提出公钥密码系统的思想1977年由Rivest, Shamir, Adleman 首次实现了著名的RSA密码系统，它的安全基于大整数素因子分解的困难性上。3.1.2 RSA密码系统描述每个实体有自己的公钥(n,e)及私钥p,q,d，其中n=p.q是两个大素数之积, 。 实体B加密消息,将密文在公开信道上传送给实体A。 实体A接到密文后对其解密。加密算法实体B做如下动作 1.得到实体A的真实公钥(n,e) 2.

22、把消息表示成整数m,0mn-1 3.使用平方乘积算法，计算 4.将密文发送给实体A解密算法 实体A接受到密文C，使用私钥d计算 ,证明：对任何 有 这里要证明 首先证明 对 ,显然有 当 时,由Fermat定理知 同理推出 最后得到3.1.3 RSA实现1密钥生成 每个实体A建立他的RSA公钥和相应的私钥 a.生成两个大的随机素数p和q，并且 位长大体相同 b.计算n=p.q， c.选择随机数e, , （推出是奇数） d.求 ，即用扩展的Euclidean算法求 的解d（推出也是奇数） e.公布实体A的公钥（n,e），由实体A秘密保存私钥p,q,d 2加密和解密的有效性 若能分解n，就能由e公

23、钥计算出私钥d。为此应n=p.q足够长。当前整数素因子分解算法能分解十进制数长度是130，故选取的素数p和q应该是100的十进制数。目前RSA的一些硬件实现使用512 bit 的n（相当154位十进制数，所以不能提供长期的安全性），速度达600 Kbit / 秒。由于二次筛法、数域筛法等因子分解算法的出现，我们推荐768bit，长期安全应该使用1024bit。 粗略地说，RSA硬件实现比DES硬件实现慢1500倍。RSA软件实现比DES软件实现慢100倍。为了加速解密，实体A不是简单平方-乘积算法计算 ，而是利用p，q计算令 ， ，用中国剩余定理解求出明文m。这样速度可以提高48倍。3RSA安

24、全性分析首先我们研究如下事实的等价性 a.计算 b.求1模n非平凡二次方根 c.分解的素因子由此看出攻击RSA可能采取的方法,上述事实的等价性分析如下：已知n和 由定义n=p.q和 得知 的它的两个根为p和q，即能分解n。实际上知道 就可以从公钥e计算出私钥d。已知n=p.q的素因子p,q， 中元素1是模p二次剩余，它的两个二次方根为1，p-1。 中元素1是模q二次剩余，它的两个二次方根为1，q-1。用中国剩余定理求解下面4个同余方程组得到4个模n同余解z，它们必是(1,n-1,x,n-x)使 。其中x,n-x是模n非平凡二次方根 例如：求出z=1,z=92,z=311,z=402,z=92,

25、311为1模403的非平凡二次方根。反过来,已知1的模n非平凡二次方根,即知道 且 ,显然 。 用Euclidean算法在多项式时间内能求出或 ，它们就是p或q，故能分解n。例如： ,x=92,311为1模403的非平凡二次方根。gcd (92+1, 403)=31,gcd (92-1, 403)=13 。gcd (311+1, 403)=13, gcd (311-1, 403)=313.1.4 RSA在实现时要注意的问题 1.在构造n时应选择p和q使得p-1 和q-1 有大的素因子。一般选择p和 (p-1)/2均是素数的p。 2.每个用户必须有自己的模数n，用户之间不要共享n。这里有两个原因

26、: 1某中心选择公用的RSA模数n，然后把 分发给众多用户。由 任何一对 都能分解模数n。从而本质上任何用户都可以求出共享 该模数的每个用户的解密密钥 。 2如果用户1公钥为 , 用户2公钥为 , 其中 。用户3要把同一个消息x发送给用户1和用户2， 它们分别为 ， 。窃听者截获就可以计算出x。其步骤是： a.计算 b.计算 3RSA的同态性质 (Homomorphic Property) RSA的同态性质是指乘积的密文是密文的乘积，即 的密文 其中对手想解开密文 但是不让实体A知道m于是对手随机选择整数 并用代替来掩盖明文m.让实体A对 解密得到 对手再计算出明文 对待这种选择密文攻击，实践

27、中可以通过在明文消息中强行加入某个结构来解决。如果密文C解密后不具有这种结构，则实体A发现是欺骗行为而拒绝C。这种做法以很高的概率使 不具有这种精心选择的结构，从而对手取不到 。4小的加密指数为了增强加密的有效性，希望选择较小的加密指数e（如=3）.一组实体可以有相同的加密指数，前面说过每个实体必须有自己各不相同的模数。如果相同的消息要送给多个实体的话，就不应该使小的加密指数 例如：实体A要送给m三个不同实体，他们的公钥分别是 , , ,其中 互素对手窃取到密文 使用中国剩余定理解下面同余方程组 得到x并求它的三次方根就恢复明文m。 为了防止这类攻击，在加密前把随机生成的字符串附在明文的后面.

28、这个过程叫“消息加盐”(Salting the message).对于小的 消息m和e， 也可以采用加盐的办法。 小的加密指数对于小的明文（ ）也存在问题。对手只 需计算密文的e次方根就能恢复明文。选择小的e或选择e的二进 制表示中1的位数少。好处是可以加速加密算法。在实际使用中一 般取 e=3 或者 。 5消息隐藏问题 如果 ，则明文加密后没有被隐藏。不难看出 共有 个消息未被隐藏（9）为此我们最好选取安全素数，即对于素数p，(p-1)/2也是素数。如果p和q是随机素数，e也是随机选的（或选择e比较小如e=3或 ），则一般RSA加密未隐藏的消息所占比例小的可以忽略不计。3.1.6 有关算法

29、扩展的辗转相除法、求逆、中国剩余定理等算法已经在前面介绍过。现在给出求幂的算法和素性测试算法。1）求幂的算法（平方乘积法） 输入 ， ，的二进制表示为 输出 ，如果 ，则返回值 。 如果 ，则 对 做 如果 则 例如：求 这里 ，最后求出 = 7。计算过程中各参数列表如下 0 1 2 3 1 1 0 1 3 9 13 16 3 10 10 7 2）素性测试算法 在实际中为了生成大随机素数,首先生成大随机数,然后使用 概率多项式时间Monte Carlo算法测试它们的素性 (Primality)。这些算法速度快,但是有可能出错,通过多次 运行能使出错概率降到任意小.它的理论依据是素数定理。 该定

30、理告诉我们在1px的所有整数中是素数的比例 为 ,即随机地选一个p,它是素数的概率约为 例如对于模数n是512位，它的十进制长度是154位，p和q约为77位。 ，也就是说平均取177个长为77的十进制数就会有一个是素数。如果我们只取奇数，此概率加大一倍为2/177。定义（模二次剩余）p是奇素数，1xp-1是整数。如果存在y,0yp-1 使 得 ，则称x是一个模p二次剩余 ( Quadratic Residue Modulo p )。所有模p二次剩余构成集合 。 若x不是p的倍数且x不是一个模p二次剩余，则称x是一个模p非 二次剩余( Quadratic Non-residue Modulo p

31、 )。所有模p 非二次剩余构成集合 。例如:p=11, ,定理（Euler判别准则） p是素数，x是一个模p二次剩余当且仅当 上例中 ，而 。 验证了3是模p二次剩余，而10不是。Legendre symbol 若p是素数，则 Jacobi symbol 令 ，定义如果n是素数，则对任何a成立 如果n是合数，则 中至少有一半的整数使 不成立 证明：设 使得 不成立。使 成立 的所有整数是 ，当 时 不成立。 对所有 ， 不成立。 例如： 中模21二次剩余集合 ， ， ，8是“21为合数的Euler证据”。 ， ，20是“21的素性的Euler谎言”。若n是奇整数，选择一个随机整数a, 由于公钥

32、密码学时代的到来（特别是RSA）使Solovay-Strassen概率素性测试变得大众化。因为Miler-Rabin测试在有效性和标准性都要好一些，所以现在不再使用这个测试了。但是Solovay-Strassen 算法是概率素性测试的历史起点。现在许多软件中还在沿用这个测试。 所谓判定问题(Decision Problem)是指问题要回答的是“是”或“否”，而概率算法(Probabilistic Algorithm)是使用随机数的算法 偏向“是”的(yes-biased) Monte Carlo算法 判定问题的一个概率算法，对“yes”实例回答总是对的，而“no”实例回答可能是错误的。偏向“非

33、”的(no- biased)Monte Carlo算法 判定问题的一个概率算法，对“no”实例回答总是对的，而“yes”实例回答可能是错误的。Solovay-Strassen 素性测试（对合数而言是yes-biased Monte Carlo算法） 输入：奇整数和安全参数。 输出：对问题“是素数吗？”回答“是素数”或“是合数” 对 做 选择一个随机整数a, 用平方乘积算法计算 如果 ，则返回“是合数” 计算Jacobi符号 如果与模不同余，则返回“是合数”。 返回“是素数” *算法框图3-9* 如果该算返回“是合数”，那么一定是合数，其原因是 “素数必遵守Euler准则”。换句话说：如果真是素

34、数， 不管怎样选取算法总是会返回“是素数”。如果真是合 数，对而言至多有 是Euler谎言。所以该算 法返回“是素数”的概率小于 。 另外，这里不需要测试 。否则的话，必推 出 ，从而 并返回“是合数”。 Miller-Rabin素性测试 (yes-biased Monte Carlo算法) 输入：奇整数 ， 安全参数 输出：对问题“n是素数吗？”给出“是素数”或“是合数”回答 令 ，r 是奇数 对 做Miller-Rabin素性测试 (yes-biased Monte Carlo算法) 选择一个随机整数a, ,计算； 如果 不成立，则 当 且 时做 如果 ，则返回“n是合数”并退出 如果 ，

35、则返回“n是合数”并退出 返回“n是素数”Miller-Rabin素性测试 (yes-biased Monte Carlo算法) 这里依据的事实是：1)n是奇素数时，令 ，r是奇数。对所有满足gcd (a,n)=1的a， 或对某个 ， 。2)n是奇合数时，令 ，r是奇数。a满足 如果 不满足且对所有 ， 都不成立，则称a是“n是合数的强证据”(Strong Witness)Miller-Rabin素性测试 (yes-biased Monte Carlo算法) 如果 或存在 ， ，则称“n是以a为底的强素数”，“a是n的素性 强谎言”(Strong Liar)。 若是奇合数，1, 2, , n-

36、1中至多有 个“n的素性强谎 言”。例如n = 91 = 7*13, 它的强谎言有18个，它们是 1,9,10,12, 16,17, 22, 29, 38, 53, 62, 69,74, 75, 79, 81, 82, 90。 下面用反证法证明：如果是奇素数，则Miller-Rabin算法一定不会返回“n是合数”。 Miller-Rabin素性测试 (yes-biased Monte Carlo算法) 假若对某个素数n返回“n是合数”，那么在循环 中必然对 均不满足 而n是素数 。由此推出 ，因 不成立，故有 。 如此进行下去，最终得到 从 Miller-Rabin算法得到结论“是素数”。 3

37、.1.7 因子分解 因子分解比生成大素数更困难，因子分解模数是攻击RSA最直接的方法。RSA公钥加密系统的出现极大地促进对大整数因子分解方法研究的热潮。特别是借助计算机网络进行分布式计算取得较大进展。 *1983年Davis, Holdredge, Simmons利用二次筛法成功地分解了69位十进制数（它是 的一个合数因子） l* 1989年Lenstra, Manasse利用二次筛法使用数百台工作站分解了106位十进制数*位1990年Lenstra, Manasse, Pollar利用数域筛法使用700台工作站花费个月时间将155十进制数 分解成三个素数（分别为7，49，99位）之积 。*1

38、994年Atkins, Graff, Lenstra, Lerland利用二次筛法动用台计算机联网花费个月时间分解了129位十进制数 3.1.7 因子分解由此可以看出，目前的分解能力对154位十进制数（512bit）的模长已经造成威胁，人们建议使用308位十进制数（1024bit）模长。因子分解算法分成特殊目的和一般目的两类。当被分解的数具有特殊形式，可以为它量身定做因子分解算法。算法运行速度与因子的特定性质有关。例如： *Pollard rho算法找合数小的因子 *l Pollard 算法找合数n的素因子p，如果所有满足 的素数因子 ，即所谓 关于小的界B是平滑的。*椭圆曲线算法它是在 上随

39、机的椭圆曲线群上的Pollard 算法 :*3.1.7 因子分解 *特殊数域筛对于型为 ，其中 都较小的n使用数域筛进行分解 一般目的分解算法的运行时间只与n的大小有关。例如 *二次筛对于预先选定的小素数集合B，找整数x使 的所有素因子都在B中，最后将某些x相乘似的每个在B中的因子出现偶数次，即找到同余方程 ，从而分解 n*一般数域筛试图寻找x和y使 成立，但是 不成立。这里要使用两个因子库，其中一个是小于某个界的所有素因子，另一个是在适当选择的代数数域中范数小于某个界的所有素理想。 3.1.7 因子分解基于RSA公钥密码系统安全性考虑应满足 *p,q要足够大，一般应在十进制100位到125位

40、 *如果 ，要求 差不宜太小，最好与p,q位数接近。但是p与q数值不要接近。 *gcd (p-1,q-1)尽可能小 3.2 Rabin密码系统 Rabin于1979年提出一种变形的RSA算法，称之为Rabin算法。可以证明它的安全性等价于大整数因子分解问题。 3.2.1 Rabin算法 Rabin算法中n 和B是公钥，其中n是Blum数( ， 且 ), 。p和q是私钥。对于Blum数有如下事实：*若n是Blum数， ，则在 中有且仅有a的一个二次方根称为主根(Principal Square Root)。例如 ，1，4，16的主根分别为1，16，4。*n是Blum数， ，则 3.2.1 Rab

41、in算法Rabin公钥密码系统的加解密算法如下 加密运算 解密运算 只要 不被分解，Rabin密码系统是计算安全的能够抵抗选择明文攻击。如果掌握n的素因子分解，即已知p, q, y, B, 由密文y经由如下步骤得到明文x。 令 ，3.2.1 Rabin算法*求 的解*求 的解*再求四个联立同余方程得到 的四个解。8逐个检验哪个是明文。可以通过在明文中引如冗余，以方便识别解密得到的明文。 注：因 ，A是p模二次剩余，有 ，故 。 ， 3.2.1 Rabin算法例如：n = 7*11 = 77是Blum数, B = 9, ( n, B )是公钥。首先计算出 ， , , .Rabin算法中 加密算法

42、解密算法 若明文 ，它的密文 3.2.1 Rabin算法解密过程如下：令 ， 。得出C是模7的二次剩余和模11的二次剩余 , 又 求出解下面四个同余方程组 3.2.1 Rabin算法分别得出 并代入 ,求出各自对应的明文 。令u是1模n的方根， 即密文 对应的明文为 。如果事先利用私钥p和q计算出1模n的方根 ，从而 , 和 是密文对应的四个明文。 3.2.1 Rabin算法这样我们只要解一个同余方程组，其中 ， 。解出z代入 得到明文x。四个明文分别是 ， ， 。上例中1模77的二次方根为 =（1，76，34，43）。从解出z并求出x= 24，四个明文分别为24，44，2和66。3.2 EI

43、Gamal公钥密码系统3.2.1离散对数问题 EIGamal公钥密码系统在众多协议中广泛应用。它的安全性是基于离散对数问题的困难性。离散对数问题： p是素数,是 的本原元素， 。求唯一的整数a， 使得 。记整数为 。 若小心选择p，对于离散对数问题尚没有多项式时间算法，故认为它是困难问题。为了抵抗已经知道的攻击，一般p至少150 bit，p-1应至少有大的素因子。 3.2.2 ElGamal公钥密码系统 P是素数,是 的本原元素, .整数a, 0ap-2使得 .其中p,是公开的,a是秘密的. 加密算法选择随机数 ，密文 ， 其中 , 解密算法 ElGamal公钥密码系统是非确定的，它的密文依赖

44、于明文与加密者所选择的随机数k。相同的密文加密得到的密文不一定相同。 是明文的x掩码 (masked)。 显然 。 为攻破ElGamal公钥密码系统直接的方法是计算离散对数。当 所有的因子都是小素数时可以采用PohligHellman算法。此外可以仿照因子分解算法引入因子库，先计算因子库中素数的离散对数，然后计算期望元素的离散对数，这就是目前最有效的指标计算方法。（应密106110页） EIGamal公钥密码系统可以在任何循环群上实现。选择群的标准是： 群中的运算容易实现，以保证有效性 在群中离散对数问题在计算上是困难的，以保证安全性 目前最受关注的是 、 和定义在有限域上的椭圆曲线的点所构成

45、的循环群。椭圆曲线群的特点是对同一个基域F上可以选择不同的椭圆曲线。这样，域的运算相同使用可采用相同芯片实现。3.2.3 椭圆曲线令素数p3, . 上的椭圆曲线E: 是满足同余方程 的解 ,和一个无穷远点O组成。这里 不成立.在椭圆曲线E上定义二元运算“+”。假设P,Q 是E上的两点， , P+O=O+P=P不难证明(E, +)为交换群，O为零元。对任何 ,例如： 上的椭圆曲线 。首先确定该曲线上的点 上有13个点O, (2,4), (2,7), (3,5), (3,6), (5,2), (5,9), (7,2), (7,9), (8,3), (8,8), (10,2),(10,9), 它对前

46、面定义的加法构成循环群，生成元为(2, 7)。下面计算= (2, 7) + (2, 7) , , ,所以 2= (5, 2) 同样可以算出一般，椭圆曲线上点数|E| 我们要找E的循环子群，在它上面离散对数是难解问题，所以需要研究E的结构。可以证明：在 上定义的椭圆曲线E，存在整数 使得 ，而且 ， 由此如果能计算出整数 ，我们就知道E有循环子群同构于 把它用到ElGamal公钥密码系统中。3.2.4 Menozes-Vanstone椭圆曲线密码系统 Menozes-Vanstone于1993年提出一个新版本的椭圆曲线密码系统。它只把椭圆曲线用在掩码上。 令E是 （素数 3）上的椭圆曲线，E的循

47、环子群H上的离散对数是难解问题。取 ， ，保存密钥a,公开椭圆曲线方程 、。 加密算法 明文 随机选取 , , , , 解密算法 利用自己的私钥a ,计算 上面有下划线的公式计算是在椭圆曲线上进行。例如 前例中取 ， ， ， ， 。 , 其中 , 利用私钥 计算 ，解同余方程 和 得出 。 3.3 Merkle-Hellman背包公钥密码系统 Merkle-Hellman背包公钥密码系统是Merkle和Hellman于1978年首次提出的。该密码系统和它的几个变形在80年代初已被攻破。但是它的设计思想仍然值得学习和借鉴。该系统的安全性是基于背包（子集和）问题的困难性。子集和问题 是正整数，问是

48、否有0-1向量 使得 子集和问题是判定问题，它只要回答“是”或“不 是”。它是NP-完全问题，不知道解它的多项式时间算法。注意：我们这里是一种搜索问题，即对于任何回答“是”的实例, 找到相应的向量。背包公钥加密算法利用一类称之为超递增背包问题的存在性。基本思想是构造一个超递增背包问题并伪装成普通的背包问题。解前者有快速算法，而解后者是一个非常困难的问题。 超递增背包序列是满足 的序列 超递增背包问题 可在O(n)时间容易地解决，其的算法的输入为T，超递增整数序列 ，如果有解则输出 。例如: 是超递增整数序列, 由上面算法求出 ，从而有 2 + 9 + 21 +215 + 450 + 946 = 1643背包公钥密码系统 令 是超递增整数序列，取素数 , , 其中 t是公开的，s,