(网络空间安全技术实践)7.2大整数素性检测实验

7.2 大整数素性检测实验,实验目的： 掌握大整数素性检测原理，并利用Visual C+编程实现Miller-Rabin素 性检测算法，进而生成大素数。 实验内容： 实现大整数素性检测算法，用于有效生成大素数。,网络空间安全实践教程,1,7.2 大整数素性检测实验,实验原理： 实现了大整数的运算后，还需要生成大素数p。其具体过程如下： 1、生成指定bit数的随机的奇数N 2、利用Miller-Rabin素性检测算法判断N是否为素数，若通过，令p=N即可，否则返回1继续做，直到通过为止。,网络空间安全实践教程,2,7.2 大整数素性检测实验,实验原理： 单次Miller-Rabin素性检测算法 要对N做素性检测，先将N-1分解成2sd，其中d是奇数，再随机选择 ，若对所有的 ，都有 则N是合数，否则，有不小于3/4的概率N是素数。 多次Miller-Rabin素性检测算法 循环调用单次Miller-Rabin素性检测算法，若调用次数为loop，则合数通过素性检测(即该算法错误概率)将不超过(1/4)loop,网络空间安全实践教程,3,7.2 大整数素性检测实验,实验原理： 生成指定bit数的随机奇数：使用rand( ) % 256对每个字节生成随机 数。可参考如下代码： Bigint BigRandOdd(int bytes) /生成bit数为8*bytes的随机奇数 Bigint res = 0; for(int i = 0; i bytes-1; i+) res.numi = rand() % 256; /对每个字节生成随机数 res.numbytes-1 = 128 + rand() % 128; /最高位取成1 if( !(res.num0 ,网络空间安全实践教程,4,7.2 大整数素性检测实验,实验原理： 生成指定bit数的素数：可参考如下代码： Bigint GenPrime(int bytes) /生成bit数为8*bytes的素数 Bigint res = BigRandOdd(bytes); int loop = 20; while(!MillerRabin(res, loop) res = BigRandOdd(bytes); return res; ,网络空间安全实践教程,5,7.2 大整数素性检测实验,实验要点说明： 生成大素数时，因为2以上的偶数不是素数，所以直接随机生成奇数即可。 实验中loop表示调用单次MIller-Rabin素性检测算法的次数，建议取成20即可。,网络空间安全实践教程,6,7.2 大整数素性检测实验,实验准备： Windows 操作系统 Visual Studio 2010以上开发环境,网络空间安全实践教程,7,7.2 大整数素性检测实验,实验步骤： 利用Visual C+开发环境，使用7.1中的大整数结构体，先实现生成指定bit的随机数、生成0,n)随机数、单次Miller-Rabin素性检测算法。 实现多次Miller-Rabin素性检测算法，再生成指定bit数的素数。,网络空间安全实践教程,8,7.2 大整数素性检测实验,实验结果要求： 编程实现大整数的Miller-Rabin素性检测算法，给出关键编程思路。 总结实验过程中遇到的问题和经验。,网络空间安全实践教程,9,7.2 大整数素性检测实验,实验视频：,网络空间安全实践教程,10,