Hi Guest

More contents, please log on!

Bitmere.com 区块链技术 Content

非对称加密之RSA算法

有个胖子他姓杨
31 0 0
简介

    1977年,MIT的三位老师Rivest、Shamir和Adleman设计了一种算法,可以实现非对称加密。这种算法以他们三个人的名字命名为RSA。RSA算法是使用最为广泛的非对称加密算法。RSA加密利用了单向函数正向求解很简单,反向求解很复杂的特性。

    具体是利用了:

    1.对两个质数相乘容易,而将其合数分解很难。即n=p1*p2,已知p1、p2求n简单,已知n求p1、p2困难。

    2.(m^e)modn=c,已知m、e、n求c简单,已知e、n、c求m很难。

    原理

    RSA加密,实现了公开密钥,就是A可以给所有人发送公钥,其他人把要加密的信息用这把公钥加密后发送给A,A用私钥解密就可以获得加密的信息了。反过来,A要发送加密信息给B,只要知道B的公钥就可以了,而这个公钥是公开的。

    公钥n、e的生成:随机选取两个质数p1、p2,n=p1*p2,再随机选取一个整数e,e与φ(n)互质。

    加密过程:(m^e)modn=c,其中m为原信息,c为密文,n、e为公钥。

    解密过程:(c^d)modn=m,其中d为解密密钥。

    解密密钥d的求解:

    (c^d)modn=(((m^e)modn)^d)modn=((m^e)^d)modn=(m^ed)modn

    费马定理:

    若p是素数,a与p互素,则a^(p-1)≡1(modp)

    举例

    加密过程举例(1):

    1.挑选两个质数,如p=61和q=53

    2.计算N=p*q=3233

    3.计算(p-1)(q-1)=60*52=3120【这一步可以计算(p-1)和(q-1)的最小公倍数,从而使得计算的d比较小;17关于780的模逆是413,比2753要小】

    4.选择与3120互质的一个数e=17

    5.计算得出d,使得d是e关于3120的模逆,得出d=2753

    6.如果明文是5,那么密文是5^17(mod3233)=3086

    7.解密,3086^2753(mod3233)=5

    关于模逆:先用“辗转相除法”…

    加密过程举例(2)-中间人:

    A:有一个公钥n、e。例如:3127、3。

    B:有一个信息m。例如:89。

    C:偷听者

    A:

    第一步:随机找两个质数p1、p2,一个奇数e。例如:53、59、3。

    第二步:计算n=p1*p2得到n,计算欧拉函数φ(n)=(p1-1)*(p2-1)得到φ(n),计算钥匙d=(k*φ(n)+1)/e得到d。

    例如:53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。

    第三步:发送n、e给大家知道//n、e就是公钥,d就是密钥。

    C:获得n、e

    B:

    第一步:获得n、e

    第二步:加密信息m,(m^e)modn=c,获得加密信息c。例如:(89^3)mod3127=1394。

    第三步:发送c给A

    C:

    第一步:截获加密信息c

    第二步:破解信息c,此时C只有n、e、c,只有把n分解质因数才能破解,而此分解很困难特别是当n很大的时候。

    A:

    第一步:收到加密信息c

    第二步:解密信息c,(c^d)modn=m,获得信息m。例如:(1394^2011)mod3127=89。

    完成

    安全性

    为什么RSA是不会被破解的呢?

    为了解密,关键是要找出私钥。如果已知(p-1)(q-1),那么就很容易算出来私钥。而为了获得(p-1)(q-1),就需要知道p和q的值。为了获得p和q的值,就必须对N进行因式分解。

    1874年,WilliamStanleyJevons就在自己的书《科学的原则》中写道:

    读者中有人能发现是哪两个数的乘积为8616460799吗?我想这个答案只有我自己知道。

    书中他描述了单向函数(one-wayfunction)与密码学的关系,还提出了因子分解问题可以用作创建trapdoor函数。

    到目前为止,关于RSA可靠性的描述:

    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。

    假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。

    只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。

    RSA的正确性:

    可以使用欧拉函数和欧拉定理来证明。

    (这个证明还必须补充一部分就是m和n不互质的情况。欧拉定理只是在m和n互质时才有用。)

    如果m和n不互质,因为n是两个质数p和q的乘积,所以m必然是p或q的倍数(因为要求m

    那么问题来了,如果黎曼猜想真的被证明了,那么RSA算法的可靠性是否会成空中楼阁呢?

    应用

    RSA的应用:数字签名

    最普遍的应用,网站身份认证。如何证明我们连上的网站就是支付宝alipay呢?如果因为各种原因,如域名污染,我们的浏览器访问了攻击者网站,这时一定要进行验证。

    验证,就是要检查一个证书。当我们以HTTPS的方式连上一个网站时,网站会首先给我们发送一个证书。这个证书里包含有它的域名、公钥等信息。同时这个证书是由专门的第三方公信机构CA使用自己的私钥签了名的。浏览器在拿到这个证书之后,首先用第三方公信机构CA的公钥对这个证书解密,然后查看和比对证书里的域名和浏览器地址栏的域名,完全匹配才认为是正确的网站。

    如果域名被污染,虽然攻击者网站可以拷贝一份正常网站的证书,但是因为证书中包括了正常网站的公钥,如果它不能获得正常网站的私钥,那么它就没有办法对加密信息进行解密。从而不能正常建立连接。
BitMere.com is Information release platform,just provides information storage space services.
The opinions expressed are solely those of the author,Does not constitute advice, please treat with caution.
You have to log in before you can reply Login | 立即注册

Points Rules

Write the first review

有个胖子他姓杨 初中生
  • Follow

    0

  • Following

    0

  • Articles

    10

Promoted