RSA是一种密码体制。RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是目前使用最广泛的公钥密码体制之一。为它是信息通信安全的基石,保证了加密数据不会被破解
二密钥发展历史
1976年以前,所有的加密方法都是同一种方式:
(1)甲方选择某一种加密规则,对信息进行加密;
(2)乙方使用同一种规则,对信息进行解密。
由于加密和解密使用同样规则(规则就简称”密钥”),这就是”对称加密”。
这种模式必须解决一个问题:通信双方必须同时拥有“密钥”,也就是说,把信息加密解决的问题,转化为密钥的保存和传递,就成了最头疼的问题。
1976年,两位美国计算机学家WhitfieldDiffie和MartinHellman,提出了一种全新的思路,解决密钥的保存和传递问题,这就是著名的”Diffie-Hellman密钥交换算法”。这个算法的原理就是:加密和解密可以使用不同的规则,这要规则间有某种关联关系,可以推导出密钥,就避免了直接传递密钥。这种新的加密模式被称为”非对称加密算法”。
1977年由罗纳德·李维斯特(RonRivest)、阿迪·萨莫尔(AdiShamir)和伦纳德·阿德曼(LeonardAdleman)一起提出了RSA,”非对称加密算法”,RSA就是他们三人姓氏开头字母拼在一起组成的。具有里程碑式的贡献,开创了密码学的先河,是的密码在信息安全和通信保密方面做出了巨大的贡献。
这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。
三数学理论
RSA算法的安全性基于RSA问题的困难性,也就是基于大整数因子分解的困难性上。但是RSA问题不会比因子分解问题更加困难,也就是说,在没有解决因子分解问题的情况下可能解决RSA问题,因此RSA算法并不是完全基于大整数因子分解的困难性上的。
(1)互质
如果两个正整数,除了1以外,没有其他公因子,大家就称这两个数是互质。
(2)欧拉函数
如果两个正整数m和n互质,那么m的φ(n)次方减去1,可以被n整除
(3)费马小定理
欧拉定理的特殊情况:如果两个正整数m和n互质,而且n为质数!那么φ(n)结果就是n-1。
四RSA的定理模型:
设p,q是两个素数,n=p*q;
假设整数e满足1<e<φ(n),(e,φ(n))=1;
1、那么e,φ(n)就满足了定理(5),所以就存在整数s、d,e*d+s*φ(n)=1;
2、假设存在一个整数a,(a,n)=1;那么a和q,p也应该互素,即(a,p)=1;(a,q)=1;
既然(a,p)=1;那就满足了定理(6);所以a^φ(p)=1modp;
等式两边同时做φ(q)次幂运算,得到(a^φ(p))^φ(q)=1^φ(q)modp,
整理得a^(φ(p)*φ(q))=1modp;
套用定理(5),φ(n)=φ(p)*φ(q),所以a^φ(n)=1modp;
等式两边同时做s次幂运算,得到a^(s*φ(n))=(1^s)modp=1modp;
左右在个乘以a,得到a^(1+(s*φ(n)))=amodp;
这是大家发现1+(s*φ(n))不就是e*d吗?(套用1、结论);所以:
a^(e*d)=amodp;①这是一个重要的结论,同理,q,p在本质上是相同的,所以
a^(e*d)=amodq;②
算式①和算式②可以利用剩余定理得出结论a^(e*d)=amod(p*q);
剩余定理是比较复杂的,不过大家可以狭义的理解为这样的数学题,一个整数,被5除余1,被7除余1,那么这个整数最小是多少呢?答案是36,因为这个整数一定被5*7=35除余1,所以它是36,71,106……所以最小是36;
那么a^(e*d)=amod(p*q)就很好理解了,因为n=p*q;所以a^(e*d)=amodn;
五加解密过程
以密码通信中的两位经典人物:Alice和Bob,为例。描述一下非称加密算法的流程,假设爱丽丝要与鲍勃进行加密通信,她该怎么生成公钥和私钥呢?
在此可以看到,非对称加密是通过两个密钥(公钥-私钥)来实现对数据的加密和解密的。公钥用于加密,私钥用于解密。
现在就来看看RSA算法是怎么来对数据进行加密的吧,如下是一幅RSA加密算法流程及加密过程图。
加密过程:
A提取消息m的消息摘要h(m),并使用自己的私钥对摘要h(m)进行加密,生成签名s
A将签名s和消息m一起,使用B的公钥进行加密,生成密文c,发送给B。
解密过程:
B接收到密文c,使用自己的私钥解密c得到明文m和数字签名s
B使用A的公钥解密数字签名s解密得到H(m)。
B使用相同的方法提取消息m的消息摘要h(m)
B比较两个消息摘要。相同则验证成功;不同则验证失败。
RSA加密过程简述
A和B进行加密通信时,B首先要生成一对密钥。一个是公钥,给A,B自己持有私钥。A使用B的公钥加密要加密发送的内容,然后B在通过自己的私钥解密内容。
数字签名的作用是保证数据完整性,机密性和发送方角色的不可抵赖性
假设A要想B发送消息,A会先计算出消息的消息摘要,然后使用自己的私钥加密这段摘要加密,最后将加密后的消息摘要和消息一起发送给B,被加密的消息摘要就是“签名”。
B收到消息后,也会使用和A相同的方法提取消息摘要,然后使用A的公钥解密A发送的来签名,并与自己计算出来的消息摘要进行比较。如果相同则说明消息是A发送给B的,同时,A也无法否认自己发送消息给B的事实。
其中,A用自己的私钥给消息摘要加密成为“签名”;B使用A的公钥解密签名文件的过程,就叫做“验签”。
上面就是RSA的原理和全部过程,真正的应用中,不需要理解如此复杂的密码学原理。有很多开源的库,可以直接使用。
后续
RSA公钥体制的安全性是基于大数分解(严格的说是对两个大质数的乘积进行分解)这一数学难题的。尽管RSA是目前使用最为广泛的公钥加密算法,但人们对其安全性的质疑和研究自其诞生之日起就从没停止过。更令人担忧的是,RSA中的指数运算保留了输入的乘积结构。
最近,来自澳大利亚昆士兰大学和偶国中科大的两个研究小组独立的建造出了能够运行Shor算法的量子计算机原型。而Shor正是一种能够高效的进行大数分解运算的计算机!对此,《新科学家》杂志报道说:出现能够运行Shor算法的量子计算机具有极为深远的意义,这意味着量子计算带来的最为可怕的威胁即将成为现实——它能够轻松的破解保护大家银行账号等的密码!所以说,道高一尺魔高一丈,破解和反破解是永恒的话题。
详细介绍RSA加密算法(数学原理 实现过程) 并举例说明如何将一个简单的明文利用此算法进行加密? – 网络