纯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展开。密钥生成过程可以分解为以下几步选择两个大质数随机生成两个足够大的质数p和q。这里的“足够大”通常指1024位或2048位二进制数对应着约308位或617位的十进制数。这是安全的基础。计算模数nn p * q。n的长度就是密钥长度如2048位。n会被公开作为公钥的一部分。计算欧拉函数φ(n)φ(n) (p-1) * (q-1)。这个值必须保密它决定了后续密钥对的关系。选择公钥指数e选择一个整数e满足1 e φ(n)且e与φ(n)互质最大公约数为1。通常使用固定值65537(0x10001)因为它二进制表示中1很少能优化加密运算速度且安全性经过充分验证。计算私钥指数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实现的核心挑战JavaScriptES2020之前只有一种数字类型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 模块划分与职责大数运算模块这是整个库的基石。它需要实现一个BigInt类为避免与ES2020原生BigInt混淆我们命名为BigInteger并提供以下核心方法构造函数从字符串十进制/十六进制、字节数组或另一个大数初始化。基本运算add,subtract,multiply,divide,mod。比较运算compareTo,equals。位运算shiftLeft,shiftRight,and,or,xor。辅助方法toByteArray,toString,isProbablePrime内部会调用米勒-拉宾测试。随机数生成模块密码学的安全源于随机性。我们需要一个可靠的随机数生成器来生成密钥种子和大质数候选。在浏览器中可以使用window.crypto.getRandomValues。为了兼容非浏览器环境需要提供一个备用方案如使用伪随机数生成器但安全性会降低。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)使用公钥验证签名本质是用公钥解密签名并与摘要对比。数据编码与填充模块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位的大质数流程如下生成一个随机的bitLength位奇数。用小质数表比如前1000个质数进行试除快速排除明显是合数的候选。这是一个非常有效的预过滤。对通过预过滤的候选数进行多轮例如10-20轮米勒-拉宾测试。米勒-拉宾测试原理 对于一个待测奇数n将其写成n d * 2^s 1其中d是奇数。 然后随机选择一个底数a2 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 || M00保证转换后的大整数小于模数n。02表示这是公钥操作加密的填充块。PS非零的伪随机填充字符串长度至少为8字节用于增加随机性。00分隔符。M原始明文消息。实现时我们需要生成随机的PS然后拼接成完整的块最后将这个字节块转换为一个大整数进行加密。解密后去除填充 解密得到大整数转换回字节数组后需要解析这个结构检查第一个字节是否为0x00。检查第二个字节是否为0x02。找到第一个0x00分隔符的位置从第三个字节开始查找。分隔符之后的部分就是原始明文M。需要验证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); // trueAPI设计要点异步生成generateKeyPair应返回一个Promise因为生成大质数非常耗时避免阻塞主线程。编码选项encrypt/decrypt方法应支持输入/输出为字符串UTF-8/Base64或字节数组Uint8Array。填充指定显式指定填充方案让使用者清楚自己使用的算法。错误处理对密钥格式错误、消息过长、填充错误等情况应抛出明确的异常。6. 性能优化与安全考量6.1 性能瓶颈分析与优化方向纯JavaScript RSA库的性能瓶颈主要集中在大数运算尤其是模幂运算。以下是一些优化思路使用BigIntES2020如果目标环境支持ES2020可以直接使用原生的BigInt类型。它的运算由引擎底层优化速度远超我们自己实现的数组模拟。这可以作为一个“高性能”分支。但需要注意BigInt的位运算如取模%对于非常大的整数可能仍有性能问题且与旧环境不兼容。算法优化乘法实现Karatsuba算法或更高级的Toom-Cook、FFT算法来处理超大数乘法。模运算实现蒙哥马利约减算法。它通过将数字转换到一种特殊的表示形式使得模乘运算可以避免昂贵的除法是高性能模幂运算的核心。素数生成使用更高效的随机数生成和更智能的候选数筛选如只生成可能为质数的特定形式如k * 2^m 1的候选数。预计算与缓存对于私钥操作如果保存了p,q,dP,dQ,qInv等值可以使用中国剩余定理来加速解密和签名速度能提升3-4倍。Web Worker将耗时的密钥生成、加解密操作放入Web Worker避免阻塞浏览器主线程保持页面响应。6.2 安全注意事项与“坑”点实录自己实现密码学库安全是重中之重。以下是一些必须警惕的陷阱随机数质量Math.random()绝对不可用于密码学它是不安全的伪随机数生成器。在浏览器中必须使用crypto.getRandomValues()。在Node.js中使用crypto.randomBytes()。侧信道攻击我们的代码运行在JavaScript虚拟机中时间攻击和缓存攻击风险相对较低但仍需注意。例如在快速模幂算法中根据指数位的不同执行result (result * base) % modulus的时机也不同理论上可能泄露指数信息。可以考虑使用“恒定时间”实现的算法但JS环境很难做到真正的恒定时间。密钥管理私钥绝对不能以任何形式暴露在客户端。这个库生成的密钥对如果用于客户端加密那么公钥可以发给客户端用于加密但解密必须在持有私钥的服务端进行。切勿在客户端用私钥解密那等同于把钥匙给了别人。填充方案选择如前所述PKCS#1 v1.5有已知风险。对于新系统应优先考虑实现并默认使用OAEP填充。错误信息泄露解密或验签失败时返回的错误信息应尽可能通用如“解密失败”而不要透露具体是填充错误还是数据错误防止攻击者利用错误信息进行攻击。整数溢出与边界检查在将字节数组转换为大整数时必须确保转换后的整数严格小于模数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开销更多明文长度更短。如果需要加密更长的数据标准做法是生成一个随机的对称密钥如AES密钥。用这个对称密钥加密你的长数据。用RSA公钥加密这个对称密钥。将加密后的对称密钥和加密后的数据一起发送。 这称为“混合加密”系统结合了非对称加密的密钥分发优势和对称加密的速度优势。实现一个完整的、安全的、高效的RSA库是一个庞大的工程。本文带你走完了核心原理、关键实现和主要“坑点”的全程。记住这个项目的首要价值是学习和理解。当你真正理解了每一行代码背后的数学和工程考量你不仅拥有了一个工具更获得了洞察更复杂密码学系统的基础能力。如果在实际产品中需要RSA请务必选择经过时间检验的成熟库如node-rsa、jsencrypt或直接使用Web Crypto API。