RSA加密的数学原理

2021-04-10 本文已影响0人 spyn_n

RSA非对称加密概述

该加密方式需要两个秘钥：公开的秘钥简称公钥（publickey）和私钥（privatekey）。公钥加密，私钥解密；私钥加密，公钥解密。

欧拉函数

求某个正整数内有多少个与之互质的数的个数，我们叫欧拉函数，用φ(n)表示；
如：φ(8), 8以内的数有：1、2、3、4、5、6、7，这7个数与8互质的有：1、3、5、7共4个，所以φ(8) = 4。
如果n是个质数，那么φ(n) = n-1。
还有一种特殊情况，如果n可以分解为A * B，并且A和B是互质的关系，那么φ(n) = φ(A * B) = φ(A) * φ(B) = (A-1) * (B-1)。

补充定理

人类伟大的数学家经过一代又一代才验证的公式，我们只需记住，作为我们的基础公式去推导（站在巨人的肩膀上），就好比如1+1=2在某个特定的领域就是真理，我们无需验证，也毋庸置疑。

定理	公式	备注
欧拉定理	m^φ(n) mod n ≡ 1	如果两个正整数m和n互质，那么m的φ(n)次方减1，能被n整除。
费马小定理	m^(n-1) mod n ≡ 1	欧拉定理的特殊情况，n为质数时
模反元素	e * d mod x ≡ 1 或 e * d ≡ k* x + 1	e与x互质，d是e对x的模反元素
条件m<n时	m^k*φ(n) mod n ≡ 1	欧拉定理中，当m<n时，使得公式成立

推导过程

迪菲赫尔曼秘钥交换

逻辑Hank笔记

客户端随机生成一个数字 $\color{#006400}{13}$ ，服务器随机生成一个数字 $\color{#006400}{15}$ ，客户端通过一定的算法（该算法只有服务器和客户端知道）3¹³ mod 17 = 12运算得到一个数12，发送给服务器，服务器拿到数12，通过一定算法（12¹⁵ mod 17 = 10）此时10可以认为是明文。服务器用随机生成的15通过一定的运算3¹⁵ mod 17 = 6，得到6发送给客户端，同样的客户端拿到6,进行6¹³ mod 17 = 10运算，拿到明文。客户端和服务器只进行交换了一个无关的6和12就达到交换明文10的目的。尽管第三方可能截获数据传输，拿到6和12，但是除非知道算法，否则很难破解，这就是著名的迪菲赫尔曼秘钥交换。
3 ^(13*15) mod 17 = 10 = 3 ^(15*13) mod 17

∴ m ^e mod n = C
C ^d mod n = m ^(e*d) mod n

当且仅当m^e*d mod n ≡ m (m < n,且d是e对φ(n)的模反元素)
∴➡得到☞ m ^e mod n = C ----加密
C ^d mod n = m ----解密

说明	备注
公钥	n和e
私钥	n和d
明文	m
密文	C

一般n会很大，所以要求φ(n)不容易，最简单的方式就是n可以因式分解成两个很大的互质的数p1，p2，这样φ(n) = (p1 - 1) * (p2 - 1)。根据公式推导过程φ(n) = x，所以根据模反元素，可以求得e，d，也就得到了公钥和私钥。

RSA安全性

根据上面的推理，RSA的关键因素是：p1，p2，e，d，n，φ(n)。要知道私钥的d，就要知道e，φ(n)，要知道φ(n)，就要知道p1，p2，又因为n是很大，所以要因式分解到正确的p1，p2是很难的，就保证了其RSA的安全性。因为数据大，速度会比较慢，不适合用户大数据的加密。