本篇内容介绍了“如何理解加密算法RSA”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
RSA加密
我们需要先预习一下还给数学老师的知识
欧拉函数
在数论中,存在正整数 n,小于n并且与n互质的正整数的数目称为n的欧拉函数记着φ(n)。例如:
φ(7) 7对应的比7小的与7互质的数有1、2、3、4、5、6共6个,因此φ(7)=6;
φ(8) 8对应的比8小的与8互质的数有1,3,5,7共4个,因此φ(8)=4;
φ(9) 9对应的比9小的与9互质的数有1,2,4,5,6,7,8共7个,,因此φ(9)=7。
通式(P是数N的质因数)
φ(10)=10×(1-1/2)×(1-1/5)=4;
φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;
φ(49)=49×(1-1/7)=42。
若m n互质:φ(n * m)=φ(n)* φ(m),如果n为质数那么φ(n)=n-1。
分解质因数求值:φ(12)=φ(4 * 3)=φ( 2^2 * 3^1 )=( 2^2 - 2^1 ) * (3^1 - 3^0)=4。
欧拉定理
如果两个正整数m和n互质,那么m的φ(n) 次方对n取余衡等于1。m^φ(n)%n≡1。
费马小定理
存在一个质数p,而整数a不是p的倍数,则存在a^(p-1)%p≡1。费马小定理是欧拉定理的特殊情况。因为φ(p)=p-1(任何数都与质数互质)。
模反元素
如果两个正整数e和x互质,那么一定存在一个整数d,使得ed-1能够被x整除,则称d是e对x的模反元素。e * d % x≡1,那么e * d ≡ k*x+1。
由以上定理得出以下几个公式:
m^φ(n)%n≡1
m^(k * φ(n))%n≡1 两端同乘以m
m^(k * φ(n)+1)%n≡m
e * d≡k * x+1
m^e * d%n≡m 替换第3步k * φ(n)+1
而m^e*d%n≡m就是我们需要的一个非对称加密的公式。m为明文,e和d分别对应的是公钥私钥。迪菲卡尔曼秘钥交换对公式拆分:
m^e%n=c 加密
c^d%n=m 解密
其中c为通过e加密后的密文,然后通过d可以解出明文m。因此:
公钥: e、n
秘钥:d、n
明文:m
密文:c
RSA加密过程
取两个质数p1、p2;
确定n值,n=p1 * p2,n值一般会很大长度一般为1024个二进制位;
确定φ(n),φ(n)=(p1-1) * (p2-1);
确定e值,1
确定d值,e*d%φ(n)=1;
加密 c=m^e%n;
解密m=c^d%n。
实际验证:
p1=3, p2=7;
n=p1 * p2=3 * 7=21;
φ(n)=(p1-1) * (p2-1)=2*6=12;
1
e * d % φ(n)=5 * d % 12=1,得d=17;
设置明文m=3,则c = m^e % n = 3^5 % 21=12;
解密密文m=c^d % n=12^17 % 21=3。
通过上面的讲解我们知道在RSA 加密中用到的几6个参数
p1 p2 n φ(n) e d
这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。
那么,有无可能在已知n和e的情况下,推导出d?
e*d%φ(n)=1 (只有知道e和φ(n),才能算出d。)
φ(n)=(p1-1) * (p2-1) (只有知道p1和p2,才能算出φ(n)。)
n=p1*p2 (只有将n因数分解,才能算出p和q。)
结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。
可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。维基百科这样写道:
"对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。
假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。
只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。"
或许你看到这里还不相信,我写个程序挨着试 不就可以破解出来吗?例如 21 你或许会很快的分解成 3×7 但是这个数再大一点 比如 这个质数 2^57,885,161-1 它有超过1千7百万个数位 如果让传统计算机来验证他是不是质数 估计可以跑到天荒地老。
“如何理解加密算法RSA”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站,小编将为大家输出更多高质量的实用文章!