因为要考网安所以来学rsa
一开始没了解不知道，后来带着公式自己算了算发现还挺神奇，后面一定有很庞大的数学原理支持，但是发现看不太懂，本文简单介绍下rsa的计算方法罢
我们需要什么？
| 符号 | 含义 | 来源 | 主要用途 | 公开性 |
|---|---|---|---|---|
| p, q | 两个大质数 | 随机挑选的大质数 | 用来算 n 和 φ(n) | ❌ 保密 |
| n | 模数 (modulus) | (n = p*q) | 加密/解密都要对 n 取模 | ✅ 公开 |
| φ(n) | 欧拉函数 φ(n) | (φ(n) = (p-1)(q-1))（p,q 是质数时） | 用来求 d（e 的模逆） | ❌ 不公开 |
| e | 公钥指数 (public exponent) | 选一个满足数字e (gcd(e,φ(n)) = 1) | 加密、验证签名 | ✅ 公开 |
| d | 私钥指数 (private exponent) | 解方程（e*d%φ(n)=1） 得到 | 解密、生成签名 | ❌ 保密 |
| m | 明文 | - | 待加密数据 | ❌ 保密 |
| c | 密文 | - | 加密后数据 | ✅ 公开 |
计算方式
假设已知p，q和e
首先算出n
n=p*q
然后算出
φ(n) = (p-1)(q-1)
接下来计算d，解方程即可 e*d%φ(n)=1 //计算的时候用φ(n)乘以(1,2,3…..)（枚举）加上1然后看看枚举的哪一个乘数可以使其除以e是整数，就能得到d，（计算的时候一般会给的数好算一些，正常应用场景这一步是很难进行的qwq
于是我们可以得到公钥和私钥
公钥：（e,n）
私钥：（d,n）
加密过程
c=(m**e)%n
解密过程
m=(c**d)%n
看个例子
令p=11，q=5，e=3
于是乎，n=p*q=55
φ(n)=(p-1)(q-1)=10*4=40
计算e*d % φ(n)=1 得到d=27
公钥：（3，55）；私钥：（27，55）
加密：假设明文m=8 ；c=m^e%n=8^3%55=17
解密 c=17 ；m=c^d%n=17^27%55=8
以防你不信，贴个结果(真神奇吧
