当前位置: 首页 > 原创新闻 > RSA加密算法实验

RSA加密算法实验

发表于:2021-03-16 15:15 作者: mtr 阅读数(1509人)

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。


对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。尽管如此,只有一些RSA算法的变种被证明为其安全性依赖于因数分解。假如有人找到一种快速因数分解的算法的话,那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长,用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天,RSA加密安全性受到了挑战。


1983年麻省理工学院在美国为RSA算法申请了专利。这个专利2000年9月21日失效。由于该算法在申请专利前就已经被发表了,在世界上大多数其它地区这个专利权不被承认。


1.RSA算法公钥与密钥的产生

假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥:

随意选择两个大的质数p和q,p不等于q,计算N=pq;

根据欧拉函数,求得r = (p-1)(q-1);

选择一个小于 r 的整数 e,求得 e 关于模 r 的模反元素,命名为d;(模反元素存在,当且仅当e与r互质)

将 p 和 q 的记录销毁。

(N,e)是公钥,(N,d)是私钥。Alice将她的公钥(N,e)传给Bob,而将她的私钥(N,d)藏起来。


2.加密消息

假设Bob想给Alice送一个消息m,他知道Alice产生的N和e。他使用起先与Alice约好的格式将m转换为一个小于N的整数n,比如他可以将每一个字转换为这个字的Unicode码,然后将这些数字连在一起组成一个数字。假如他的信息非常长的话,他可以将这个信息分为几段,然后将每一段转换为n。用下面这个公式他可以将n加密为c:

ne ≡ c (mod N)

计算c并不复杂。Bob算出c后就可以将它传递给Alice。


3.解密消息

Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n:cd ≡ n (mod N)得到n后,她可以将原来的信息m重新复原。

解码的原理是:

cd ≡ n e·d(mod N)

以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)。由费马小定理可证明(因为p和q是质数)

n e·d ≡ n (mod p) 和n e·d ≡ n (mod q)

这说明(因为p和q是不同的质数,所以p和q互质)

n e·d ≡ n (mod pq)