MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » RSA简介(3)——寻找质数

RSA简介(3)——寻找质数

www.MyException.Cn  网友分享于:2013-08-16  浏览:0次
RSA简介(三)——寻找质数

  要生成RSA的密钥,第一步就是要寻找质数,本节专讲如何寻找质数。

  

  我们的质数(又称素数)、合数一般是对正整数来讲,质数就是只有1和本身两个的正整数,合数至少有3个约数,而1既不是合数也不是质数。

  质数有无穷多个,这个早在古希腊时期就被证明了,使用反证法很容易证明:假设质数只有有限多,分别为a1.....an,则a1*a1....*an+1大于所有的质数,却不以任何质数为约数,推出矛盾,从而假设错误。

  

  在质数的分布上,有个定理:

  lim  ∏ (n)/(n/ln(n)) = 1

  n→

   其中∏ (n)是小与等于n的质数的个数。

  找质数的第一个门槛还是靠随机,上述公式,可以推导出质数的密度ρ (n)(因为∏ (n)并非连续函数,此处密度只是概率上的密度)为

  lim ρ (n)/(n/ln(n))‘ = 1

  n→

 (n/ln(n))' = (ln(n)-1)/ln2(n),

  从而

  

  lim ρ (n)/(1/ln(n)) = 1

 

  n→

 

   那么,在n附近寻找质数,大约平均每ln(n)次可以找到一个质数。

  涉及到密钥的生成,随机算法要小心了,用时间种子与伪随机算法一起当然是不安全的,最好以硬件随机为基础的随机数,这样无规律,难以从密钥生成机制直接下手破解。

  

  接下来就需要质数判定算法。

  最土的算法:判断p是不是质数,就从2开始,挨个整数判断到p-1,看看是否其中有p的约数,如果没有,就是质数。

  这个算法效率太低O(p),但输入的信息量是p的位数级别,所以此算法应为指数级算法。

  明显提高的算法:如果p是合数,那么必然有一个不为1的约数小于或等于sqrt(p),于是刚才从2挨个整数判断到p-1修整一下,只需要判断到sqrt(p)即可。

  这个算法效率比前面那个算法好太多了,可是依然是指数级算法,只是指数从线性下降到平方根级别。

  可是我们RSA这里的指数动辄几百个bits,甚至两千多个bits,此种算法一样不靠谱。虽然上述算法还可以继续优化,比如测试了一个整数不是p的约数,就尽量不要测试这个整数的整数倍,只是,算法依然很慢。实际上,的确存在多项式级别的确定质数判定算法,第一个这样的算法是AKS算法,2002年由印度人解决。但目前靠谱的算法都是如此的慢,我们需要基于概率的判定方法。

  前两节谈到了模乘群,对于质数p,所有的小于p的正整数在模乘下构成一个群,该群的阶为p-1,则p-1是所有小于p的正整数以p为模的模乘周期的整数倍,这就是著名的费马小定理:

  如果a和p互质,且p为质数,则ap-1%p=1

  费马小定理虽然没有给出一个质数的鉴定方法,但告诉了我们,如果右边等号不成立,则p一定是合数,而基于概率的判定方法一般都会以费马小定理作为基础零件。RSA中一般用Miller-Rabin算法。

  Miller-Rabin算法同时利用了另外一个定义:

  p是质数,x是正整数,x2%p=1,那么x%p=1或者x%p=p-1

  完整描述Miller-Rabin算法如下:(https://en.wikipedia.org/wiki/Miller–Rabin_primality_test) 

write n − 1 as 2**r·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← ad mod n
   if x = 1 or x = n − 1 then
      continue WitnessLoop
   repeat r − 1 times:
      x ← x·x mod n
      if x = 1 then
         return composite
      if x = n − 1 then
         continue WitnessLoop
   return composite
return probably prime

  里面用到了第二节提到的模幂算法,用bc实现了一遍Miller-Rabin算法,因为bc里面无自带随机函数,就直接利用标准输入来输入随机数了,整个实现如下:

#!/usr/bin/bc -q
define mod_mul(a1,a2,n)
{
        return a1*a2%n;
}
define mod_exp(a,b,n)/* a^b%n */
{
        while(b%2==0) {
                a = mod_mul(a,a,n);
                b /= 2;
        }
        ret = a;
        b /= 2;
        while(b!=0) {
                a = mod_mul(a,a,n);
                if(b%2 == 1)
                        ret = mod_mul(a,ret,n);
                b /= 2;
        }
        return ret;
}
define Miller_Rabin(p, t)
{
        if(p==1) {
                return 0;
        }
        if(p<3) {
                return 1;
        }
        if(p%2==0) {
                return 0;
        }


}
define get_rand_num()
{
        return read();
}

define Miller_Rabin_test(n, k)
{
        d = n-1;
        r = 0;
        while(d%2!=1) {
                d /= 2;
                r++;
        }

        for(i=0;i<k;i++) {
                a = get_rand_num();
                x = mod_exp(a,d,n);
                if(x==1||x==n-1) {
                        continue;
                }
                for(j=1;j<r;j++) {
                        x = mod_mul(x,x,n);
                        if(x==1) {
                                return 0;
                        } else if(x==n-1) {
                                j = r;
                                continue;
                        }
                }
                if(j==r) {
                        return 0;
                }
        }
        return 1;
}

  

 

文章评论

我是如何打败拖延症的
我是如何打败拖延症的
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
漫画:程序员的工作
漫画:程序员的工作
一个程序员的时间管理
一个程序员的时间管理
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
程序员的鄙视链
程序员的鄙视链
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
总结2014中国互联网十大段子
总结2014中国互联网十大段子
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
Java程序员必看电影
Java程序员必看电影
 程序员的样子
程序员的样子
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
鲜为人知的编程真相
鲜为人知的编程真相
代码女神横空出世
代码女神横空出世
中美印日四国程序员比较
中美印日四国程序员比较
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
为什么程序员都是夜猫子
为什么程序员都是夜猫子
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
编程语言是女人
编程语言是女人
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员必看的十大电影
程序员必看的十大电影
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个调试和排错的小建议
10个调试和排错的小建议
程序员都该阅读的书
程序员都该阅读的书
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
程序员和编码员之间的区别
程序员和编码员之间的区别
我的丈夫是个程序员
我的丈夫是个程序员
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有