登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

素数测试 因子分解 与RSA系统  

2009-09-03 23:06:58|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转载请注明作者:phylips@bmy 出处:http://duanple.blog.163.com/blog/static/7097176720098311658625/

RSA加密系统,实际上基于这样一个基本事实。大数的素性测试要比因子分解简单的多,因子分解是一个难问题。

素数测试

如何测试一个数n是不是素数呢?简单的办法就是试一下它能否整除比它小的那些数,当然可以优化只检测小于sqare(n),但是无论如何优化,需要检测的数的个数都将不会小于小于sqare(n)的素数的个数。根据拉格朗日定理,小于n的素数的个数大概=n/ln(n),也就是说这个数目很大,数量级上很接近n了。所以这个路子实际上很难降低复杂度。

先看一个定理,1640年费马小定理:

对于一个素数p,所有的 1<a<p 满足 a^(p-1) = 1 mod p

正是这个定理被用来进行素数测试,用它进行测试,还得满足另一个条件如果p是合数等式不成立,当然最好是对于所有的a都不成立。但是实际上只能保证有一部分a不成立。比如合数341=11*31 但是2^340 = 1 mod 341.这样只能退而求其次,如果能保证对绝大多数的a不成立也可以啊。实际上这点是成立的。

可以证明,对于一个合数我们至少可以找到让它不满足费马等式的a占到一半。

这个事实可以这样证明。我们首先假设存在某一个数a,a^(p-1) != 1 mod p.这样我们在假设所有满足的数b 对于每一个满足的数b我们都可以找到一个对应的数a*b,而这个数刚好不满足费马等式。因为(ab)^(p-1) = b^(p-1) != 1 mod p.

当然也保证这个结论成立,还得有一些知识,首先对于固定的a,当它乘以不同的b时,它们mod p的结果都是不同的,实际上这又基于另一个结论:{对于 1< x < p ,将它们变成nx%p,实际上是进行了一个新的映射,也就是说不会出现重复值。}这样呢,就保证了a*b mod p之后不会是重复的数,也就保证了它们的个数不会缩水。

我们可以看到每找到一个满足的,就可以找到一个不满足的,这就说明不满足的数目起码不会比满足的数目少。当也有意外情况,实际上也有一类合数n很特殊对于它们来说,对于所有与n互素的数a,它们都满足a^(n-1) = 1 mod n,这样的数被叫做卡迈克尔数。最起码这种数会降低测试的准确度,严重的可能导致存在一个可以完全通过费马测试的合数。

针对这种情况,Rabin and Miller测试又加了项,基于如下定理:如果一个数!= 正负1 mod N,但它的平方=1 mod N,那么这个数是合数。所以在计算a^(N-1)的时候,首先把N-1写成了2^t*u的形式,然后逐步计算a^u mod N, a^2u mod N...a^(N-1) mod N,当首次发现1时,检查它的前一项结果是不是1或者-1.这样就可以进一步提供测试的精度。

实际的测试,只要看a=2就可以了,因为只有很少一部分合数可以通过这个测试。


RSA系统

因为它有一个公钥和私钥,这个是可以公开的,这样就不需要一个秘密会面,只要把自己的公钥公布,这样其他人就可以利用这个公钥直接加密,第三者即使拿到公钥也还是无法知道内容,只有利用私钥才能解密。

传统的加密方法,是发送者和接受者使用同一个密钥。

现在RSA由于效率不够高,还主要用作开头传递密钥方面。然后用这个传统密钥进行传输的加密。

实际上这样一个全新的加密系统,正是基于了素数测试和因子分解这两个问题的不对称性。

首先信息的接受者生成两个大素数p q,方法就是随机生成大数,然后用素数测试它是不是素数,因为素数的分布密度是很高的,所以可以很快得到两个大素数。

然后计算N=pq,同时选择一个与(q-1)(p-1)互素的数e,计算出一个d值,ed = 1 mod (q-1)(p-1),实际上就是求e的逆元,这个可以利用扩展欧几里德算法求解。然后把(N,e)作为公钥发布,(N,d)则是私钥。

假设要发送的信息为x(x<N),则x' = x^e mod N,这样x'就是加密后的数,发送它,

然后接受者x',计算x'^d mod N ,这个结果就等于x.


实际上这里面依赖于一个等式 x = x^ed mod N,而之所以选择(q-1)(p-1)正是为了保证这个等式的成立。下面来证明为什么 x = x^ed mod N。

因为ed= 1 mod (q-1)(p-1),可以写成ed = 1+k(q-1)(p-1)
我们需要证明x^ed - x = 0 mod N 即x^(1+k(q-1)(p-1)) - x = 0 mod N
而x^(1+k(q-1)(p-1)) - x = x*(x^k(q-1)(p-1) - 1)
而根据费马小定理,我们又有x^(p-1) = 1 mod p,x^(q-1) = 1 mod q,p,q是素数所以mod它们的乘积也满

足x^k(q-1)(p-1) = 1 mod pq = 1 mod N,这样x^k(q-1)(p-1) -1 = 0 mod N,很明显x*(x^k(q-1)(p-1) - 1)  = 0 mod N,证明完毕。

 

实际上正是通过选择ed= 1+k(q-1)(p-1),保证了x^k(q-1)(p-1) mod N =1 也就保证了x = x^ed mod N

  评论这张
 
阅读(1295)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018