密码工程- 课件 第六章 RSA算法

密码学基础之江实验室刘哲算法描述01RSA算法概述1978年，RonaldRivest、AdiShamir和LeonardAdleman提出了一种基于有限域的公钥密码实现方案：RSA，算法的名称是他们三个人首字母的缩写。RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。原理：大整数分解困难问题。

应用场景：（1）小片段数据的加密，如密钥传输。（2）数字签名，如互联网上的数字证书。RSA公司的三位创始人RSA加密

算法描述示例RSA签名

算法描述示例算法原理02解密算法的正确性推导

基础实现03大整数运算:大整数加减法

0102大整数加法的代码表示大整数减法的代码表示大整数加法大整数减法大整数运算：大整数模加

大整数模加的代码表示大整数模加03大整数运算：大整数模减大整数模减的代码表示大整数模减

04

基于费马小定理的大整数求逆:

基于二进制扩展欧几里得(BEEA)算法的大整数求逆:大整数运算：大整数求逆基于BEEA的大整数求逆05大整数求逆费马小定理模逆BEEA模逆基本原理通过模幂运算求逆元保持等式，通过不断移位和减法求逆元计算特点调用模乘、模平方操作，算法结构简单大量使用移位代替除法，速度快效率稍慢一些（取决于幂大小），但代码短小、结构稳定计算效率高，特别适合大数运算代码量小，容易集成，适合资源受限场景稍复杂，需要维护多组变量和状态安全性较高，能防止通过功耗信息泄露秘密数据，能抵抗SPA、组合攻击有安全隐患，2017年Aldaya指出：容易通过功耗分析（SPA）泄露底数的比特位应用场景安全性要求高、资源受限（如嵌入式、智能卡）对计算速度要求极高，但安全性可控的环境费马小定理模逆

VSBEEA模逆蒙哥马利模乘只用乘法和移位操作实现模乘，极大减少除法开销时间恒定，避免定时攻击特点:将数转换到蒙哥马利域（即变换成特殊形式）定义蒙哥马利乘积通过蒙哥马利约减快速计算结果核心思想:RSA算法的核心运算是模幂运算，模乘是模幂的基础1985年，Montgomery提出蒙哥马利模乘（MontgomeryMultiplication）算法起源:蒙哥马利模乘算法蒙哥马利模乘MonPro有5种实现方法：SOS（SeparatedOperandScanning）CIOS（CoarselyIntegratedOperandScanning）CIHS（CoarselyIntegratedHybridScanning）其中CIOS是最快速的实现方法。蒙哥马利模乘算法-CIOS表6-2

不同方法实现MonPro算法的性能对比（时间/ms）表6-1

不同方法实现MonPro计算复杂度对比（s为操作数字长）FIOS（FinelyIntegratedOperandScanning）FIPS（FinelyIntegratedProductScanning）幂指数运算：二进制扫描法

算法描述示例表6-3

for循环执行幂指数运算：固定窗口算法

算法描述示例表6-4固定窗口算法示例计算过程幂指数运算：滑动窗口算法

算法描述示例优化实现04预备知识：基于RNS的运算

描述:

注意事项:对于大整数运算，不处理它本身，而是同时处理它在一组小整数模数下的余数，各个模数之间互不相关，可以并行计算，借此来提升效率。原理:全称:ResidueNumberSystem。

缺点:需要多次小模数运算和最后CRT重建（有应用形成费用）；模基选择需要精心挑选。

预备知识：固定时间的模幂运算

预备知识：RNS模约减

预备知识：RNS蒙哥马利模约减

基于CPU的优化:基于蒙哥马利的运算

计算步骤:原理:逐位乘法和加法类型:Schoolbook算法优点:计算过程直观，容易理解缺点:时间复杂度高；不适合非常大的整数乘法

类型:Karatsuba算法优点:时间复杂度低；适用于较大整数缺点:递归算法，需要更多内存空间；对小规模整数乘法优势不明显计算步骤:原理:通过分治思想来减少乘法次数，从而提高计算效率。基于CPU的优化:基于AVX2指令的RNS运算CPU实现

基于CPU的优化:基于RNS运算的CPU实现表6-8展示了基于RNS约减和RNS蒙哥马利约减的模约减、模乘、模平方时间比较。RNS蒙哥马利约减速度是RNS约减速度的两倍。RNS蒙哥马利约减操作所需处理向量大小是RNS约减的一半。表6-9展示了基于RNS约减和RNS蒙哥马利约减，在RSA-024、RSA-2048和RSA-3072签名中的延迟。基于RNS蒙哥马利约减的签名比RNS约减的签名快两倍。基于GPU的优化

基于快速素数生成的优化

在Miller-Rabin检验算法输出合数后，不重新选择一个随机数，而是前一个奇数加上一个固定值，成为一个新的奇数，再进行筛选和素性检测，如算法6-11所示。基于快速素数生成的优化试除法适用于小范围