RSA 算法原理

RSA 算法是非对称加密算法中的一个重要应用

RSA 算法由 5 部分组成

• 原文（Message）：需要加密的信息，数字、文字、视频等
  • 用 M 表示
• 密文（Ciphertext）: 加密后得到的信息
  • 用 C 表示
• 公钥：（Public Key）
  • 用 PU 表示
• 私钥：（Private Key）
  • 用 PR 表示
• 加密算法（Encryption)：若 E(x) 为加密算法，加密的过程可以理解为 C = E(M)
• 解密算法（Decryption)：若 D(x) 为解密算法，解密的过程可以理解为 M = D(C)

计算公钥和私钥步骤

• 选择两个互质数 p，q
  • 互质数：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）
• 将 p q 相乘，记为 n = p * q
• 计算 n 的欧拉函数 φ(n) ，记为：φ(n) = (p-1)(q-1)
  • 欧拉函数：任意给定正整数 N，在小于等于 N 的正整数之中，有多少个与n构成互质关系？计算这个值的方法就叫做欧拉函数
• 随机选择一个整数 e，满足两个条件：1. φ(n) 与 e 互质 2. 1 < e < φ(n)
• 计算 d, ed = 1 mod φ(n)，可以用扩展欧几里得算法求解
• 最终把 (e, n) 封装称公钥，(d, n) 封装称私钥

加密

用公钥（e, n）加密，给定一段文本 M
则：C = M^e mod n

解密

用私钥（d，n）解密
则：M = C^d mod n

举个例子

let p =61, q = 53;
let n = p * q; //n = 3233

let phi = (p-1)(q-1); //phi = 3120
let e = findCoprime(phi);//e=17

let d = (1 mod(phi))/e; //d = 2753

public_key = (e=17, n=3233);
private_key = (d=2753, n=3233);

//Given a plaintext M = 123
C = (123^17) % 3233 = 855;
M = (855^2753)%3233 = 123;

参考
What is the RSA algorithm?
RSA 算法的加密原理是什么?