RustCrypto RSA源码深潜下Montgomery模幂、随机Blinding与CRT解密实现原理【免费下载链接】RSARSA implementation in pure Rust项目地址: https://gitcode.com/gh_mirrors/rsa1/RSA本文深入解析 RustCrypto RSA 加密库纯 Rust 实现的 RSA 密码学库解密路径中的三大核心机制Montgomery 模幂消除大数除法、随机 Blinding防计时侧信道与CRT 中国剩余定理加速解密约 4 倍提速。面向想要读懂密码学库内部原理的 Rust 新手全文基于src/algorithms/rsa.rs的真实源码逐段拆解帮你快速看懂这个库快在哪里、安全在哪里。一、解密管线全景三个机制各管一段打开核心文件 src/algorithms/rsa.rsrsa_decrypt函数约 L37-L142的流水线可以拆成三段正好对应本文三个主题阶段做什么防御/加速目标关键代码位置① 前置检查密文长度与大小校验c n防异常输入L45-L51② 随机 Blindingc ← c·r^e mod n记住 r⁻¹防计时侧信道L58-L64③ CRT 或普通模幂优先走 CRT 快路径解密提速约 4 倍L68-L132④ 反 Blindingm ← m·r⁻¹ mod n还原明文L134-L141这些裸 RSA原语只通过 src/hazmat.rs 的hazmat模块对外暴露需在 Cargo.toml 的features中启用hazmat []模块文档里用☢️ HAZARDOUS API反复警告裸 RSA 绝不能直接用于生产加密它只是给 OAEP、PSS 等已经过评审的高级构造做底层积木。普通用户走的是 src/key.rs 中RsaPrivateKey::decrypt/sign这类高层 API。 阅读提示下文提到的BoxedUint是crypto-bigint提供的可变位宽大整数BoxedMontyParams/BoxedMontyForm则是它的 Montgomery 参数与 Montgomery 形式封装——这两个类型是理解后文的钥匙。二、Montgomery模幂把除法变乘加密钥构造时付一次账2.1 为什么模幂是 RSA 的瓶颈RSA 加密 算c m^e mod n解密 算m c^d mod n。对 2048 位模数、指数高达几千位的情况朴素实现要反复做大数乘 大数取模而取模就是大数除法——大数体系里最贵的运算。Montgomery 表示法的核心思想是把参与运算的数提前换币到 Montgomery 域域内的乘法只靠移位、乘加就能完成约简彻底绕开显式除法只有进出域各转换一次。2.2 参数预计算n_params在密钥构造时一次性建好看 src/key.rs 的RsaPublicKey::new_with_max_size约 L233-L243先校验模数n为奇数Montgomery 要求模数与 2 互素然后调用BoxedMontyParams::new(n_odd)生成 Montgomery 参数n_params随密钥对象一起长期保存见RsaPublicKey结构体字段L32-L42。这就是一次付费、处处受益之后所有模幂都复用同一份参数。私钥的 CRT 路径还要再为p、q各建一份见RsaPrivateKey::precomputeL546-L607中的p_params/q_params。2.3 两条模幂入口变长 vs 定长指数rsa.rs里封装了两条进 Montgomery 域的路径L233-L256pow_mod_params先reduce_vartime把底数规约进域再base.pow(exp)按指数实际位长扫描。用于解密时的c^d mod n慢路径。pow_mod_params_vartime_exp_bits改用pow_bounded_exp(exp, exp_bits)按已知的指定位宽扫描循环次数与指数具体取值无关——注释里明确写道指数的位长可能泄漏在时间模式里所以只对公钥加密这种短指数典型 65537即 17 位场景使用。reduce_vartime本体也很精炼L252-L256rem_vartime取余 →resize_unchecked对齐位宽 →BoxedMontyForm::new换入 Montgomery 域。三步完成进币。2.4 一个有意思的旁支从 (n, e, d) 找回 p 和 qfrom_components允许调用方不传素因子此时 src/key.rs 的from_components_innerL353-L415会走recover_primessrc/algorithms/rsa.rs L261-L326按 NIST SP 800-56B 附录 C.2 的确定性算法利用de ≡ 1 (mod λ(n))构造a (de−1)·gcd(n−1, de−1)再解一元二次方程x² − bx n 0求出p、q。也就是说私钥材料本身足以反推出 CRT 加速所需的素数库在导入 PKCS#1/PKCS#8 密钥时测试向量见 tests/examples/pkcs1/ 与 tests/examples/pkcs8/含 2048/4096 位 der/pem 样例会静默完成这件事。三、随机Blinding给计时攻击套上随机噪声3.1 攻击面时间会说话BoxedUint的模幂并非恒定时间实现——指数中 1 的个数会影响执行路径攻击者若能稳定测量每次解密的耗时就可能逐步恢复私钥dREADME 中的 Marvin 攻击正是这类远程计时攻击的实例仓库自带 marvin-toolkit/ 的 Docker 复现环境见 marvin-toolkit/README.md。随机 Blinding 的对策是让每次运算处理的数值都不一样时间噪声自然被抹平。3.2blind解密前先掺沙子L175-L213blind函数的注释把数学原理写得清清楚楚翻译成三步抽随机数r BoxedUint::try_random_mod_vartime(rng, key.n())并用while循环保证r.invert_mod(n)能求出逆元即gcd(r, n) 1对素数模下几乎必然成立计算混淆因子r^e mod n复用 2.3 节的变长指数模幂再c.mul_mod(rpowe, n)得到c c·r^e mod n——注意这等价于先解密再乘上 r因为(m^e·r^e)^d m·r (mod n)安全清零rpowe.zeroize()立刻抹掉中间变量zeroize库避免密钥材料残留在内存里。unblindL216-L231就是收尾一步m·r⁻¹ mod n把沙子里的 r 捞出来。3.3rsa_decrypt_and_check给 CRT 结果加一道防伪校验L156-L172CRT 计算涉及多份预存值任何一份被写坏或被恶意构造的密钥污染都可能导致解密出看似合法的错误明文。因此rsa_decrypt_and_check在解密完成后用公钥把结果再加密一次与原始密文比对不一致即返回Error::Internal。这是解密后验签的经典防御成本是一次公钥模幂很便宜。3.4 敏感数据的生命周期管理库对秘密材料的清理贯穿始终src/key.rs 的RsaPrivateKey实现DropL116-L122析构时d、primes、precomputed全部zeroize()并声明ZeroizeOnDropPrecomputedValuesL126-L157析构时清零dp、dqblind内的rpowe.zeroize()src/algorithms/rsa.rs L203。四、CRT解密两次半尺寸模幂换 4 倍速度4.1 预计算值PrecomputedValues结构体CRT中国剩余定理路径的前提是拿到dp d mod (p−1)、dq d mod (q−1)、qinv q⁻¹ mod p三件套。它们由RsaPrivateKey::precomputesrc/key.rs L546-L607统一算好装进PrecomputedValues { dp, dq, qinv, p_params, q_params }L126-L139——注意qinv直接以BoxedMontyForm存储这样后面用它做乘法可以零转换成本from_components构造密钥时会顺手尝试预计算失败也不影响正确性自动降级走慢路径。4.2 逐步对照代码L68-L132rsa_decrypt先用match判断 CRT 材料是否齐全且不是多素数密钥L66-L75齐全则走快路径// m1 c^dp mod p —— 约 1024 位模上的模幂2048 位密钥为例 c_mod_dp c % p; m1 BoxedMontyForm::new(c_mod_dp, p_params).pow(dp) // m2 c^dq mod q —— 同样半尺寸 c_mod_dq c % q; m2 BoxedMontyForm::new(c_mod_dq, q_params).pow(dq).retrieve()位宽细节值得留意L98-L111p和q的bits_precision可能不同所以合并(m1 − m2) mod p前要先按Ordering::Less / Greater / Equal三种情况对齐精度避免直接相减得到错误余数。随后// h qinv · (m1 − m2) mod p —— qinv 是 MontyForm一次域内乘法 h (qinv * m1).retrieve() // m m2 h·q —— 宽乘法后截断回 n 的位宽 m m2.wrapping_add(h.concatenating_mul(q))这里concatenating_mul拼接乘法算出完整的h·q再try_resize回n的位宽配合wrapping_add天然完成了模n的意义。4.3 性能账为什么快约 4 倍模幂复杂度近似与模数尺寸² × 指数位长成正比。CRT 把一次 2048 位模上的 2048 位指数模幂拆成两次 1024 位模上的约 1024 位指数模幂模数平方降到 1/4指数也减半总代价约为原方案的 1/4再加上h·q只需一次宽乘——这就是经典 CRT 加速的来源。4.4 优雅降级缺材料就自动走慢路径match的_ 分支只有一行pow_mod_params(c, d, n_params)L128-L131。只要dp/dq/qinv/p_params/q_params任何一项为None例如密钥从未预计算成功或者密钥是多素数 RSAprimes().len() 2就自动退回完整的c^d mod n。对使用者而言完全透明。五、从高层 API 到核心原语一次解密的完整调用链以 OAEP 解密为例串起前面所有机制src/key.rsRsaPrivateKey::decrypt_blinded(rng, Oaep::Sha256::new(), ciphertext)L638-L645——带 RNG 的版本会启用 Blinding不带 RNG 的decrypt则传入DummyRngOption::None禁用之src/oaep/decrypting_key.rsDecryptingKey的RandomizedDecryptor实现把 RNG 继续下传最终调用内部decrypt_digest(rng, key, ...)OAEP 解填充前执行rsa_decrypt裸 RSA 原语——即本文拆解的Blinding → CRT 模幂Montgomery→ Unblinding三件套再按 PKCS#1 v2.x 规则剥离 OAEP 填充并校验掩码输出明文。签名侧同构src/pss/blinded_signing_key.rs 的BlindedSigningKeyRSA-BSSA 盲签名同样是带 RNG 的签名 先盲化、后签名、再解盲的套路。六、速查本文源码地图与延伸阅读主题文件关键符号裸 RSA 加密/解密/Blinding/CRTsrc/algorithms/rsa.rsrsa_encryptrsa_decryptrsa_decrypt_and_checkblindunblind模幂入口与域转换src/algorithms/rsa.rspow_mod_paramspow_mod_params_vartime_exp_bitsreduce_vartime素因子恢复src/algorithms/rsa.rsrecover_primesNIST 800-56B C.2密钥结构/预计算/清零src/key.rsRsaPublicKeyRsaPrivateKeyPrecomputedValuesprecompute密钥部件抽象src/traits/keys.rsPublicKeyPartsPrivateKeyPartshazmat 对外出口src/hazmat.rsrsa_decryptrsa_decrypt_and_checkrsa_encryptOAEP 解密src/oaep/decrypting_key.rsDecryptingKeydecrypt_with_rngMarvin 攻击复现工具marvin-toolkit/marvin-toolkit/README.md密钥测试向量tests/examples/pkcs1/、tests/examples/pkcs8/rsa2048/rsa4096 的 der/pem核心结论一句话RustCrypto RSA 用密钥构造期一次性建好 Montgomery 参数换来每次模幂免除法用每次解密都重新抽 r把计时侧信道搅成噪声再用p/q 半尺寸双模幂 CRT 重组拿到约 4 倍的解密吞吐——三者正交叠加且每一步都有zeroize兜底清理内存是纯 Rust 密码学库里相当值得精读的一份工程范本。 实践建议生产代码请直接调用decrypt_blinded/sign_with_rng等带 RNG 的 APIhazmat特性仅留给需要实现新构造比如新的填充方案的开发者并牢记模块文档那句警告——不要用它实现没有经过同行评审的算法。【免费下载链接】RSARSA implementation in pure Rust项目地址: https://gitcode.com/gh_mirrors/rsa1/RSA创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
RustCrypto RSA源码深潜（下）：Montgomery模幂、随机Blinding与CRT解密实现原理
RustCrypto RSA源码深潜下Montgomery模幂、随机Blinding与CRT解密实现原理【免费下载链接】RSARSA implementation in pure Rust项目地址: https://gitcode.com/gh_mirrors/rsa1/RSA本文深入解析 RustCrypto RSA 加密库纯 Rust 实现的 RSA 密码学库解密路径中的三大核心机制Montgomery 模幂消除大数除法、随机 Blinding防计时侧信道与CRT 中国剩余定理加速解密约 4 倍提速。面向想要读懂密码学库内部原理的 Rust 新手全文基于src/algorithms/rsa.rs的真实源码逐段拆解帮你快速看懂这个库快在哪里、安全在哪里。一、解密管线全景三个机制各管一段打开核心文件 src/algorithms/rsa.rsrsa_decrypt函数约 L37-L142的流水线可以拆成三段正好对应本文三个主题阶段做什么防御/加速目标关键代码位置① 前置检查密文长度与大小校验c n防异常输入L45-L51② 随机 Blindingc ← c·r^e mod n记住 r⁻¹防计时侧信道L58-L64③ CRT 或普通模幂优先走 CRT 快路径解密提速约 4 倍L68-L132④ 反 Blindingm ← m·r⁻¹ mod n还原明文L134-L141这些裸 RSA原语只通过 src/hazmat.rs 的hazmat模块对外暴露需在 Cargo.toml 的features中启用hazmat []模块文档里用☢️ HAZARDOUS API反复警告裸 RSA 绝不能直接用于生产加密它只是给 OAEP、PSS 等已经过评审的高级构造做底层积木。普通用户走的是 src/key.rs 中RsaPrivateKey::decrypt/sign这类高层 API。 阅读提示下文提到的BoxedUint是crypto-bigint提供的可变位宽大整数BoxedMontyParams/BoxedMontyForm则是它的 Montgomery 参数与 Montgomery 形式封装——这两个类型是理解后文的钥匙。二、Montgomery模幂把除法变乘加密钥构造时付一次账2.1 为什么模幂是 RSA 的瓶颈RSA 加密 算c m^e mod n解密 算m c^d mod n。对 2048 位模数、指数高达几千位的情况朴素实现要反复做大数乘 大数取模而取模就是大数除法——大数体系里最贵的运算。Montgomery 表示法的核心思想是把参与运算的数提前换币到 Montgomery 域域内的乘法只靠移位、乘加就能完成约简彻底绕开显式除法只有进出域各转换一次。2.2 参数预计算n_params在密钥构造时一次性建好看 src/key.rs 的RsaPublicKey::new_with_max_size约 L233-L243先校验模数n为奇数Montgomery 要求模数与 2 互素然后调用BoxedMontyParams::new(n_odd)生成 Montgomery 参数n_params随密钥对象一起长期保存见RsaPublicKey结构体字段L32-L42。这就是一次付费、处处受益之后所有模幂都复用同一份参数。私钥的 CRT 路径还要再为p、q各建一份见RsaPrivateKey::precomputeL546-L607中的p_params/q_params。2.3 两条模幂入口变长 vs 定长指数rsa.rs里封装了两条进 Montgomery 域的路径L233-L256pow_mod_params先reduce_vartime把底数规约进域再base.pow(exp)按指数实际位长扫描。用于解密时的c^d mod n慢路径。pow_mod_params_vartime_exp_bits改用pow_bounded_exp(exp, exp_bits)按已知的指定位宽扫描循环次数与指数具体取值无关——注释里明确写道指数的位长可能泄漏在时间模式里所以只对公钥加密这种短指数典型 65537即 17 位场景使用。reduce_vartime本体也很精炼L252-L256rem_vartime取余 →resize_unchecked对齐位宽 →BoxedMontyForm::new换入 Montgomery 域。三步完成进币。2.4 一个有意思的旁支从 (n, e, d) 找回 p 和 qfrom_components允许调用方不传素因子此时 src/key.rs 的from_components_innerL353-L415会走recover_primessrc/algorithms/rsa.rs L261-L326按 NIST SP 800-56B 附录 C.2 的确定性算法利用de ≡ 1 (mod λ(n))构造a (de−1)·gcd(n−1, de−1)再解一元二次方程x² − bx n 0求出p、q。也就是说私钥材料本身足以反推出 CRT 加速所需的素数库在导入 PKCS#1/PKCS#8 密钥时测试向量见 tests/examples/pkcs1/ 与 tests/examples/pkcs8/含 2048/4096 位 der/pem 样例会静默完成这件事。三、随机Blinding给计时攻击套上随机噪声3.1 攻击面时间会说话BoxedUint的模幂并非恒定时间实现——指数中 1 的个数会影响执行路径攻击者若能稳定测量每次解密的耗时就可能逐步恢复私钥dREADME 中的 Marvin 攻击正是这类远程计时攻击的实例仓库自带 marvin-toolkit/ 的 Docker 复现环境见 marvin-toolkit/README.md。随机 Blinding 的对策是让每次运算处理的数值都不一样时间噪声自然被抹平。3.2blind解密前先掺沙子L175-L213blind函数的注释把数学原理写得清清楚楚翻译成三步抽随机数r BoxedUint::try_random_mod_vartime(rng, key.n())并用while循环保证r.invert_mod(n)能求出逆元即gcd(r, n) 1对素数模下几乎必然成立计算混淆因子r^e mod n复用 2.3 节的变长指数模幂再c.mul_mod(rpowe, n)得到c c·r^e mod n——注意这等价于先解密再乘上 r因为(m^e·r^e)^d m·r (mod n)安全清零rpowe.zeroize()立刻抹掉中间变量zeroize库避免密钥材料残留在内存里。unblindL216-L231就是收尾一步m·r⁻¹ mod n把沙子里的 r 捞出来。3.3rsa_decrypt_and_check给 CRT 结果加一道防伪校验L156-L172CRT 计算涉及多份预存值任何一份被写坏或被恶意构造的密钥污染都可能导致解密出看似合法的错误明文。因此rsa_decrypt_and_check在解密完成后用公钥把结果再加密一次与原始密文比对不一致即返回Error::Internal。这是解密后验签的经典防御成本是一次公钥模幂很便宜。3.4 敏感数据的生命周期管理库对秘密材料的清理贯穿始终src/key.rs 的RsaPrivateKey实现DropL116-L122析构时d、primes、precomputed全部zeroize()并声明ZeroizeOnDropPrecomputedValuesL126-L157析构时清零dp、dqblind内的rpowe.zeroize()src/algorithms/rsa.rs L203。四、CRT解密两次半尺寸模幂换 4 倍速度4.1 预计算值PrecomputedValues结构体CRT中国剩余定理路径的前提是拿到dp d mod (p−1)、dq d mod (q−1)、qinv q⁻¹ mod p三件套。它们由RsaPrivateKey::precomputesrc/key.rs L546-L607统一算好装进PrecomputedValues { dp, dq, qinv, p_params, q_params }L126-L139——注意qinv直接以BoxedMontyForm存储这样后面用它做乘法可以零转换成本from_components构造密钥时会顺手尝试预计算失败也不影响正确性自动降级走慢路径。4.2 逐步对照代码L68-L132rsa_decrypt先用match判断 CRT 材料是否齐全且不是多素数密钥L66-L75齐全则走快路径// m1 c^dp mod p —— 约 1024 位模上的模幂2048 位密钥为例 c_mod_dp c % p; m1 BoxedMontyForm::new(c_mod_dp, p_params).pow(dp) // m2 c^dq mod q —— 同样半尺寸 c_mod_dq c % q; m2 BoxedMontyForm::new(c_mod_dq, q_params).pow(dq).retrieve()位宽细节值得留意L98-L111p和q的bits_precision可能不同所以合并(m1 − m2) mod p前要先按Ordering::Less / Greater / Equal三种情况对齐精度避免直接相减得到错误余数。随后// h qinv · (m1 − m2) mod p —— qinv 是 MontyForm一次域内乘法 h (qinv * m1).retrieve() // m m2 h·q —— 宽乘法后截断回 n 的位宽 m m2.wrapping_add(h.concatenating_mul(q))这里concatenating_mul拼接乘法算出完整的h·q再try_resize回n的位宽配合wrapping_add天然完成了模n的意义。4.3 性能账为什么快约 4 倍模幂复杂度近似与模数尺寸² × 指数位长成正比。CRT 把一次 2048 位模上的 2048 位指数模幂拆成两次 1024 位模上的约 1024 位指数模幂模数平方降到 1/4指数也减半总代价约为原方案的 1/4再加上h·q只需一次宽乘——这就是经典 CRT 加速的来源。4.4 优雅降级缺材料就自动走慢路径match的_ 分支只有一行pow_mod_params(c, d, n_params)L128-L131。只要dp/dq/qinv/p_params/q_params任何一项为None例如密钥从未预计算成功或者密钥是多素数 RSAprimes().len() 2就自动退回完整的c^d mod n。对使用者而言完全透明。五、从高层 API 到核心原语一次解密的完整调用链以 OAEP 解密为例串起前面所有机制src/key.rsRsaPrivateKey::decrypt_blinded(rng, Oaep::Sha256::new(), ciphertext)L638-L645——带 RNG 的版本会启用 Blinding不带 RNG 的decrypt则传入DummyRngOption::None禁用之src/oaep/decrypting_key.rsDecryptingKey的RandomizedDecryptor实现把 RNG 继续下传最终调用内部decrypt_digest(rng, key, ...)OAEP 解填充前执行rsa_decrypt裸 RSA 原语——即本文拆解的Blinding → CRT 模幂Montgomery→ Unblinding三件套再按 PKCS#1 v2.x 规则剥离 OAEP 填充并校验掩码输出明文。签名侧同构src/pss/blinded_signing_key.rs 的BlindedSigningKeyRSA-BSSA 盲签名同样是带 RNG 的签名 先盲化、后签名、再解盲的套路。六、速查本文源码地图与延伸阅读主题文件关键符号裸 RSA 加密/解密/Blinding/CRTsrc/algorithms/rsa.rsrsa_encryptrsa_decryptrsa_decrypt_and_checkblindunblind模幂入口与域转换src/algorithms/rsa.rspow_mod_paramspow_mod_params_vartime_exp_bitsreduce_vartime素因子恢复src/algorithms/rsa.rsrecover_primesNIST 800-56B C.2密钥结构/预计算/清零src/key.rsRsaPublicKeyRsaPrivateKeyPrecomputedValuesprecompute密钥部件抽象src/traits/keys.rsPublicKeyPartsPrivateKeyPartshazmat 对外出口src/hazmat.rsrsa_decryptrsa_decrypt_and_checkrsa_encryptOAEP 解密src/oaep/decrypting_key.rsDecryptingKeydecrypt_with_rngMarvin 攻击复现工具marvin-toolkit/marvin-toolkit/README.md密钥测试向量tests/examples/pkcs1/、tests/examples/pkcs8/rsa2048/rsa4096 的 der/pem核心结论一句话RustCrypto RSA 用密钥构造期一次性建好 Montgomery 参数换来每次模幂免除法用每次解密都重新抽 r把计时侧信道搅成噪声再用p/q 半尺寸双模幂 CRT 重组拿到约 4 倍的解密吞吐——三者正交叠加且每一步都有zeroize兜底清理内存是纯 Rust 密码学库里相当值得精读的一份工程范本。 实践建议生产代码请直接调用decrypt_blinded/sign_with_rng等带 RNG 的 APIhazmat特性仅留给需要实现新构造比如新的填充方案的开发者并牢记模块文档那句警告——不要用它实现没有经过同行评审的算法。【免费下载链接】RSARSA implementation in pure Rust项目地址: https://gitcode.com/gh_mirrors/rsa1/RSA创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
