RSA算法简单介绍:

RSA算法是非对称加密算法,在1977年被罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的,故取名为RSA非对称加密算法,而今在计算机数据加密领域以及电子商业中广泛使用.

致敬三位伟大的数学家

图片来自百度百科

RSA数学原理:

提问:

设想我们如果有一个正整数n,有多少个数与n互为互质关系?

tag:什么叫互质关系?

互质关系(即两个数,除了1以外,没有其他的公约数,那么我们就称之为这两个数是互质关系.例如:3和8是互质关系,而2和8就不是.)

φ(n)与欧拉函数:

而求n的互质关系数的个数的方式(也就是上述的提问),我们就称为欧拉函数.通常我们用φ(n)来表示.

举例:

φ(8) = 4;(1,3,5,7与8互质)

φ(7) = 6;(1,2,3,4,5,6与7互质)

欧拉函数的特性:

1.如果n本身是一个质数(也就是说n本身除了1和自己不被任何数整除,例如7)

那么φ(n) = n - 1; 比如φ(7) = 7 - 1 = 6;

2.如果n能够分解成两个质数(a,b)的乘积(例如15 可以 分解成 3 * 5 ,而3和5是质数)

那么φ(n) = φ(a) * φ(b);

由于a是质数,b也是质数,所以φ(a) = a - 1,φ(b) = b - 1;(根据第一条)

那么我们可以推论得出 φ(n) = (a - 1) * (b - 1);

欧拉定理:

如果两个正整数m和n互质,那么m的φ(n)次方减去1,可以被n整除.

公式: m^φ(n) % n == 1;

即是m的φ(n)次方模以 n 恒等于1.

例如:3 和 5  互质,那么 3^φ(5) % 5 == 1.也就是说 3 ^ 4 % 5 == 1; 

费马小定理:(我一直觉得这个定理是废话)

欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。

就是说: m^φ(n) % n == 1,当n是质数的时候 m^φ(n) % n = m^(n - 1) % n == 1.

欧拉定理公式转换:

由于欧拉定理我们知道:

m^φ(n) % n == 1.

而1^k 还是等于 1. 那么 也就是说 m^φ(n) % n = (m^φ(n) % n)^k = m ^ (k * φ(n) ) % n == 1.

第一步转换结果

我们在这个等式基础上左右乘以m.也就是说 m ^ (k * φ(n) ) % n = m ^ (k * φ(n)  + 1) % n == m.

第二步转换结果

最终转换结果我们且先记下,先看下模反元素.

模反元素:

如果两个正整数e和x互质,那么一定能够找到一个整数d,使得e * d  - 1可以整除 x.那么也就可以说,d就是e相对于x的模反元素.

我们可以记为:e * d % x == 1.

变换: 既然 e * d % x == 1.那么 e * d == k * x + 1.(k为某个可计算出来的正整数).

举例:

如 3 和 5 互质 那么 3 * d  = k *  5 + 1. d 可以为 4, k 为 16.

观察

e * d = k * x + 1. 等式右边 的 k * x + 1 跟 欧拉定理公式变化的最后一步 k * φ(n) + 1是一致的.

那么也就可以推论得出:

m ^ (k * φ(n)  + 1) % n  = m ^ (k * x + 1) % n = m ^( e * d )  % n == m.

即是:

m ^( e * d )  % n == m.

最终变换公式

这个公式的满足条件:

首先这个公式里的k * x + 1 被替代成 k * φ(n) + 1.故而x 是这个公式里的φ(n).

所以这个公式:

1.d 要是e 相对于 φ(n) 的模反元素.(所以e也相对于φ(n)互质)

2.m要小于n.

迪菲赫尔曼密钥交换:

客户端和服务器分别取一个随机数13和15

在上图中,客户端和服务器约定了一个数17得到它的源根3.分别各随机出一个值13和15.

1.客户端通过公式计算得到6发送给服务器.服务器通过公式计算得到值12发送给客户端.

2.第三方在网络中窃取到6和12.

3.客户端得到服务器的数据6.通过6套入公式中得到值10.服务器得到客户端发送的数据12,套入公式中同样得到值10.

4.此时信息发送完毕!

交换原理:

回到之前的上图 客户端在随机出13后,通过3 ^ 13 % 17 得到12,此时服务器 接收到12.通过12 ^ 15 % 17 = 10.而服务器 在随机出15后,通过3 ^ 15 % 17 得到6 发送给客户端,客户端拿到6后 通过 6 ^ 13 % 17 同样也得到10

信息交换

我们可以看到 

客户端这里计算了 (3 ^ 15  % 17) ^13 %17  = 3 ^ (15 * 13) % 17 = 10.

tag: (3 ^ 15  % 17)  是服务器给的

服务器这里计算了 (3 ^ 13  % 17) ^15 %17  = 3 ^ (13 * 15) % 17 = 10.

tag:  (3 ^ 13  % 17)   是客户端给的

信息交换

也就是说之前的客户端和服务器 将 m ^(e * d) % n 的公式成功拆分成了两部分:

m ^ e % n = C.(加密)

C ^ d % n = m.(解密)

Nice!! 到这里 我们就可以模拟出一个完整的RSA加解密流程了.

公式说明:

m ^ e % n = C.(加密)

C ^ d % n = m.(解密)

在上述公式中,e和n 是公钥. d 和 n 是私钥.C是密文,m是明文.

明文在通过公钥加密成密文C. 而C通过私钥解密成明文m.

知道原理后,那么请问我们如果要破解RSA应该怎么做?

如果我们要破解RSA,首先我们掌握的信息有密文C,公钥e和n.未知的则是私钥d和n以及明文m.因为n是公钥中携带的 所以我们要知道明文m,首先要知道私钥的d.已知d是公钥中的e相对于φ(n)的模反元素,所以要求得d需要知道φ(n).而n我们是已知的,如果要求φ(n),需要将n因式分解将n分解成两个质数p1,p2通过公式 φ(n) = (p1 - 1)*(p2 - 1).来求出φ(n).最终通过φ(n)找到模反元素私钥d.

但是事实是,这个n一般的值都特别大,对一个大整数n进行因式分解,计算量相当恐怖,目前人类已经分解的最大整数是232个十进制位，768个二进制位.

而当今我们为了确保信息的安全,采用RSA加密的通常是1024个二进制位或者2048个二进制位.所以相对而言,采用RSA加密的信息一般是安全的.

在MAC下使用终端来演示RSA:

在MacOS系统中一般使用内置OpenSSL(开源密码库)来进行终端运行.

常用命令

命令演示:

openssl genrsa -out private.pem 1024.(生成一个1024个二进制位的私钥)

openssl rsa -in private.pem -pubout -out public.pem.(根据私钥导出公钥)

加密:

openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt

解密:

openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt

RSA的特性:

由于RSA计算量比较大,所以效率比较低,但是因为公钥私钥分开,所以安全系数比较高.

通常我们用RSA加密一些数据量小的文件,如果数据量比较大,那么我们更多的会考虑对称加密算法比如DES,3DES,AES.

所以我们更多的用RSA加密对称加密的密钥或者用于数字签名.