RSA算法详解
总括： 本文详细讲述了RSA算法详解，包括内部使用数学原理以及产生的过程。
相濡以沫。到底需要爱淡如水。
之前写过一篇文章 SSL协议之数据加密过程 ，里面详细讲述了数据加密的过程以及需要的算法。SSL协议很巧妙的利用对称加密和非对称加密两种算法来对数据进行加密。这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述。首先先来了解下这个算法的历史：
RSA是1977年由 罗纳德·李维斯特 （Ron Rivest）、 阿迪·萨莫尔 （Adi Shamir）和 伦纳德·阿德曼 （Leonard Adleman）一起提出的。当时他们三人都在 麻省理工学院 工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
但实际上，在1973年，在英国政府通讯总部工作的数学家 克利福德·柯克斯 （Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。
所以谁是RSA算法的发明人呢？不好说，就好像贝尔并不是第一个发明电话的人但大家都记住的是贝尔一样，这个地方我们作为旁观者倒不用较真，重要的是这个算法的内容：
RSA算法用到的数学知识特别多，所以在中间介绍这个算法生成私钥和公钥的过程中会穿插一些数学知识。生成步骤如下：
随意选择两个大的质数p和q，p不等于q，计算N=p*q;
什么是质数?我想可能会有一部分人已经忘记了，定义如下：
比如2，3，5，7这些都是质数，9就不是了，因为3*3=9了
r = φ(N) = φ(p)φ(q) = (p-1)(q-1) 。
这里的数学概念就是什么是欧拉函数了，什么是欧拉函数呢？
欧拉函数 的定义：
互质 的定义：
例如： φ(8) = 4 ，因为 1,3,5,7 均和 8 互质。
推导欧拉函数:
（1）如果 n = 1 , φ(1) = 1 ；(小于等于1的正整数中唯一和1互质的数就是1本身)；
（2）如果 n 为质数， φ(n) = n - 1 ；因为质数和每一个比它小的数字都互质。比如5，比它小的正整数1,2,3,4都和他互质；
(3) 如果 n 是 a 的 k 次幂，则 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1) ；
(4) 若 m , n 互质，则 φ(mn) = φ(m)φ(n)
证明： 设 A , B , C 是跟 m , n , mn 互质的数的集，据 中国剩余定理 (经常看数学典故的童鞋应该了解，剩余定理又叫韩信点兵，也叫孙子定理)， A * B 和 C 可建立双射一一对应)的关系。（或者也可以从初等代数角度给出 欧拉函数积性的简单证明 ） 因此的φ(n)值使用 算术基本定理 便知。（来自维基百科）
选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为 d （ ed = 1(mod r) 模反元素存在，当且仅当e与r互质）， e 我们通常取65537。
模反元素：
比如 3 和 5 互质， 3 关于 5 的模反元素就可能是2，因为 3*2-1=5 可以被5整除。所以很明显模反元素不止一个，2加减5的整数倍都是3关于5的模反元素 {...-3, 2,7,12…} 放在公式里就是 3*2 = 1 (mod 5)
上面所提到的欧拉函数用处实际上在于欧拉定理：
欧拉定理：
欧拉定理就可以用来证明模反元素必然存在。
由模反元素的定义和欧拉定理我们知道， a 的 φ(n) 次方减去1，可以被n整除。比如，3和5互质，而 5 的欧拉函数 φ(5) 等于4，所以 3 的 4 次方 (81) 减去1，可以被 5 整除（ 80/5=16 ）。
小费马定理：
此时我们的 (N , e) 是公钥， (N, d) 为私钥，爱丽丝会把公钥 (N, e) 传给鲍勃，然后将 (N, d) 自己藏起来。一对公钥和私钥就产生了，然后具体的使用方法呢？请看： SSL协议之数据加密过程详解
我们知道像RSA这种非对称加密算法很安全，那么到底为啥子安全呢？
我们来看看上面这几个过程产生的几个数字：
N 和 e 我们都会公开使用，最为重要的就是私钥中的 d ， d 一旦泄露，加密也就失去了意义。那么得到d的过程是如何的呢？如下:
所以得出了在上篇博客说到的结论，非对称加密的原理：
将a和b相乘得出乘积c很容易，但要是想要通过乘积c推导出a和b极难。即对一个大数进行因式分解极难
目前公开破译的位数是768位，实际使用一般是1024位或是2048位，所以理论上特别的安全。
RSA算法的核心就是欧拉定理，根据它我们才能得到私钥，从而保证整个通信的安全。
AiPPT
2024-09-19 广告
