首页 > 代码库 > RSA算法

RSA算法

2024-10-20 01:55:02   211人阅读

RSA算法其实在大学本科的课程已经学过了，不过当时理解的不深，这篇博客就当加深理解和复习了。
 

首先抛出2个问题：

    为什么要用对称加密，解决了什么问题？
    RSA算法是怎么保证加密信息不被破解的？
先回答第一个问题：
    最初的加密算法是对称加密算法，加密和解密方式都是同一种规则。
例如：
    A使用某一个加密规则，对信息进行加密。B使用同样的规则，对信息进行解密。这个加密规则我们称为密钥。这个加密模式带来了另外一个问题就是如何保证密钥的安全传输。
 
    非对称加密算法就解决了上面的问题。A方首先生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
    B获取A的公钥并且对信息进行加密。
    A获取加密的信息后，使用私钥解密。
因为私钥是不公开的，从而避免上面的问题。
 
第二个问题，RSA算法是怎么保证加密信息不被破解的？
 
    要知道RSA算法是怎么保证加密信息不被破解的，需要来看下他的生成密钥和公钥的过程，下面举个例子：
 
第一步，选择两个不相同的质数p和q
    例如选择了31和101
 
第二步，计算p和q的乘积n
    n = 31 * 101= 3131
 
    n的长度就是密钥的长度，3131写成二进制是110000111011 一共12位，所以这个密钥就是12位，实际中RSA密钥一般是1024位，重要场合为2048位
 
第三步，计算n的欧拉函数φ(n)
    根据公式 φ(n) = (p-1)(q-1)
    φ(n) = 3000
 
第四步，随机选择一个整数e,条件是1<e<φ(n) ,且e与φ(n)互质。
    这里选择e为311
 
第五步，计算e对于φ(n)的模反元素d
    所谓的模反元素就是指有一个整数d，可以使得ed被φ(n)除的余数为1.
    ed=1(mod φ(n))
 
    这个式子等价于
    ed-1=kφ(n)
 
    上面式子实质上就是对ex + φ(n)y = 1，这个二元一次方程求解。
    已知e=311,φ(n)=3000,
    311x+3000y= 1
    这个方程可以用‘扩展欧几里得算法’求解，（ｘ，ｙ）＝（791，-82）
 
    所以d=791
 
第六步，将n和e封装为公钥,n和d封装为私钥。
    n=3131 ,e=311,d=791
    所以公钥就是(3131，311)，私钥就是(791)
 
    RSA算法的可靠性：
    上面生成密钥的步骤，一共出现了六个数字。
    p,q,n,φ(n),e,d
    上面六个数字中公钥用到了两个n和e，其余的四个数字都是不公开的，其中最重要的是d,因为n和d组成了私钥，一旦d泄漏就等于私钥泄漏了。
 
    有没有可能在已知n和e的情况下，推导出d？
    首先 ed=(mod φ(n))，只有知道e和φ(n)，才能算出d。
    然后 φ(n)=(p-1)(q-1),只有知道p和q，才能算出φ(n)。
    最后n=pq。只有将n因数分解，才能算出p和q。
 
    也就是说如果n可以被因数分解，d就可以算出来了，也就以为这私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法
 
    对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠
举个例子：你可以对3133（31*101）进行因数分解，但是我们很难弄对下面数字进行因数分解
   12301866845301177551304949

　　58384962720772853569595334
　　79219732245215172640050726
　　36575187452021997864693899
　　56474942774063845925192557
　　32630345373154826850791702
　　61221429134616704292143116
　　02221240479274737794080665
　　351419597459856902143413

 

它等于这样两个质数的乘积：

   33478071698956898786044169

　　84821269081770479498371376
　　85689124313889828837938780
　　02287614711652531743087737
　　814467999489
　　　　×
　　36746043666799590428244633
　　79962795263227915816434308
　　76426760322838157396665112
　　79233373417143396810270092
　　798736308917

    事实上，这大概是人类已经分解的最大整数（232个十进制位，768个二进制位）。比它更大的因数分解，还没有被报道过，因此目前被破解的最长RSA密钥就是768位。

 
    所以可以看到RSA的的安全性是依赖于大数字的因数分解的。而大数字的因数分解，目前来说还没高效的方法解决，所以RSA的安全性是很高的。而且密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
 
最后看一下如果根据公钥加密，私钥解密。

 

（1）加密要用公钥 (n,e)
    假设我们要加密的的字符为‘w‘ ，这里用ascii作为编码格式w对应十进制的值为119，需要注意的是需要加密的信息的值必须要小于n。
所谓加密，就是算出下面式子的c：
            me ≡ c (mod n)
公钥是(3131，311) n=3131, e =311
            119311 ≡ c(mod 3131)
可以求出c=564
 
（2）解密要用私钥(n,d)
拿到c=564之后，就用自己的私钥（3131,791）解密
可以证明下面的等式一定成立，这里就不证明了。
            cd ≡ m (mod n)
 
            564791 ≡ m (mod 3131)
可以求出m=119
 
这样子就可以解密得出119了。
    至此，加密解密过程完成。
    我们可以看到，如果不知道d，就没有办法从c求出m。而前面已经说过，要知道d就必须分解n，这是极难做到的，所以RSA算法保证了通信安全。
   还有个问题，公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？有两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种"对称性加密算法"（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。

RSA算法


联系
我们