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/lnp1/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的非平方剩余