【八】基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列

本次第八部分主要介绍相关项目的具体模块的设计方案，如相关算法的软件实现；

下面介绍采用软件生成RSA公钥私钥对的方法

RSA公钥、私钥对软件生成方法

对于RSA算法，给出两个大的素数很容易，但是对于给出两个大素数的乘积，去找他们的因子就非常的困难，这也是为什么RSA算法的关键所在。因此，如何产生一个随机的大素数，变得非常重要。下面给出产生伪素数以及其素性的检验算法，并采用Python语言编写。

伪素数的生成与检测

伪素数的生成即其检测目前比较主流的是Miller-Rabin算法，该算法是基于费马定理的一个变体，主要由费马定理引申而来。费马定理可以描述为: n是一个奇素数，a是任何整数(1≤a≤n-1)，则 。

Miller-Rabin算法可以描述为：如果n是一个奇素数，将n-1表示成 的形式(r是奇数)，a是和n互素的任何整数，那么 ，或者对某个j(0≤j≤s－1，j∈Z) 等式 成立。该理论是Fermat定理推导而来：n是一个奇素数，则方程 只有±1两个解。

具体描述过程如下：

最大公约数算法

上面已经给出了产生大素数的方法，根据1.2节RSA公钥密码的设计方案，根据公式(1): ，使用欧几里得算法求两数最大公约数的算法，具体描述如下表3-2所示：

模逆算法

为了求得1.2节RSA公钥密码设计中方案中的私钥，即公式(2): , 使用扩展欧几里得算法，求模逆的具体算法如下表3-3所示

模幂算法

使用蒙哥马利算法来计算模幂 的算法：

蒙哥马利模乘模型和调整因子模型参考3.2节验证组件中的reference model。下面介绍指数掩码模型和模幂模型。

指数掩码模型

根据模幂算法8，对指数进行重新编码，计算模型如下表3-5所示：

模幂模型

根据模幂算法8，计算模型如下表3-6所示：

【一】基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列

2021-02-28

【二】基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列

2021-03-01

【三】基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列

2021-03-02

【四】基于Montgomery算法的高速、可配置RSA密码IP核硬件设计系列

2021-03-03

【五】基于Montgomery算法的高速、可配置RSA密码IP核硬件设

2021-03-05

【六】基于Montgomery算法的高速、可配置RSA密码IP核硬件设

2021-03-08

【七】基于Montgomery算法的高速、可配置RSA密码IP核硬件设

2021-03-09