第十二讲密码执行上课件.ppt

1、第十二讲 密码执行(上)在某个特定代数结构上的密码方案的执行效率主要由以下几个因素决定：参数尺寸，时间与存储平衡，可以获得的处理能力，以及使用的数学算法。这一讲和下一讲主要讨论潜在用于密码方案中代数结构上关键计算的有效算法。这里介绍的算法因为是实现密码系统的关键技术，所以在各种文献中有广泛研讨。虽然有些文献也试图指出各种算法的优势所在，但是通常并没有给出系统的比较。本讲提要 q 素数问题 q 模幂1 素数问题 对密码系统的攻击。应用时不受到相关的针其在定的附加性质，以使得素数还应该满足某些特然，化搜索素数的策略。当可能通过这个概率来优者不率非常小，以使得攻击某一特定形式素数的概择为且足够随机，

2、也就是选下，素数必须足够大并。在这种情况形成模和找到两个素数是为相关参数。另一个例子域上的离散对数并找到来定义有限要找到一个素数要问题。一个例子是需的首数是实现公钥密码系统有效的产生公开密钥参qpnqppRSA1.1 Miller-Rabin 测试。对素数一个强伪证据的被称为的一个强伪素数。整数被称为对基则，或对于某个否则，也就是，如果。对合数的一个强证据被称为则，并且对于全部如果的整数。，一个在区间是是奇数。令，这里为一个奇合数并且令令。有对于某个或则有。，为一个整数满足令是一个奇数。，这里为一个奇素数，并且令令)()(mod 1 1 0)(mod 1(2)()(mod 11 0 )(mod

3、 1(1)11 21 )(mod 1 1 0)(mod 1 1 )(21 222naannasjnananasjnanarrnnnasjnanaarr nnrrrrsrrsjjj 定义1定义1事实1事实1 1.1 Miller-Rabin测试(续)。素数。合数，则如果。合数则，如果。计算：。则做如下步骤：并且如果。计算。，选择一个随机整数：是一个奇数。满足写。合数或素数的答案是素数否输出：一个对于问题。和一个安全参数一个奇整数输入：测试)(Return (3)(return 1 (2.3.3)(return 1 (2.3.2.2)(mod (2.3.2.1)following thedo 1

4、and 1 le Whi(2.3.2)1 (2.3.1)1 1 (2.3)(mod (2.2)22 (2.1)following thedo to1 from For (2)2 =1 (1)?1 3),(RABIN-MILLER)Rabin-(Miller2yy=nyyysjjyynaynaatirrnntntnrs 算算法法1 11.1 Miller-Rabin测试(续)。而，这是因为有是合数并且可以分解，则是合数。如果。其它情况意味着是素数，同余。因此，如果模与小定理素数根据是的平方根，如果。这是，则计算了。如果我们到达在之前的步骤已经结束前一种情况，算法应该的一个非平凡因子。给出，是合数

5、。后一种情况并且，或者。由此这意味着。步执行后的值。假定步的在第表示我们用)(mod1)(mod1)(mod1)(mod11Fermat)(mod)1()(mod1)(mod1)(mod1)(mod1(2.3)222211112/)1(112222223nynynnnynnynnananayynnynnynynynyjyyssssnnnssj .测试测试Rabin Rabin-证明Miller证明Miller1.1 Miller-Rabin测试(续)数。的素数为基时是强伪素全部小于个十进制的数对道有一个时是强伪素数。我们知为基对全部，都存在无穷多个整数基的集合限个是已经证明对于任何有伪素数的数

6、量很少，但的强伪素数。虽然强对基为，共有到2003372329110 (1)10BbB 评述.评述.1.1 Miller-Rabin测试(续)的素性测试方法。测试是非常有效。因此，有最多只数认定为素数的可能性我们可以认为将一个合，则。如果能性至多为的情况下发生误判的可测试在随机选择基我们已经知道使用续Rabin-Miller10(1/4)101/4Rabin-Miller(2)610ta)(评述.评述.1.1 Miller-Rabin测试(续)2561)561(mod1256133561)1(561)561(mod1)561(mod1 )561(mod67 )561(mod166 )561(m

7、od2632 2 35 2235165601 561 560232232122013504的伪素数。是对基，而，由于的一个非平凡因子。然为，是一个合数。进一步，我们得出由于。则令。和，因此，则。令yyyyyyyyyarnns例子1例子11.1 Miller-Rabin测试(续)的速度不相同。序列同余于的原因是各个素数模的分解。我们可以用这种方法，但没有和了因子包含，因此，的情况下同余和模是仅在模由于。，。我们可以计算由于承接156117 11 3 11113)17(mod1 )11(mod1 )3(mod1 )561(mod1)17(mod1 )11(mod1 )3(mod1 )561(mod

8、67)17(mod4 )11(mod1 )3(mod1 )561(mod166)17(mod8)11(mod1 )3(mod1 )561(mod263 17113561)(223210yyyyyyn例子1例子1例子2例子2 1.1 Miller-Rabin测试(续)。，之后同时为和到达测试，也就是序列同时可以通过。仅有一种情况。因此，可以分解和况下，我们就有不同的情况。在这种情的速度之后为到达和出现序列。有可能的情况并且假定考虑1)(mod1)(mod1Rabin-Miller)(mod1)(mod111)(mod)(mod)(mod111111qypynnqypyqypynaqpniiiii

9、in例子2的评述.例子2的评述.1.2 素数产生 素数产生不同于前面的素性测试，但是通常与后者密切相关。前者允许被测试整数有固定的一些方式构造，这将有可能比随机选择测试整数更有效率。1.2.1 随机搜索可能的素数是素数。判定，直到是一个适当的安全参数，这里，输入比特整数奇意选择一个比特素数的策略，即任找到随机的的。这告诉我们一个合理是大约的奇整数中素数的比率例如，所有小于。大约是的奇整数中素数的比率偶数，小于的正整数中一半是。由于小于比率大约是的正整数中素数的小于根据素数分布理论，在ntnttnnkkxxxxx)(RABIN-MILLER)()(RABIN-MILLER1/177 ln(2)2

10、/(51222/ln 1/ln 512算法1算法11.2.1 随机搜索可能的素数(续)步。否则，转到第则输出素数，如果步。，则转到第奇素数整除。如果可以的某个是否可以被小于使用直接除方法判断。比特的奇整数随机产生一个比特概率素数。一个随机的输出：。和一个安全参数输入：一个整数，测试使用(1)(return)()(RABIN-MILLER(3)(1)(2)(1)(SEARCH-RANDOM)Rabin-Miller(ntnBnnkktktk算法1算法1算法2算法2 1.2.1 随机搜索可能的素数(续)试之前就已经被淘汰。测销比较大的的合数将在进入相对开，也就是，可以通过除法测试阶段的奇数则只有，

11、。例如，如果除法测试的奇数大约为理论，可以通过。根据的所有素数除以小于要用的小因子，这实际只需界否含有小于预先定义的测试其是测试前，先对随机整数在应用占相对大的比例，随机整数由于包含小素数因子的Rabin-Miller80%20%256=ln1.12/MertensRabin-Miller)1(nBB nBBnn 解释.解释.1.2.1 随机搜索可能的素数(续)。有于全部上的一个奇整数，则对，是来自于区间如果。一个具体的结论是：的概率是返回为一个合数，我们可以定义分重要。而实际是合数的概率十通过因此，估计是一个概率素数。返回的数的数一定为素数，通过明通过测试测试并没有给出数学证由于，ttktk

12、pxxnptknn1/4)(10 3 )SEARCH(-RANDOMRabin-Miller)2()续(60算法2算法2算法2算法2 解释.解释.1.2.1 随机搜索可能的素数(续)改进。的上界可以得到进一步使用更为先进的技术，续tkp,)(2(。表示的表中的条目和的上界如上表。对应于，和对于取值 jt kt k/pj tkptk)21(,1.2.2 强素数。有一个大素数因子，为并且；有一个大素数因子，为；有一个大素数因子，为满足如下条件：，和，存在整数被称为是强素数，如果一个素数trsprptsrp 1(3)1 (2)1(1)1.2.2 强素数(续)。将这个素数定为，中发现第一个素数。，在序

13、列。选择一个整数。计算。将这个素数定为，中发现第一个素数。，。在序列选择一个整数。和基本相等的大素数随机产生两个比特规模。产生一个强素数的产生强素数算法)(Return (5)2 .2 1 2 (4)1)(mod(2 (3)12.2 1 12(2)(1)(Gordon000000200000psrjppjjjjsrjpjsrsptiriiiitii tspr摘要：摘要：算法3算法3 1.2.2 强素数(续)。的比特长度将略微小于的一半，而是的比特长度和的比特长度。注意确控制输出素数，可以准，的尺寸和参数，通过仔细选择素数素数。法执行输出是一个概率算试，测试是一个概率素性测于。由的全体素数做除法

14、测试以对其先用小于某个界素性测试，当然也可步中对每个可能的数的和可以用来完成第测试概率素数。来产生一个可以使用和步中，素数在第rtpsrpjitsBts (2)GordonRabin-Miller(4)(2)(Rabin-Miller(1)(1)00算法1算法1算法2算法2 解释.解释.1.2.3 产生DSA素数。并且；对于某个，这里比特的素数；是一个也就是，；三个条件：满足如下和素数数字签名算法需要两个)1(|(3)80 64512=22 (2)160 2 2 (1)NIST1160159pqll+LpqqqpLL1.2.3 产生DSA素数(续)是一个概率素数。直到发现。的素性，这里测试，使

15、用特的奇整数。比是一个注意。形成置的最高比特和最低比特将。计算。，它的比特长度为无需保密选择一个随机种子重复如下步骤：。这里，满足和使用长除法，得到对。计算。，并且，这里比特的素数和一个比特的素数一个输出：，输入：整数素数的方法产生qtqtqqqUsHsHUgsbn+bLbnLl+Lpql LpLqllg 18)(RABIN-MILLER(2.4)160(1(2.3)2 mod 1)()(2.2)160)(2.1)(2)160 0 1601 )1(64512(1)1(|64512 160 8 0 DSANIST 算算法法4 41.2.3 产生DSA素数(续)步。转移到第。，置。，是一个概率素数

16、，则如果。的素性，这里测试，使用则做如下步骤：，如果。注意。并置计算。比特整数。是一个。令定义如下，对于整数。置：。，置续(2)(5)1 1 (4.5)(return 5)(RABIN-MILLER 2 (4.4)2 (mod 1()1()2mod(4.3)2)2mod(222 )(2 (4.2)2 (mod)(following thedo to0 from For (4.1)following thedo 4096 While(4)2 0(3)(1160)1(16013202160101njjiipqptptppqpcXpq Xc VV V V VW LXWXWkjsHVnkijiLnbn

17、nnLgk 算算法法4 41.2.3 产生DSA素数(续)密密钥。个实体的秘，以利于其之后恢复每和的弱的系统参数于用阻止信任中心故意产生的产生。这一特征可以和方法核实同样的公开，任何人可以使用和计数器生的可能。如果种子子来控制素数产这就排除了通过控制种视为真实的随机种子。，这一过程的输出被步和第预测和控制的随机过程可输入，但经过了一个不不是产生素数的算法的随机种子值。比特的串影射成长度的二进制比特函数，它将小于代表pqpqissHDSA)(4.1)(2.2)(2)hash1602hash 1-SHA (1)64 解释.解释.1.2.3 产生DSA素数(续)测试。试，之后再进行的所有奇素数的除法

18、测个界可以先使用小于某和数为了改善效率，候选素。的输出是一个概率素数测试是一个概率测试，。由于步和步。这要求第素数的概率最多不超过数为，素性测试判定一个合强的素性测试，也就是用步使和第的原始描述文献仅要求续Rabin-Miller (4)Rabin-Miller 5(4.4)18(2.4)(1/2)(4.4)(2.4)186 FIPS(3)(80Bpqtt算算法法4 4 解解释释.2 模幂 情况是综合两者。的乘法次数。最理想的法是减少计算模幂需要的时间；另一种方结构上两个元的乘法一种是减少在某个代数减少计算模幂的时间。模幂。通常有两种方法的算术操作之一就是公钥密码系统的最重要eg ElGama

19、l (3)RSA (2)(1)类算法。加密签名都可以使用这任意选择。可以固定而指数数固定底数模幂算法。底类算法。加密签名都可以使用这任意选择。可以固定而底数数固定指数模幂算法。指的情况。与指数意选择底数基本模幂技术。可以任幂算法。我们考虑三种类型的模eggeeg2.1 问题模型2.1.1 加法链为底数。表示以这里，很大时，有的确切值。当情况下相对较小们仅知道在的最短加法链长度。我为令。，计算：的方法：个快速计算的最短加法链给出了一。，使得，和，存在某个对于每一个；，满足，序列的加法链是一个正整数2loglog log log(1)(1)log()()()(2)(1)1 1 (2)1(1)132

20、121 eeoeeleeleeelgggggeuuuikjkjile uuuuuelluuuuekjill解释.解释.定义2定义22.1.2加-减法链对数密码系统。限域离散用于椭圆曲线密码和有加减法链可以有效的应。，链，我们可以得到更短的但是如果允许使用减法，的最短加法链是举例来说，如，减法。方法是允许其它操作，一种缩短加法链长度的解释。，使得，和，存在某个对于每一个；，满足，数序列的加减法链是一个正整(2)31 32 16 8 4 2 131 21 11 10 5 3 2 131 (1)1 1 (2)1(1)121.kjilluuuikjkjile uuuuue定义3定义32.1.3 加法序

21、列和向量加法链。，这里，是，的最短加法序列长度，证明了。，就是，算一组乘幂的情况，也加法序列可以应用于计。，它包含了，链的加法序列是一个加法，max log log log)1(log)()(Yao(2)(1)2121212121212121tttteeetlteeeeeeoteeeeleeeleeegggeeeuuueeet 解释.解释.定义4定义42.1.3 加法序列和向量加法链(续)。是，算多乘幂的情形，也就向量加法链可以用来计。，使得，和，存在某个对于每一个；，满足，是一个向量序列，一个向量加法链teteekjiltltgggDDDikjkjtilDDDDDDDDeeeD2121110

22、1021(1)0 (2)1 0 0 0 1 0 0 0 1 (1)解释.解释.定义5定义52.1.3 加法序列和向量加法链(续)全问题。完法序列问题是等人证明了寻找最短加。，就是，法序列的问题等价，也量的问题与寻找最短加证明了寻找最短加法向的最短加法向量。，是，令续NPDowney)3()1()()(Olivos )(2)(21212121teeeleeeleeeeeeltttt 解释.解释.2.2 一般模幂技术2.2.1 二进制方法。则，如果。则，如果：。输出：。和一个正整数输入：从左向右二进制模幂)Return(3)1 (2.2)(2.1)following thedo 0 down to

23、 from For (2)1(1)(2011AgAAeAAAtit iAge eeeeGgiett算法5算法5)(100011011 283 8 2283。和。注意计算tg2.2.1 二进制方法(续)。平均：，最小：，最大：因此，乘的总数量为：。我们有。进制表示中的数量在二重量的是，这里：步第乘数。的二进制比特扩张的位是，这里：步第平方1/22/31)/2(1 1 12 1)(1)(1)(1Hamming)()()(2.2)(1)(2.1)(ttttttttteHeeHeHett效效率率.2.2.1 二进制方法(续)2.2.1 二进制方法(续)。则，如果。则，如果。，。输出：。和一个正整数输入

24、：从右到左二进制模幂算法)Return(3)(2.2)1 (2.1):following thedo to0 from For (2)1(1)(2011ASSStiSAAet igSAge eeeeGgiett6 。计算283g2.2.1 二进制方法(续)。平均：，最小：，最大：因此，乘的总数量为：。我们有。：步第乘。：步第平方1/22/31)/2(1 1 12 1)(1)(1)()(2.1)()(2.2)(ttttttttteHeHt效率.效率.2.2.1 二进制方法(续)。的乘法效率可能高于任意的计算乘法，。对于特定选择的某些为任意值代替乘法为固定值则是用乘法模幂的从左向右二进制。时计算乘法仅当定。要由计算平方的时间限的总体运行时间主，则个乘法和平方处理单元供一可以并行。假定可以提一个循环中的两个操作相互独立的，因此，计算过程中平方和乘是在。注意器存储中需要一个额外的寄存在SASgAgSSAggASAeSi 算算法法5 5算算法法6 6算算法法6 6算算法法6 6算算法法6 6评评述述.)()(1(2)(1)2.2.1 二进制方法(续)谢谢!