复旦大学：《信息安全原理》课程教学资源（PPT课件）第3章 现代加密算法（3/4）

3.RSA的实现 ■RSA的硬件实现,其最快速度也是DES 的1/1000,512bt的RSA大约为1MBs, 软件实现的速度只有DES的软件实现的 1/100,因此在速度上RSA是无法与对称 密码体制相比的。 ■目前RSA体制主要用在密钥交换和认证 ■512bit的RSA软件实现可达20KB/s。 ■如果选e=65537时,运算速度可大大加快, 这是因为65537的二进制表示中只有两个 可极大地减少运算量 23:31:48

23:31:48  3. RSA的实现  RSA的硬件实现，其最快速度也是DES 的1/1000，512bit的RSA大约为1MB/s， 软件实现的速度只有DES的软件实现的 1/100，因此在速度上RSA是无法与对称 密码体制相比的。  目前RSA体制主要用在密钥交换和认证  512bit的RSA软件实现可达20KB/s。  如果选e=65537时，运算速度可大大加快， 这是因为65537的二进制表示中只有两个 1，可极大地减少运算量

1)素性检测 ■在RSA的具体实现时,首先要求两个大素数。 会不会因为用户的增加而导致会有两个人选择了同样的素 数呢?素数是否会被因为更换而用完? 素数定理:不超过N的素数大约有N/mN个 以1024bi来看,它作为两个长度接近512b的素数乘积被 产生。大约有2512/512个这样的素数,即大约有t=10151个 每对素数形成一个模,则有C(10151,2)=1030个不同的模 而对于给定的模,又可以有许多密钥对可选。1030个模的 概念是,如果给地球上每个人每天10个新模,则可持续(按 70亿=7×109人口算,103002.6×1013)3.84×1023年 若要求素数长度在512bi则上述数据为2512/512 2511511=251(2/512-1/511)=2511×0.0019=2502,故在此要求下 给地球上每个人每天10个新模,也可持续3×10284年 因此不必担心两个人选择同样素数的情况发生,和素数被 用完的情况。 23:31:48

23:31:48  1)素性检测  在RSA的具体实现时，首先要求两个大素数。  会不会因为用户的增加而导致会有两个人选择了同样的素 数呢？素数是否会被因为更换而用完？  素数定理：不超过N的素数大约有N/lnN个，  以1024bit来看，它作为两个长度接近512bit的素数乘积被 产生。大约有2512/512个这样的素数，即大约有t=10151个， 每对素数形成一个模，则有C(10151, 2)=10300个不同的模， 而对于给定的模，又可以有许多密钥对可选。 10300个模的 概念是，如果给地球上每个人每天10个新模，则可持续(按 70亿=7×109人口算，10300/2.6×1013)3.84×10287年.  若要求素数长度在 512bit 则上述数据为 2512/512 － 2511/511=2511(2/512-1/511)= 2511×0.0019=2502,故在此要求下 给地球上每个人每天10个新模，也可持续3×10284年  因此不必担心两个人选择同样素数的情况发生，和素数被 用完的情况

能切实可行地产生大素数 ■根据素数定理,如果随机选择一个整数p, 则p是素数的概率是(p/np)/p=1/np 若要求512bit的素数,则有1/mp≈/354, 若规定是随机选择奇整数,则概率为 1/177。 ■适当长度的177个随机奇整数中有一个是 素数。 ■因此产生大素数是确实可行的。 ■检测素数的方法有概率测试法。 23:31:48

23:31:48  能切实可行地产生大素数？  根据素数定理，如果随机选择一个整数p， 则p是素数的概率是(p/lnp)/p=1/lnp。  若要求512bit的素数，则有1/lnp1/354， 若规定是随机选择奇整数，则概率为 1/177。  适当长度的177个随机奇整数中有一个是 素数。  因此产生大素数是确实可行的。  检测素数的方法有概率测试法

概率测试法就是对给定的大整数进行检验,每 次都输出一个结果Yes或No。 种是输出Yes表示该数是素数的概率为0.5 输出No则表示该数肯定不是素数。 ■若N通过了r次检验(即输出都是Yes),则它不 是素数的概率将为2r,当r足够大时,几乎可认 为N是素数。 Solovay- Strassen检验法和Mer- Rabin检验法 都是利用这一原理构造的。 另一种是输出Yes表示该数肯定是素数,输出 No则表示该数不是素数概率为0.5,由于按此 方法得到的数一定是素数,故也称这类方法为 确定性检验法。 23:31:48

23:31:48  概率测试法就是对给定的大整数进行检验，每 次都输出一个结果Yes或No。  一种是输出Yes表示该数是素数的概率为0.5， 输出No则表示该数肯定不是素数。  若N通过了r次检验(即输出都是Yes)，则它不 是素数的概率将为2-r,当r足够大时，几乎可认 为N是素数。  Solovay-Strassen检验法和Miller-Rabin检验法 都是利用这一原理构造的。  另一种是输出Yes表示该数肯定是素数，输出 No则表示该数不是素数概率为0.5，由于按此 方法得到的数一定是素数，故也称这类方法为 确定性检验法

a Solovay-strassen检验法的方法是如果要检验 m是否为素数,则在{1,2m-1}中随机取n, 并验证(n,m)是否等于1,和 Jacob符号J(m,n) 是否等于nm1/2modm。 这里J(m,n)=nn (m=p,,.p) p1八P2)(Pr n「1n是p的平方剩余 {-1n是P的非平方剩余 所谓平方剩余问题就是指,对于给定的一个奇数 n和整数a,决定a是否为模n的平方剩余,即判 定x2= a mod n是否有解,若有解,则a是modn的 平方剩余,否则a是模n的非平方剩余。 23:31:48

23:31:48  Solovay-Strassen检验法的方法是,如果要检验 m是否为素数，则在{1,2,…m-1}中随机取n， 并验证(n,m)是否等于1，和Jacobi符号J(m,n) 是否等于n(m-1)/2mod m。  这里J(m,n)= (m=p1p2…pr)      prn pn pn  1 2    是 的非平方剩余 是 的平方剩余 ii i n p n p pn 1 1 所谓平方剩余问题就是指，对于给定的一个奇数 n和整数a，决定a是否为模n的平方剩余，即判 定x2=a mod n是否有解，若有解，则a是mod n的 平方剩余，否则a是模n的非平方剩余

若m为素数,则有(m,m)=1且J(m,n 1)2modm。 若m不是素数,则等式J(m,n)=nm1modm 可能成立可能不成立。 有结论:对于奇合数,至多有一半使等式成 立,即至多有0.5的概率使上述等式成立。 若随机选择100个整数进行检验,上式均成立, 则m不是素数的概率小于21001030,因此可 认为m是素数。 23:31:48

23:31:48  若m为素数，则有(n,m)=1且J(m,n)= n(m- 1)/2mod m。  若m不是素数，则等式J(m,n)=n(m-1)/2mod m 可能成立可能不成立。  有结论：对于奇合数，至多有一半使等式成 立，即至多有0.5 的概率使上述等式成立。  若随机选择100个整数进行检验，上式均成立， 则m不是素数的概率小于2-100=10-30，因此可 认为m是素数

(1)如果n是奇数,m1=m2modn,则|m|="2|。 (2)如果n是奇数,则 1若n≡±1mod8 n(-1若n≡+3mo8 2如果n是奇数,则《)(mm) 特别当m2+t(t.奇数),则m 若m≡n≡3mod4 如果m和n是奇数,则(⑦) 否则 应用上述4个特性,可以在多项式时间内计算 Jacobi符 号 23:31:48

23:31:48  计算n(m-1)/2mod m有多项式时间算法， 那么怎么计算J(m,n)?  不能根据Jacobi符号的定义来计算，  因为只有在知道m的分解后才能计算， 而知道m的分解当然就知道m是否为素 数了  可以利用数论中的结果在不分解m的前 提下计算Jacobi符号。主要利用四条性 质： (1)如果 n 是奇数， m 1 = m 2 mod n，则       nm nm1 2 。 (2)如果 n 是奇数，则         1 3mod8 2 1 1mod8 nn n 若若 (3)如果 n 是奇数，则       nm nm n m1m2 1 2 。 特别当 m=2kt(t 为奇数)，则        nt n n m k 2 (4)如果 m 和 n 是奇数，则              否则若 m n m n m n n m 3mod4 应用上述 4 个特性，可以在多项式时间内计算 Jacobi 符 号

Miller-rabin检验法也是一个多项式时间算法, 它比 Solovay- Strassen检验法快,执行一次的 错误概率最多为1/4 ■对于奇整数n的 Miller-Rabin素性测试算法如 下 (1)令n-1=2km,m是奇数; ■(2)对i=1 to t do ①选择随机整数a(2≤a≤n-2); ②计算b= ammon; ③Ifb=modn, then n是素数and返回,else ④ If j=k then n是合数,算法终止 oIfb=1modn, then n是素数and返回, else计算b=b2modm,j=j计1,goto④ 23:31:48

23:31:48  Miller-Rabin检验法也是一个多项式时间算法， 它比Solovay-Strassen检验法快，执行一次的 错误概率最多为1/4 。  对于奇整数 n 的Miller-Rabin素性测试算法如 下：  (1) 令n-1=2 k m，m是奇数；  (2) 对i=1 to t do  ①选择随机整数a(2  a n-2)；  ②计算 b  a mmodn;  ③If b 1modn，then n是素数 and 返回,else 令j=1  ④If j=k then n是合数，算法终止  ⑤If b -1modn, then n是素数 and 返回，  else 计算 b  b 2modn, j=j+1,goto ④

确定性检验法是通过对给定的大整数进 行检验,下面介绍一种确定性检验法 ■采用了基于 Pocklington定理的特殊情形, 并将其改造为一递归算法加以实现 ■定理的特殊情形的描述: 定理:设n=2RF+1,其中F的真分解为 F=,如果存在整数a满足:anl=1modn 且(am)q-1,n)=1(j=1,…,r), 那么n的每一个素因子p具有p=mF+1的形式,其中 m21。更进一步,如果F>v或者F为奇数且F>R,那 么n是素数。 23:31:48

23:31:48  确定性检验法是通过对给定的大整数进 行检验，下面介绍一种确定性检验法。  采用了基于Pocklington定理的特殊情形， 并将其改造为一递归算法加以实现  定理的特殊情形的描述：  定理：设n=2RF+1，其中F的真分解为 F=，如果存在整数a满足:an-11mod n ， 且(a(n-1)/qj-1,n)=1( j=1,…r), 那么 n 的每一个素因子 p 具有 p=mF+1 的形式，其中 m 1。更进一步，如果 F> n 或者 F 为奇数且 F>R，那 么 n 是素数

7Y 函数 Prime Test(a)对较小的整数a进行有效地素性判 别,当且仅当a是素数时返回TRUE, 当且仅当a不能被小于等于b的素数除尽时,函数 " TrialDivision(ab)返回值为TRUE 函数 Checklemmal(n,q验证所给参数是否满足引理 中的条件,满足时可知n是素数,返回TRUE 温函数 GenRelativeS根据条件概率分布,可以从区 间 0.511中选择一个值作为相对规模 日函数 P2用于2的幂运算。 试除判定法的边界g被设定为某一常数copt的k2 倍,其中copt的最优值可通过试验来确定,这里取 为0.1。 常数 margin保证了R的取值范围应该足够大,以保 证该区间内至少包含一些成功的R。 算法可用来生成几乎随机的可证安全素数 23:31:48

23:31:48  在实际应用中，采用了一种易于实现的简化算法，只是所生成的 素数的差异性有所降低。  上述定理中令r=1 即F=q 。  下面给出函数RandomPrime 的 C语言描述  LongInt RandomPrime(int k)  {if(kk0 && kk>k-margin);  q=RandomPrime( kk);  success=FALSE;  I=Power2(k-2)/q;  while(!success)  { R=Random(I,2*I);  n=2*R*q+1;  a=Random(2,n-1);  if(TrialDivison(n,g))success=CheckLemmal(n,a,q);} }  rerurn(n);} 函数 PrimeTest(a)对较小的整数 a 进行有效地素性判 别，当且仅当 a 是素数时返回 TRUE， 当且仅当 a 不能被小于等于 b 的素数除尽时，函数 TrialDivision ( a,b )返回值为 TRUE 。 函数 CheckLemmal(n,a,q)验证所给参数是否满足引理 中的条件，满足时可知 n 是素数，返回 TRUE 。 函数 GenRelativeSize 根据条件概率分布，可以从区 间 [0.5,1 ]中选择一个值作为相对规模。 函 数 Power2 用于 2 的幂运算。 试除判定法的边界 g 被设定为某一常数 c_opt 的 k 2 倍，其中 c_opt 的最优值可通过试验来确定，这里取 为 0.1 。 常数 margin 保证了 R 的取值范围应该足够大，以保 证该区间内至少包含一些成功的 R 。 算法可用来生成几乎随机的可证安全素数