纯JavaScript实现RSA加密库：从大数运算到PKCS#1填充

1. 项目概述：为什么我们需要一个纯JavaScript的RSA加密库？

在Web应用开发中，数据安全传输是一个绕不开的核心议题。无论是用户登录凭证、支付信息，还是敏感的业务数据，在从客户端发往服务器的过程中，如果以明文形式在网络中“裸奔”，其风险不言而喻。HTTPS协议固然是解决传输层安全的黄金标准，但它并非万能。在某些场景下，我们依然需要在应用层对关键数据进行额外的加密处理，实现“端到端”或“客户端到服务端特定接口”的加密。这就是RSA这类非对称加密算法大显身手的地方。

然而，当我们的战场限定在浏览器端时，工具的选择就变得棘手起来。Node.js环境有成熟的crypto模块，但浏览器里的JavaScript运行时是沙盒化的，没有直接的系统级加密接口。虽然现代浏览器提供了Web Crypto API，但其API较为底层，且在不同浏览器中的支持度和细微行为可能存在差异。更重要的是，对于一些需要固定加密流程、特定填充方案（如PKCS#1 v1.5），或者需要在非浏览器环境（如某些特定的JavaScript运行时）中使用的场景，一个纯JavaScript实现、不依赖特定浏览器API的RSA库就显得尤为珍贵。

我这次要分享的，就是基于JavaScript从头实现一个RSA加密库的经验。这个库的目标是：不依赖任何原生加密接口，完全在JavaScript层面实现RSA算法的关键步骤，包括密钥生成、加密、解密、签名和验签。它可能不适合对性能要求极高的高频加密场景，但对于理解RSA原理、进行教学演示、或在某些受限制的环境下提供加密能力，具有不可替代的价值。通过这个项目，你不仅能得到一个可用的工具，更能深入理解大数运算、模幂计算、素数生成等密码学背后的核心机制。

2. RSA算法核心原理与JavaScript实现的挑战

在动手写代码之前，我们必须吃透RSA算法的“三板斧”：密钥生成、加密和解密。这不仅仅是调用API，而是要理解其数学本质，并思考如何在JavaScript中实现这些数学运算。

2.1 RSA算法的数学基石

RSA的安全性建立在“大数分解难题”之上。简单来说，给你两个非常大的质数p和q，把它们相乘得到n很容易；但反过来，给你这个巨大的n，让你找出原来的p和q，在现有计算能力下几乎不可能。整个算法就围绕这个n展开。

密钥生成过程可以分解为以下几步：

1. 选择两个大质数：随机生成两个足够大的质数p和q。这里的“足够大”通常指1024位或2048位二进制数，对应着约308位或617位的十进制数。这是安全的基础。
2. 计算模数n：n = p * q。n的长度就是密钥长度（如2048位）。n会被公开，作为公钥的一部分。
3. 计算欧拉函数φ(n)：φ(n) = (p-1) * (q-1)。这个值必须保密，它决定了后续密钥对的关系。
4. 选择公钥指数e：选择一个整数e，满足1 < e < φ(n)，且e与φ(n)互质（最大公约数为1）。通常使用固定值65537(0x10001)，因为它二进制表示中1很少，能优化加密运算速度，且安全性经过充分验证。
5. 计算私钥指数d：计算d，使得(d * e) % φ(n) = 1。也就是说，d是e在模φ(n)下的模逆元。这个d就是私钥的核心，必须严格保密。

至此，我们得到了：

• 公钥：由(n, e)组成。
• 私钥：由(n, d)组成。有时也会保存p,q,d等用于加速运算。

加密与解密过程：

• 加密（用公钥）：对于明文消息m（需要先转换为一个小于n的整数），计算密文c = m^e mod n。
• 解密（用私钥）：对于密文c，计算明文m = c^d mod n。

公式看似简单，但魔鬼藏在细节里。m^e或c^d这两个幂运算，当指数e或d是几百位的大数时，直接计算的结果将是天文数字，远超任何编程语言中普通整数类型的表示范围。因此，核心挑战在于实现高效的大数运算和模幂运算。

2.2 JavaScript实现的核心挑战

JavaScript（ES2020之前）只有一种数字类型Number，即双精度浮点数，它能安全表示的整数范围仅在-(2^53 -1)到2^53 -1之间。对于RSA所需的大整数，这远远不够。

挑战一：大数表示我们必须用其他方式表示大整数。最常用的方法是使用数组。例如，将一个很大的十进制数或二进制数，按固定位数（如32位或16位）分割，存储在一个数组中。数组的每个元素称为一个“字”。这样，我们就可以模拟手工计算的方式，实现大数的加、减、乘、除、模运算。这就是所谓的“大数库”基础。

挑战二：模幂运算优化直接计算m^e mod n会先得到一个无比巨大的中间结果，然后再取模，这在时间和空间上都是灾难。必须使用优化算法。最经典的是快速模幂算法，它基于二进制展开和平方乘思想：

// 伪代码思路 function modPow(base, exponent, modulus) { let result = 1n; // 假设这里是大整数 base = base % modulus; while (exponent > 0) { // 如果当前二进制位为1 if (exponent & 1) { result = (result * base) % modulus; } // 移到下一位 exponent = exponent >> 1; base = (base * base) % modulus; } return result; }

这个算法将时间复杂度从 O(e) 降低到了 O(log e)，是工程实现的关键。

挑战三：素数生成与检验生成大质数p和q是一个概率性过程。通常采用“随机生成大奇数 -> 进行素性检测”的循环。素性检测算法有很多，从简单的试除法到复杂的米勒-拉宾概率测试。对于RSA，米勒-拉宾测试是实际应用中的标准，因为它速度快，且可以将误差概率控制在极低的范围内（例如进行k轮测试，误判概率小于4^{-k}）。

挑战四：性能瓶颈纯JavaScript实现的大数运算，尤其是乘法和模运算，相比原生代码（如C语言）或浏览器的Web Crypto API，速度会慢几个数量级。因此，我们的库定位要清晰：适用于非性能敏感场景。在实现时，需要精心设计算法，比如使用Karatsuba算法优化大数乘法，使用Barrett约减优化模运算。

注意：在真实的、对安全性和性能有严格要求的线上环境中，强烈建议使用浏览器原生的Web Crypto API或经过严格审计的成熟库。这个纯JS实现项目的主要价值在于教育、原理验证和特定受限环境。

3. 库的整体架构与核心模块设计

基于以上分析，我们可以将库划分为几个核心模块，每个模块职责单一，便于测试和维护。

3.1 模块划分与职责

1. 大数运算模块：这是整个库的基石。它需要实现一个BigInt类（为避免与ES2020原生BigInt混淆，我们命名为BigInteger），并提供以下核心方法：

   • 构造函数：从字符串（十进制/十六进制）、字节数组或另一个大数初始化。
   • 基本运算：add,subtract,multiply,divide,mod。
   • 比较运算：compareTo,equals。
   • 位运算：shiftLeft,shiftRight,and,or,xor。
   • 辅助方法：toByteArray,toString,isProbablePrime（内部会调用米勒-拉宾测试）。

2. 随机数生成模块：密码学的安全源于随机性。我们需要一个可靠的随机数生成器来生成密钥种子和大质数候选。在浏览器中，可以使用window.crypto.getRandomValues。为了兼容非浏览器环境，需要提供一个备用方案（如使用伪随机数生成器，但安全性会降低）。

3. RSA核心算法模块：这个模块基于大数模块，实现RSA的数学逻辑。

   • generateKeyPair(bitLength)：生成指定长度的RSA密钥对。内部流程包括：生成两个大质数、计算n和φ(n)、选择e、计算d。
   • encrypt(publicKey, message)：使用公钥(n, e)加密消息。消息需要先进行填充（如PKCS#1 v1.5）并转换为大整数。
   • decrypt(privateKey, ciphertext)：使用私钥(n, d)解密密文。
   • sign(privateKey, messageHash)：使用私钥对消息摘要进行签名（本质是用私钥加密摘要）。
   • verify(publicKey, messageHash, signature)：使用公钥验证签名（本质是用公钥解密签名并与摘要对比）。

4. 数据编码与填充模块：RSA算法本身操作的是大整数。实际应用中，我们需要处理字符串、字节数组。这个模块负责：

   • 填充：直接加密小整数或不填充的数据是不安全的。PKCS#1 v1.5填充或OAEP填充是必须的，它们能增加随机性，防止某些攻击。
   • 编码：在加密前，将UTF-8字符串转换为字节数组，并按照填充规则构造成一个小于n的大整数。解密后，执行反向操作，提取出原始字节数组，再解码为字符串。

3.2 密钥的存储与格式

生成的密钥对需要以某种格式导出，方便存储和交换。常见的格式有：

• PKCS#1：传统格式，仅包含密钥的数学组成部分（n, e, d, p, q等）。
• PKCS#8：更通用的格式，可以封装私钥和公钥信息。
• SPKI：用于公钥。
• PEM：将上述DER编码的二进制数据，进行Base64编码，并加上-----BEGIN PUBLIC KEY-----这样的头尾标识，形成文本格式。

我们的库可以选择实现最简单的导出方式：将n,e,d等大数转换为十六进制字符串或Base64字符串，以JSON对象形式输出。更复杂的格式可以在后续扩展。

// 示例：简化的密钥对结构 const keyPair = { publicKey: { n: "AABBCC...", // 十六进制字符串 e: "010001" // 通常就是65537的十六进制 }, privateKey: { n: "AABBCC...", d: "DDEEFF...", p: "...", // 可选，用于加速解密 q: "..." // 可选 } };

4. 关键代码实现与难点剖析

接下来，我们深入到几个最关键部分的代码实现，并讨论其中的细节和“坑”。

4.1 大数运算的实现：以乘法和模运算为例

我们使用一个Uint32Array来存储大数的各个“字”（32位块），低位在前（小端序）。这是为了便于进行进位处理。

大数乘法（基础版）：最朴素的方法是模拟竖式乘法，时间复杂度为O(n²)。对于我们的教学库，可以先实现这个版本以保证正确性。

class BigInteger { constructor(words) { // words: Uint32Array this.words = words; } multiply(other) { const lenThis = this.words.length; const lenOther = other.words.length; const resultWords = new Uint32Array(lenThis + lenOther).fill(0); for (let i = 0; i < lenThis; i++) { let carry = 0; const a = this.words[i]; for (let j = 0; j < lenOther; j++) { // 注意：两个32位数相乘可能产生64位结果 const product = BigInt(a) * BigInt(other.words[j]) + BigInt(resultWords[i + j]) + BigInt(carry); resultWords[i + j] = Number(product & 0xffffffffn); // 取低32位 carry = Number(product >> 32n); // 取高32位作为进位 } resultWords[i + lenOther] = carry; } // 去除高位的0 return new BigInteger(this._trimZeros(resultWords)); } _trimZeros(words) { let i = words.length - 1; while (i > 0 && words[i] === 0) i--; return words.slice(0, i + 1); } }

实操心得：在JavaScript中处理大数乘法时，最大的坑是中间结果的溢出。a * b如果a和b是JavaScript的Number类型，乘积超过2^53就会丢失精度。因此，在计算乘积时，必须先将操作数转换为BigInt，完成计算后，再取模得到32位结果和进位。这是保证计算正确的关键。在性能优化时，可以引入Karatsuba算法，将复杂度降至约O(n^1.585)。

模运算与快速模幂：模运算a mod n通常通过除法实现，而大数除法是运算中最复杂的。一种优化方法是使用“Barrett约减”，它通过预计算一个与模数n相关的常数，将大部分的取模运算转化为乘法和移位，在多次对同一个n取模时（如模幂运算中）能极大提升速度。

快速模幂算法的实现，直接应用了前面提到的“平方乘”思想，但所有运算都必须基于我们自己的BigInteger类。

modPow(exp, modulus) { // 处理指数为0的情况 if (exp.equals(BigInteger.ZERO)) return BigInteger.ONE.mod(modulus); let result = BigInteger.ONE; let base = this.mod(modulus); // 先取模，减少后续运算量 let exponent = exp.clone(); while (exponent.compareTo(BigInteger.ZERO) > 0) { // 检查指数最低位是否为1 if (exponent.isOdd()) { result = result.multiply(base).mod(modulus); } // 指数右移一位（除以2） exponent = exponent.shiftRight(1); // 底数平方 base = base.multiply(base).mod(modulus); } return result; }

4.2 素数生成与米勒-拉宾测试

生成一个bitLength位的大质数，流程如下：

1. 生成一个随机的bitLength位奇数。
2. 用小质数表（比如前1000个质数）进行试除，快速排除明显是合数的候选。这是一个非常有效的预过滤。
3. 对通过预过滤的候选数，进行多轮（例如10-20轮）米勒-拉宾测试。

米勒-拉宾测试原理： 对于一个待测奇数n，将其写成n = d * 2^s + 1（其中d是奇数）。 然后，随机选择一个底数a（2 <= a <= n-2）。 计算x = a^d mod n。 如果x == 1或x == n-1，则本轮测试通过。 否则，将x连续平方s-1次，每次平方后检查是否等于n-1。如果某次等于n-1，则本轮通过；如果始终不等于，则n一定是合数。 通过多轮测试（选择不同的随机a），可以将n是合数的概率降到极低。

isProbablePrime(iterations = 16) { // 处理小质数 if (this.compareTo(BigInteger.TWO) < 0) return false; if (this.equals(BigInteger.TWO) || this.equals(BigInteger.valueOf(3))) return true; if (this.isEven()) return false; // 偶数不是质数 // 快速试除小质数 const smallPrimes = [/* 小质数数组 */]; for (const p of smallPrimes) { if (this.mod(BigInteger.valueOf(p)).equals(BigInteger.ZERO)) { return this.equals(BigInteger.valueOf(p)); } } // 米勒-拉宾测试 // 1. 将 n-1 写成 d * 2^s let d = this.subtract(BigInteger.ONE); let s = 0; while (d.isEven()) { d = d.shiftRight(1); s++; } const nMinusOne = this.subtract(BigInteger.ONE); for (let i = 0; i < iterations; i++) { // 随机选择底数 a, 2 <= a <= n-2 const a = this._randomBigInt(BigInteger.TWO, nMinusOne); let x = a.modPow(d, this); // 使用我们实现的模幂 if (x.equals(BigInteger.ONE) || x.equals(nMinusOne)) { continue; // 本轮通过 } let continueLoop = false; for (let r = 1; r < s; r++) { x = x.multiply(x).mod(this); if (x.equals(nMinusOne)) { continueLoop = true; break; } } if (continueLoop) continue; return false; // 一定是合数 } return true; // 很可能是质数 }

4.3 PKCS#1 v1.5 填充的实现

原始RSA加密（教科书式RSA）有很多弱点。填充方案通过给明文增加结构化和随机化的数据来增强安全性。

加密填充流程： 假设我们的RSA密钥长度是2048位，那么模数n是2048位，能加密的最大数据块长度是256字节 - 填充开销。 PKCS#1 v1.5加密填充格式如下：

00 || 02 || PS || 00 || M

• 00：保证转换后的大整数小于模数n。
• 02：表示这是公钥操作（加密）的填充块。
• PS：非零的伪随机填充字符串，长度至少为8字节，用于增加随机性。
• 00：分隔符。
• M：原始明文消息。

实现时，我们需要生成随机的PS，然后拼接成完整的块，最后将这个字节块转换为一个大整数进行加密。

解密后去除填充： 解密得到大整数，转换回字节数组后，需要解析这个结构：

1. 检查第一个字节是否为0x00。
2. 检查第二个字节是否为0x02。
3. 找到第一个0x00分隔符的位置（从第三个字节开始查找）。
4. 分隔符之后的部分就是原始明文M。
5. 需要验证PS的长度至少为8字节。

注意事项：PKCS#1 v1.5填充在实现上容易受到“填充预言攻击”。虽然这种攻击在实际网络环境中条件较为苛刻，但对于新项目，更推荐使用安全性更强的OAEP填充。由于OAEP实现更复杂（需要哈希函数和掩码生成函数），在初版库中可以先实现v1.5，但必须明确告知使用者其潜在风险。

5. 完整使用示例与API设计

一个设计良好的库，应该提供清晰、简洁的API。下面是我们这个RSA库可能的使用方式。

// 1. 生成密钥对 (这是一个非常耗时的操作，在浏览器中可能阻塞UI，务必在Web Worker中执行) const rsa = new JSRSALib(); const keyPair = await rsa.generateKeyPair(1024); // 生成1024位密钥，线上建议2048位以上 console.log('公钥n:', keyPair.publicKey.n); console.log('公钥e:', keyPair.publicKey.e); console.log('私钥d:', keyPair.privateKey.d); // 2. 加密 const publicKey = keyPair.publicKey; const message = "这是一条秘密消息"; const encryptedMessage = rsa.encrypt(publicKey, message, 'PKCS1v1_5'); console.log('加密后(Base64):', encryptedMessage); // 输出Base64编码的密文 // 3. 解密 const privateKey = keyPair.privateKey; const decryptedMessage = rsa.decrypt(privateKey, encryptedMessage, 'PKCS1v1_5'); console.log('解密后:', decryptedMessage); // 应等于原始消息 // 4. 签名与验签 const dataToSign = "重要合同"; const hash = sha256(dataToSign); // 先计算消息的哈希值，这里假设有一个SHA256函数 const signature = rsa.sign(privateKey, hash, 'PKCS1v1_5'); console.log('签名:', signature); const isValid = rsa.verify(publicKey, hash, signature, 'PKCS1v1_5'); console.log('验签结果:', isValid); // true

API设计要点：

• 异步生成：generateKeyPair应返回一个Promise，因为生成大质数非常耗时，避免阻塞主线程。
• 编码选项：encrypt/decrypt方法应支持输入/输出为字符串（UTF-8/Base64）或字节数组（Uint8Array）。
• 填充指定：显式指定填充方案，让使用者清楚自己使用的算法。
• 错误处理：对密钥格式错误、消息过长、填充错误等情况，应抛出明确的异常。

6. 性能优化与安全考量

6.1 性能瓶颈分析与优化方向

纯JavaScript RSA库的性能瓶颈主要集中在大数运算，尤其是模幂运算。以下是一些优化思路：

1. 使用BigInt（ES2020）：如果目标环境支持ES2020，可以直接使用原生的BigInt类型。它的运算由引擎底层优化，速度远超我们自己实现的数组模拟。这可以作为一个“高性能”分支。但需要注意，BigInt的位运算（如取模%）对于非常大的整数可能仍有性能问题，且与旧环境不兼容。
2. 算法优化：
   • 乘法：实现Karatsuba算法或更高级的Toom-Cook、FFT算法来处理超大数乘法。
   • 模运算：实现蒙哥马利约减算法。它通过将数字转换到一种特殊的表示形式，使得模乘运算可以避免昂贵的除法，是高性能模幂运算的核心。
   • 素数生成：使用更高效的随机数生成和更智能的候选数筛选（如只生成可能为质数的特定形式，如k * 2^m + 1的候选数）。
3. 预计算与缓存：对于私钥操作，如果保存了p,q,dP,dQ,qInv等值，可以使用中国剩余定理来加速解密和签名，速度能提升3-4倍。
4. Web Worker：将耗时的密钥生成、加解密操作放入Web Worker，避免阻塞浏览器主线程，保持页面响应。

6.2 安全注意事项与“坑”点实录

自己实现密码学库，安全是重中之重。以下是一些必须警惕的陷阱：

1. 随机数质量：Math.random()绝对不可用于密码学！它是不安全的伪随机数生成器。在浏览器中，必须使用crypto.getRandomValues()。在Node.js中，使用crypto.randomBytes()。
2. 侧信道攻击：我们的代码运行在JavaScript虚拟机中，时间攻击和缓存攻击风险相对较低，但仍需注意。例如，在快速模幂算法中，根据指数位的不同，执行result = (result * base) % modulus的时机也不同，理论上可能泄露指数信息。可以考虑使用“恒定时间”实现的算法，但JS环境很难做到真正的恒定时间。
3. 密钥管理：私钥绝对不能以任何形式暴露在客户端。这个库生成的密钥对，如果用于客户端加密，那么公钥可以发给客户端用于加密，但解密必须在持有私钥的服务端进行。切勿在客户端用私钥解密！那等同于把钥匙给了别人。
4. 填充方案选择：如前所述，PKCS#1 v1.5有已知风险。对于新系统，应优先考虑实现并默认使用OAEP填充。
5. 错误信息泄露：解密或验签失败时，返回的错误信息应尽可能通用（如“解密失败”），而不要透露具体是填充错误还是数据错误，防止攻击者利用错误信息进行攻击。
6. 整数溢出与边界检查：在将字节数组转换为大整数时，必须确保转换后的整数严格小于模数n。所有运算都要进行边界检查，防止意外产生负数或超出范围的值。

7. 常见问题与调试技巧

在开发和使用的过程中，你肯定会遇到各种问题。这里记录了一些典型问题和排查思路。

问题1：加密/解密结果不对，或者解密时抛出“填充错误”。

• 检查数据编码：确保加密前的明文和解密时的密文编码一致。是UTF-8字符串还是Base64？加密函数输出的是十六进制字符串还是Base64？一个常见的错误是，加密时输入字符串，解密时却把Base64字符串当成了原始字节数组处理。
• 检查填充方案：加密和解密使用的填充方案必须完全相同。如果你用PKCS1_OAEP加密，就必须用PKCS1_OAEP解密。
• 检查密钥是否匹配：确认解密使用的私钥正是加密所用公钥对应的私钥。可以尝试用公钥加密一个非常短的消息（如数字42），然后用私钥解密看是否能还原。
• 逐步调试：将加密过程拆解：输出填充后的字节数组、转换后的大整数、模幂运算后的密文大整数，再转换回字节数组。对比每一步的结果是否符合预期。解密过程同理。

问题2：密钥生成速度极慢，尤其是2048位以上。

• 这是正常现象。纯JS生成大质数本身就是计算密集型任务。1024位密钥在普通电脑上可能需要几秒，2048位可能需要几十秒甚至更久。
• 优化建议：
  • 确保使用了高效的米勒-拉宾测试，并且用小质数表进行了预筛选。
  • 将生成过程放入Web Worker。
  • 考虑降低素性测试的迭代次数（如从16次降到10次），但这会略微增加误判概率，需权衡。
  • 终极方案：对于生产环境，应在服务端生成密钥，或使用原生Web Crypto API (window.crypto.subtle.generateKey)。

问题3：在Node.js环境中运行报错，提示window未定义。

• 我们的库可能使用了浏览器特有的window.crypto。需要做环境检测。

  function getRandomBytes(length) { if (typeof window !== 'undefined' && window.crypto && window.crypto.getRandomValues) { const array = new Uint8Array(length); window.crypto.getRandomValues(array); return array; } else if (typeof require !== 'undefined') { // Node.js 环境 const crypto = require('crypto'); return crypto.randomBytes(length); } else { throw new Error('找不到安全的随机数生成器'); } }

问题4：如何与其它语言（如Java/Python）生成的RSA密钥互通？

• 密钥格式：这是互通的关键。你需要将密钥导出为标准格式（如PKCS#8 PEM）。我们的简易JSON格式其他语言无法识别。你需要实现PEM编码导出功能。
• 填充方案：确保两端使用完全相同的填充方案。PKCS#1 v1.5是互通性最好的。
• 数据格式：加密后的数据，通常以字节数组或Base64字符串传输。确保发送和接收方对数据格式的约定一致。

问题5：消息长度限制是多少？

• 对于RSA，能加密的明文最大长度（字节）由密钥长度和填充方案决定。
• 公式大致为：最大明文长度 = (密钥位数 / 8) - 填充开销。
• 例如，2048位密钥（256字节）：
  • PKCS#1 v1.5 填充开销至少11字节，所以最大明文约为245字节。
  • OAEP 填充（使用SHA-1）开销更多，明文长度更短。
• 如果需要加密更长的数据，标准做法是：
  1. 生成一个随机的对称密钥（如AES密钥）。
  2. 用这个对称密钥加密你的长数据。
  3. 用RSA公钥加密这个对称密钥。
  4. 将加密后的对称密钥和加密后的数据一起发送。 这称为“混合加密”系统，结合了非对称加密的密钥分发优势和对称加密的速度优势。

实现一个完整的、安全的、高效的RSA库是一个庞大的工程。本文带你走完了核心原理、关键实现和主要“坑点”的全程。记住，这个项目的首要价值是学习和理解。当你真正理解了每一行代码背后的数学和工程考量，你不仅拥有了一个工具，更获得了洞察更复杂密码学系统的基础能力。如果在实际产品中需要RSA，请务必选择经过时间检验的成熟库，如node-rsa、jsencrypt或直接使用Web Crypto API。