RSA加密
一、简介
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的,RSA就是他们三人姓氏开头字母拼在一起组成的。
使用公钥加密的数据,利用私钥进行解密
使用私钥加密的数据,利用公钥进行解密
RSA是一对密钥。分别是公钥和私钥,这个公钥和私钥其实就是一组数字!其二进制位长度可以是1024位或者2048位.长度越长其加密强度越大,目前为止公之于众的能破解的最大长度为768位密钥,只要高于768位,相对就比较安全.
二、基础数论
- 素数 又称质数,指在一个大于1的自然数中,除了1和此整数自身外,不能被其他自然数整除的数。
- 互质 又称互素。若N个整数的最大公因子是1,则称这N个整数互质。
- 模运算 即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上,当两个整数除以同一个正整数,若得相同余数,则二整数同余。
- 欧拉函数 计算小于或等于n的正整数中与n互质的数的数目,以φ(n)表示。
如果n是质数的某一个次方,即 n = p^k (p为质数,k为大于等于1的整数),则φ(n) = φ(p^k) = p^k - p^(k-1)。如果n是质数,则 φ(n)=n-1 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。如果n可以分解成两个互质的整数之积,即 n = p * k ,则φ(n) = φ(p * k) = φ(p1)*φ(p2)
- 欧拉定理 对任何两个互质的正整数a, m(m>=2)有:
- 费马小定理 当m是质数p时,此式则为:
- 模反元素 如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。这时,b就叫做a的“模反元素”。
三、加密解密算法
根据欧拉定理经过一系列转换得到的公式:
使用迪菲赫尔曼密钥交换得到最终RSA加密公式:
现在可以知道,加密解密的算法为:
加密:m^e % n = c
解密:c^d % n = m
m就是原始数据,c是密文,公钥是n和e,私钥是n和d,只有n和e是公开的。
由此可知如果想要破解RSA则需要知道φ(n)的值,只能对n进行因数分解。如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。
大整数的因数分解,目前是一件非常困难的事情。除了暴力破解,还没有发现别的有效方法。
所以只要n足够大,就可以认为RSA是安全的。
四、公钥和私钥生成过程
1.随机选择两个不相等的质数p和q。
2.计算p和q的乘积n。
3.计算n的欧拉函数φ(n)。
4.随机选择一个整数e,也就是公钥当中用来加密的那个数字
5.计算e对于φ(n)的模反元素d。也就是密钥当中用来解密的那个数字
6.将n和e封装成公钥,n和d封装成私钥。
p=3 q=5
n=15
φ(15)=(3-1)*(5-1) =8
e=3------->随机选
d=11-------3*11%8=1公钥(15,3) 私钥(15,11)m=3
3^3%15=12
12^11%15=3m=6
6^3%15=6
6^11%15=6搞定收工!
五、安全性
1999年,RSA-155 (512 bits)被成功分解,花了五个月时间(约8000 MIPS年)和224 CPU hours在一台有3.2G中央内存的Cray C916计算机上完成。
2009年12月12日,编号为RSA-768(768 bits, 232 digits)数也被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性,普遍认为用户应尽快升级到2048-bit或以上。
现在1024的还是安全的,但是还是建议选择更大位数的。
六、RSA加密限制
RSA算法本身要求加密内容也就是明文长度m必须0<m<密钥长度n,并且实际明文长度需要减去padding字节长度。
我们一般使用的padding标准有NoPPadding、OAEPPadding、PKCS1Padding等,其中PKCS#1建议的padding就占用了11个字节。
以PKCS#1为例,对于1024长度的密钥,128字节(1024bits)-减去11字节正好是117字节,但对于RSA加密来讲,padding也是参与加密的,所以,依然按照1024bits去理解,但实际的可以加密的明文只有117字节了。
那么问题来了,如果需要加密的明文大于限制应该如何去做?
(1)分段加密,将明文分割为117字节的多段,逐一进行加密
(2)只传递重要部分,比如改用对称加密,密文用RSA加密后传递