rsa基础学习

密码学 > rsa

Created At : 2020-05-27 11:46

Views 👀 :

rsa基础

各参数所代表的含义：

<1> 参数N代表模数，在RSA中进行模运算
<2> 参数E，d分别代表公钥指数和私钥指数
<3> p,q分别为模数N分解后得到的值
<4> C，m分别代表密文和明文
<5> dp≡d mod (p−1)      dq≡d mod (q−1)这两个参数是在d的基础上的延申

各参数之间的关系：

1
2
3

<1> c≡m^e (mod N)    m≡c^d (mod N)
<2> phi=(p-1)*(q-1)  e*d≡1 (mod phi)
这里很重要的一点是e,d的取值范围,1<e<phi,1<d<phi,同时gcd(phi,e)=gcd(phi,d)=1

这也是RSA解密的基础运算，就是拿到公钥指数E和模数N，将模数N分解为两个质因数，求得私钥指数d，从而利用加密过程或解密过程将最终的内容拿到。

这里需要讲一下公钥加密解密体系
以对称加密为例，加密所使用的密钥与解密所使用的密钥是同一个，这样破译的难点集中于加密函数复杂度的设计以及密钥的长度，更多的是一种线性的处理方式；而公钥加密体系将这种问题避开，转而将加密解密的数据进行基于离散数学的运算，这里就提到了我们公私钥指数的关系
1
e*d≡1 (mod phi)
在数值小的时候运算是极为简单的，不过当数值增加到指数次方时，求离散数学的逆的难度也会相对应地指数次增长。
但并不是说，公钥破解难度只在这里。好多教材和论文，将rsa这种基于大素数的公钥加密的破解，都解释为只要能够将大素数分解，这个加密体系就不复存在。其实，并没有直接证据能够证明，大素数分解与公钥破解的直接联系。
就比如在RSA的解密过程中，当e=3，此时N为分解难度特别大的2048bit级别时，仍旧可以利用低指数攻击，在不分解N的情况下，将整个密文完整解密出来，所以众多的rsa的攻击方式来源不止是针对N的分解，更多的是从RSA的其他参数下手，使得解密过程更为简单便捷。
接下来我们用几道例题来说明

1	在RSA中，已知C=34 ，N=123，e=11,那么m为多少？

开始分析，这里知道N，我们使用YAFU分解，可以知道N的两个素因数是3和41
求得phi=240=80,(11d)%phi=1,所以d=51
m≡c^d (mod(N))=34^51(mod 123)=19
这里用到的YAFU是一个在分解N常用的一个离线工具，它适用于素因数相差特别大或者特别小的情况，能够很快的分解出来，所以一些很小的数可能分解时间比大的数要长，原因在这里。
除了这个以外，当面对特别大的素数时，我们可以使用在线网站 http://www.factordb.com/ ,这是一个在线网站，相当于是一个数据库，管理员将以往有分解出来的素数放在网站上，供查询。

除此之外，利用算法进行脚本分解，不过成功率很低。