基于多处理器构造安全椭圆曲线的并行化设计与

摘　要：安全椭圆曲线是椭圆曲线密码体制理论研究与实际应用的前提和根本，本文通过分析GF(p)上构造安全椭圆曲线的算法与一种奇素数域构造给定长度的素数阶的椭圆曲线算法，将两种算法适合并行化的部分进行并行化处理，并设计了基于多处理器的构造安全椭圆曲线的并行化模型，进而实现加快构造安全椭圆曲线的速度。

关键词：构造椭圆曲线；多处理器模型；并行算法；设计与实现

中图分类号：TP302    文献标识码：A     文章编号：
1. 前言
　　安全椭圆曲线是ECC理论研究与实际应用的前提和基础，如果椭圆曲线不安全，那么ECC中的各种快速算法的研究、密码体制的研究与在实践中的应用都是空想。ECC的安全性取决于有限域上椭圆曲线离散对数的难解性。所谓构造安全椭圆曲线，就是通过选择并确定椭圆曲线的参数和密钥，使椭圆曲线能抵御目前的所有攻击。
　　构造有限域上安全椭圆曲线的方法一般有两种：随机曲线法(Schoof Elkies Atkin,SEA) 和复乘法（Complex Multiplication,CM）。SEA法是通用的方法，它可以构造出许多安全椭圆曲线，但实现起来复杂。CM法相对比较简单，实现速度也比较快，但这种方法找出的椭圆曲线含有复乘，可能存在安全隐患。本文通过分析文献[3]中GF(p)上构造安全椭圆曲线的算法与文献[4]中一种奇素数域构造给定长度的素数阶的椭圆曲线算法，分别将适合并行化的部分进行并行化处理以加快构造安全椭圆曲线的速度。
2. GF(p)上构造安全椭圆曲线的算法分析与并行模型架构设计
　　文献[32]中提出GF(p)上构造安全椭圆曲线的算法描述如下：
　　输入：有限域的大小p>3
　　输出：椭圆曲线E(a,b)、#E(a,b)=kh, k是大的素因子、且
　　算法步骤：
　　Step1：随机产生GF(p)上的一条椭圆曲线E(a,b)：；
　　Step2：利用SEA算法计算出#E(a,b)；
Step3：利用大整数分解算法分解#E(a,b)，并检测#E(a,b)的分解中有无大于的素因子k，如果没有，返回Step 1；
　　Step4：检测，否则返回 Step 1；
　　Step5：检测。否则返回Step 1；
　　Step6：输出a、b、#E(a,b)、k、h＝#E(a,b)/k。
　　上面算法利用SEA算法计算出#E(a,b)后，执行Step3、Step4与Step5的主要目的是得到有效的a、b、#E(a,b)、k、h＝#E(a,b)/k，由于此算法是串行执行的，每一步不成功都要返回Step 1，这必导致速度缓慢。为了加快构造安全椭圆曲线的速度，将原来串行化算法中适合并行化的部分进行并行计算。由于Step3、Step4与Step5之间相互没有依赖关系，所以可以并行执行Step3、Step4与Step5，然后输出a、b、#E(a,b)、k、h＝#E(a,b)/k。
　　基于多处理器构造GF(p)上安全椭圆曲线模型架构（如图1）的设计思想是三个处理器共享一个循环缓存区和一个公共列表，处理器Ⅰ负责利用大整数分解算法分解#E(a,b)，并检测#E(a,b)的分解，找出的素因子写到循环缓存区中；处理器Ⅱ从循环缓存区中读取并验证，然后将存储到公共列表中；处理器Ⅲ负责验证；最后输出a、b、#E(a,b)、k、h＝#E(a,b)/k.

2.1 基于多处理器GF(p)上构造安全椭圆曲线的并行算法设计
　　输入：有限域的大小p>3
　　输出：椭圆曲线E(a,b)、#E(a,b)=kh, k是大的素因子、且
　　算法步骤：
　　Step1：随机产生GF(p)上的一条椭圆曲线E(a,b)：；
　　Step2：利用SEA算法计算出#E(a,b)；
Step3：(1)处理器Ⅰ利用大整数分解算法分解#E(a,b)，并检测#E(a,b)的分解中有无大于的素因子k，如果没有，返回Step 1；
           (2)处理器Ⅱ检测，否则返回 Step 1；
           (3)处理器Ⅲ检测。否则返回Step 1；
　　Step4：输出a、b、#E(a,b)、k、h＝#E(a,b)/k。
3. 构造给定长度的素数阶椭圆曲线算法分析
　　文献[33]提出构造给定长度的素数阶的椭圆曲线算法描述如下：
　　输入：大素数q的长度
　　输出：素数p、q、上阶为q的椭圆曲线E'
　　算法步骤：
　　Step1：取定负奇基本判别式，使适当小；
　　Step2：确定m，n的取值范围，使具有长度；
Step3：在Step 2确定的范围中随机选取奇数m，n，令，检查p的素性，直到p为素数为止；
Step4：令，检查q的素性，若q不是素数，转Step 3，若q是素数，转Step 5；
Step5：计算（函数），并求出的一个根；
Step6：构造以为不变量的椭圆曲线：其中；
　　Step7：随机选取，构造椭圆曲线：；
　　Step8：选取点，若，输出p ,q, E'，否则，转Step 7。
　　上述构造给定长度的素数阶的椭圆曲线串行算法中Step2、Step 3和Step 4的主要目的是找出满足给定长度的两个大素数p和q，其中，，直到p，q都是素数为止。
　　为了加快构造安全椭圆曲线的速度，本文主要是将原来串行化算法中适合并行化的部分进行并行运算。根据文献[3]中对构造安全椭圆曲线快速算法串行化程序的分析可知，寻找p、q的时间复杂度为，串行化程序最耗时的部分是在循环中，判断，是否为素数，这占用了80%以上的运行时间，并且检验p、q素性之间相互没有依赖关系。因此可以对它们实行并行化，加快构造安全椭圆曲线的速度。
3.1基于多处理器检验、素性的并行模型
  该模型架构中的多个处理器共享循环缓存区和三个存储器，此循环缓存区的大小为(其中)是一个标准的循环缓存区，它可以显示空闲与饱和两种状态。

　　各个处理器可以访问、、这三个存储器，存储器存储并提供处理器执行标量乘的操作结果，存储器存储并提供循环缓存区数据的结果，存储器提供第一个数据的地址并存储到循环缓存区，还有一个位标记显示循环缓存区中数据的类型。
　　基于多处理器构造安全椭圆曲线并行检验、素性算法的实现过程中所有处理器都同时参与了检验、素性的运算，这样不但提高了计算效率和处理器的利用率，而且保证了所有处理器单元的负载均衡，能以较快的速度检验、的素性,加快了构造安全椭圆曲线的速度。
3.2基于多处理器检验、素性的并行算法的设计
　　改进算法主要将文献[4]的串行化算法中串行判断，是否为素数的部分设计为并行化，并行检验， 的素性。
　　改进算法描述如下：
　　先预计算一些常用的负奇基本判别式计算的根能加快构造椭圆曲线的速度。特别的，当时，是一次多项式，这时可以直接得到的根，现将的负奇基本判别式及相应的根列表如下：

　输入：大素数q的长度
　输出：素数p、q，上阶为q的椭圆曲线E'
　算法步骤：
　Step1：取定负奇基本判别式，使适当小；
 Step2：确定m，n的取值范围，使具有长度；
Step3：其中一个处理器在St ep 2确定的范围中随机选取奇数m，n，计算， ，将结果写到循环缓存区中；其余的S-1个 处理器从循环缓存区中读取数据、，并行检查、的素性，直到、为素数并输出、；
Step4：计算（或Weber函数），并求出的一个根；
Step5：构造以为不变量的椭圆曲线：其中；
Step6：随机选取，构造椭圆曲线：；
Step7：选取点，若，输出、，E'，否则，转Step 6。
3.3基于多处理器检验、素性的并行算法的性能分析
　　根据检验、素性的并行算法，设计基于共享内存多处理器并行检验、素性的系统架构，基于多处理器模型的思想是假定一个处理器在给定范围内随机选取奇数m、n，计算，，接着将m、n写进缓冲区buffer，然后其余S-1个处理器从缓冲区buffer中读取数据、，并行检验、的素性，并且S个处理器可以异步运行。这样不但提高了计算效率和处理器的利用率，而且保证了所有处理器单元的负载均衡，能以较快的速度检验、的素性,加快了构造安全椭圆曲线的速度。
4. 结束语
　　椭圆曲线密码体制常用于智能卡和无线设备等计算资源或存储资源有限的环境，则对产生安全椭圆曲线的快速算法的研究有重要的实践价值。比如，由于计算的复杂性，RSA 的密钥不会在智能卡中产生，而是预产生再装入智能卡，而椭圆曲线密码体制可直接在智能卡中产生参数和密钥。本文通过分析GF(p)上构造安全椭圆曲线的算法与一种奇素数域构造给定长度的素数阶的椭圆曲线算法，将两种算法适合并行化的部分进行并行化处理，并设计了基于多处理器的构造安全椭圆曲线的并行化模型，进而设计了基于多处理器GF(p)上构造安全椭圆曲线的并行算法和基于多处理器检验、素性的并行算法，实现加快构造安全椭圆曲线的速度。
参考文献：
. Communications, Circuits and Systems, 2005 Proceedings.2005 International Conference on 2005, 13(1):71~73.