密钥管理技术改.ppt

《密钥管理技术改.ppt》由会员分享，可在线阅读，更多相关《密钥管理技术改.ppt（64页珍藏版）》请在三一文库上搜索。

1、第3章 密钥管理技术,3.1 密钥的管理内容 3.2 密钥的分配技术 3.3 公钥密码 3.4 RSA算法 3.5 椭圆曲线密码体制,3.1 密钥的管理内容,密钥是加密算法中的可变部分，利用加密手段对大量数据的保护归结为对密钥的保护，而不是对算法或硬件的保护。密码体制可以公开， 密码设备可能丢失，但密码机仍可以使用。然而一旦密钥丢失或出错，不但合法用户不能获取信息，而且可能使非法用户窃取信息，因此，网络系统中密钥的保密和安全管理问题就成为首要的核心问题。,密钥管理是处理密钥自产生到最终销毁整个过程中的有关问题，包括密钥的设置、生成、分配、验证、 启用/停用、 替换、 更新、 保护、 存储、 备

2、份/恢复、丢失、销毁等等。密钥管理方法实质上因所使用的密码体制（对称密码体制和公钥密码体制）而异， 所有的这些工作都围绕一个宗旨，即确保使用中的密码是安全的。,1. 密钥设置协议 目前流行的密钥管理方案中一般采用层次的密钥设置，目的在于减少单个密钥的使用周期，增加系统的安全性。总体上密钥分两大类： 数据加密密钥(DK)和密钥加密密钥(KK)。前者直接对数据进行操作，后者用于保护密钥，使之通过加密而安全传递。,2. 密钥生成 算法的安全性依赖于密钥，密钥的产生首先必须考虑具体密码系统的公认的限制， 如果用一个弱的密钥生成方法，那么整个体制是弱的。因为能破译密钥生成算法，所以就不需要去破译加密算法

3、了。减少的密钥空间，易受到穷举攻击。如果采用姓名等的弱密钥选择也易受到穷举的字典攻击。因此， 好的密钥应该是随机密钥， 但为了便于记忆， 密钥不能选得过长，不能选完全随机的数串， 要选自己易记而别人难以猜中的密钥，要做到这些可采用密钥揉搓或碾碎技术。可见密钥的生成是困难的，特别对公钥密码体制来说，生成密钥更加困难，因为密钥必须满足某些数学特征（必须是素数的，是二次剩余的，等等）。,3. 密钥的分配 主要研究密码系统中密钥的发送、 验证等传送中的问题， 在3.2节中进一步介绍。,4. 密钥的保护 密钥从产生到终结的整个生存期中，都需要加强安全保护。 密钥决不能以明文的形式出现，所有密钥的完整性也

4、需要保护， 因为一个攻击者可能修改或替代密钥，从而危机机密性服务。 另外， 除了公钥密码系统中的公钥外，所有的密钥需要保密。 在实际中，存储密钥的最安全的方法是将其放在物理上安全的地方。当一个密钥无法用物理的办法进行安全保护时，密钥必须用其它的方法来保护，可通过机密性（例如，用另一个密钥加密）或完整性服务来保护。在网络安全中，用最后一种方法可导致密钥的层次分级保护。,5. 密钥的存储 密钥存储时必须保证密钥的机密性、认证性、完整性、防止泄露和修改。 最不复杂的的密钥存储问题是单用户的密钥存储，用户加密文件以备以后用。因为只涉及他一个人，且只有他一人对密钥负责。一些系统采用简单方法：密钥存放在用

5、户的脑子中， 而决不放在系统中，用户只需记住密钥，并在需要对文件加密或解密时输入。在某些系统中用户可直接输入64 bit密钥，或输入一个更长的字符串，系统自动通过密钥碾碎技术从这个字符串生成64 bit密钥。,其它解决方案有：将密钥储存在磁卡、ROM密钥卡或智能卡中，用户先将物理标记插入加密箱上或连在计算机终端上的特殊读入装置中， 然后把密钥输入到系统中。当用户使用这个密钥时，他并不知道它，也不能泄露它。使储存和保护它更加地直观。把密钥平分成两部分，一半存入终端, 一半存入ROM密钥使得这项技术更加安全。 美国政府的STU-III 保密电话就是用的这种方法。丢失了ROM密钥并不能使加密密钥受到

6、损害换掉它一切就正常如初。丢失终端密钥情况也如此。这样，两者之一被损害都不能损害整个密钥。,可采用类似于密钥加密密钥的方法对难以记忆的密钥进行加密保存。例如，一个RSA私钥可用DES(数据加密标准)密钥加密后存在磁盘上，要恢复密钥时，用户只需把DES密钥输入到解密程序中即可。如果密钥是确定性地产生的（使用密码上安全的伪随机序列发生器），每次需要时从一个容易记住的口令产生出密钥会更加简单。,6. 密钥的备份/恢复 密钥的备份是非常有意义的，在密钥主管发生意外的情况下， 以便恢复加密的信息，否则加密的信息就会永远地丢失了。 有几种方法可避免这种事情发生。最简单的方法称密钥托管方案，它要求所有雇员将

7、自己的密钥写下来交给公司的安全官， 由安全官将文件锁在某个地方的保险柜里（或用主密钥对它们进行加密）。 当发生意外情况时， 可向安全官索取密钥。,一个更好的方法是采用一种秘密共享协议，即将密钥分成若干片，然后，每个有关的人员各保管一部分，单独的任何一部分都不是密钥， 只有将所有的密钥片搜集全，才能重新把密钥恢复出来。,7. 密钥的泄露与撤销 密钥的安全是所有的协议、技术、算法安全的基本条件， 如果密钥丢失、被盗、出现在报纸上或以其它方式泄露，则所有的保密性都失去了，惟一补救的办法是及时更换新密钥。 如果对称密码体制泄露了密钥，必须更换密钥，并希望实际损失最小。如果是一个私钥，问题就大了，公钥或

8、许就在所有网络的服务器上。如果其他人得到了泄露的私钥，这个人就可以在网络上冒名顶替，读加密邮件、对信件签名、签合同等等。,私钥泄露的消息通过网络迅速蔓延是最致命的。任何公钥数据库必须立即声明一个特定私钥被泄露，以免怀疑有人用该泄露的密钥加密消息。 如果用户知道他的密钥是何时泄密的，并且KDC（密钥分配中心）正在管理密钥，用户应该通知KDC密钥已经泄露。 如果没有KDC， 就要通知所有可能接收到用户消息的人。 如果用户不知道他的密钥泄露的确切时间，问题就复杂了， 用户要求撕毁合同，因为偷密钥者可能冒名代替他签了其它合同， 这将引起争执而由法律、 公证机构裁决。,8. 密钥的有效期 没有哪个加密密

9、钥能无限期使用， 其原因如下： (1) 密钥使用时间越长，它泄露的机会就越大。人们会写下密钥，也会丢失，偶然事件也会发生的。 (2) 如果密钥已泄露，那么密钥使用越久，损失就越大。 如果密钥仅用于加密一个文件服务器上的单个预算文件，它的丢失仅意味着该文件的丢失。如果密钥用来加密文件服务器上所有预算信息，那么，损失就大得多。,(3) 密钥使用越久，人们花费精力破译它的诱惑力就越大甚至采用穷举攻击法。破译了两个军事单位使用一天的共享密钥， 就会使某人能阅读当天两个单位之间的通信信息。破译所有军事机构使用一年的共享密钥，就会使同样的人获取和伪造通行全球一年的信息。 (4) 对用同一密钥加密的多个密文

10、进行密码分析一般比较容易。,对任何密码应用，必须有一个密钥的有效期。不同密钥应有不同有效期，如电话就是把通话时间作为密钥有效期，当再次通话时就启用新的密钥。专用通信信道就不这么明显了，密钥应当有相对较短的有效期，这主要依赖数据的价值和给定时间里加密数据的数量。 密钥加密密钥无需频繁更换，因为它们只是偶尔地用作密钥交换，只是给密钥破译者提供了很少的密文分析，且相应的明文也没有特殊的形式。然而，如果密钥加密密钥泄露，那么其潜在损失将是巨大的，因为，所有的通信密钥都经其加密。在某些应用中，密钥加密密钥一般是一月或一年更换一次。,用来加密保存数据文件的加密密钥不能经常地变换。在人们重新使用文件前，文件

11、可以加密储藏在磁盘上数月或数年， 每天将它们解密， 再用新的密钥进行加密， 这无论如何都不能加强其安全性，这只是给破译者带来了更多的方便。一种解决方法是每个文件用惟一的密钥加密，然后再用密钥加密密钥把所有密钥加密，密钥加密密钥要么被记忆下来，要么被保存在一个安全地点，或在某个地方的保险柜中。当然，丢失该密钥意味着丢失了所有的文件加密密钥。,公开密钥密码应用中的私钥的有效期是根据应用的不同而变化的。用作数字签名和身份识别的私钥必须持续数年（甚至终身）， 用作抛掷硬币协议的私钥在协议完成之后就应该立即销毁。即使期望密钥的安全性持续终身，两年更换一次密钥也是要考虑的。许多网络中的私钥仅使用两年，此后

12、用户必须采用新的私钥。旧密钥仍需保密，以防用户需要验证以前的签名， 但是新密钥将用作新文件签名，以减少密码分析者所能攻击的签名文件数目。,9. 控制密钥使用 控制密钥使用是为了保证密钥按预定的方式使用，在一些应用中控制怎样使用密钥是有意义的，有的用户需要控制密钥或许仅仅是为了加密，有的或许是为了解密。可以赋予密钥的控制信息的有：密钥的主权人、密钥合法使用期限、 密钥识别符、 密钥预定的用途、密钥限定的算法、密钥预定使用的系统、密钥授权用户、 在密钥生成、 注册、证书有关的实体名字等。 运用这些限制的一个方案是在密钥后面附加一个控制向量（CV， Control Vector）用它来标定密钥的使用

13、和限制。对CV取单向Hash运算，然后与主密钥异或，把得到的结果作为密钥对密钥进行加密，再把合成的加密了的密钥跟CV存在一起。恢复密钥时，对CV取Hash运算再与主密钥异或，最后用结果进行解密。,10. 密钥的销毁 如果密钥必须定期替换，旧密钥就必须销毁。 旧密钥是有价值的，即使不再使用，有了它们，攻击者就能读到由它加密的一些旧消息。 密钥必须安全地销毁。如果密钥是写在纸上的那么必须切碎或烧掉； 如果密钥存在EEPROM硬件中，密钥就应进行多次重写；如果密钥存在EPROM或PROM硬件中，芯片就应被打碎成小碎片；如果密钥保存在计算机磁盘里，就应多次重写覆盖磁盘存储的实际位置或将磁盘切碎。,3.

14、2 密钥的分配技术,3.2.1 密钥分配实现的基本方法 1 基于对称加密算法的， 建立安全信道 要使通信的双方保密通信，他们就需要同一密钥，这种密钥可当面分发或通过可靠信使传递，传统的方法是通过邮政或通信员传送密钥。这种方法的安全性取决于信使的忠诚和素质， 该方法成本高，适用于高安全级密钥。为了既安全又减少费用， 可采用分层方式传送，通信员仅传送密钥加密密钥，而不去传送大量的数据加密密钥，这既减少了通信员的工作量，又克服了用一个密钥加密过多数据的问题。,对密钥分发问题的另一个方法是将密钥分成许多不同的部分， 然后用不同的并行信道发送出去，有的通过电话，有的通过邮寄等等。即使截获者能收集到密钥，

15、但缺少某一部分，他仍然不知道密钥是什么，所以该方法一般用于除个别特殊情况外的任何场合。 对称加密体制中对密钥分配还可以采用多级层次结构来实现， 即将密钥分成两类：初始密钥和密钥加密密钥。初始密钥用于保护数据， 密钥加密密钥用于保护初始密钥。初始密钥有时也被称做会话密钥，密钥加密密钥有时也被称做主密钥。用主密钥对会话密钥加密以后，可通过公用网传送，或用双钥密钥体制分配来实现，如果采用的加密系统足够安全，则可将其看成是一种安全通道。如ANSI X9.17标准中规定了该种密钥的分配方法。,2基于双钥体制的，利用数学上求逆的困难性，建立安全信道 Newman等在1986年提出的SEEK(Secure

16、Electronic Exchange of Keys)密钥分配体制系统，采用的是Diffie-Hellman和Hellman-Pohlig密码体制，这一方法已被用于美国Cylink公司的密码产品中，在小型网络中，每对用户可以很好地使用密钥加密密钥。 如果网络变大，每对用户必须交换密钥，n个人的网络总的交换次数为n（n-1）/2。1000人网络则需近500 000次，在这种情况下， 建造一个密钥管理中心进行密钥分配，会使操作更加有效。,3 基于量子密码建立安全信道 密码学的信息理论研究指出，通信双方A到B可通过先期精选、信息协调、保密增强等密码技术使A和B共享一定的密码信息。,3.2.2 密钥

17、分配实现的基本工具 认证技术和协议技术是分配密钥的基本工具，认证技术是安全分配密钥的保障，协议技术是实现认证必须遵守的流程。,3.2.3 密钥分配系统实现的基本模式 密钥分配系统实现的基本模式有两种,一种是对小型网络， 由于用户人数较少，每对用户之间可采用共享一个密钥的方法， 如图3.1所示。 图中k表示A和B之间共享的密钥。,图 3.1,另一种是在一个大型网络中，如由n个用户组成的系统中，希望相互之间保密通信，则需要生成n(n-1)/2 个密钥进行分配和存储， 这样密钥的分配问题就变得复杂，因此为了解决这一问题， 常采用密钥中心管理方式。在这种结构中，每个用户和密钥中心共享一个密钥，保密通信

18、的双方之间无共享密钥。 密钥中心机构有两种形式：密钥分配中心(KDC)和密钥传送中心(KTC)。在KDC中，当A向KDC请求发放与B通信用的密钥时，KDC生成一个密钥k传给A, 并通过A传给B，如图3.2(a)所示。 或者利用A和B与KDC共享密钥，由KDC直接传送给B，如图3.2(b)所示。,图 3.2,密钥传送中心(KTC)和密钥分配中心(KDC)十分相似，主要区别在于由通信方的一方产生需求的密钥，而不是由中心来产生。当A希望和B通信时，它产生密钥k并将密钥发送给KTC， KTC再通过A转送给B，如图3.3(a)所示，或直接送给B，如图3.3(b)所示。 利用A与B和KTC的共享密钥来实现

19、。,图 3.3,3.2.4 密钥的验证 在密钥分配过程中，需要对密钥进行验证，以确保准确无误地传送给指定的用户，防止伪装信使用假密钥套取信息，并防止密钥分配中的错误。当你收到密钥时，如何知道这是对方传送的而不是其他人传送的呢？如果是对方亲自递给你的，那自然简单；如果通过可靠的信使传送密钥，必须相信信使，并需要对密钥进行确认， 例如采用指纹法。而让信使传送加密密钥可能更安全。如果密钥由密钥加密，必须相信只有对方才拥有那个加密密钥；如果运用数字签名协议来给密钥签名，那么当验证签名时就必须相信公开密钥数据库；如果某个密钥分配中心（KDC）在对方的公钥上签名， 则必须相信KDC的公开密钥副本不曾被篡改

20、过。这些都需要对公开密钥认证。,如果被篡改，任何一个人都可以传送一个加密和签名的消息而将它伪装成来自对方，当你访问公开密钥数据库以验证对方的签名时， 却认为是正确的。利用该缺陷的一些人声称公钥密码体制是无用的，公钥体制对提高安全性一点用处也没有， 但实际情况却复杂得多。采用数字签名和可信赖KDC的公钥体制， 使得一个密钥代替另一个密钥变得非常困难。你可以通过电话核实对方的密钥，那样他可以听到你的声音。声音辨别是一个真正的好的鉴别方案。如果是一个秘密密钥，他就用一个单向Hash函数来核实密钥，AT&T、TSD就是用这种方法对密钥进行验证的。 有时，核实一个公开密钥到底属于谁并不重要，核实它是否属

21、于去年的同一个人或许是有必要的。如果某人送了一个签名提款的信息到银行，银行并不关心到底谁来提款，它仅关心是否与第一次来存款的人属同一个人。,3.3 公钥密码,公开密钥密码体制是现代密码学的最重要的发明和进展。 一般理解密码学(Cryptography)就是保护信息传递的机密性，但这仅仅是当今密码学主题的一个方面。对信息发送与接收人的真实身份的验证、对所发出/接收信息在事后的不可抵赖以及保障数据的完整性是现代密码学主题的另一方面。公开密钥密码体制对这两方面的问题都给出了出色的解答，并正在继续产生许多新的思想和方案。在公钥体制中，加密密钥不同于解密密钥，人们将加密密钥公诸于众，谁都可以使用；而解密

22、密钥只有解密人自己知道。 迄今为止的所有公钥密码体制中，RSA系统是最著名、使用最广泛的一种。,1976年提出公共密钥密码体制，其原理是加密密钥和解密密钥分离，这样，一个具体用户就可以将自己设计的加密密钥和算法公诸于众， 而只保密解密密钥。任何人利用这个加密密钥和算法向该用户发送的加密信息，该用户均可以将之还原。 公共密钥密码的优点是不需要经安全渠道传递密钥，大大简化了密钥管理。 它的算法有时也称为公开密钥算法或简称为公钥算法。,3.3.1 公钥密码体制的基本概念 1. 密钥对 在基于公钥体系的安全系统中，密钥是成对生成的，每对密钥由一个公钥和一个私钥组成。在实际应用中，私钥由拥有者自己保存，

23、 而公钥则需要公布于众。为了使基于公钥体系的业务（如电子商务等）能够广泛应用，一个基础性关键的问题就是公钥的分发与管理。公钥本身并没有什么标记，仅从公钥本身不能判别公钥的主人是谁。在很小的范围内，比如A和B这样的两人小集体，他们之间相互信任，交换公钥，在互联网上通信，没有什么问题。这个集体再稍大一点，也许彼此信任也不成问题， 但从法律角度讲这种信任也是有问题的，如再大一点， 信任问题就成了一个大问题。,2. 证书 互联网络的用户群决不是几个人互相信任的小集体，在这个用户群中，从法律角度讲用户彼此之间都不能轻易信任。所以公钥加密体系采取了另一个办法，将公钥和公钥的主人名字联系在一起，再请一个大家

24、都信得过有信誉的公正、权威机构确认，并加上这个权威机构的签名，这就形成了证书。由于证书上有权威机构的签字，因此大家都认为证书上的内容是可信任的；又由于证书上有主人的名字等身份信息， 别人就很容易地知道公钥的主人是谁。,3. 电子签证机关 前面提及的权威机构就是电子签证机关（即CA）。CA也拥有一个证书（内含公钥），当然，它也有自己的私钥，所以它有签字的能力。 网上的公众用户通过验证CA的签字从而信任CA，任何人都可以得到CA的证书（含公钥），用以验证它所签发的证书。如果用户想得到一份属于自己的证书，他应先向CA提出申请, 在CA判明申请者的身份后，便为他分配一个公钥， 并且CA将该公钥与申请者

25、的身份信息绑在一起，并为之签字后， 便形成证书发给那个用户（申请者）。,如果一个用户想鉴别另一个证书的真伪，他就用CA的公钥对那个证书上的签字进行验证（如前所述， CA签字实际上是经过CA私钥加密的信息，签字验证的过程还伴随使用CA公钥解密的过程），一旦验证通过，该证书就被认为是有效的。CA除了签发证书之外，它的另一个重要作用是证书和密钥的管理。 由此可见， 证书就是用户在网上的电子个人身份证， 同日常生活中使用的个人身份证作用一样。 CA相当于网上公安局，专门发放、验证身份证。,3.3.2 公钥密码体制的原理 单向函数 定义3-1可逆函数 令f是集A到集B的一个映射，如果对任意的x1x2，x

26、1, x2A，有y1y2, y1, y2B，则称f是从A到B的单射， 或一对一映射，或可逆的函数，记为y=f(x)。 定义3-2单向函数 一个可逆函数y=f(x), 如果满足以下两条就称为一个单向函数: 对于给定所有xA，能方便地计算出f(x); 对于给定的所有y，求x是困难的，以致于实际是做不到的。,例3.1 有限域GF(p)中的指数函数f(x)=bx，其中p是素数，即 y=f(x)=bx, xGF(p) 也就是x为满足0xp-1的整数。其逆运算是求离散对数，即 x=logbN 给定x求y是容易的，即是当p足够大时，如b=2, p=2100需做100次乘法，利用高速计算机可在0.1ms内完成

27、。但是从x=logbN中要计算x是非常困难的，如b=2, p=2100，所需计算量为1600年， 可见，当p很大时，有限域GF(p)中的指数函数f(x)=bx是一个单向函数。 , 用于构造公约密码常用的单向函数 ） 多项式求根 有限域GF(p)上的一个多项式 y=f(x)=(xn+an-1xn-1+a1x+a0) mod p 当给定多项式中的系数a和x, p以后，利用Honer算法，最多进行n次乘法，n-1次加法，就可求出y值。但已知多项式的系数a和y, p以后，要求x，就需要对高次方程求根，至少要进行不少于n2（lbp)2的整数次乘法, 当n, p很大时很难求解。,） 离散对数 如果p是一足

28、够大的素数，a是0, 1, 2, , p-1中与p互素的数。 则已知p, a, x, 计算y=f(x)-ax mod p并不困难; 若已知p, a, y, 计算x=logby mod p(称为离散对数问题)，就很困难了。如p=512, 则计算乘法次数为1077。,） 大整数分解(Factorrization Problme) 若已知两个大素数p, q，求n=pq仅需一次乘法，但已知n求p, q则是几千年来数论专家的一道难题。已知的各种算法有： 试除法、二次筛、数域筛、椭圆曲线, 其中RSA问题是FAC问题的特例。n是两个素数p, q之积，给定n以后求p, q的问题称为RSA问题。求n=pq分解

29、问题有以下几种形式： (1) 分解整数n为p, q; (2) 给定整数M, C，求d使得CdM mod n; (3) 给定整数k, C，求M使得MkC mod n; (4) 给定整数x, C，决定是否存在y使得xy2 mod m（二次剩余问题）。,） 菲-赫尔曼(Diffie-Hellman）问题 给定素数p，可构造一乘群Z*p，令为Z*p的生成元，若已知a, b，求ab问题为菲-赫尔曼问题。 ） 二次剩余问题 给定一个奇合数n和整数a，决定是a否为mod n平方剩余问题就称为二次剩余问题。, 公钥密码体制的原理 若用户A有一加密密钥ka, 有一解密密钥ka，可将加密密钥ka公开，而解密密钥k

30、a保密，若B要向A传送明文m，可查A的加密密钥ka，若用A的加密密钥ka加密的密文,则A收到密文c以后，用只有自己才知道的解密密钥ka对c进行解密得,由于加密密钥ka不同于解密密钥ka，因此公钥密码体制也称为非对称密码体制。若任何第三者窃得密文，但由于无解密密钥ka ，便无法恢复明文。 其加、解密码模型如图3.4(a)所示。 公钥密码体制的另一种模型是认证模型， 用于数据起源的认证， 以确保信息的完整性。在这种情况下，任何人都可以获得解密密钥，解读信息，但只有具有相应加密密钥的人才能产生该信息，其模型如图3.4(b)所示。,图 3.4 (a) 加解密模型； (b) 认证模型,3.4 RSA 算

31、 法,公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的。但目前最流行的RSA是1977年由MIT Ronald L.Rivest,Adi Shamir和Leonard M.Adleman三名数学家共同开发的, RSA分别取自三名数学家的名字的第一个字母。 RSA的基础是数论的欧拉定理， 它完全依赖于大数的因子分解的困难性。,欧拉定理 若整数a和m互素，则,a(m)1 mod m,其中, (m)是比m小，且与m互素的正整数个数。,3.4.1 RSA算法描述 1. RSA密钥的产生 (1) 选择两个大素数p#, q（保密）。 (2) 计

32、算n=pq(p, q分别为两个互异的大素数，n的长度大于512 bit，这主要是因为RSA算法的安全性依赖于因子分解大数问题)。 欧拉函数 (n)=(p-1)(q-1) (3) 随机选择加密密钥e，要求e和(n)互质。 (4) 利用Euclid算法计算解密密钥d, 满足de1 mod(n)。 其中n和d也要互素。数e和n是公钥，d是私钥。两个素数p, q不再需要，应该丢弃，不要让任何人知道。,2. 加密 (1) 加密信息m（二进制表示）时， 首先把m分成等长数据块m1、m2、mi块长s，其中2sn，s要尽可能的大。 (2) 对应的密文是： cimei mod n。,3. 解密 解密时计算：,例

33、3.2,p=43, q=59, n=pq=4359=2539 (n)=4258=2436, e=13,解方程de=1 mod 2436 2436=13187+5 13=52+3 5=3+2 3=2+1 1=3-2， 2=5-3， 3=13-25 5=2436-13187 1=3-2=3-(5-3)=23-5 =2(13-25)-5 =213-55 =213-5(2436-13187) =93713-52436,即 937131 mod 2436 取 e=13, d=937,若取明文public key encryptions，先将明文按两个一组进行分块，再将明文数字化，如按英文字母表的顺序得：

34、 pu=1520, bl=0111, ic=0802, ke=1004, ye=2404, nc=1302, ry=1724, pt=1519, io=0814, ns=1418。 利用加密得到密文：pu=0095, bl=1648, ic=1410, ke=1299, ye=1365, nc=1379, ry=2333, pt=2332, io=1751, ns=1289。,3.4.2 RSA算法中的计算问题 RSA算法中首先遇到的问题就是如何选取大的素数， 数百年来，人们对素数的研究一直感兴趣，那么，是否有一个简单的公式可以产生素数？答案是否定的。 有人曾猜想若n|2n-2，则n为素数。n

35、=3,3|23-2，n341时是正确的，但n=341时，猜想是错误的。,有人曾猜想若p为素数，则Mp=2p-1为素数, 但M11, M67, M257不是素数, 猜想错误。如果p为素数，Mp也为素数，则称Mp为Mersenne数。Fermat推测Fn=22n+1为素数, n为正整数, 但n=5时是错误的。 人们感兴趣的另一个问题是素数的个数到底有多少？答案是有无穷多。素数在数轴上的分布情况是 ,如x=10, (x)=4, 该式所含的素数为2、3、5、7。,64 bit大的素数中有素数的个数为2.051017; 128bit大的素数中有素数的个数为1.91036; 256 bit大的素数中有素数

36、的个数为3.251074。 可见素数的个数相当多。到底如何产生一个素数呢？常用的方法有概率测试素数法， 确定性验证素数法。,1. 概率测试素数法 概率测试素数法有Solovay-Strassen测试法、Lehman测试法、 Miller-Rabin测试法。它们都是利用数论理论构造一种算法，对于一个给定的大正整数，进行一次测试，使素数的概率为1/2， 若进行了r次测试，则第n步使素数的概率为=2-r，n为素数的概率为1-，若r足够大(如r=100)，则几乎认为n是素数。 若概率测试法得到的准素数是合数（出现的概率很小）， 则不会造成太大的问题，因为在采用RSA体制加解密时，就会出现异常。,2确定

37、性验证素数法 确定性验证素数法是RSA体制实用化研究的基础问题之一。 定理3-1 令pi+1=hipi+1，若满足下述条件，则pi+1必为素数。 (1) pi是奇素数; (2) hi4(pi+1), hi为偶数; (3) (4) 。 利用此定理可由16 bit素数p0推导出32 bit素数p1，再由素数p1可推导出64 bit素数等，以此类推。,1) 关于安全素数及其获得 幂剩余函数具有特殊的周期性，反复运算M=Ce mod n若干次后，将还原为最初的M。例如, p=17, q=11, n=pq=187, e=7, m=123。可以验证，m经过4次RSA连续变换，可得m4=m。,m1=123,

38、 1237183 mod 187 m2=183, 183+772 mod 187 m3=72, 72+730 mod 187 m4=30, 30+7123 mod 187,早期的RSA算法就曾被人用这种方法破译，所以在生成密钥时，应采用“安全素数”。所谓安全素数p，应满足： (1) p是一个位数足够大的随机素数; (2) p-1含有一个大的素数因子r; (3) p+1含有一个大的素数因子; (4) r-1含有一个大的素数因子t。,2) 安全素数的获得 (1) 选择两个指定长度的奇数a, b。 (2) 在a附近产生随机素数s，在b附近产生随机素数t。 (3) 由t产生素数r： r=1+2t; 若

39、r非素数，则r=r+2直到r是素数。 (4) 由r, s生成p: p=(sr-1-rs-1) mod (rs); 若p为偶数, 则p=p+rs; p=p+2rs直到p为素数。,3) 高次幂的求模算法C=Me mod p RSA加、解密变换都要进行高次幂的求模运算。求C=Memodp可通过对指数e的二进制化来实现。例如, 求117 mod 17， 7=(111)2即7=22+21+20 117mod 17=(11) 2211211mod 17 具体步骤如下：将e用二进制表示, e=kl, kl-1, , k0, ki0, 1, 0il c=1 For i=10 C=C2 mod p 若ki=1，则C=C(M modp)。,